English  |  正體中文  |  简体中文  |  Items with full text/Total items : 63190/95884 (66%)
Visitors : 4618519      Online Users : 340
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/35241

    Title: Fault-tolerant simulation of a class of regular graphs in hypercubes and incrementally extensible hypercubes
    Other Titles: 模擬具正規性的網路拓蹼結構至具有容錯能力之超立方體及可逐步擴充超立方體結構圖
    Authors: 武士戎;Wu, Shih-jung
    Contributors: 淡江大學資訊工程學系博士班
    葛煥昭;Keh, Huan-chao
    Keywords: 容錯;超立方體;可逐步擴充超立方體;費伯納茲立方體;Embedding;Hypercube;Incrementally Extensible Hypercube;IEH Fibonacci cube;Fault-tolerant
    Date: 2006
    Issue Date: 2010-01-11 06:15:07 (UTC+8)
    Abstract: 在大型平行計算機器中,超立方體結構圖(hypercube)是最為廣泛使用的。其結構上的正規性(regularity)可使得電腦系統能較容易地被建立起來,而平行演算法上的容錯性使得一般與網路拓蹼結構相關的平行演算法不須經過大幅修改就能容易地被移植到超立方體結構電腦系統上來執行。可逐步擴充超立方體(Incrementally Extensible Hypercube)是超立方體的變形結構,它可以有任意的節點個數,並且保證其直徑(diameter)為節點個數和的對數值,以及每一個節點的鏈結分支度(degree)相差最多為1。本論文中,我們討論將一些正規的網路拓蹼,例如,環路(ring)、網格(mesh)及樹(tree),嵌入至有容錯能力的可逐步擴充超立方體結構的演算法。
    而費伯納茲立方體結構(Fibonacci Cube),也是近年熱門的超立方體變形結構,本論文也一並討論將它嵌入至有容錯能力之超立方體結構的方法。在這些議題中,我們利用位元移動的方法,提出了一些容錯演算法,並且得到了重要的結果。在可逐步擴充超立方體有節點發生故障的情形下,可將環路結構完全嵌入,並達到延展度4、擴張度N、壅塞度1及負載度1。容錯程度達到O(n*log2m)。網格與樹的嵌入也有O(n2-(r+s)2)及O(n2-h2)的容錯程度。此外我們也對於費伯納茲立方體結構嵌入至有錯誤節點的超立方體結構的演算法作一討論,並達到延展度3、擴張度N、壅塞度1及負載度1及O(m2-n2)的容錯程度。
    The hypercube is a widely-used interconnection architecture in the parallel machine. The Incrementally Extensible Hypercube (IEH), which is derived from the hypercube, is a generalization of interconnection network. Unlike the hypercube, the IEH can be constructed for any number of nodes. In other words, the IEH is incrementally expandable. In this thesis, the problem of embedding and reconfiguring some regular structures is considered in an IEH with faulty nodes. In recent years, the Fibonacci cube is a new interconnection architecture derived from hypercube. It also has some properties differ from hypercube. Thus we discuss the embedding of Fibonacci cube into the faulty hypercube. Some fault-tolerant embedding algorithms are proposed in this thesis. First, the algorithm in the present study enables us to obtain the good embedding of a ring into a faulty IEH with 2-expansion. Such result can be tolerated up to (n+1) faults with congestion 1, load 1, and dilation 3. When we allow unbounded expansion, the result of embedding of a ring into a faulty IEH can be tolerated up to O(n*log2m) faults with congestion 1, load 1, and dilation 4. The embedding methods in the study are mainly optimized for balancing the processor loads, under the situation of minimizing dilation and congestion as far as possible. Next we consider embedding of mesh into faulty IEH. In 2-expansion, it can be tolerated (n+1) faults with dilation 3, congestion 1, and load 1. Moreover, it can be tolerated up to O(n2-(r+s)2) in unbounded expansion. We discuss embedding of a complete binary tree into faulty IEH in the third. The cost is dilation 4, congestion 1, and load 1. In 2-expansion and unbounded expansion, embedding of a complete binary tree into faulty IEH can be tolerated (n+1) and O(n2-h2) faults. Finally, embedding of Fibonacci cube into faulty hypercube with dilation 3, congestion 2, load 1, unbounded expansion and O(m2-n2) faults can be tolerated, induced by our algorithm.
    Appears in Collections:[Graduate Institute & Department of Computer Science and Information Engineering] Thesis

    Files in This Item:

    File SizeFormat

    All items in 機構典藏 are protected by copyright, with all rights reserved.

    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library & TKU Library IR teams. Copyright ©   - Feedback