Spatial Sorting Algorithms for Parallel Computing in Networks

Max OrHai, Christof Teuscher
Portland State University
Fifth IEEE Conference on Self-Adaptive and Self-Organizing Systems Workshops (SASOW), 2011


   title={Spatial Sorting Algorithms for Parallel Computing in Networks},

   author={OrHai, M. and Teuscher, C.},



Download Download (PDF)   View View   Source Source   



Many basic techniques in computer science have been founded on the assumption that physical computing resources are scarce but orderly, and that the cost of effective direct communication between physically distant parts of a computer system is affordable. In large scale cluster computing installations, fine-grained parallel computing hardware, or wireless mesh networks, these familiar assumptions may not hold. In this paper we present adaptations of two especially simple classic sequential sorting algorithms, namely bubble sort and insertion sort, to parallel execution in spatially constrained networks of devices, using particle systems and asynchronous automata graphs. In both cases we are able to get significant speed-ups of these naive $O(n^2)$ algorithms, attaining linear time complexity or better given sufficient parallelism. For insertion sort, we obtain these results without depending on any but statistical properties the network medium. We discuss potential extensions of these physically and biologically inspired techniques to more complex parallel algorithms.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: