高等計算機系統結構研究生課程高等計算機系統結構課程介紹參考書目：1．PattersonD.A.，Hennesy

J.L.，Computer

Architecture：AQuantitativeApproach，Morgan

KanfmannPublishers，1995。2．ComputerOrganization &Design：The

Hardware／SoftwareInterface。第一章高等計算機的核心技術——并行處理第二章加速比性能模型與可擴展性分析第三章互連與通信第四章劃分與調度第五章并行存儲器系統第六章CacheCoherence第七章MemoryConsistency第八章指令級并行處理第一章高等計算機的核心技術——并行處理1.1什么是并行處理

1.1.1并行處理定義 1.1.2并行性級別1.2為什么要開發并行處理技術1.3并行處理計算機結構沿革1.4其它并行處理計算機技術1.1什么是并行處理1.1.1并行處理定義并行處理是指同時對多個任務或多條指令、或同時對多個數據項進行處理。 完成此項處理的計算機系統稱為并行處理計算機系統。弗林分類法按照指令流和數據流多倍性的特點，計算機可以劃分為以下四類：1、SISD：單指令流單數據流計算機2、SIMD：單指令流多數據流計算機3、MISD：多指令流單數據流計算機4、MIMD：多指令流多數據流計算機SISD：傳統的單CPU順序機SIMD：空間并行，多PE，向量處理MISD：流水線＋脈動陣列，專用MIMD：真正的并行處理機，包括共享存儲器型和消息傳遞型。MMPUCUDSISIS1、SISD：單指令流單數據流計算機

SISD典型單處理機，包括：單功能部件處理機：IBM1401，VAX-11

多功能部件處理機：IBM360/91，370/168，CDC6600

流水線處理機：標量流水線處理機MM1PU2CU….ISISPUnPU1MM2MMnDS2DSnDS12、SIMD：單指令流多數據流計算機

SIMD并行處理機、陣列處理機、向量處理機、相聯處理機、超標量處理機、超流水線處理機、…多個PU按一定方式互連，在同一個CU控制下，多各自的數據完成同一條指令規定的操作；從CU看，指令順序（串行）執行，從PU看，數據并行執行。3、MISD：多指令流單多數據流計算機MMCU1PU1CUnPUnCU2PU2……IO脈動式陣列（systolicarray）PU2CU1….IS3IS1PUnPU1MM1DS1CU2CUn….IS2MM2DS2MM2DS2IS1IS2IS3包括：緊密偶合：IBM3081、IBM3084松散偶合：D-825、Cmmp、CRAP-23、MIMD：多指令流單多數據流計算機

同時性（simultaneity）——兩個或多個事件在同一時刻發生，資源重復。

并發性（concurrency）——兩個或多個事件在同一時間間隔內發生，分時共用。

流水特性（pipelining）——在一個重疊的時間內所發生的流水事件，時間重疊。

1.1.2并行性級別

粒度（granularity）：衡量一個軟件進程的計算量的度量。最簡單的是指此程序段中的指令數。分細、中、粗三種。 按粒度的不同，并行性級別可以分為指令級、循環級、過程級、子程序級和作業級等不同的層次。它們對應的計算粒度可以為細粒度、中粒度和粗粒度。如下：1.指令級并行典型細粒度，一般少于20條指令。借助優化編譯器自動檢測并行性，將源代碼變成運行時系統能識別的并行形式。2.循環級并行

典型循環含少于500條指令，由于有些循環操作在連續迭代中并不相關，易于向量化，是在并行機或向量機上運行的最優程序結構。遞歸循環的并行化比較困難。向量處理由優化編譯器在循環級開發，仍屬于細粒度計算。3.過程級并行

中粒度并行，指令少于2000條，分析過程間的并行性比細粒度要困難。有時需要重新設計程序，并要編譯器的支持。SIMD、多任務處理屬于這一層。4.子程序級并行（粗）中粒度并行，幾千條指令，常在messagepassing多計算機上以SIMD或MIMD方式執行。并行性主要由算法設計人員與程序員開發。5.作業級并行粗粒度并行，數萬條指令，常由加載程序和操作系統處理這類并行性，靠算法有效性來保證。一般說來： 細粒度：用并行化或向量化編譯器來開發，共享變量通信支持。 中粒度：靠程序員和編譯器一起開發，共享變量通信。 粗粒度：取決于操作系統和算法的效率，消息傳遞通信。例子：在共享存儲器型多處理機上執行：

