隨著集成電路技術(shù)的飛速發(fā)展,片上系統(tǒng)體系結(jié)構(gòu)的復(fù)雜性不斷增加,成千上萬的核集成在一個(gè)芯片中。因此,帶寬、可擴(kuò)展性、端到端延遲和吞吐量的設(shè)計(jì)都面臨著瓶頸。片上系統(tǒng)內(nèi)核間的互連結(jié)構(gòu)（即互連網(wǎng)絡(luò)）已成為高性能多核處理器設(shè)計(jì)中必須考慮的關(guān)鍵問題。片上網(wǎng)絡(luò)作為一種新的互連方式,克服了傳統(tǒng)總線在芯片設(shè)計(jì)中的局限性。片上網(wǎng)絡(luò)借鑒了傳統(tǒng)并行處理機(jī)中的互連網(wǎng)絡(luò)結(jié)構(gòu),其中網(wǎng)格和環(huán)繞是片上網(wǎng)絡(luò)最流行的兩種結(jié)構(gòu)。在片上網(wǎng)絡(luò)的設(shè)計(jì)與分析中,其布線與布局結(jié)構(gòu)極大地影響著系統(tǒng)性能。片上處理器受到空間、成本和功耗的限制,內(nèi)部以二維芯片布局為主,因此,高維互連網(wǎng)絡(luò)的通信方式需要通過二維布局與布線來實(shí)現(xiàn)。超立方體是常用的互連網(wǎng)絡(luò)之一,具有正則性、對(duì)稱性、高連通性等優(yōu)點(diǎn),但也存在直徑較大的問題。交換超立方體與3-元n-立方體分別是超立方體的重要變型,它們不僅保留了超立方體的優(yōu)良性質(zhì),而且增加了一些新的特性。片上網(wǎng)絡(luò)的布線與布局問題可以模擬為圖嵌入問題。本文重點(diǎn)研究了交換超方體和3-元n-立方體在兩類常用的芯片結(jié)構(gòu)——網(wǎng)格與環(huán)繞中的嵌入,主要研究?jī)?nèi)容如下:1.首先給出了交換超立方體的一個(gè)最佳集與一個(gè)最大導(dǎo)出子圖。然后給出了交... 

【文章來源】：蘇州大學(xué)江蘇省

【文章頁數(shù)】：115 頁

【學(xué)位級(jí)別】：博士

【部分圖文】：

圖１－１?ＮｏＣ體系結(jié)構(gòu)??２??

交換超立方體和３－元心立方體在網(wǎng)格與環(huán)繞中的嵌入?第二章相關(guān)知識(shí)??點(diǎn)上，可以得到嵌入的延展率為２，擁塞度為４，膨脹率和負(fù)載均為１。在圖２－ｌ（ｂ）中，??將３－超立方體的頂點(diǎn)都映射到頂點(diǎn)數(shù)為８的環(huán)形網(wǎng)絡(luò)中，可以得到嵌入的延展率為３，??擁塞度為３，膨脹率和負(fù)載均為１。??１?２?３??？?ｆ?ｆ??（ｂ?ＨＩ?＾＾￣￣＾＾＾?？？參??１?２３?４５６７８９??７?８?９??？?４?４??（４網(wǎng)格到線性陣列中的嵌入??——／??（ｂ）?３－維超立方體到環(huán)網(wǎng)中的嵌入??圖２－丨網(wǎng)格和超立方體到線性陣列和環(huán)網(wǎng)中的嵌入??將互連網(wǎng)絡(luò)嵌入到線性陣列（或者環(huán)網(wǎng)）也叫作線性布局（循環(huán)線性布局）或??者線性布置（循環(huán)線性布置）ｍｗｉ。線性布局是圖Ｇ到／／之間一個(gè)單射函數(shù)釦該函??數(shù)０：１／—丨１，２，．．．，《丨將圖６中的每個(gè)頂點(diǎn)分配不同的整數(shù)（從１到《），使得圖〇中的??每個(gè)頂點(diǎn)和每條邊與圖／／形成一個(gè)特定的對(duì)應(yīng)關(guān)系，其中／／表示一條水平的線性陣??列，其頂點(diǎn)按照其對(duì)應(yīng)關(guān)系進(jìn)行標(biāo)號(hào)為１，２，．．．，《（如圖２－１（３））。循環(huán)布局是存在一個(gè)??函數(shù)廣：＼／４｛１，２，．．．，《｝，同樣是對(duì)具有《個(gè)頂點(diǎn)的圖分配不同的整數(shù)（從１到《），而??是將圖的頂點(diǎn)布局到一個(gè)圈中，其中最后一個(gè)頂點(diǎn)（標(biāo)號(hào)為ｎ的頂點(diǎn)）與第一個(gè)頂點(diǎn)??（標(biāo)號(hào)為１的頂點(diǎn)）相鄰（如圖２－ｌ（ｂ））。這兩種情形下，負(fù)載度均為１。關(guān)于布局的優(yōu)??化問題，主要有以下幾個(gè)優(yōu)化目標(biāo)。??割寬最小化問題（Ｃｕｔｗｉｄｔｈ?Ｍｉｎｉｍｉｚａｔｉｏｎ?Ｐｒｏｂｌｅｍ，?ＣＭＰ）是一個(gè)ＮＰ－難的最小??極大線性布局問題［９４］。它是在線性陣列上

