【摘要】：高效的容錯(cuò)技術(shù)對(duì)于提高多處理器系統(tǒng)的可靠性至關(guān)重要。環(huán)網(wǎng)(Torus)是連接多處理器陣列的重要網(wǎng)絡(luò)結(jié)構(gòu),而環(huán)網(wǎng)處理器陣列上的容錯(cuò)重構(gòu)技術(shù)目前尚屬空白。針對(duì)環(huán)網(wǎng)陣列的特殊連接方式,將環(huán)網(wǎng)陣列重構(gòu)問(wèn)題轉(zhuǎn)化為矛盾圖上求解最大獨(dú)立集問(wèn)題。矛盾圖上的結(jié)點(diǎn)表示故障處理器的替換方案,而邊代表了不同替換方案之間的不可共存特性。主要是根據(jù)三種不同的冗余處理器分布方案,設(shè)計(jì)生成矛盾圖算法,求解最大獨(dú)立集算法,以及由獨(dú)立集生成邏輯處理器陣列算法,取得了令人滿意的結(jié)果。實(shí)驗(yàn)結(jié)果表明,當(dāng)陣列規(guī)模較小或故障率較低時(shí),一行一列和十字型的冗余單元分布的重構(gòu)能力較好;而隨著陣列規(guī)�；蚬收下实脑龃�,三種冗余單元分布策略的重構(gòu)成功率都隨之下降,但可通過(guò)增加冗余單元以及調(diào)整冗余分布來(lái)改善容錯(cuò)效果。此外,從實(shí)驗(yàn)結(jié)果中還可以看出,環(huán)網(wǎng)處理器陣列的容錯(cuò)能力顯然優(yōu)于網(wǎng)格(Mesh)處理器陣列。
【圖文】：

所示是一個(gè)規(guī)模為２×３的環(huán)網(wǎng)處理器陣列，在其上一行和左一列集成了冗余單元。容錯(cuò)重構(gòu)的功能是通過(guò)向陣列中插入開(kāi)關(guān)和連線實(shí)現(xiàn)的，開(kāi)關(guān)和連線將每個(gè)處理單元連接在一起，從而使得陣列可以靈活地改變處理單元之間的連接方式。其中開(kāi)關(guān)單元具有三種狀態(tài)，這些狀態(tài)可以根據(jù)陣列的需求進(jìn)行切換。為了單獨(dú)考慮處理單元的重構(gòu)情況，本文做出了如下假設(shè)：（１）故障單元能夠轉(zhuǎn)化為連接單元，即連線；（２）開(kāi)關(guān)單元、連線及冗余單元均不含故障。Ｆｉｇｕｒｅ１Ｒｅｃｏｎｆｉｇｕｒａｂｌｅａｒｃｈｉｔｅｃｔｕｒｅ圖１可重構(gòu)結(jié)構(gòu)多數(shù)文獻(xiàn)都采用假設(shè)（１）；而假設(shè)（２），因?yàn)殚_(kāi)１４２４ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ＆Ｓｃｉｅｎｃｅ計(jì)算機(jī)工程與科學(xué)２０１５，３７（８）

布的不同，每個(gè)故障單元可能有著不同個(gè)數(shù)的補(bǔ)償通道。當(dāng)冗余單元的分布如圖１所示時(shí)，每個(gè)故障單元在理論上有兩個(gè)可能的補(bǔ)償通道，其方向分別是向上、向左，用［ｘ－，ｙ］、［ｘ，ｙ－］來(lái)表示。類(lèi)似地用［ｘ＋，ｙ］、［ｘ，ｙ＋］表示補(bǔ)償通道的方向向下、向右。（２）相鄰。所謂水平方向的相鄰關(guān)系是指兩個(gè)水平補(bǔ)償通道［ｘ１，ｙ－１］、［ｘ２，ｙ＋２］滿足｜ｘ１－ｘ２｜＝１，，且ｙ１＞ｙ２，同理可定義豎直方向的相鄰關(guān)系。圖２ａ所示的兩條補(bǔ)償通道為非相鄰情況，而圖２ｂ中所示的為相鄰情況。Ｆｉｇｕｒｅ２Ｒｅｐｌａｃｅｍｅｎｔｐａｔｈｓ圖２相鄰和非相鄰補(bǔ)償通道（３）相交。包括兩種情況：①兩個(gè)故障單元不在同一行或同一列上；②兩個(gè)故障單元位于同一行或同一列上。圖３ａ所示為兩個(gè)故障單元既非同一行，也非同一列，圖３ｂ所示為兩個(gè)故障單元位于同一行。Ｆｉｇｕｒｅ３Ｉｎｔｅｒｓｅｃｔ圖３相交２．２問(wèn)題描述及以往研究工作問(wèn)題Ｒ給定一個(gè)規(guī)模為ｍ×ｎ的環(huán)網(wǎng)連接的物理陣列Ｈ，Ｈ中還包含一定數(shù)量的冗余處理器單元。當(dāng)Ｈ中部分處理器發(fā)生故障時(shí)，利用冗余處理器單元對(duì)故障處理器單元進(jìn)行替換，得到一個(gè)ｍ×ｎ邏輯陣列。為了構(gòu)造有效的邏輯陣列，原始的ｍ×ｎ的物理陣列中所有故障單元都必須能夠被冗余單元所替換，并且替換補(bǔ)償通道間不能出現(xiàn)相交和相鄰的情況。如圖４所示，當(dāng)故障單元ｕ向右進(jìn)行補(bǔ)償，故障單元ｖ向左進(jìn)行補(bǔ)償時(shí)，即為所定義的相鄰情況，此時(shí)需要使用雙通道進(jìn)行布線才能實(shí)現(xiàn)（圓圈標(biāo)記處），而本文所研究的是在單通道的情況下，因而不允許存在相鄰情況。由于環(huán)網(wǎng)在水平和垂直方向上都
【作者單位】： 天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院;天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;
【基金】：國(guó)家自然科學(xué)基金資助項(xiàng)目(61173032);國(guó)家自然科學(xué)基金天元青年基金資助項(xiàng)目(11326211)
【分類(lèi)號(hào)】：TP332;TP302.8