L1: DO 10 I=1,N L2: A(I)=B(I)+C(I) L3: 10 Continue L4: SUM=0 L5: DO 20 J=1,N L6: SUM=SUM+A(J) L7: 20 Continue假設：L2，L4，L6每行要用一個機器周期。L1，L3，L5，L7所需時間可以忽略。 所有數組已經裝入主存，程序已裝入Cache中（取指令和加載數據可以忽略不計）。 忽略總線爭用或存儲器訪問沖突。 上面的程序實際上把數組B(I)和C(I)相加，最后得到一個總和。

共享存儲多處理機結構如下圖：P1P2……Pm系統互連I/OSM1……SMm處理機共享存儲器 在單機系統中，2N個周期可以完成上述的操作：

I循環中執行N次獨立迭代需要N個周期；

J循環中執行N次遞歸迭代也需要N個周期。 在共享存儲型的多處理機系統上： 假設有M臺處理機，可以將循環分成M段，每段有L=N/M個元素。 代碼如下所示：

Doall k=1,M Do10I=L(k-1)+1,kL A(I)=B(I)+C(I) 10 Continue

SUM(k)=0 Do20J=1,L

SUM(k)=SUM(k)+A(L(k-1)+J) 20 Continue

Endall 分段的I循環可以在L個周期中完成； 分段的J循環在L個周期中產生M個部分和。 所以產生所有的M個部分和共需要2L個周期（還需要將這些部分和合并）。 假設經過共享存儲器的處理機之間的每次通信操作需要k個周期。 設N=32，M=8，則經過2L（即8個周期）后在8臺處理機上各有一個部分和，還需要8個數相加。 為了合并部分和，可以設計一個l層的二進制加法樹，其中l=log2M，加法樹用l(k+1)個周期從樹葉到樹根順序合并M個部分和，如下：

二進制加法樹： 所以，多處理機系統需要 才能得到最終的結果。 假定數組中有N=220個元素，順序執行需要2N=221個機器周期，假設機器間通信的開銷平均值為k=200個周期，則在M=256臺處理機的并行執行需要：第一章高等計算機的核心技術——并行處理 1.1什么是并行處理

1.2為什么要開發并行處理技術 1.3并行處理計算機結構沿革 1.4其它并行處理計算機技術1.2為什么要開發并行處理技術

對單用戶，可以提高加速比（SpeedupOriented)；

對多用戶，可以提高吞吐率（ThroughputOriented).

對不同的需求我們可以做需求分析如下： 1.天氣預報 天氣預報模式為非線性偏微分方程，預報臺風暴雨過程，計算量為1014—1016次浮點運算，需要10GFlops—100GFlops的巨型機。 用途：局部災害性天氣預報。2.石油工業

地震勘探資料處理 油藏數值模擬 測井資料處理 地震勘探由數據采集、數據處理和資料解釋三階段組成。 目前采用的三維地震勘探比較精確的反映地下情況，但數據量大，處理周期長。

100平方公里的三維勘探面積，道距25米，60次覆蓋，6秒長記錄，2毫秒采樣，一共采集2.881010個數據，約為116GB。 疊加后數據為4.8108個數據。用二維疊前深度偏移方法精確的產生地下深度圖像，需要進行251012FLOP，采用100MFLOPs機器計算250天，1GFLOPs機計算25天，10GFLOPs機器35分。考慮到機器持續速度常常是峰值速度的10-30%，所以需要100GFlops的機器。CrayT932/32約為60GFLOPs。3.航空航天 研究三維翼型對飛機性能的影響。數值模擬用時間相關法解Navier-Stoker方程，網格分點為1204050，需內存160MB，6億計算機上解12小時，如果在數分鐘內完成設計，則需要千億次計算機。4.重大挑戰性課題需求（圖3.5）

計算空氣動力學：千億次/秒（1011）

圖像處理： 百億次/秒（1010）

AI： 萬億次/秒（1012）5.核武器 核爆炸數值模擬，推斷出不同結構與不同條件下核裝置的能量釋放效應。 壓力： 幾百萬大氣壓 溫度： 幾千萬攝氏度 能量在秒級內釋放出來。設計一個核武器型號，從模型規律、調整各種參數到優選，需計算成百上千次核試驗。LosAlamos實驗室要求計算一個模型的上限為8-10小時。 千萬次機上算橢球程序的計算模型需要40-60CPU小時。 二維計算，每方向上網格點數取100，二維計算是一維的200倍，三維是一維的33000倍。若每維設1000網格點，則三維計算是一維的幾十萬倍之多。此時對主存儲器容量要數十、數百億字單元（64位）。 另外還有I/O能力的要求，可視化圖形輸出。 6.解決方案只有開發并行處理技術才能滿足要求：