１０?１１０１０??／?１￣￣Ｊｘ＇?ｊｌ￣￣ｉ?＼??＼?／?／?ｏｏｑｏｏ?ｏｉｏｏｏ卜、一ｏｏｏｉｏ?ｏｉｂｉｏ?．??＼?ｏｑ＾ｐｏ?ｏｏｏｏｉ?０乂ｏｏｏ；?贏?／、邊一＇??〇〇ｉｊｒ?卜Ｈ?ｗ。＂?＇丨??ｕｏ〇（ｉ／?ｊ１００１?＂ｊ＇Ａ?＼?１?〇〇ｉ＾ｆ〇〇＂／＼＂〇（Ｓｒ＾ｎ〇?！??＾?＇Ｑ＾??ｕｖｒｏｏ＂?ｉｎ?）ｉ?ｍ丨丨一?Ｉ＇ｏｒｒｏ?ｉｏｏｏｉ?１００１１?ｎ〇〇ｉ?ｎｏｎ??ＥＨ（＼，３）?ＥＨ?（２，２）??圖２－３?￡州．，與￡／／２．２，其中虛線表示＆邊集，實(shí)線表示￡：邊集，黑線表示￡，邊集??總之，￡／／、．，中的頂點(diǎn)數(shù)目與込＋，＋?１中頂點(diǎn)數(shù)目相同，而邊的數(shù)目大約為２ｗ＋ｉ的??一羊。維邊，或者叫，的（Ｓ?＋?／＋１）－邊，是指ｗ與ｖ僅在第ｄ位不相同。這種??情況下，｝叫做ｘ的心鄰居，表示為ｖ?＝?ｙＶｒｆ（ｘ）。令表示￡／／ｗ的所有維邊，那??么，￡（￡／／，．，）?＝?構(gòu)，可以更準(zhǔn)確的表示為舊⑷仏．，）丨＝（．ｓ’?＋?＾?＋?２）２Ｈ?＝??（卜丄輕冊(cè)丨）丨＿。??交換超立方體的幾個(gè)性質(zhì)如下：??（１）?￡／／、．，同構(gòu)于￡／／，／９１。??（２）?—個(gè)￡７７、．，能夠被分成兩個(gè)或者兩個(gè)一個(gè)￡／／、，也能夠被分解??成Ｙ個(gè)不相交的ｇｊｌ２ｓ個(gè)不相交的（２／１９１。??（３）?￡／／，，，的連通度／＜（五／／，，，）?＝?Ｓ＋?１，其中１?幺?ｊ?幺?ｆ＿〇??交換超立方體比超立方體具有更低的鏈路復(fù)雜度，它可以直接影響系統(tǒng)的硬件??成本和ＶＬＳＩ實(shí)現(xiàn)１ｍ１。??２．２．２?３？元立方體及其基本性質(zhì)??３－元立方體定義如下：??

【參考文獻(xiàn)】：
期刊論文
[1]異構(gòu)三維片上網(wǎng)絡(luò)布局優(yōu)化的超圖劃分算法[J]. 宋國(guó)治,張大坤,馬杰超,涂遙,劉暢.  計(jì)算機(jī)科學(xué)與探索. 2016(06)
[2]一種考慮擁擠度的布線模型及其算法[J]. 陳秀華.  福州大學(xué)學(xué)報(bào)(自然科學(xué)版). 2015(01)
[3]一個(gè)同時(shí)考慮時(shí)延約束和擁擠度優(yōu)化的總體布線新方法[J]. 呂麗華,馬琪,謝滿得.  微電子學(xué)與計(jì)算機(jī). 2006(04)

博士論文
[1]交換交叉立方體上若干性質(zhì)的研究[D]. 周東仿.蘇州大學(xué) 2017
[2]若干互連網(wǎng)絡(luò)的圈嵌入和路嵌入[D]. 程冬琴.北京交通大學(xué) 2015
[3]基于智能算法的片上網(wǎng)絡(luò)布局優(yōu)化研究[D]. 樂千榿.電子科技大學(xué) 2014
[4]并行計(jì)算機(jī)故障診斷及WDM網(wǎng)絡(luò)路由與波長(zhǎng)分配問題研究[D]. 余翠.重慶大學(xué) 2014
[5]k-元n-立方體的路和圈[D]. 李晶.山西大學(xué) 2011
[6]幾類規(guī)則互連網(wǎng)絡(luò)的嵌入與容錯(cuò)嵌入研究[D]. 董強(qiáng).重慶大學(xué) 2010



本文編號(hào)：3266283