Superlinear Scalability in Parallel Computing and Multi-robot Systems : Shared Resources, Collaboration, and Network Topology

Abstract

The uniting idea of both parallel computing and multi-robot systems is that having multiple processors or robots working on a task decreases the processing time. Typically we desire a linear speedup, that is, doubling the number of processing units halves the execution time. Sometimes superlinear scalability is observed in parallel computing systems and more frequently in multi-robot and swarm systems. Superlinearity means each individual processing unit gets more efficient by increasing the system size—a desired and rather counterintuitive phenomenon. In an interdisciplinary approach, we compare abstract models of system performance from three different fields of research: parallel computing, multi-robot systems, and network science. We find agreement in the modeled universal properties of scalability and summarize our findings by formulating more generic interpretations of the observed phenomena. Our result is that scalability across fields can be interpreted as a tradeoff in three dimensions between too competitive and too cooperative processing schemes, too little information sharing and too much information sharing, while finding a balance between neither underusing nor depleting shared resources. We successfully verify our claims by two simple simulations of a multi-robot and a network system.