3Tperformance：

TeraflopsofComputingPower TerabyteofMainMemory Terabyte/sofI/Obandwidth第一章高等計算機的核心技術——并行處理1.1什么是并行處理1.2為什么要開發并行處理技術1.3并行處理計算機結構沿革

1.3.1向量機與多向量機 1.3.2SIMD計算機 1.3.3Shared-MemoryMultiprocessors 1.3.4Distributed-MemoryMultiprocessors

1.3.5四類實用的并行系統1.4其它并行處理計算機技術1.3并行處理計算機結構沿革1.3.1向量機與多向量機向量機的結構如下圖：ScalarFunctionalpipelinesScalarControlunitscalarprocessorscalarinstructionMainMemory(Programanddata)MassStorageHostComputerI/O(user)VectorControlunitvectorregistersvectorprocessorcontrolVectorFunctionalpipelinesVectorFunctionalpipelines……vectorinstruction程序和數據從Host進入主機指令先在Scalarcontrolunit譯碼，如是標量或控制操作指令，則在標量功能流水部件種執行。如果是向量指令，則進入向量控制部件。register-to-register：

Crayseries FujitsuVP2000seriesmemory-to-memory：

Cyber205多向量機發展過程：CDC7600(CDC,1970)CDCCyber205(Levine,1982)Memory-MemoryCray1(Russell,1978)register-registerETA10(ETA,Inc,1989)CrayY-MPCrayResearch1989FujitsuNECHitachiModelsCrayMPPCrayResearch1993其中：

CrayY-MP,C90：

Y-MP有2，4，8個處理器，而C90有16個處理單元（PE），處理速度16GFlops。

ConvexC3800family：8個處理器，4GB主存儲器，

Peakperformance為2GFlops。1.3.2SIMD計算機SIMD計算機的結構如下圖：ControlUnitProc0Mem0Proc1Mem1……ProcN-1MemN-1PE0PE1PEN-1InterConnectionNetworkMasParMP-1：可有1024，4096，…，16384個處理器。在16KPEs，32位整數運算，16KB局部存儲器模塊的配置下，可達26000MIPS，單精度浮點運算1.5GFlops，雙精度浮點運算650MFlops。CM-2：

65536個處理單元，1Mbit/PE。 峰值速率為28GFlops，持續速率5.6GFlops。SIMD計算機發展過程圖如下：IlliacIV(1968)GoodYearMPP(1980)BSP(1982)MasParMP1(1990)IBMGF/11(1985)DAP610(AMT，Inc.1987)CM2(1990)CM5(1991)1.3.3MIMD－Shared-MemoryMultiprocessorsUMA(Uniform-memory-access)model：

物理存儲器被所有處理機均勻共享，所有處理機對所有存儲字具有相同的存取時間。P0I/OP1SM1……PnSMnInterConnectionNetwork(Bus、Crossbar、MultistageNetwork)……處理器共享存儲器NUMA(NonUniform-memory-access)model：訪問時間隨存儲字的位置不同而變化。P1……PnLMnInter-ConnectionNetwork……LM1P2LM2……COMA(Cache-onlymemoryarchitecture)：只用高速緩存的多處理機 遠程高速緩存訪問則借助于分布高速緩存目錄進行。PDInterConnectionNetwork……distributedcachedirectoriesCPDCPDCKendallSquareResearch’sKSR-1Shared-MemoryMultiprocessors發展過程如下：Cmmp(cmu,1972)IllinoisCedar(1987)UltraComputerNYU(1983)FujitsuVPP500(1992)IBMRP3(1985)BBNButterfly(1989)stanford/Dash(1992)KSR-1(1990)1.3.4MIMD－Distributed-MemoryMultiprocessorsP……Message-passinginterconnectionnetwork(Mesh,ring,torus,hypercube,cube,cycle)MPMPMP……PPMMMMP……MPMP……MP例子：

IntelParagonXP/s：

