Title :
Multithreading implementation of a distributed shortest path algorithm on EARTH multiprocessor
Author :
Thulasiraman, Parimala ; Tian, Xin-Min ; Gao, Guang R.
Author_Institution :
Sch. of Comput. Sci., McGill Univ., Montreal, Que., Canada
Abstract :
Network optimization refers to those optimization problems defined on weighted graphs. In general, the shortest path and max-flow problems have served as critical building blocks in formulating solutions to more complex network optimization problems. In this paper, as the first step in studying and evaluating implementations of network optimization problems on multithreaded multiprocessors, we present a multithreaded implementation of a distributed shortest path algorithm proposed by K.M. Chandy and J. Misra (1982) on the EARTH-MANNA multithreaded architecture, and discuss performance results on the ERTH-MANNA system
Keywords :
distributed algorithms; multiprocessing systems; parallel architectures; performance evaluation; synchronisation; EARTH multiprocessor; EARTH-MANNA multithreaded architecture; distributed shortest path algorithm; max-flow problems; multithreaded multiprocessors; multithreading implementation; network optimization; performance results; weighted graphs; Complex networks; Computer architecture; Computer science; Earth; Geoscience; Microprocessors; Multithreading; Reduced instruction set computing; Switches; Yarn;
Conference_Titel :
High Performance Computing, 1996. Proceedings. 3rd International Conference on
Conference_Location :
Trivandrum
Print_ISBN :
0-8186-7557-8
DOI :
10.1109/HIPC.1996.565844
