題-1_100_100.jpg)
基本信息
- 項目名稱：
- 可重構(gòu)多處理器陣列的容錯上界
- 小類：
- 信息技術(shù)
- 簡介：
- 可重構(gòu)多處理器陣列的容錯上界
- 詳細(xì)介紹：
- 可重構(gòu)多處理器陣列的容錯上界
作品專業(yè)信息
撰寫目的和基本思路
- 對于一個給定的多處理器陣列，可以通過去除陣列中的某些行，利用這些行的可利用的點(diǎn)在邏輯上補(bǔ)償陣列中的其他不可用點(diǎn)，以提高處理器的利用率。本作品從研究被去除的行與增加的最大邏輯列數(shù)之間的關(guān)系入手，推理出自己的結(jié)論，并在此基礎(chǔ)上進(jìn)行分析，提出了自己的算法。
科學(xué)性、先進(jìn)性及獨(dú)特之處
- 本作品針對多處理器容錯計算領(lǐng)域中的一個技術(shù)難題給予研究,同時給出了求解這一問題新算法，計算出了可用處理器數(shù)量的新上界，具有極高的學(xué)術(shù)價值。
應(yīng)用價值和現(xiàn)實意義
- 作品具有很好的實際應(yīng)用價值和很好的應(yīng)用前景，該課題研究的成果將會大大提高大規(guī)模集成電路（VLSI）的使用性能，非常符合現(xiàn)在國家倡導(dǎo)的高性能低功耗的目標(biāo)。
學(xué)術(shù)論文摘要
- 本文討論了一種求解可重構(gòu)多處理器陣列容錯上界的新算法，此問題是多處理器容錯計算領(lǐng)域中的一個技術(shù)難題，由于其理論上具有難解性，以至于在學(xué)術(shù)界近十年來都沒有突破性進(jìn)展.本論文分析了陣列中去除行與增加邏輯列的關(guān)系并提出了SAR（Select andReverse）算法并給予了理論上的證明.此算法通過打破陣列中影響邏輯列總數(shù)的瓶頸條件，逐步增加邏輯列數(shù)，最終計算出問題的新上界.通過試驗?zāi)M結(jié)果計算得出，當(dāng)處理器錯誤率在10%的情況下，對于128×128規(guī)模的處理器陣列，本算法將該問題上界降低9.43%。
獲獎情況
- 無
鑒定結(jié)果
- 申報者在其所描述的項目中論據(jù)充分，引證可靠，項目內(nèi)容真實有效。可以進(jìn)行立項申請。
參考文獻(xiàn)
- Chor Ping Low,Member,IEEE,"An Efficient Reconfiguration Algorithm for Degradable VLSI/WSI Arrays,"IEEE Trans on Computers, vol 49, no.6, pp.553-559,June 2000.
同類課題研究水平概述
- 到目前為止主要有兩種方法解決陣列重組問題：冗余方法和重構(gòu)方法。所謂冗余方法就是在制造芯片時預(yù)留一定數(shù)量的備用處理單元，當(dāng)有工作處理單元出現(xiàn)故障時，使用備用處理單元來取代不能正常工作的處理器。針對冗余方法有不同的策略，很多文獻(xiàn)[1]-[7]詳細(xì)陳述了這些策略，還有的學(xué)者提出了帶有備用行和列的處理器體系。這種方法的最大特點(diǎn)是，重構(gòu)后陣列的大小是固定不變的，但是，如果備用處理器不能完全取代發(fā)生故障的處理器，冗余重構(gòu)策略就失效，導(dǎo)致整個系統(tǒng)停止工作。 不同于冗余方法，重構(gòu)方法把陣列中的所有元素都同等對待，不提前預(yù)留備用處理單元。這種方法采用的是在故障發(fā)生后通過盡可能多的使用剩余的無故障處理單元來構(gòu)建目標(biāo)陣列的策略。重構(gòu)后的VLSI陣列的階數(shù)比原VLSI陣列的要小，因此，這種方法又被稱為降階重構(gòu)方法。 對于VLSI陣列上的降階重構(gòu)方法的研究開始于80年代，一些學(xué)者開始了對降階重構(gòu)問題模型分析、解決策略的探討。90年代后，降階重構(gòu)方法的研究發(fā)展迅速，S. Y. Kuo 和 I.Y. Chen針對本問題在三種不同的選路約束條件下進(jìn)行了研究：1) 行、列穿越方式（rowand column bypass），2) 行穿越、列選路方式（row bypass andcolumn rerouting），3) 行、列選路方式（row and columnrerouting）。通過研究，他們證明了大多數(shù)基于這三種約束條件下而產(chǎn)生的問題都是NP完全問題，同時他們針對這類問題提出了啟發(fā)式的解決算法。 C.P. Low and H.W.Leong提出了在第二及第三種約束條件下的通用啟發(fā)式解決算法，可以在多項式時間內(nèi)找到近似最優(yōu)解，并且指出在第二種約束條件下陣列重組問題的一個特例可以在線性時間內(nèi)得到最優(yōu)解，并給出了算法的詳細(xì)描述和證明過程。這是一種新的基于貪心策略的啟發(fā)式算法。由于第二種選路約束在重構(gòu)時具有更大的靈活性，后續(xù)的很多研究都偏向于以此為模型。
