【摘要】：急劇增長的芯片集成密度使得多處理器系統(tǒng)在制造或者系統(tǒng)運行過程中發(fā)生故障的可能性大大增加。為提高系統(tǒng)可靠性,本文針對已有工作不足之處,研究了在包含故障單元的二維、三維處理器陣列上構(gòu)造無故障邏輯子陣列的問題,主要研究內(nèi)容和創(chuàng)新點包括以下幾方面。第一、本文研究了二維、三維處理器陣列容錯機(jī)制問題。與現(xiàn)存方法不同,本文全面地考慮了陣列中存在的處理器故障、連線故障和拓?fù)溟_關(guān)故障,分別設(shè)計了二維、三維陣列上的增強(qiáng)型容錯模型。本文在增強(qiáng)型容錯模型上,將拓?fù)溟_關(guān)故障轉(zhuǎn)化為連線故障,之后對連線故障分類處理。第二、本文研究了最大無故障邏輯陣列的構(gòu)造問題。首先證明了容錯重構(gòu)問題是NP難解的,之后著重研究了特定約束條件下的重構(gòu)問題。本文分析了傳統(tǒng)選路模式的不足,設(shè)計了更加靈活的列選路模式及面選路模式來輔助重構(gòu)過程,消除了補償距離的約束,大大提高了構(gòu)造無故障邏輯陣列的效率。本文設(shè)計了高效重構(gòu)算法,在給定的約束條件下,能夠分別獲得二維、三維最大邏輯陣列,并給出了證明。第三、本文研究了利用并行技術(shù)來加速容錯重構(gòu)的問題。設(shè)計了兩種集中式并行重構(gòu)方法:多線程算法利用多個線程并行地構(gòu)造各個邏輯列,而基于分治策略的并行方法則是并行地構(gòu)造每一個邏輯列。本文還設(shè)計了兩種分布式并行重構(gòu)方法,能夠依靠陣列自身的處理器單元來實現(xiàn)陣列的重構(gòu)。第四、本文研究了緊致邏輯陣列的構(gòu)造問題,即陣列互連網(wǎng)絡(luò)冗余最小化問題。首先證明了互連網(wǎng)絡(luò)冗余的最小化問題是NP難解問題,之后設(shè)計算法來構(gòu)造特定規(guī)模的緊致陣列,以及最大規(guī)模的緊致陣列。為衡量所提出方法的性能,本文研究了二維、三維邏輯陣列的互連網(wǎng)絡(luò)長度的下界。實驗結(jié)果表明所構(gòu)造陣列與所計算下界較為接近,說明二者都接近于最優(yōu)解。
【學(xué)位授予單位】：天津大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2014
【分類號】：TP332


本文編號：2801029