【共引文獻(xiàn)】

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

1 周美婷;武繼剛;姜桂圓;;容錯(cuò)處理器陣列的并行重構(gòu)及VHDL實(shí)現(xiàn)[J];小型微型計(jì)算機(jī)系統(tǒng);2015年02期

2 賀佩蘭;姜桂圓;;靈活列選路模式下構(gòu)造緊致邏輯陣列的高效算法[J];小型微型計(jì)算機(jī)系統(tǒng);2015年02期

【相似文獻(xiàn)】

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

1 陳萬(wàn)福;查新檢索工作中的容錯(cuò)理論與容錯(cuò)技術(shù)[J];醫(yī)學(xué)情報(bào)工作;2001年05期

2 黎珊珊;實(shí)時(shí)分布式計(jì)算機(jī)系統(tǒng)的容錯(cuò)技術(shù)研究[J];計(jì)算機(jī)與數(shù)字工程;2002年06期

3 劉耀,胡越明,金利峰;高可靠計(jì)算機(jī)系統(tǒng)的容錯(cuò)技術(shù)[J];計(jì)算機(jī)工程;2004年S1期

4 張穎;李義杰;包劍;;計(jì)算機(jī)容錯(cuò)技術(shù)的研究與應(yīng)用[J];遼寧工程技術(shù)大學(xué)學(xué)報(bào);2004年S1期

5 龔健;楊孟飛;;基于可進(jìn)化硬件的容錯(cuò)技術(shù)及其原理[J];航天控制;2006年06期

6 邵清;魏峗;;《計(jì)算機(jī)系統(tǒng)容錯(cuò)技術(shù)》課程教學(xué)研究與探討[J];上海理工大學(xué)學(xué)報(bào)(社會(huì)科學(xué)版);2006年03期

7 周榮;;容錯(cuò)技術(shù)研究[J];商情(教育經(jīng)濟(jì)研究);2008年05期

8 辛?xí)粤?王銳;岳國(guó)峰;;容錯(cuò)技術(shù)在黑龍江省水利信息網(wǎng)中的應(yīng)用[J];黑龍江科技信息;2009年19期

9 萬(wàn)靖;;計(jì)算機(jī)聯(lián)鎖系統(tǒng)容錯(cuò)技術(shù)[J];科學(xué)咨詢(xún)(科技管理);2010年06期

10 李洪超;;計(jì)算機(jī)系統(tǒng)的容錯(cuò)技術(shù)方法[J];單片機(jī)與嵌入式系統(tǒng)應(yīng)用;2010年11期

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

1 蒙建波;吳銀成;楊俊永;;容錯(cuò)技術(shù)與儀表的發(fā)展[A];第三次全國(guó)會(huì)員代表大會(huì)暨學(xué)術(shù)會(huì)議論文集[C];2002年

2 王東盛;;容錯(cuò)技術(shù)在衛(wèi)星控制系統(tǒng)中的應(yīng)用[A];第十屆全國(guó)容錯(cuò)計(jì)算學(xué)術(shù)會(huì)議論文集[C];2003年

3 于洪濤;黃文軒;王和;;一種雙機(jī)容錯(cuò)方案及其應(yīng)用[A];開(kāi)創(chuàng)新世紀(jì)的通信技術(shù)——第七屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集[C];2001年

4 閔應(yīng)驊;;網(wǎng)絡(luò)容錯(cuò)與安全研究述評(píng)[A];第十屆全國(guó)容錯(cuò)計(jì)算學(xué)術(shù)會(huì)議論文集[C];2003年

