【摘要】：隨著大規(guī)模并行計(jì)算系統(tǒng)中處理器數(shù)目的增加和處理速度的加快，整個(gè)系統(tǒng)的通信開銷也在急劇增長，因而需要有效的通信網(wǎng)絡(luò)來實(shí)現(xiàn)處理器之間的快速通信。傳統(tǒng)的電互連由于帶寬、時(shí)延、能耗等方面的缺陷，無法滿足大規(guī)模并行計(jì)算機(jī)通信的需求。光互連由于具有極高的傳輸帶寬、極低的傳輸時(shí)延以及極低的功耗等優(yōu)良的特性，成為大規(guī)模并行計(jì)算機(jī)的新一代通信網(wǎng)絡(luò)。 波分復(fù)用（WDM）是光通信的關(guān)鍵技術(shù)之一，其核心思想，是將同一條光纖按照波長劃分成多個(gè)信道，可以同時(shí)傳輸多個(gè)光信號。所謂將通信模式嵌入WDM光網(wǎng)絡(luò)，就是將通信模式中的每個(gè)子任務(wù)映射到網(wǎng)絡(luò)中的某個(gè)結(jié)點(diǎn)，并為每對需要直接通信的結(jié)點(diǎn)分配一條光路，使得經(jīng)過同一條光纖的所有光路具有不同的波長。并行計(jì)算的一個(gè)重要課題，就是將各種典型通信模式有效地嵌入各種典型WDM光網(wǎng)絡(luò)，，實(shí)現(xiàn)高效率通信。由于波長是極為寶貴的資源，這就要求我們尋找所需波長數(shù)最少的波長分配方案，這就是WDM光網(wǎng)絡(luò)上的波長分配問題。 超立方體、交叉立方體以及局部扭曲立方體都是典型通信模式，線性陣列則是典型的WDM網(wǎng)絡(luò)拓?fù)�。本文主要研究如何將上述通信模式嵌入線性陣列光網(wǎng)絡(luò)，使得所需波長數(shù)最小。具體研究成果如下： （1）研究了如何將局部扭曲立方體靜態(tài)地嵌入線性陣列。提出了一個(gè)具體的嵌入方案，運(yùn)用最大導(dǎo)出子圖技術(shù)證明了該方案的最優(yōu)性，并且給出了相應(yīng)的波長分配算法，使得所需波長數(shù)達(dá)到最小。 （2）研究了如何將廣義立方體靜態(tài)地嵌入線性陣列。提出了自然嵌入方案，證明了該方案的最優(yōu)性，并確定了陣列中每條邊的擁塞度。在此基礎(chǔ)上，研究了交叉立方體的半雙工和全雙工通信模式在線性陣列上的路由和波長分配問題，證明了自然嵌入方案在兩種通信模式下均具有最小波長數(shù)，并且給出了相應(yīng)的波長分配算法。 （3）研究了如何將基于超立方體的雙調(diào)排序動(dòng)態(tài)地嵌入線性陣列。根據(jù)雙調(diào)排序的特點(diǎn)提出了維嵌入的概念，由此提出了兩個(gè)嵌入方案，并對其所需波長數(shù)進(jìn)行了分析，結(jié)果表明，這兩種波長分配方案所需波長數(shù)明顯小于最優(yōu)的靜態(tài)波長分配方案。 （4）研究了如何將雙調(diào)排序算法嵌入片上光總線網(wǎng)絡(luò)。針對雙調(diào)歸并操作的特點(diǎn)，提出了一個(gè)波長分配方案，進(jìn)而提出了對n個(gè)元素的無序序列進(jìn)行雙調(diào)排序的波長分配方案，證明了該方案所需波長數(shù)是n2。 最后，對本文工作進(jìn)行了總結(jié)，并對后續(xù)研究進(jìn)行了展望。
[Abstract]:With the increase of processor number and processing speed in large scale parallel computing system, the communication overhead of the whole system is also increasing rapidly. Therefore, effective communication network is needed to realize fast communication between processors. Because of the shortcomings of bandwidth, delay and energy consumption, traditional electrical interconnection can not meet the needs of large-scale parallel computer communication. Due to its excellent characteristics such as high transmission bandwidth, extremely low transmission delay and extremely low power consumption, optical interconnection has become the new generation communication network of large-scale parallel computers. Wavelength division multiplexing (WDM) is one of the key technologies in optical communication. Its core idea is to divide the same optical fiber into multiple channels according to wavelength and transmit multiple optical signals at the same time. Embedding communication mode into WDM optical network is to map each subtask of communication mode to a node in the network and assign an optical path to each pair of nodes that need direct communication. All optical paths passing through the same optical fiber have different wavelengths. An important task of parallel computing is to embed various typical communication modes into typical WDM optical networks to achieve efficient communication. Because wavelength is an extremely valuable resource, we need to find the least number of wavelength assignment scheme, which is the wavelength assignment problem in WDM optical networks. Hypercubes, cross cubes and locally distorted cubes are typical communication modes, while linear arrays are typical WDM network topologies. This paper focuses on how to embed the above communication modes into linear array optical networks to minimize the required wavelengths. The results are as follows: (1) We study how to embed the locally twisted cube into the linear array statically. In this paper, a specific embedding scheme is proposed, and the optimality of the scheme is proved by using the maximum derived subgraph technique, and the corresponding wavelength assignment algorithm is given to minimize the number of required wavelengths. (2) We study how to embed generalized cube into linear array statically. A natural embedding scheme is proposed, the optimality of the scheme is proved, and the congestion degree of each edge in the array is determined. On this basis, the routing and wavelength assignment problems of half-duplex and full-duplex communication modes on linear arrays of crossed cubes are studied. It is proved that the natural embedding schemes have the minimum number of wavelengths in both communication modes. The corresponding wavelength assignment algorithm is also given. (3) how to dynamically embed the hypercube-based bimonal ordering into a linear array is studied. The concept of dimension embedding is put forward according to the characteristics of double tone ordering, and two embedding schemes are put forward, and the number of wavelengths required is analyzed. The results show that, The number of wavelengths required by these two wavelength assignment schemes is obviously smaller than that of the optimal static wavelength assignment scheme. (4) how to embed the bimodal sorting algorithm into the on-chip optical bus network is studied. According to the characteristics of dual modulation merging, a wavelength assignment scheme is proposed, and then a wavelength assignment scheme is proposed for ordering the disordered sequence of n elements. It is proved that the number of wavelengths required in this scheme is N2. Finally, the work of this paper is summarized, and the future research is prospected.
【學(xué)位授予單位】：重慶大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2014
【分類號】：TN929.1

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

