SPANNING TREES FOR BINARY DIRECTED DE BRUIJN NETWORKS AND THEIR APPLICATIONS TO LOAD BALANCING

使用平行計算機系統的主要理由之一為其具有改進計算性能與資源共用的潛力，欲達到此目的系統中必須有一個有效的方法將一個或是多個訊息由一個節點傳遞到其他節點上，然而此傳遞訊息的方法是否有效往往決定於所用的綱路結構。在本論文中，我們將考慮二元有向de Bruijin網路並且定義兩個跨越樹分別稱為：向上-0跨越樹(upward-0 spanning tree)與向下-0跨越樹(downward-0 spanning tree),以滿足所需的訊息傳遞，並且應用於負載平衡(load balancing)。結果顯示，時間雜度為O(log＾(2)2 N+∑(〓△(下標 i)≠0)△(下標 i))，其中N為節點數目而△(下標 i)為每一個節點i的資訊轉移時間，1≤i≤N。

關鍵字

無資料

並列摘要

One of the major reasons of using parallel computer systems is that they have the potential for improving performance and resource sharing. To achieve this, an efficient way must be provided to broadcast a message or messages from a node to every other nodes in the system. However, the efficiency of transferring messages in a system is determined by the architecture of the underlying inter connection network of the system. In this paper, we consider the systems based on binary directed de Bruijn networks and define two shortest path spanning trees: the upward-0 spanning tree and the downward-0spanning tree, to meet various message transfer requirements. To demonstrate the usage of these spanning trees, an application to the load-balancing problem is considered. The resulting time complexity is O(log＾(2)N+Σ(subscript 〓△i≠0)△(subscript i)),where N is the number of nodes and△(subscript i)is the total transfer time for the load difference of each node i, for all 1≤i≤N,on the binary directed de Bruijn networks.

並列關鍵字

de Bruijn network ； downwad spanning tree ； load balancing ； load sharing ； parallel computer systems ； and upward spanning tree

國際替代計量

SPANNING TREES FOR BINARY DIRECTED DE BRUIJN NETWORKS AND THEIR APPLICATIONS TO LOAD BALANCING

未授權

主題瀏覽