采用50MHz的i860處理器，每個節點16-128MB主存儲器，采用2D-Mesh互連，浮點運算5-300GFlops，或2.8-160Gips。

nCube2SModel80：

有4096-8192個PE，主存儲器16384-262144MB，浮點運算163800-34000MFlops，整數運算61000-123000MIPS。 CosmicCube(1981)nCube-2/6400(1990)Mosaic(1992)Intelparagon(1992)MIT/Jmachine(1992)intel

iPSC’s(1983)Distributed-Memorymultiprocessors發展進程：1.3.5四類實用的并行系統1.向量機與多向量機硬、軟件技術相對成熟、應用廣泛、市場占有率高。很難達到3Tperformance來解決GrandChallenge

問題。 下面圖表說明了這一類機器的發展過程。GFlops100100.11976197919821985198819911994YearCray1/10.16GFCrayX-MP/20.24GFCray2/41.9GFCrayY-MP/82.6GFCrayJ916/163.2GFCrayC916/1616GFCrayT932/3260GF2.對稱式多處理機SMP

SMP：Symmetric

MultiProcessors SharedMemorymultiProcessors SmallsizeMultiProcessors

處理機之間無主從之分，對外有相同的訪問權，都有執行操作系統核心和I/O服務程序的能力。 共享存儲器、統一地址空間，系統編程比較容易。

CPU可多至16臺左右，做服務器用，市場前景好。典型的SMP有：

SunSPARCserver1000 SunSPARCcenter2000 SGIPowerChallengeSGIPowerChallengeL：2-6CPU，1.8GFlopsSGIPowerChallengeXL：

2-18CPU，5.4GFlops

*64位MIPSchip，每周期指令發射數為4

*8路交錯主存、帶寬為1.2GB/s

*I/O帶寬320MB/s（每個控制器），配置4個可達1.2GB/s3.MPP系統（分布存儲）多于100個PE，消息傳遞，分布存儲； 可擴展，峰值可達3Tperformance；

貴，市場有限； 持續速度是峰值速度的3-10%； 可解決某些GrandChallenge問題，是國家綜合實力的象征。 4.機群系統

NOW：NetworkOfWorkstations

COW：ClusterOfWorkstations特點： 投資風險小，軟件財富繼承性好；可構成異構系統，資源利用率高； 通信開銷大。 一種典型的機群系統結構如下：CPUMemoryI/OCPUMemoryI/O……CPUMemoryI/OI/OI/OI/OMemoryMemory……MemoryCPUCPUCPUNetwork第一章高等計算機的核心技術——并行處理

1.1什么是并行處理 1.2為什么要開發并行處理技術

1.3并行處理計算機結構沿革

1.4其它并行處理計算機技術1.4其它并行處理計算機技術1.數據流技術 dataflow以數據驅動機制代替控制流機制 當功能部件輸入端的操作數可用時就啟動執行；可開發程序中所有的并行性，但費用昂貴，實際性能與功能部件數量、存儲器帶寬以及掛起和可用部件相匹配的程度有關。 如：MIT的MonSoos，*T

ETL的Sigma1，EM52.多線程 每臺處理機有多個控制線程，同時運行多個現場，是實現時延隱藏的一種有效機制。 比如:

Tera，Alewife

成本高。3.邏輯推理與規約結構 邏輯推理： 日本第五代機，面向邏輯語言、執行速度慢，軟件與程序設計環境欠豐富。

規約結構：

Alice，PGR，面向函數語言，執行速度慢，軟件與環境欠豐富。4.關鍵技術 并行算法（數值算法與非數值算法） 并行計算模型 互連與通信 并行存儲技術 同步與時延隱藏技術 并行I/O

劃分、調度與負載平衡 優化編譯 并行調試 工具與環境5.美國的主要行動（1）組織基于NSF的國家科學計算聯盟 （NationalComputationalScienceAlliance）

建立國家科技網（Grid）：97.11開始，五年計劃，總經費3.4億美元。

目標：使美國在全國范圍內的元計算機（網上的計算機可作為一個整體看待）達到實用水平。 為在桌面上解決計算科學與工程時提供一個有力的解題環境。 解決基于元計算環境的并行、分布、協作和immersive等問題。

UIUC、San

Diago組織實施。（2）DOE（能源部）支持的ASIC計劃 （AcceleratedStrategicComputingInitiative）

保證在21世紀美國在核研究和核儲備繼續處于領先地位。 以LosAlamos，