1 關(guān)亞林;曾艷奇;逯貴禎;;基于并行計(jì)算環(huán)境的混波室三維仿真[J];中國傳媒大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年03期

2 程克非;羅江華;李紅波;;一種新的基于HPM并行計(jì)算性能數(shù)據(jù)采集方法[J];重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年01期

3 王結(jié)臣;王豹;胡瑋;張輝;;并行空間分析算法研究進(jìn)展及評述[J];地理與地理信息科學(xué);2011年06期

4 阮定益;;并行式matlab平臺(tái)搭建[J];電腦知識與技術(shù);2008年08期

5 胡海峰;;樹狀成本估算模型的并行處理[J];電腦知識與技術(shù);2009年28期

6 古奮飛;王良俠;;淺析Linux集群技術(shù)[J];電腦知識與技術(shù);2010年06期

7 肖強(qiáng)華;寧丹;;計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)中多處理機(jī)技術(shù)[J];電腦知識與技術(shù);2010年06期

8 古奮飛;王良俠;張莉;;基于Linux集群的高性能低成本的校園網(wǎng)解決方案[J];電腦知識與技術(shù);2012年02期

9 李焱;胡祥云;金鋼燮;吳桂桔;廖國忠;王程;;基于MPI的一維大地電磁并行計(jì)算研究[J];地球物理學(xué)進(jìn)展;2010年05期

10 崔金芳;張雪英;白靜;;基于OMAP5912的嵌入式非特定人連續(xù)語音識別系統(tǒng)[J];電聲技術(shù);2009年09期

相關(guān)會(huì)議論文 前8條

1 肖永浩;黃清南;;基于分塊數(shù)據(jù)結(jié)構(gòu)的沖擊問題并行計(jì)算[A];中國計(jì)算力學(xué)大會(huì)'2010（CCCM2010）暨第八屆南方計(jì)算力學(xué)學(xué)術(shù)會(huì)議（SCCM8）論文集[C];2010年

