Title :
A Parallel Floyd-Warshall algorithm based on TBB
Author :
Jian Ma ; Ke-Ping Li ; Zhang, Li-yan
Author_Institution :
Sch. of Transp. Eng., Tongji Univ., Shanghai, China
Abstract :
The paper presents one novel algorithms: Parallel Floyd-Warshall algorithm(PF) based on multi-core computer with Threading Building Blocks (TBB). TBB offers a rich and complete approach to express parallelism in a C++ program. Serial Floyd-Warshall algorithm(SF) and PF are implemented and verified with TBB for the all-pairs shortest path problem. Experiments show that the efficiency of multi-threaded of PF is obviously superior to single-threaded of PF which is enormously better than SF. At this point, PF can be efficiently applied to the systems of large node number and it leads to a significant improvement in running efficiency. Furthermore, the running results of multi-threaded of PF are stable when thread number is relatively large.
Keywords :
C++ language; graph theory; multi-threading; parallel algorithms; C++ program; all-pairs shortest path problem; multicore computer; multithreading; parallel Floyd-Warshall algorithm; serial Floyd-Warshall algorithm; threading building blocks; Algorithm design and analysis; Concurrent computing; Libraries; Multicore processing; Parallel processing; Parallel programming; Scalability; Shortest path problem; Transportation; Yarn; Floyd-Warshall algorithm; Multi-threadedk; Parallel algorithm; Serial algorithm; Threading Building Blocks(TBB);
Conference_Titel :
Information Management and Engineering (ICIME), 2010 The 2nd IEEE International Conference on
Conference_Location :
Chengdu
Print_ISBN :
978-1-4244-5263-7
Electronic_ISBN :
978-1-4244-5265-1
DOI :
10.1109/ICIME.2010.5477752
