本科系統(tǒng)結(jié)構(gòu)課件 chapter6-4

§4脈動(dòng)陣列處理機(jī)為要求計(jì)算量很大的信號(hào)/圖像處理及科學(xué)計(jì)算的特定算法需要卡內(nèi)基-梅隆大學(xué)的美籍華人H.T.Kung于1978年提出脈動(dòng)陣列處理（SystolicArray）機(jī)具有較高的計(jì)算并行性脈動(dòng)陣列結(jié)構(gòu)原理通用脈動(dòng)陣列結(jié)構(gòu)SystolicArchitecturesOrchestrate（編制、合成）

dataflowforhighthroughputwithlessmemoryaccessDifferentfrompipeliningNonlineararraystructure,multidirectiondataflow,eachPEmayhave(small)localinstructionanddatamemoryDifferentfromSIMDEachPEmaydosomethingdifferentInitialmotivationVLSIenablesinexpensivespecial-purposechipsRepresentalgorithmsdirectlybychipsconnectedinregularpatternSystolicArchitecturesMPEPEPEMPEConventionalSystolicarraysReplaceaprocessingelement(PE)withanarrayofPE’swithoutincreasingI/ObandwidthTwoCommunicationStylesCPUCPUCPULocalMemoryLocalMemoryLocalMemorySystoliccommunicationMemorycommunicationCPULocalMemoryCPULocalMemoryCPULocalMemoryCharacteristicsPracticalrealizations(e.g.InteliWARP)usequitegeneralprocessorsEnablevarietyofalgorithmsonsamehardwareButdedicatedinterconnectchannelsDatatransferdirectlyfromregistertoregisteracrosschannelSpecialized,andsameproblemsasSIMDGeneralpurposesystemsworkwellforsamealgorithms(localityetc.)脈動(dòng)陣列結(jié)構(gòu)的構(gòu)形一維線形二維矩形二維六邊形二維二叉樹性二維三角形三維。。。舉例在一個(gè)脈動(dòng)式二維陣列結(jié)構(gòu)上進(jìn)行兩個(gè)3*3矩陣相乘每一個(gè)處理單元PE含有一個(gè)乘法器和一個(gè)加法器，完成一個(gè)內(nèi)積運(yùn)算MatrixMultiplicationa11a12a13a21a22a23a31a32a33*b11b12b13b21b22b23b31b32b33=c11c12c13c21c22c23c31c32c33ConventionalMethod:N3ForI=1toNForJ=1toNForK=1toNC[I,J]=C[I,J]+A[J,K]*B[K,J]; SystolicMethodThiswillruninO(n)time!ToruninNtimeweneedNxNprocessingunits,inthiscaseweneed9.P9P8P7P6P5P4P1P2P3Weneedtomodifytheinputdata,likeso:a13a12a11a23a22a21a33a32a31b31b32b33b21b22b23b11b12b13Flipcolumns1&3Fliprows1&3andfinallystaggerthedatasetsforinput.P9P8P7P6P5P4P1P2P3a13a12a11a23a22a21a33a32a31b31b21b11b32b22b12b33b23b13Ateverytickoftheglobalsystemclockdataispassedtoeachprocessorfromtwodifferentdirections,thenitismultipliedandtheresultissavedinaregister.342

253325*=342

253325233628

253934283237Letstrythisusingasystolicarray.P9P8P7P6P5P4P1P2P32433523235235322543*32435232523532254Clocktick:1900000000P1P2P3P4P6P5P7P8P92*34*23*4235352353225Clocktick:217120600000P1P2P3P4P6P5P7P8P93*32*45*22*34*53*2352532Clocktick:3233261680900P1P2P3P4P6P5P7P8P93*42*22*25*53*32*24*355Clocktick:42336182533413120P1P2P3P4P6P5P7P8P93*25*25*35*33*22*5Clocktick:523362825391928226P1P2P3P4P6P5P7P8P92*35*23*5Clocktick:6233628253934283212P1P2P3P4P6P5P7P8P95*5Clocktick:7233628253934283237P1P2P3P4P6P5P7P8P9373228343925233628233628253934283237P1P2P3P4P6P5P7P8P9Sameanswer!In2n+1time,canwedobetter?Theanswerisyes,thereisanoptimization.脈動(dòng)陣列結(jié)構(gòu)特點(diǎn)結(jié)構(gòu)簡(jiǎn)單、規(guī)整，模塊化強(qiáng)，可擴(kuò)充，非常適合用超大規(guī)模集成電路實(shí)現(xiàn)；PE間數(shù)據(jù)通信距離短、規(guī)則，使數(shù)據(jù)流和控制流的設(shè)計(jì)、同步控制等均簡(jiǎn)單規(guī)整；脈動(dòng)陣列中所有的PE能同時(shí)運(yùn)算，具有較高的計(jì)算并行性，可通過流水獲得很高的運(yùn)算效率和吞吐率。輸入數(shù)據(jù)能被多個(gè)處理單元重復(fù)使用，大大減輕了陣列與外界的I/O通信量，降低了對(duì)系統(tǒng)主存和I/O系統(tǒng)頻寬的要求；脈動(dòng)陣列的構(gòu)形于特定計(jì)算任務(wù)和算法密切相關(guān)，具有某種專用性，限制了應(yīng)用范圍，這對(duì)VLSI不利；通用脈動(dòng)陣列結(jié)構(gòu)關(guān)鍵因素：受陣列結(jié)構(gòu)的通用性及I/O帶寬約束所限制的陣列結(jié)構(gòu)的規(guī)模大小不同算法要求有不同的陣列結(jié)構(gòu)，以及大小不同的陣列發(fā)展通用陣列結(jié)構(gòu)的途徑（1）通過增設(shè)附加的硬件，對(duì)陣列的拓?fù)浣Y(jié)構(gòu)和互連方式用可編程開關(guān)進(jìn)行重構(gòu)，即經(jīng)程序重新配置陣列的結(jié)構(gòu)美國(guó)Purdue大學(xué)，Chip(Configurable