2 李根;李連崇;唐春安;唐世斌;王振;;巖石流固/熱固作用下?lián)p傷演化并行分析系統(tǒng)及應(yīng)用[A];中國計(jì)算力學(xué)大會(huì)'2010（CCCM2010）暨第八屆南方計(jì)算力學(xué)學(xué)術(shù)會(huì)議（SCCM8）論文集[C];2010年

3 張亞林;吳錦龍;李于鋒;趙曉平;;PANDA軟件框架的應(yīng)用模板研究[A];中國計(jì)算力學(xué)大會(huì)'2010（CCCM2010）暨第八屆南方計(jì)算力學(xué)學(xué)術(shù)會(huì)議（SCCM8）論文集[C];2010年

4 董延華;張曄;白文秀;;影響基于PC集群系統(tǒng)的因素研究[A];第六屆全國信息獲取與處理學(xué)術(shù)會(huì)議論文集（2）[C];2008年

5 武艷強(qiáng);江在森;楊國華;;最小二乘配置方法在提取GPS時(shí)間序列信息中的應(yīng)用[A];GPS技術(shù)應(yīng)用研究論文專輯[C];2007年

6 張志敏;梁逸曾;王家俊;;并行交互檢驗(yàn)方法及其在近紅外光譜中的應(yīng)用[A];中國化學(xué)會(huì)第26屆學(xué)術(shù)年會(huì)化學(xué)信息學(xué)與化學(xué)計(jì)量學(xué)分會(huì)場論文集[C];2008年

7 程煜峰;徐幼平;普業(yè);;并行計(jì)算在數(shù)值預(yù)報(bào)模式中的應(yīng)用[A];第28屆中國氣象學(xué)會(huì)年會(huì)——S17第三屆研究生年會(huì)[C];2011年

8 丁曉剛;鮑廣宇;胥秀峰;;一種可用于指控軟件的多核并行編程模式研究[A];2014第二屆中國指揮控制大會(huì)論文集（上）[C];2014年

相關(guān)博士學(xué)位論文 前10條

1 陸軍;基于組合學(xué)的數(shù)據(jù)編碼方法研究[D];哈爾濱工程大學(xué);2010年

2 程湯培;地下水流動(dòng)數(shù)值模擬的高效并行計(jì)算研究[D];中國地質(zhì)大學(xué)（北京）;2011年

3 劉苗;基于認(rèn)知無線電的PAPR優(yōu)化算法及ICI抑制算法的研究[D];吉林大學(xué);2011年

4 吳超;信息檢索中top-k問題的并行算法及優(yōu)化研究[D];中國科學(xué)技術(shù)大學(xué);2011年

5 李明國;混凝土梁橋?yàn)r青鋪裝結(jié)構(gòu)分析與材料優(yōu)化研究[D];長安大學(xué);2011年

6 董強(qiáng);幾類規(guī)則互連網(wǎng)絡(luò)的嵌入與容錯(cuò)嵌入研究[D];重慶大學(xué);2010年

7 刁克功;分區(qū)管理模式給水管網(wǎng)的水力分析與模擬技術(shù)研究[D];北京工業(yè)大學(xué);2011年

8 李銀;橢圓曲線密碼中的有限域算術(shù)運(yùn)算研究[D];上海交通大學(xué);2011年

9 龔春葉;面向異構(gòu)體系結(jié)構(gòu)的粒子輸運(yùn)并行算法研究[D];國防科學(xué)技術(shù)大學(xué);2011年

10 李根;基于模擬的水巖耦合變形破壞過程及機(jī)理研究[D];大連理工大學(xué);2011年

相關(guān)碩士學(xué)位論文 前10條

1 朱圣鑫;并行GPBiCG（m，l）算法與預(yù)處理技術(shù)[D];中國工程物理研究院;2010年

2 蘭任;基于并行混合粒子群算法的蛋白質(zhì)結(jié)構(gòu)預(yù)測[D];大連理工大學(xué);2010年

3 高和東;GPU并行計(jì)算在LSSVM建模中的研究與應(yīng)用[D];大連理工大學(xué);2010年

4 張晶;ABEEMσπ/MM模型中能量求解的并行化[D];遼寧師范大學(xué);2010年

5 田野;環(huán)境衛(wèi)星光學(xué)影像自動(dòng)配準(zhǔn)算法研究與并行實(shí)現(xiàn)[D];遼寧工程技術(shù)大學(xué);2009年

6 楊玨;基于并行環(huán)境求解TSP問題[D];昆明理工大學(xué);2009年

7 羅r

本文編號：2327938