A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs)

摘要: The ability to provide uniform shared-memory access a significant number of processors in single SMP node brings us much closer the ideal PRAM parallel computer. Many algorithms can be adapted SMPs with few modifications. Yet there are studies that deal implementation and performance issues running PRAM-style on SMPs. Our study this paper focuses implementing spanning tree Spanning is an important problem sense it building block for many other graph also because representative large class irregular combinatorial problems have simple efficient sequential implementations fast algorithms, but these often no known implementations. Experimental been conducted related (minimum connected components) using computers, only achieved reasonable speedup regular topologies implicitly partitioned good locality features or very dense graphs limited numbers vertices. In we present new randomized algorithm superior first time achieves arbitrary (both topologies) when compared best finding tree. This uses several techniques give expected scales linearly p suitably inputs (n>p^2). As notoriously hard any achieve speedup, our may shed light computers. main results are1.A practical symmetric multiprocessors exhibits speedups topologies; 2.an experimental reveals approach previous algorithms. source code freely-available from web site. pc.ece.unm.edu.