頁籤選單縮合
題名 | Efficient All-to-All Broadcast in Star Graph Interconnection Networks=在星狀圖網路中有效率的多對多廣播 |
---|---|
作者 | 曾煜棋; 許健平; 章戊霖; | 書刊名 | Proceedings of the National Science Council : Part A, Physical Science and Engineering |
卷期 | 22:6 1998.11[民87.11] |
頁次 | 頁811-819 |
分類號 | 448.86 |
關鍵詞 | 星狀圖網路; 多對多廣播; All-to-all personalized/non-personalized broadcast; Collective communication; Interconnection network; Routing; Star graph; |
語文 | 英文(English) |
中文摘要 | 在本文中,我們探討在星狀圖網路中的二種通訊問題:『多對多個人化』和『多 對多非個人化』廣播。前人之研究僅將資料傳輸時間 (data transmission time) 予以最佳 化,但忽略了準備資料傳輸的啟動時間 (start-up time)。因此,前人之結果雖然宣稱為最 佳解,其實僅在啟動時間可以忽略的情況下成立。本文中,我們考量將啟動時間和傳輸時間 同時予以最佳化。我們發展的多對多個人化廣播演算法較前人之結果更有效率。我們發展的 多對多非個人化廣播演算法也優於前人之結果,除非啟動時間相較於傳輸時間極小的情形之 外(其比例約為 O(1/(n-1)!),其中 n 為星狀圖之維度)。 模擬結果顯示我們的結果相較 於前人之結果約有 10%~80% 之改進。 |
英文摘要 | In this paper, we study the all-to-all personalized and non-personalized broadcast problems in a star graph. This work is motivated by the observation that existing works in the literature only try to optimize the data transmission time, but ignore the start-up time required to initialize communication. As a result, existing algorithms, although claimed to be optimal, are only so when the start-up time is negligible. In this paper we try to optimize both costs at the same time. We develop an all-to-all personalized broadcast algorithm that is more efficient than existing results. We also present an all-to-all nonpersonalized broadcast algorithm that outperforms existing results in most cases except when the startup time is very small (in a ratio of O( ), where n is the dimension of the star graph) compared to the transmission time. Extensive simulations have been conducted, which show 10%~80% improvement over existing results. |
本系統之摘要資訊系依該期刊論文摘要之資訊為主。