擴增性超立方體結構嵌入環狀與樹狀結構

機構典藏 > College of Engineering > Graduate Institute & Department of Computer Science and Information Engineering > Research Paper > Item 987654321/7144

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/7144

Title:	擴增性超立方體結構嵌入環狀與樹狀結構
Other Titles:	Embedding Rings and Trees into Incrementally Extensible Hypercube
Authors:	葛煥昭
Contributors:	淡江大學資訊工程學系
Keywords:	超立方體;逐步擴增超立方體;平行處理;嵌入演算法;Hypercube;Intermentally extensible hypercube (IEH);Parallel processing;Embedding algorithm
Date:	1998
Issue Date:	2009-03-16 15:41:42 (UTC+8)
Abstract:	加速計算與資源共享是目前平行與分散式電腦系統研發的主要兩大目標。而一個好的平行電腦與分散式網路之拓蹼結構應該具備有低分支度(degree)、正規性(regularity)、較短的直徑(diameter)、較佳的容錯能力、演算法的包容性和有效率的路徑決策(routing)。超立方體結構(hypercubes)具有上述大部分的優良網路拓蹼特性，其結構上的正規性可使得電腦系統能較容易地被建立起來，而平行演算法上的包容性使得一般與結構相關的平行演算法，也就是網路上常見的拓蹼結構，例如:環(rings)、網絡(meshes)、樹(trees)等，不須經過大幅修改就能容易地被移植到超立方體結構電腦系統上來執行。儘管超立方體結構的網路拓蹼特性在理論和實作上有許多優點，但它有節點個數必須符合2n的限制。因此它並不適用於任意數目的節點個數，因此超立方體結構在節點的個數上並不具備可逐步擴增的能力。可逐步擴增的超立方體結構圖(Incrementally Extensible Hypercube (IEH)graphs)，為一新型網路拓樸結構圖，其設計主要的精神在於能適當地連結各個不同大小的多維度子立方體結構(subcubes)，它的特性除了適用於任意數目的節點個數以外，它還具備了最佳的容錯能力與僅為(n+1)的直徑，且最重要的是在此結構中，兩節點間其分支度差最大為1，這同時說明了它有較佳的正規性。本研究計劃針對超立方體與可逐步擴增的超立方體結構圖中的部分問題加以討論。將環狀與完全二元樹嵌入可逐步擴增的超立方體結構圖中，在研究中，發現除了節點個數為2n-1時，其可逐步擴增的超立方體結構僅包含漢米爾頓(Hamiltonian)路徑外，其它所有的可逐步擴增的超立方體結構皆包含漢米爾頓環路。同時也利用歸納法(induction)並結合格雷碼(Gray code)對此提出證明。而根據這項結果，更進一步地，可以將任意個數的環狀結構包含在其中，同時把其上的平行演算法直接移植到上面，而不會影響執行時間，並使得擴張度(dilation)和膨脹率(expansion)均為1。此外，本論文提出一模式簡易、有效並遞迴式處理完全二元樹嵌入可逐步擴增的超立方體結構，更進一步其他類型二元樹嵌入問題。所提出之嵌入模式所得之結果為擴張度(dilation)為1、膨脹率(expansion)為1且擁擠度亦為1。
Appears in Collections:	[Graduate Institute & Department of Computer Science and Information Engineering] Research Paper

Files in This Item:

File	Description	Size	Format
872213E032002.pdf		326Kb	Adobe PDF	478	View/Open

Loading...