本科系统结构课件 chapter6-4

§4脉动阵列处理机为要求计算量很大的信号/图像处理及科学计算的特定算法需要卡内基-梅隆大学的美籍华人H.T.Kung于1978年提出脉动阵列处理（SystolicArray）机具有较高的计算并行性脉动阵列结构原理通用脉动阵列结构SystolicArchitecturesOrchestrate（编制、合成）

dataflowforhighthroughputwithlessmemoryaccessDifferentfrompipeliningNonlineararraystructure,multidirectiondataflow,eachPEmayhave(small)localinstructionanddatamemoryDifferentfromSIMDEachPEmaydosomethingdifferentInitialmotivationVLSIenablesinexpensivespecial-purposechipsRepresentalgorithmsdirectlybychipsconnectedinregularpatternSystolicArchitecturesMPEPEPEMPEConventionalSystolicarraysReplaceaprocessingelement(PE)withanarrayofPE’swithoutincreasingI/ObandwidthTwoCommunicationStylesCPUCPUCPULocalMemoryLocalMemoryLocalMemorySystoliccommunicationMemorycommunicationCPULocalMemoryCPULocalMemoryCPULocalMemoryCharacteristicsPracticalrealizations(e.g.InteliWARP)usequitegeneralprocessorsEnablevarietyofalgorithmsonsamehardwareButdedicatedinterconnectchannelsDatatransferdirectlyfromregistertoregisteracrosschannelSpecialized,andsameproblemsasSIMDGeneralpurposesystemsworkwellforsamealgorithms(localityetc.)脉动阵列结构的构形一维线形二维矩形二维六边形二维二叉树性二维三角形三维。。。举例在一个脉动式二维阵列结构上进行两个3*3矩阵相乘每一个处理单元PE含有一个乘法器和一个加法器，完成一个内积运算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.脉动阵列结构特点结构简单、规整，模块化强，可扩充，非常适合用超大规模集成电路实现；PE间数据通信距离短、规则，使数据流和控制流的设计、同步控制等均简单规整；脉动阵列中所有的PE能同时运算，具有较高的计算并行性，可通过流水获得很高的运算效率和吞吐率。输入数据能被多个处理单元重复使用，大大减轻了阵列与外界的I/O通信量，降低了对系统主存和I/O系统频宽的要求；脉动阵列的构形于特定计算任务和算法密切相关，具有某种专用性，限制了应用范围，这对VLSI不利；通用脉动阵列结构关键因素：受阵列结构的通用性及I/O带宽约束所限制的阵列结构的规模大小不同算法要求有不同的阵列结构，以及大小不同的阵列发展通用阵列结构的途径（1）通过增设附加的硬件，对阵列的拓扑结构和互连方式用可编程开关进行重构，即经程序重新配置阵列的结构美国Purdue大学，Chip(Configurable