Title :
Performance evaluation of the bubble algorithm: benefits for k-ary n-cubes
Author :
Carrión, C. ; Beivide, R. ; Gregorio, J.A.
Author_Institution :
Dipt. Electron. y Comput., Cantabria Univ., Santander, Spain
Abstract :
The bubble algorithm evaluated in this paper assures message deadlock freedom in k-ary, n-cube network without using virtual channels. This algorithm is based both on a dimension order I outing (DOR) and on a restricted injection policy extended to the dimension changes. An exhaustive comparison between the bubble mechanism and the classical deterministic virtual channels solution is presented here. For that purpose, the message router of both proposals has been designed by using VHDL descriptions and the Synopsys VLSI CAD tool. Additionally, formal models of the routers, based on colored Petri nets, have been carried out together with simulation techniques in order to assure the validation of the results and shorten the design cycle. The performance evaluation of n-dimension tori highlights the benefits of the bubble algorithm as both the temporal delay and the necessary silicon area of the message router are reduced
Keywords :
hypercube networks; parallel algorithms; performance evaluation; bubble algorithm; k-ary n-cubes; message deadlock freedom; message router; n-cube network; n-dimension tori; performance evaluation; silicon area; temporal delay; Concurrent computing; Cost accounting; Delay; Design automation; Hardware; Multiprocessor interconnection networks; Postal services; Proposals; Routing; Very large scale integration;
Conference_Titel :
Parallel and Distributed Processing, 1999. PDP '99. Proceedings of the Seventh Euromicro Workshop on
Conference_Location :
Funchal
Print_ISBN :
0-7695-0059-5
DOI :
10.1109/EMPDP.1999.746699
