標題: | Circuit-switched broadcasting in multi-port multi-dimensional torus networks |
作者: | Wang, SY Tseng, YC Ni, SY Sheu, JP 資訊科學與工程研究所 Institute of Computer Science and Engineering |
關鍵字: | broadcast;circuit switching;collective communication;interconnection network;parallel processing;torus |
公開日期: | 1-十一月-2001 |
摘要: | The one-to-all broadcast is the most primary collective communication pattern in a multicomputer network. This paper studies this problem in a circuit-switched torus with alpha -port capability, where a node can simultaneously send and receive alpha messages at one time. This is a generalization of the one-port and all-port models. We show how to efficiently perform broadcast in tori of any dimension, any size, square or nonsquare, using near optimal numbers of steps. The main techniques used are: (i) a "span-by-dimension" approach, which makes our solution scalable to torus dimensions, and (ii) a "squeeze-then-expand" approach, which makes possible solving the difficult cases where tori are non-square. Existing results, as compared to ours, can only solve very restricted sizes or dimensions of tori, or use more numbers of steps. |
URI: | http://dx.doi.org/10.1023/A:1011650615731 http://hdl.handle.net/11536/29328 |
ISSN: | 0920-8542 |
DOI: | 10.1023/A:1011650615731 |
期刊: | JOURNAL OF SUPERCOMPUTING |
Volume: | 20 |
Issue: | 3 |
起始頁: | 217 |
結束頁: | 241 |
顯示於類別: | 期刊論文 |