5 龔健;楊孟飛;;硬件進(jìn)化系統(tǒng)的容錯(cuò)性研究[A];第十四屆全國(guó)容錯(cuò)計(jì)算學(xué)術(shù)會(huì)議(CFTC'2011)論文集[C];2011年

6 歐陽(yáng)一鳴;余雅瓊;郭凱;;基于同構(gòu)片上網(wǎng)絡(luò)拓?fù)淇芍貥?gòu)的容錯(cuò)硬件結(jié)構(gòu)[A];第六屆中國(guó)測(cè)試學(xué)術(shù)會(huì)議論文集[C];2010年

7 高航;羅宇;;RTEMS上基于軟件重算的容錯(cuò)支撐設(shè)計(jì)研究[A];2008年全國(guó)開(kāi)放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集(下冊(cè))[C];2008年

8 張魯飛;程華;;高性能計(jì)算機(jī)容錯(cuò)技術(shù)綜述[A];2010通信理論與技術(shù)新發(fā)展——第十五屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集（下冊(cè)）[C];2010年

9 張煥國(guó);;記索西埃教授來(lái)華講學(xué) 紀(jì)念中國(guó)計(jì)算機(jī)學(xué)會(huì)容錯(cuò)專(zhuān)業(yè)委員會(huì)成立十八周年[A];第十屆全國(guó)容錯(cuò)計(jì)算學(xué)術(shù)會(huì)議論文集[C];2003年

相關(guān)重要報(bào)紙文章 前10條

1 艾先;容錯(cuò)技術(shù)掃描[N];中國(guó)貿(mào)易報(bào);2004年

2 ;容錯(cuò)技術(shù)的發(fā)展與應(yīng)用展望[N];計(jì)算機(jī)世界;2001年

3 常文杰;新容錯(cuò)浪潮[N];網(wǎng)絡(luò)世界;2004年

4 劉雨;讓容錯(cuò)服務(wù)器“平民化”[N];中國(guó)計(jì)算機(jī)報(bào);2007年

5 樊強(qiáng);容錯(cuò)服務(wù)器 服務(wù)未來(lái)[N];中國(guó)電腦教育報(bào);2004年

6 ;容錯(cuò)技術(shù)應(yīng)用前景[N];中國(guó)高新技術(shù)產(chǎn)業(yè)導(dǎo)報(bào);2004年

7 宋家雨;容錯(cuò)之錯(cuò)[N];網(wǎng)絡(luò)世界;2007年

8 孔令男;容錯(cuò)技術(shù)高端商用領(lǐng)域的核心[N];中國(guó)國(guó)門(mén)時(shí)報(bào);2004年

9 遼河石油勘探局物資公司 趙雁　林斌;存儲(chǔ)容錯(cuò)：魚(yú)與熊掌可以兼得[N];中國(guó)計(jì)算機(jī)報(bào);2010年

10 本報(bào)記者 劉學(xué)習(xí);容錯(cuò)推新集群服務(wù)器[N];計(jì)算機(jī)世界;2009年

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

1 李旭;基于非易失內(nèi)存的高性能計(jì)算容錯(cuò)技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2013年

2 林勇;基于進(jìn)化型硬件的容錯(cuò)方法研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2007年

3 朱萍;硬實(shí)時(shí)容錯(cuò)調(diào)度算法研究[D];華中科技大學(xué);2011年

4 徐建軍;面向寄存器軟錯(cuò)誤的容錯(cuò)編譯技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2010年

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

1 代征;彈性函數(shù)在彈性容錯(cuò)技術(shù)中的應(yīng)用研究[D];武漢大學(xué);2004年

2 張國(guó)強(qiáng);星載并行處理計(jì)算機(jī)系統(tǒng)容錯(cuò)技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2006年

3 張淑燕;基于嵌入式多核平臺(tái)的并行冗余線程容錯(cuò)技術(shù)研究[D];哈爾濱工業(yè)大學(xué);2009年

4 王博偉;嵌入分布系統(tǒng)多模式容錯(cuò)技術(shù)研究[D];西北工業(yè)大學(xué);2007年

5 琚巍巍;分布式存儲(chǔ)系統(tǒng)容錯(cuò)技術(shù)的研究與實(shí)現(xiàn)[D];西安電子科技大學(xué);2009年

6 陸永平;公安網(wǎng)環(huán)境下拜占庭故障模型容錯(cuò)技術(shù)研究[D];大連理工大學(xué);2013年

7 王偉成;星載計(jì)算機(jī)多機(jī)并行系統(tǒng)容錯(cuò)技術(shù)研究與設(shè)計(jì)[D];國(guó)防科學(xué)技術(shù)大學(xué);2010年

8 李林虎;基于編譯中間代碼的關(guān)鍵變量容錯(cuò)技術(shù)[D];國(guó)防科學(xué)技術(shù)大學(xué);2011年

9 朱浩;云環(huán)境下MapReduce容錯(cuò)技術(shù)的研究[D];上海交通大學(xué);2012年

10 唐敏;云環(huán)境下中間數(shù)據(jù)容錯(cuò)方法的研究[D];遼寧大學(xué);2011年

本文編號(hào)：2541448