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