第10章 多處理機(jī)

第10章多處理機(jī)10.1 引言10.2 對(duì)稱(chēng)式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)10.3 分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)10.4 同步10.5 同時(shí)多線(xiàn)程10.6大規(guī)模并行處理機(jī)MPP10.7 多處理機(jī)實(shí)例1：T110.8 多處理機(jī)實(shí)例2：Origin

20001.單處理機(jī)系統(tǒng)結(jié)構(gòu)正在走向盡頭？2.多處理機(jī)正起著越來(lái)越重要的作用。近幾年來(lái)，人們確實(shí)開(kāi)始轉(zhuǎn)向了多處理機(jī)。Intel于2004年宣布放棄了其高性能單處理器項(xiàng)目，轉(zhuǎn)向多核（multi-core）的研究和開(kāi)發(fā)。IBM、SUN、AMD等公司并行計(jì)算機(jī)應(yīng)用軟件已有了穩(wěn)定的發(fā)展。充分利用商品化微處理器所具有的高性能價(jià)格比的優(yōu)勢(shì)。3.本章重點(diǎn)：中小規(guī)模的計(jì)算機(jī)(處理器的個(gè)數(shù)＜32)

（多處理機(jī)設(shè)計(jì)的主流）10.1引言10.1引言Flynn分類(lèi)法

SISD、SIMD、MISD、MIMDMIMD已成為通用多處理機(jī)系統(tǒng)結(jié)構(gòu)的選擇，原因：MIMD具有靈活性；MIMD可以充分利用商品化微處理器在性能價(jià)格比方面的優(yōu)勢(shì)。計(jì)算機(jī)機(jī)群系統(tǒng)（cluster）是一類(lèi)廣泛被采用的MIMD機(jī)器。10.1.1并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的分類(lèi)10.1引言根據(jù)存儲(chǔ)器的組織結(jié)構(gòu)，把現(xiàn)有的MIMD機(jī)器分為兩類(lèi)：（每一類(lèi)代表了一種存儲(chǔ)器的結(jié)構(gòu)和互連策略）集中式共享存儲(chǔ)器結(jié)構(gòu)最多由幾十個(gè)處理器構(gòu)成。各處理器共享一個(gè)集中式的物理存儲(chǔ)器。這類(lèi)機(jī)器有時(shí)被稱(chēng)為SMP機(jī)器（Symmetricshared-memoryMultiProcessor）UMA機(jī)器（UniformMemoryAccess）

10.1引言對(duì)稱(chēng)式共享存儲(chǔ)器多處理機(jī)的基本結(jié)構(gòu)10.1引言分布式存儲(chǔ)器多處理機(jī)存儲(chǔ)器在物理上是分布的。每個(gè)結(jié)點(diǎn)包含：處理器存儲(chǔ)器I／O互連網(wǎng)絡(luò)接口在許多情況下，分布式存儲(chǔ)器結(jié)構(gòu)優(yōu)于集中式共享存儲(chǔ)器結(jié)構(gòu)。10.1引言10.1引言將存儲(chǔ)器分布到各結(jié)點(diǎn)有兩個(gè)優(yōu)點(diǎn)如果大多數(shù)的訪(fǎng)問(wèn)是針對(duì)本結(jié)點(diǎn)的局部存儲(chǔ)器，則可降低對(duì)存儲(chǔ)器和互連網(wǎng)絡(luò)的帶寬要求；對(duì)本地存儲(chǔ)器的訪(fǎng)問(wèn)延遲時(shí)間小。最主要的缺點(diǎn)處理器之間的通信較為復(fù)雜，且各處理器之間訪(fǎng)問(wèn)延遲較大。簇：超級(jí)結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)內(nèi)包含個(gè)數(shù)較少（例如2～8）的處理器；處理器之間可采用另一種互連技術(shù)（例如總線(xiàn)）相互連接形成簇。10.1引言?xún)煞N存儲(chǔ)器系統(tǒng)結(jié)構(gòu)和通信機(jī)制共享地址空間物理上分離的所有存儲(chǔ)器作為一個(gè)統(tǒng)一的共享邏輯空間進(jìn)行編址。任何一個(gè)處理器可以訪(fǎng)問(wèn)該共享空間中的任何一個(gè)單元（如果它具有訪(fǎng)問(wèn)權(quán)），而且不同處理器上的同一個(gè)物理地址指向的是同一個(gè)存儲(chǔ)單元。這類(lèi)計(jì)算機(jī)被稱(chēng)為

分布式共享存儲(chǔ)器系統(tǒng)

（DSM:DistributedShared-Memory)NUMA機(jī)器（NUMA:Non-UniformMemoryAccess)

10.1.2存儲(chǔ)器系統(tǒng)結(jié)構(gòu)和通信機(jī)制10.1引言把每個(gè)結(jié)點(diǎn)中的存儲(chǔ)器編址為一個(gè)獨(dú)立的地址空間，不同結(jié)點(diǎn)中的地址空間之間是相互獨(dú)立的。整個(gè)系統(tǒng)的地址空間由多個(gè)獨(dú)立的地址空間構(gòu)成每個(gè)結(jié)點(diǎn)中的存儲(chǔ)器只能由本地的處理器進(jìn)行訪(fǎng)問(wèn)，遠(yuǎn)程的處理器不能直接對(duì)其進(jìn)行訪(fǎng)問(wèn)。每一個(gè)處理器-存儲(chǔ)器模塊實(shí)際上是一臺(tái)單獨(dú)的計(jì)算機(jī)現(xiàn)在的這種機(jī)器多以集群的形式存在通信機(jī)制共享存儲(chǔ)器通信機(jī)制共享地址空間的計(jì)算機(jī)系統(tǒng)采用10.1引言處理器之間是通過(guò)用load和store指令對(duì)相同存儲(chǔ)器地址進(jìn)行讀/寫(xiě)操作來(lái)實(shí)現(xiàn)的。消息傳遞通信機(jī)制多個(gè)獨(dú)立地址空間的計(jì)算機(jī)采用通過(guò)處理器間顯式地傳遞消息來(lái)完成消息傳遞多處理機(jī)中，處理器之間是通過(guò)發(fā)送消息來(lái)進(jìn)行通信的，這些消息請(qǐng)求進(jìn)行某些操作或者傳送數(shù)據(jù)。

10.1引言例如：一個(gè)處理器要對(duì)遠(yuǎn)程存儲(chǔ)器上的數(shù)據(jù)進(jìn)行訪(fǎng)問(wèn)或操作：發(fā)送消息，請(qǐng)求傳遞數(shù)據(jù)或?qū)?shù)據(jù)進(jìn)行操作；

遠(yuǎn)程進(jìn)程調(diào)用(RPC，RemoteProcessCall)目的處理器接收到消息以后，執(zhí)行相應(yīng)的操作或代替遠(yuǎn)程處理器進(jìn)行訪(fǎng)問(wèn)，并發(fā)送一個(gè)應(yīng)答消息將結(jié)果返回。同步消息傳遞請(qǐng)求處理器發(fā)送一個(gè)消息后一直要等到應(yīng)答結(jié)果才繼續(xù)運(yùn)行。異步消息傳遞

數(shù)據(jù)發(fā)送方知道別的處理器需要數(shù)據(jù)，通信也可以從數(shù)據(jù)發(fā)送方來(lái)開(kāi)始，數(shù)據(jù)可以不經(jīng)請(qǐng)求就直接送往數(shù)據(jù)接受方。10.1引言不同通信機(jī)制的優(yōu)點(diǎn)共享存儲(chǔ)器通信的主要優(yōu)點(diǎn)

與常用的對(duì)稱(chēng)式多處理機(jī)使用的通信機(jī)制兼容。易于編程，同時(shí)在簡(jiǎn)化編譯器設(shè)計(jì)方面也占有優(yōu)勢(shì)。采用大家所熟悉的共享存儲(chǔ)器模型開(kāi)發(fā)應(yīng)用程序，而把重點(diǎn)放到解決對(duì)性能影響較大的數(shù)據(jù)訪(fǎng)問(wèn)上。當(dāng)通信數(shù)據(jù)量較小時(shí)，通信開(kāi)銷(xiāo)較低，帶寬利用較好。可以通過(guò)采用Cache技術(shù)來(lái)減少遠(yuǎn)程通信的頻度，減少了通信延遲以及對(duì)共享數(shù)據(jù)的訪(fǎng)問(wèn)沖突。10.1引言消息傳遞通信機(jī)制的主要優(yōu)點(diǎn)硬件較簡(jiǎn)單。通信是顯式的，因此更容易搞清楚何時(shí)發(fā)生通信以及通信開(kāi)銷(xiāo)是多少。顯式通信可以讓編程者重點(diǎn)注意并行計(jì)算的主要通信開(kāi)銷(xiāo)，使之有可能開(kāi)發(fā)出結(jié)構(gòu)更好、性能更高的并行程序。同步很自然地與發(fā)送消息相關(guān)聯(lián)，能減少不當(dāng)?shù)耐綆?lái)錯(cuò)誤的可能性。10.1引言可在支持上面任何一種通信機(jī)制的硬件模型上建立所需的通信模式平臺(tái)。在共享存儲(chǔ)器上支持消息傳遞相對(duì)簡(jiǎn)單。在消息傳遞的硬件上支持共享存儲(chǔ)器就困難得多。所有對(duì)共享存儲(chǔ)器的訪(fǎng)問(wèn)均要求操作系統(tǒng)提供地址轉(zhuǎn)換和存儲(chǔ)保護(hù)功能，即將存儲(chǔ)器訪(fǎng)問(wèn)轉(zhuǎn)換為消息的發(fā)送和接收。10.1引言并行處理面臨著兩個(gè)重要的挑戰(zhàn)程序中的并行性有限相對(duì)較大的通信開(kāi)銷(xiāo)10.1.3并行處理面臨的挑戰(zhàn)系統(tǒng)加速比=10.1引言第一個(gè)挑戰(zhàn)有限的并行性使計(jì)算機(jī)要達(dá)到很高的加速比十分困難。

例10.1

假設(shè)想用100個(gè)處理器達(dá)到80的加速比，求原計(jì)算程序中串行部分最多可占多大的比例？解

Amdahl定律為：由上式可得：并行比例＝0.9975

10.1引言第二個(gè)挑戰(zhàn)：多處理機(jī)中遠(yuǎn)程訪(fǎng)問(wèn)的延遲較大在現(xiàn)有的機(jī)器中，處理器之間的數(shù)據(jù)通信大約需要50～1000個(gè)時(shí)鐘周期。主要取決于：通信機(jī)制、互連網(wǎng)絡(luò)的種類(lèi)和機(jī)器的規(guī)模在幾種不同的共享存儲(chǔ)器并行計(jì)算機(jī)中遠(yuǎn)程訪(fǎng)問(wèn)一個(gè)字的典型延遲

10.1引言機(jī)器通信機(jī)制互連網(wǎng)絡(luò)處理機(jī)最大數(shù)量典型遠(yuǎn)程存儲(chǔ)器訪(fǎng)問(wèn)時(shí)間（ns）SunStarfireserversSMP多總線(xiàn)64500SGIOrigin3000NUMA胖超立方體512500CrayT3ENUMA3維環(huán)網(wǎng)2048300HPVseriesSMP8×8交叉開(kāi)關(guān)321000HPAlphaServerGSSMP開(kāi)關(guān)總線(xiàn)3240010.1引言

例10.2

假設(shè)有一臺(tái)32臺(tái)處理器的多處理機(jī)，對(duì)遠(yuǎn)程存儲(chǔ)器訪(fǎng)問(wèn)時(shí)間為200ns。除了通信以外，假設(shè)所有其它訪(fǎng)問(wèn)均命中局部存儲(chǔ)器。當(dāng)發(fā)出一個(gè)遠(yuǎn)程請(qǐng)求時(shí)，本處理器掛起。處理器的時(shí)鐘頻率為2GHz，如果指令基本的CPI為0.5（設(shè)所有訪(fǎng)存均命中Cache），求在沒(méi)有遠(yuǎn)程訪(fǎng)問(wèn)的情況下和有0.2%的指令需要遠(yuǎn)程訪(fǎng)問(wèn)的情況下，前者比后者快多少?10.1引言解有0.2%遠(yuǎn)程訪(fǎng)問(wèn)的機(jī)器的實(shí)際CPI為：

CPI＝基本CPI＋遠(yuǎn)程訪(fǎng)問(wèn)率×遠(yuǎn)程訪(fǎng)問(wèn)開(kāi)銷(xiāo)＝0.5＋0.2%×遠(yuǎn)程訪(fǎng)問(wèn)開(kāi)銷(xiāo)遠(yuǎn)程訪(fǎng)問(wèn)開(kāi)銷(xiāo)為：

遠(yuǎn)程訪(fǎng)問(wèn)時(shí)間/時(shí)鐘周期時(shí)間＝200ns/0.5ns＝400個(gè)時(shí)鐘周期

∴CPI＝0.5＋0.2%×400＝1.3

因此在沒(méi)有遠(yuǎn)程訪(fǎng)問(wèn)的情況下的機(jī)器速度是有0.2%遠(yuǎn)程訪(fǎng)問(wèn)的機(jī)器速度的1.3/0.5=2.6倍。10.1引言問(wèn)題的解決并行性不足：采用并行性更好的算法遠(yuǎn)程訪(fǎng)問(wèn)延遲的降低：靠系統(tǒng)結(jié)構(gòu)支持和編程技術(shù)在并行處理中，影響性能（負(fù)載平衡、同步和存儲(chǔ)器訪(fǎng)問(wèn)延遲等）的關(guān)鍵因素常依賴(lài)于：應(yīng)用程序的高層特性如數(shù)據(jù)的分配，并行算法的結(jié)構(gòu)以及在空間和時(shí)間上對(duì)數(shù)據(jù)的訪(fǎng)問(wèn)模式等。依據(jù)應(yīng)用特點(diǎn)可把多機(jī)工作負(fù)載大致分成兩類(lèi)：?jiǎn)蝹€(gè)程序在多處理機(jī)上的并行工作負(fù)載多個(gè)程序在多處理機(jī)上的并行工作負(fù)載10.1引言并行程序的計(jì)算／通信比率反映并行程序性能的一個(gè)重要的度量：

計(jì)算與通信的比率計(jì)算／通信比率隨著處理數(shù)據(jù)規(guī)模的增大而增加；隨著處理器數(shù)目的增加而減少。多個(gè)處理器共享一個(gè)存儲(chǔ)器。當(dāng)處理機(jī)規(guī)模較小時(shí)，這種計(jì)算機(jī)十分經(jīng)濟(jì)。近些年，能在一個(gè)單獨(dú)的芯片上實(shí)現(xiàn)2～8個(gè)處理器核。例如：Sun公司2006年T1

8核的多處理器支持對(duì)共享數(shù)據(jù)和私有數(shù)據(jù)的Cache緩存私有數(shù)據(jù)供一個(gè)單獨(dú)的處理器使用，而共享數(shù)據(jù)則是供多個(gè)處理器使用。

共享數(shù)據(jù)進(jìn)入Cache產(chǎn)生了一個(gè)新的問(wèn)題

Cache的一致性問(wèn)題10.2對(duì)稱(chēng)式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)10.2對(duì)稱(chēng)式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)多處理機(jī)的Cache一致性問(wèn)題允許共享數(shù)據(jù)進(jìn)入Cache，就可能出現(xiàn)多個(gè)處理器的Cache中都有同一存儲(chǔ)塊的副本，當(dāng)其中某個(gè)處理器對(duì)其Cache中的數(shù)據(jù)進(jìn)行修改后，就會(huì)使得其Cache中的數(shù)據(jù)與其他Cache中的數(shù)據(jù)不一致。例

由兩個(gè)處理器（A和B）讀寫(xiě)引起的Cache一致性問(wèn)題10.2.1多處理機(jī)Cache一致性10.2對(duì)稱(chēng)式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)存儲(chǔ)器的一致性如果對(duì)某個(gè)數(shù)據(jù)項(xiàng)的任何讀操作均可得到其最新寫(xiě)入的值，則認(rèn)為這個(gè)存儲(chǔ)系統(tǒng)是一致的。存儲(chǔ)系統(tǒng)行為的兩個(gè)不同方面What:

讀操作得到的是什么值When:

什么時(shí)候才能將已寫(xiě)入的值返回給讀操作需要滿(mǎn)足以下條件處理器P對(duì)單元X進(jìn)行一次寫(xiě)之后又對(duì)單元X進(jìn)行讀，讀和寫(xiě)之間沒(méi)有其它處理器對(duì)單元X進(jìn)行寫(xiě)，則P讀到的值總是前面寫(xiě)進(jìn)去的值。10.2對(duì)稱(chēng)式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)處理器P對(duì)單元X進(jìn)行寫(xiě)之后，另一處理器Q對(duì)單元X進(jìn)行讀，讀和寫(xiě)之間無(wú)其它寫(xiě)，則Q讀到的值應(yīng)為P寫(xiě)進(jìn)去的值。對(duì)同一單元的寫(xiě)是串行化的，即任意兩個(gè)處理器對(duì)同一單元的兩次寫(xiě)，從各個(gè)處理器的角度看來(lái)順序都是相同的。(寫(xiě)串行化)在后面的討論中，我們假設(shè)：直到所有的處理器均看到了寫(xiě)的結(jié)果，這個(gè)寫(xiě)操作才算完成；處理器的任何訪(fǎng)存均不能改變寫(xiě)的順序。就是說(shuō)，允許處理器對(duì)讀進(jìn)行重排序，但必須以程序規(guī)定的順序進(jìn)行寫(xiě)。10.2對(duì)稱(chēng)式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)在一致的多處理機(jī)中，Cache提供兩種功能：共享數(shù)據(jù)的遷移減少了對(duì)遠(yuǎn)程共享數(shù)據(jù)的訪(fǎng)問(wèn)延遲，也減少了對(duì)共享存儲(chǔ)器帶寬的要求。共享數(shù)據(jù)的復(fù)制不僅減少了訪(fǎng)問(wèn)共享數(shù)據(jù)的延遲，也減少了訪(fǎng)問(wèn)共享數(shù)據(jù)所產(chǎn)生的沖突。一般情況下，小規(guī)模多處理機(jī)是采用硬件的方法來(lái)實(shí)現(xiàn)Cache的一致性。

10.2.2實(shí)現(xiàn)一致性的基本方案10.2對(duì)稱(chēng)式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)Cache一致性協(xié)議在多個(gè)處理器中用來(lái)維護(hù)一致性的協(xié)議。關(guān)鍵：跟蹤記錄共享數(shù)據(jù)塊的狀態(tài)兩類(lèi)協(xié)議（采用不同的技術(shù)跟蹤共享數(shù)據(jù)的狀態(tài)）目錄式協(xié)議（directory）物理存儲(chǔ)器中數(shù)據(jù)塊的共享狀態(tài)被保存在一個(gè)稱(chēng)為目錄的地方。監(jiān)聽(tīng)式協(xié)議（snooping）每個(gè)Cache除了包含物理存儲(chǔ)器中塊的數(shù)據(jù)拷貝之外，也保存著各個(gè)塊的共享狀態(tài)信息。10.2對(duì)稱(chēng)式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)Cache通常連在共享存儲(chǔ)器的總線(xiàn)上，當(dāng)某個(gè)Cache需要訪(fǎng)問(wèn)存儲(chǔ)器時(shí)，它會(huì)把請(qǐng)求放到總線(xiàn)上廣播出去，其他各個(gè)Cache控制器通過(guò)監(jiān)聽(tīng)總線(xiàn)（它們一直在監(jiān)聽(tīng)）來(lái)判斷它們是否有總線(xiàn)上請(qǐng)求的數(shù)據(jù)塊。如果有，就進(jìn)行相應(yīng)的操作。采用兩種方法來(lái)解決Cache一致性問(wèn)題。

寫(xiě)作廢協(xié)議在處理器對(duì)某個(gè)數(shù)據(jù)項(xiàng)進(jìn)行寫(xiě)入之前，保證它擁有對(duì)該數(shù)據(jù)項(xiàng)的唯一的訪(fǎng)問(wèn)權(quán)。(作廢其它的副本)例監(jiān)聽(tīng)總線(xiàn)、寫(xiě)作廢協(xié)議舉例（采用寫(xiě)直達(dá)法）

初始狀態(tài)：CPUA、CPUB、CPUC都有X的副本。在CPUA要對(duì)X進(jìn)行寫(xiě)入時(shí)，需先作廢CPUB和CPUC中的副本，然后再將p寫(xiě)入CacheA中的副本，同時(shí)用該數(shù)據(jù)更新主存單元X。10.2對(duì)稱(chēng)式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)寫(xiě)更新協(xié)議

當(dāng)一個(gè)處理器對(duì)某數(shù)據(jù)項(xiàng)進(jìn)行寫(xiě)入時(shí)，通過(guò)廣播使其它Cache中所有對(duì)應(yīng)于該數(shù)據(jù)項(xiàng)的副本進(jìn)行更新。例監(jiān)聽(tīng)總線(xiàn)、寫(xiě)更新協(xié)議舉例（采用寫(xiě)直達(dá)法）假設(shè)：3個(gè)Cache都有X的副本。當(dāng)CPUA將數(shù)據(jù)p寫(xiě)入CacheA中的副本時(shí)，將p廣播給所有的Cache，這些Cache用p更新其中的副本。由于這里是采用寫(xiě)直達(dá)法，所以CPUA還要將p寫(xiě)入存儲(chǔ)器中的X。如果采用寫(xiě)回法，則不需要寫(xiě)入存儲(chǔ)器。10.2對(duì)稱(chēng)式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)10.2對(duì)稱(chēng)式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)寫(xiě)更新和寫(xiě)作廢協(xié)議性能上的差別主要來(lái)自：在對(duì)同一個(gè)數(shù)據(jù)進(jìn)行多次寫(xiě)操作而中間無(wú)讀操作的情況下，寫(xiě)更新協(xié)議需進(jìn)行多次寫(xiě)廣播操作，而寫(xiě)作廢協(xié)議只需一次作廢操作。在對(duì)同一Cache塊的多個(gè)字進(jìn)行寫(xiě)操作的情況下，寫(xiě)更新協(xié)議對(duì)于每一個(gè)寫(xiě)操作都要進(jìn)行一次廣播，而寫(xiě)作廢協(xié)議僅在對(duì)該塊的第一次寫(xiě)時(shí)進(jìn)行作廢操作即可。

寫(xiě)作廢是針對(duì)Cache塊進(jìn)行操作，而寫(xiě)更新則是針對(duì)字（或字節(jié)）進(jìn)行?？紤]從一個(gè)處理器A進(jìn)行寫(xiě)操作后到另一個(gè)處理器B能讀到該寫(xiě)入數(shù)據(jù)之間的延遲時(shí)間。寫(xiě)更新協(xié)議的延遲時(shí)間較小。10.2對(duì)稱(chēng)式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)監(jiān)聽(tīng)協(xié)議的基本實(shí)現(xiàn)技術(shù)實(shí)現(xiàn)監(jiān)聽(tīng)協(xié)議的關(guān)鍵有3個(gè)方面處理器之間通過(guò)一個(gè)可以實(shí)現(xiàn)廣播的互連機(jī)制相連。

通常采用的是總線(xiàn)。當(dāng)一個(gè)處理器的Cache響應(yīng)本地CPU的訪(fǎng)問(wèn)時(shí)，如果它涉及到全局操作，其Cache控制器就要在獲得總線(xiàn)的控制權(quán)后，在總線(xiàn)上發(fā)出相應(yīng)的消息。所有處理器都一直在監(jiān)聽(tīng)總線(xiàn)，它們檢測(cè)總線(xiàn)上的地址在它們的Cache中是否有副本。若有，則響應(yīng)該消息，并進(jìn)行相應(yīng)的操作。10.2.3監(jiān)聽(tīng)協(xié)議的實(shí)現(xiàn)10.2對(duì)稱(chēng)式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)寫(xiě)操作的串行化：由總線(xiàn)實(shí)現(xiàn)（獲取總線(xiàn)控制權(quán)的順序性）Cache發(fā)送到總線(xiàn)上的消息主要有以下兩種：RdMiss——讀不命中WtMiss——寫(xiě)不命中需要通過(guò)總線(xiàn)找到相應(yīng)數(shù)據(jù)塊的最新副本，然后調(diào)入本地Cache中。寫(xiě)直達(dá)Cache：因?yàn)樗袑?xiě)入的數(shù)據(jù)都同時(shí)被寫(xiě)回主存，所以從主存中總可以取到其最新值。對(duì)于寫(xiě)回Cache，得到數(shù)據(jù)的最新值會(huì)困難一些，因?yàn)樽钚轮悼赡茉谀硞€(gè)Cache中，也可能在主存中。（后面的討論中，只考慮寫(xiě)回法Cache）

10.2對(duì)稱(chēng)式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)有的監(jiān)聽(tīng)協(xié)議還增設(shè)了一條Invalidate消息，用來(lái)通知其他各處理器作廢其Cache中相應(yīng)的副本。與WtMiss的區(qū)別：Invalidate不引起調(diào)塊Cache的標(biāo)識(shí)（tag）可直接用來(lái)實(shí)現(xiàn)監(jiān)聽(tīng)。作廢一個(gè)塊只需將其有效位置為無(wú)效。給每個(gè)Cache塊增設(shè)一個(gè)共享位為“1”：該塊是被多個(gè)處理器所共享為“0”：僅被某個(gè)處理器所獨(dú)占?jí)K的擁有者：擁有該數(shù)據(jù)塊的唯一副本的處理器。10.2對(duì)稱(chēng)式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)監(jiān)聽(tīng)協(xié)議舉例在每個(gè)結(jié)點(diǎn)內(nèi)嵌入一個(gè)有限狀態(tài)控制器。該控制器根據(jù)來(lái)自處理器或總線(xiàn)的請(qǐng)求以及Cache塊的狀態(tài)，做出相應(yīng)的響應(yīng)。每個(gè)數(shù)據(jù)塊的狀態(tài)取以下3種狀態(tài)中的一種：無(wú)效（簡(jiǎn)稱(chēng)I）：Cache中該塊的內(nèi)容為無(wú)效。共享（簡(jiǎn)稱(chēng)S）：該塊可能處于共享狀態(tài)。在多個(gè)處理器中都有副本。這些副本都相同，且與存儲(chǔ)器中相應(yīng)的塊相同。已修改（簡(jiǎn)稱(chēng)M）：該塊已經(jīng)被修改過(guò)，并且還沒(méi)寫(xiě)入存儲(chǔ)器。

（塊中的內(nèi)容是最新的，系統(tǒng)中唯一的最新副本）下面來(lái)討論在各種情況下監(jiān)聽(tīng)協(xié)議所進(jìn)行的操作。響應(yīng)來(lái)自處理器的請(qǐng)求不發(fā)生替換的情況寫(xiě)作廢協(xié)議中（采用寫(xiě)回法），Cache塊的狀態(tài)轉(zhuǎn)換圖10.2對(duì)稱(chēng)式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)發(fā)生替換的情況寫(xiě)作廢協(xié)議中（采用寫(xiě)回法），Cache塊的狀態(tài)轉(zhuǎn)換圖響應(yīng)來(lái)自總線(xiàn)的請(qǐng)求每個(gè)處理器都在監(jiān)視總線(xiàn)上的消息和地址，當(dāng)發(fā)現(xiàn)有與總線(xiàn)上的地址相匹配的Cache塊時(shí)，就要根據(jù)該塊的狀態(tài)以及總線(xiàn)上的消息，進(jìn)行相應(yīng)的處理。

寫(xiě)作廢協(xié)議中（采用寫(xiě)回法），Cache塊的狀態(tài)轉(zhuǎn)換圖10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)10.3.1目錄協(xié)議的基本思想廣播和監(jiān)聽(tīng)的機(jī)制使得監(jiān)聽(tīng)一致性協(xié)議的可擴(kuò)放性很差。尋找替代監(jiān)聽(tīng)協(xié)議的一致性協(xié)議。（采用目錄協(xié)議）目錄協(xié)議目錄：一種集中的數(shù)據(jù)結(jié)構(gòu)。對(duì)于存儲(chǔ)器中的每一個(gè)可以調(diào)入Cache的數(shù)據(jù)塊，在目錄中設(shè)置一條目錄項(xiàng)，用于記錄該塊的狀態(tài)以及哪些Cache中有副本等相關(guān)信息。

10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)特點(diǎn)：對(duì)于任何一個(gè)數(shù)據(jù)塊，都可以快速地在唯一的一個(gè)位置中找到相關(guān)的信息。這使一致性協(xié)議避免了廣播操作。位向量：記錄哪些Cache中有副本。每一位對(duì)應(yīng)于一個(gè)處理器。長(zhǎng)度與處理器的個(gè)數(shù)成正比。由位向量指定的處理機(jī)的集合稱(chēng)為共享集S。分布式目錄目錄與存儲(chǔ)器一起分布到各結(jié)點(diǎn)中，從而對(duì)于不同目錄內(nèi)容的訪(fǎng)問(wèn)可以在不同的結(jié)點(diǎn)進(jìn)行。

對(duì)每個(gè)結(jié)點(diǎn)增加目錄后的分布式存儲(chǔ)器多處理機(jī)10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)目錄法最簡(jiǎn)單的實(shí)現(xiàn)方案：對(duì)于存儲(chǔ)器中每一塊都在目錄中設(shè)置一項(xiàng)。目錄中的信息量與M×N成正比。其中：M：存儲(chǔ)器中存儲(chǔ)塊的總數(shù)量N：處理器的個(gè)數(shù)由于M=K×N，K是每個(gè)處理機(jī)中存儲(chǔ)塊的數(shù)量，所以如果K保持不變，則目錄中的信息量就與N2成正比。10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)在目錄協(xié)議中，存儲(chǔ)塊的狀態(tài)有3種：未緩沖：該塊尚未被調(diào)入Cache。所有處理器的Cache中都沒(méi)有這個(gè)塊的副本。共享：該塊在一個(gè)或多個(gè)處理機(jī)上有這個(gè)塊的副本，且這些副本與存儲(chǔ)器中的該塊相同。獨(dú)占：僅有一個(gè)處理機(jī)有這個(gè)塊的副本，且該處理機(jī)已經(jīng)對(duì)其進(jìn)行了寫(xiě)操作，所以其內(nèi)容是最新的，而存儲(chǔ)器中該塊的數(shù)據(jù)已過(guò)時(shí)。這個(gè)處理機(jī)稱(chēng)為該塊的擁有者。10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)本地結(jié)點(diǎn)、宿主結(jié)點(diǎn)以及遠(yuǎn)程結(jié)點(diǎn)的關(guān)系本地結(jié)點(diǎn)：發(fā)出訪(fǎng)問(wèn)請(qǐng)求的結(jié)點(diǎn)宿主結(jié)點(diǎn)：包含所訪(fǎng)問(wèn)的存儲(chǔ)單元及其目錄項(xiàng)的結(jié)點(diǎn)遠(yuǎn)程結(jié)點(diǎn)可以和宿主結(jié)點(diǎn)是同一個(gè)結(jié)點(diǎn)，也可以不是同一個(gè)結(jié)點(diǎn)。CPUCache本地結(jié)點(diǎn)APCache遠(yuǎn)程結(jié)點(diǎn)C宿主結(jié)點(diǎn)B(Home)副本目錄存儲(chǔ)器宿主結(jié)點(diǎn)：存放有對(duì)應(yīng)地址的存儲(chǔ)器塊和目錄項(xiàng)的結(jié)點(diǎn)

K10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)在結(jié)點(diǎn)之間發(fā)送的消息本地結(jié)點(diǎn)發(fā)給宿主結(jié)點(diǎn)（目錄）的消息說(shuō)明：括號(hào)中的內(nèi)容表示所帶參數(shù)。

P：發(fā)出請(qǐng)求的處理機(jī)編號(hào)

K：所要訪(fǎng)問(wèn)的地址RdMiss（P，K）處理機(jī)P讀取地址為A的數(shù)據(jù)時(shí)不命中，請(qǐng)求宿主結(jié)點(diǎn)提供數(shù)據(jù)（塊），并要求把P加入共享集。WtMiss（P，K）

處理機(jī)P對(duì)地址A進(jìn)行寫(xiě)入時(shí)不命中，請(qǐng)求宿主結(jié)點(diǎn)提供數(shù)據(jù)，并使P成為所訪(fǎng)問(wèn)數(shù)據(jù)塊的獨(dú)占者。10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)Invalidate（K）請(qǐng)求向所有擁有相應(yīng)數(shù)據(jù)塊副本（包含地址K）的遠(yuǎn)程Cache發(fā)Invalidate消息，作廢這些副本。宿主結(jié)點(diǎn)（目錄）發(fā)送給遠(yuǎn)程結(jié)點(diǎn)的消息Invalidate（K）作廢遠(yuǎn)程Cache中包含地址K的數(shù)據(jù)塊。Fetch（K）從遠(yuǎn)程Cache中取出包含地址K的數(shù)據(jù)塊，并將之送到宿主結(jié)點(diǎn)。把遠(yuǎn)程Cache中那個(gè)塊的狀態(tài)改為“共享”。Fetch&Inv（K）

10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)從遠(yuǎn)程Cache中取出包含地址K的數(shù)據(jù)塊，并將之送到宿主結(jié)點(diǎn)。然后作廢遠(yuǎn)程Cache中的那個(gè)塊。宿主結(jié)點(diǎn)發(fā)送給本地結(jié)點(diǎn)的消息

DReply（D）D表示數(shù)據(jù)內(nèi)容。把從宿主存儲(chǔ)器獲得的數(shù)據(jù)返回給本地Cache。遠(yuǎn)程結(jié)點(diǎn)發(fā)送給宿主結(jié)點(diǎn)的消息

WtBack（K，D）把遠(yuǎn)程Cache中包含地址K的數(shù)據(jù)塊寫(xiě)回到宿主結(jié)點(diǎn)中，該消息是遠(yuǎn)程結(jié)點(diǎn)對(duì)宿主結(jié)點(diǎn)發(fā)來(lái)的“取數(shù)據(jù)”或“取/作廢”消息的響應(yīng)。10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)本地結(jié)點(diǎn)發(fā)送給被替換塊的宿主結(jié)點(diǎn)的消息MdSharer（P，K）用于當(dāng)本地Cache中需要替換一個(gè)包含地址K的塊、且該塊未被修改過(guò)的情況。這個(gè)消息發(fā)給該塊的宿主結(jié)點(diǎn)，請(qǐng)求它將P從共享集中刪除。如果刪除后共享集變?yōu)榭占?，則宿主結(jié)點(diǎn)還要將該塊的狀態(tài)改變?yōu)椤拔淳彺妗保║）。WtBack2（P，K，D）用于當(dāng)本地Cache中需要替換一個(gè)包含地址K的塊、且該塊已被修改過(guò)的情況。這個(gè)消息發(fā)給該塊的宿主結(jié)點(diǎn)，完成兩步操作：①把該塊寫(xiě)回；②進(jìn)行與MdSharer相同的操作。10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)在基于目錄的協(xié)議中，目錄承擔(dān)了一致性協(xié)議操作的主要功能。本地結(jié)點(diǎn)把請(qǐng)求發(fā)給宿主結(jié)點(diǎn)中的目錄，再由目錄控制器有選擇地向遠(yuǎn)程結(jié)點(diǎn)發(fā)出相應(yīng)的消息。發(fā)出的消息會(huì)產(chǎn)生兩種不同類(lèi)型的動(dòng)作：更新目錄狀態(tài)使遠(yuǎn)程結(jié)點(diǎn)完成相應(yīng)的操作10.3.2目錄協(xié)議實(shí)例10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)在基于目錄協(xié)議的系統(tǒng)中，Cache塊的狀態(tài)轉(zhuǎn)換圖。響應(yīng)本地CacheCPU請(qǐng)求

MCPU讀不命中/發(fā)WtBack2，發(fā)RdMissCPU寫(xiě)不命中/發(fā)MdSharer，發(fā)WtMissCPU寫(xiě)命中/發(fā)InvalidateSCPU讀命中CPU寫(xiě)命中CPU寫(xiě)不命中/發(fā)WtBack2，發(fā)WtMissCPU讀命中CPU讀不命中/發(fā)MdSharer，發(fā)RdMissICPU寫(xiě)/發(fā)WtMissCPU讀/發(fā)RdMiss10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)遠(yuǎn)程結(jié)點(diǎn)中Cache塊響應(yīng)來(lái)自宿主結(jié)點(diǎn)的請(qǐng)求的狀態(tài)轉(zhuǎn)換圖

MSIFetch&Inv/發(fā)WtBackFetch/發(fā)WtBackInvalidate10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)目錄的狀態(tài)轉(zhuǎn)換及相應(yīng)的操作如前所述：目錄中存儲(chǔ)器塊的狀態(tài)有3種未緩存共享獨(dú)占位向量記錄擁有其副本的處理器的集合。這個(gè)集合稱(chēng)為共享集合。對(duì)于從本地結(jié)點(diǎn)發(fā)來(lái)的請(qǐng)求，目錄所進(jìn)行的操作包括：10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)向遠(yuǎn)程結(jié)點(diǎn)發(fā)送消息以完成相應(yīng)的操作。這些遠(yuǎn)程結(jié)點(diǎn)由共享集合指出；修改目錄中該塊的狀態(tài)；更新共享集合。目錄可能接收到3種不同的請(qǐng)求讀不命中寫(xiě)不命中數(shù)據(jù)寫(xiě)回（假設(shè)這些操作是原子的）目錄的狀態(tài)轉(zhuǎn)換及相應(yīng)的操作

10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)ERdMiss/SWtMiss/發(fā)Fetch&Inv，UDReply，共享集＝{P}發(fā)DReply，共享集＝{P}RdMiss/發(fā)Fetch，DReply，把P加入共享集WtMiss/發(fā)Invalidate，DReply，共享集＝{P}WtBack/共享集＝{}WtMiss/發(fā)DReply，共享集＝{P}U：未緩存（Uncached）S：共享（Shared）：只讀E：獨(dú)占（Exclusive）：可讀寫(xiě)P：本地處理器10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)當(dāng)一個(gè)塊處于未緩存狀態(tài)時(shí)，對(duì)該塊發(fā)出的請(qǐng)求及處理操作為：RdMiss（讀不命中）將所要訪(fǎng)問(wèn)的存儲(chǔ)器數(shù)據(jù)送往請(qǐng)求方處理機(jī)，且該處理機(jī)成為該塊的唯一共享結(jié)點(diǎn)，本塊的狀態(tài)變成共享。WtMiss（寫(xiě)不命中）將所要訪(fǎng)問(wèn)的存儲(chǔ)器數(shù)據(jù)送往請(qǐng)求方處理機(jī)，該塊的狀態(tài)變成獨(dú)占，表示該塊僅存在唯一的副本。其共享集合僅包含該處理機(jī)，指出該處理機(jī)是其擁有者。10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)當(dāng)一個(gè)塊處于共享狀態(tài)時(shí)，其在存儲(chǔ)器中的數(shù)據(jù)是當(dāng)前最新的，對(duì)該塊發(fā)出的請(qǐng)求及其處理操作為：RdMiss將存儲(chǔ)器數(shù)據(jù)送往請(qǐng)求方處理機(jī)，并將其加入共享集合。WtMiss將數(shù)據(jù)送往請(qǐng)求方處理機(jī)，對(duì)共享集合中所有的處理機(jī)發(fā)送作廢消息，且將共享集合改為僅含有該處理機(jī)，該塊的狀態(tài)變?yōu)楠?dú)占。10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)當(dāng)某塊處于獨(dú)占狀態(tài)時(shí)，該塊的最新值保存在共享集合所指出的唯一處理機(jī)（擁有者）中。有三種可能的請(qǐng)求：RdMiss將“取數(shù)據(jù)”的消息發(fā)往擁有者處理機(jī)，將它所返回給宿主結(jié)點(diǎn)的數(shù)據(jù)寫(xiě)入存儲(chǔ)器，并進(jìn)而把該數(shù)據(jù)送回請(qǐng)求方處理機(jī)，將請(qǐng)求方處理機(jī)加入共享集合。此時(shí)共享集合中仍保留原擁有者處理機(jī)（因?yàn)樗杂幸粋€(gè)可讀的副本）。將該塊的狀態(tài)變?yōu)楣蚕怼?0.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)WtMiss該塊將有一個(gè)新的擁有者。給舊的擁有者處理機(jī)發(fā)送消息，要求它將數(shù)據(jù)塊送回宿主結(jié)點(diǎn)寫(xiě)入存儲(chǔ)器，然后再?gòu)脑摻Y(jié)點(diǎn)送給請(qǐng)求方處理機(jī)。同時(shí)還要把舊擁有者處理機(jī)中的該塊作廢。把請(qǐng)求處理機(jī)加入共享者集合，使之成為新的擁有者。該塊的狀態(tài)仍舊是獨(dú)占。WtBack（寫(xiě)回）當(dāng)一個(gè)塊的擁有者處理機(jī)要從其Cache中把該塊替換出去時(shí)，必須將該塊寫(xiě)回其宿主結(jié)點(diǎn)的10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)

存儲(chǔ)器中，從而使存儲(chǔ)器中相應(yīng)的塊中存放的數(shù)據(jù)是最新的（宿主結(jié)點(diǎn)實(shí)際上成為擁有者）；該塊的狀態(tài)變成未緩沖，其共享集合為空。10.3.3目錄的三種結(jié)構(gòu)不同目錄協(xié)議的主要區(qū)別主要有兩個(gè)所設(shè)置的存儲(chǔ)器塊的狀態(tài)及其個(gè)數(shù)不同目錄的結(jié)構(gòu)目錄協(xié)議分為3類(lèi)全映象目錄、有限映象目錄、鏈?zhǔn)侥夸?0.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)全映象目錄

每一個(gè)目錄項(xiàng)都包含一個(gè)N位（N為處理機(jī)的個(gè)數(shù)）的位向量，其每一位對(duì)應(yīng)于一個(gè)處理機(jī)。舉例

優(yōu)點(diǎn)：處理比較簡(jiǎn)單，速度也比較快。缺點(diǎn)：存儲(chǔ)空間的開(kāi)銷(xiāo)很大。目錄項(xiàng)的數(shù)目與處理機(jī)的個(gè)數(shù)N成正比，而目錄項(xiàng)的大?。ㄎ粩?shù)）也與N成正比，因此目錄所占用的空間與N2成正比?？蓴U(kuò)放性很差。10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)當(dāng)位向量中的值為“1”時(shí)，就表示它所對(duì)應(yīng)的處理機(jī)有該數(shù)據(jù)塊的副本；否則就表示沒(méi)有。在這種情況下，共享集合由位向量中值為“1”的位所對(duì)應(yīng)的處理機(jī)構(gòu)成。P1Cache位向量：（N位）……11010……共享集＝{P1，P2，…，PN-1}P2CacheP3CachePN-1CachePNCache第1位第2位第3位第位(N-1)第位N10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)有限映象目錄提高其可擴(kuò)放性和減少目錄所占用的空間。核心思想：采用位數(shù)固定的目錄項(xiàng)目限制同一數(shù)據(jù)塊在所有Cache中的副本總數(shù)。例如，限定為常數(shù)m。則目錄項(xiàng)中用于表示共享集合所需的二進(jìn)制位數(shù)為：m×log2N。目錄所占用的空間與N×成正比。舉例10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)有限映象目錄（m＝4，N≥8的情況）P1CacheP2CacheP3CacheP4CachePNCache……共享集＝{P1，P3，P4，P7}m項(xiàng)0001001101010111每一項(xiàng)的位數(shù)＝10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)缺點(diǎn)當(dāng)同一數(shù)據(jù)的副本個(gè)數(shù)大于m時(shí)，必須做特殊處理。當(dāng)目錄項(xiàng)中的m個(gè)指針都已經(jīng)全被占滿(mǎn)，而某處理機(jī)又需要新調(diào)入該塊時(shí)，就需要在其m個(gè)指針中選擇一個(gè)，將之驅(qū)逐，以便騰出位置，存放指向新調(diào)入塊的處理機(jī)的指針。鏈?zhǔn)侥夸浻靡粋€(gè)目錄指針鏈表來(lái)表示共享集合。當(dāng)一個(gè)數(shù)據(jù)塊的副本數(shù)增加（或減少）時(shí)，其指針鏈表就跟著變長(zhǎng)（或變短）。由于鏈表的長(zhǎng)度不受限制，因而帶來(lái)了以下優(yōu)點(diǎn)：既不限制副本的個(gè)數(shù)，又保持了可擴(kuò)展性。10.3分布式共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)鏈?zhǔn)侥夸浻袃煞N實(shí)現(xiàn)方法單鏈法當(dāng)Cache中的塊被替換出去時(shí)，需要對(duì)相應(yīng)的鏈表進(jìn)行操作——把相應(yīng)的鏈表元素（假設(shè)是鏈表中的第i個(gè)）刪除。實(shí)現(xiàn)方法有以下兩種：沿著鏈表往下尋找第i個(gè)元素，找到后，修改其前后的鏈接指針，跳過(guò)該元素。找到第i個(gè)元素后，作廢它及其后的所有元素所對(duì)應(yīng)的Cache副本。雙鏈法在替換時(shí)不需要遍歷整個(gè)鏈表。節(jié)省了處理時(shí)間，但其指針增加了一倍，而且一致性協(xié)議也更復(fù)雜了。采用單向鏈法的示意圖P1P2P3P4PN……共享集＝{P2}……∧表頭指針P1P2P3P4PN…………表頭指針共享集＝{P1，P4，P2}∧處理器處理器CacheCache

同步機(jī)制通常是在硬件提供的同步指令的基礎(chǔ)上，通過(guò)用戶(hù)級(jí)軟件例程來(lái)建立的。10.4同步10.4.1基本硬件原語(yǔ)

在多處理機(jī)中實(shí)現(xiàn)同步，所需的主要功能是：一組能以原子操作的方式讀出并修改存儲(chǔ)單元的硬件原語(yǔ)。它們都能以原子操作的方式讀/修改存儲(chǔ)單元，并指出所進(jìn)行的操作是否以原子的方式進(jìn)行。通常情況下，用戶(hù)不直接使用基本的硬件原語(yǔ)，原語(yǔ)主要供系統(tǒng)程序員用來(lái)編制同步庫(kù)函數(shù)。10.4同步典型操作：原子交換（atomicexchange）功能：將一個(gè)存儲(chǔ)單元的值和一個(gè)寄存器的值進(jìn)行交換。建立一個(gè)鎖，鎖值：0：表示開(kāi)的（可用）1：表示已上鎖（不可用）處理器上鎖時(shí)，將對(duì)應(yīng)于該鎖的存儲(chǔ)單元的值與存放在某個(gè)寄存器中的1進(jìn)行交換。如果返回值為0，存儲(chǔ)單元的值此時(shí)已置換為1，防止了別的進(jìn)程競(jìng)爭(zhēng)該鎖。實(shí)現(xiàn)同步的關(guān)鍵：操作的原子性10.4同步測(cè)試并置定（test_and_set）先測(cè)試一個(gè)存儲(chǔ)單元的值，如果符合條件則修改其值。讀取并加1（fetch_and_increment）它返回存儲(chǔ)單元的值并自動(dòng)增加該值。使用指令對(duì)LL(loadlinked或loadlocked)的取指令SC(storeconditional)的特殊存指令10.4同步指令順序執(zhí)行：如果由LL指明的存儲(chǔ)單元的內(nèi)容在SC對(duì)其進(jìn)行寫(xiě)之前已被其它指令改寫(xiě)過(guò)，則第二條指令SC執(zhí)行失??；如果在兩條指令間進(jìn)行切換也會(huì)導(dǎo)致SC執(zhí)行失敗。SC將返回一個(gè)值來(lái)指出該指令操作是否成功：“1”：成功“0”：不成功LL則返回該存儲(chǔ)單元初始值。10.4同步例：實(shí)現(xiàn)對(duì)由R1指出的存儲(chǔ)單元進(jìn)行原子交換操作。

try：OR R3,R4,R0//R4中為交換值。把該值送入R3 LL R2,0（R1）

//把單元0（R1）中的值取到R2

SC R3,0（R1）

//若0（R1）中的值與R3中的值相同，則置R3的值為1，否則置為0

BEQZ R3,try //存失?。≧3的值為0）則轉(zhuǎn)移

MOV R4,R2 //將取的值送往R4

最終R4和由R1指向的單元值進(jìn)行原子交換，在LL和SC之間如有別的處理器插入并修改了存儲(chǔ)單元的值，SC將返回0并存入R3中，從而使這段程序再次執(zhí)行。10.4同步LL/SC機(jī)制的一個(gè)優(yōu)點(diǎn)：用來(lái)構(gòu)造別的同步原語(yǔ)例如：構(gòu)造原子操作fetch_and_increment：

try：

LLR2,0（R1）

DADDIU R2,R2,#1

SC R2,0（R1）

BEQZ R2,try 指令對(duì)的實(shí)現(xiàn)必須跟蹤地址

由LL指令指定一個(gè)寄存器，該寄存器存放著一個(gè)單元地址，這個(gè)寄存器常稱(chēng)為連接寄存器。10.4同步采用多處理機(jī)的一致性機(jī)制來(lái)實(shí)現(xiàn)旋轉(zhuǎn)鎖。旋轉(zhuǎn)鎖處理器環(huán)繞一個(gè)鎖不停地旋轉(zhuǎn)而請(qǐng)求獲得該鎖。適合于這樣的場(chǎng)合：鎖被占用的時(shí)間很少，在獲得鎖后加鎖過(guò)程延遲很小。10.4.2用一致性實(shí)現(xiàn)鎖10.4同步無(wú)Cache一致性機(jī)制在存儲(chǔ)器中保存鎖變量，處理器可以不斷地通過(guò)一個(gè)原子操作請(qǐng)求使用權(quán)。比如：利用原子交換操作，并通過(guò)測(cè)試返回值而知道鎖的使用情況。釋放鎖的時(shí)候，處理器只需簡(jiǎn)單地將鎖置為0。

例：用原子交換操作對(duì)旋轉(zhuǎn)鎖進(jìn)行加鎖，R1中存放的是該旋轉(zhuǎn)鎖的地址。

DADDIU R2,R0,#1lockit：EXCH R2,0（R1）

BNEZ R2,lockit

10.4同步機(jī)器支持Cache一致性將鎖調(diào)入Cache，并通過(guò)一致性機(jī)制使鎖值保持一致。優(yōu)點(diǎn)：可使“環(huán)繞”的進(jìn)程只對(duì)本地Cache中的鎖（副本）進(jìn)行操作，而不用在每次請(qǐng)求占用鎖時(shí)都進(jìn)行一次全局的存儲(chǔ)器訪(fǎng)問(wèn)；可利用訪(fǎng)問(wèn)鎖時(shí)所具有的局部性，即處理器最近使用過(guò)的鎖不久又會(huì)使用。（減少為獲得鎖而花費(fèi)的時(shí)間）10.4同步改進(jìn)旋轉(zhuǎn)鎖（獲得第一條好處）只對(duì)本地Cache中鎖的副本進(jìn)行讀取和檢測(cè)，直到發(fā)現(xiàn)該鎖已經(jīng)被釋放。然后，該程序立即進(jìn)行交換操作，去跟在其它處理器上的進(jìn)程爭(zhēng)用該鎖變量。修改后的旋轉(zhuǎn)鎖程序：

lockit：LD R2,0（R1）

BNEZ R2,lockit DADDIU R2,R0,#1 EXCH R2,0（R1）

BNEZ R2,lockit3個(gè)處理器利用原子交換爭(zhēng)用旋轉(zhuǎn)鎖所進(jìn)行的操作步驟處理器P0處理器P1處理器P2鎖的狀態(tài)總線(xiàn)/目錄操作1占有鎖環(huán)繞測(cè)試是否lock=0環(huán)繞測(cè)試是否lock=0共享無(wú)2將鎖置為0（收到作廢命令）（收到作廢命令）專(zhuān)有（P0）

P0發(fā)出對(duì)鎖變量的作廢消息3Cache不命中

Cache不命中共享總線(xiàn)/目錄收到P2Cache不命中；鎖從P0寫(xiě)回4（因總線(xiàn)/目錄忙而等待）lock=0共享P2Cache不命中被處理5Lock=0執(zhí)行交換，導(dǎo)致Cache不命中共享P1Cache不命中被處理6執(zhí)行交換，導(dǎo)致Cache不命中交換完畢：返回0并置lock=1專(zhuān)有（P2）總線(xiàn)/目錄收到P2Cache不命中；發(fā)作廢消息7交換完畢：返回1進(jìn)入關(guān)鍵程序段專(zhuān)有（P1）總線(xiàn)/目錄處理P1Cache不命中；寫(xiě)回8環(huán)繞測(cè)試是否lock=0無(wú)3個(gè)處理器利用原子交換爭(zhēng)用旋轉(zhuǎn)鎖所進(jìn)行的操作10.4同步LL／SC原語(yǔ)的另一個(gè)優(yōu)點(diǎn)：讀寫(xiě)操作明顯分開(kāi)

LL不產(chǎn)生總線(xiàn)數(shù)據(jù)傳送，這使下面代碼與使用經(jīng)過(guò)優(yōu)化交換的代碼具有相同的特點(diǎn)：

lockit：

LL R2,0（R1）

BNEZ R2,lockit DADDIU R2,R0,#1 SC R2,0（R1）

BEQZ R2,lockit

第一個(gè)分支形成環(huán)繞的循環(huán)體，第二個(gè)分支解決了兩個(gè)處理器同時(shí)看到鎖可用的情況下的爭(zhēng)用問(wèn)題。盡管旋轉(zhuǎn)鎖機(jī)制簡(jiǎn)單并且具有吸引力，但難以將它應(yīng)用于處理器數(shù)量很多的情況。10.4同步

簡(jiǎn)單旋轉(zhuǎn)鎖不能很好地適應(yīng)可縮擴(kuò)性。大規(guī)模多處理機(jī)中，若所有的處理器都同時(shí)爭(zhēng)用同一個(gè)鎖，則會(huì)導(dǎo)致大量的爭(zhēng)用和通信開(kāi)銷(xiāo)。10.4.3同步性能問(wèn)題10.4同步

例10.3

假設(shè)某條總線(xiàn)上有10個(gè)處理器同時(shí)準(zhǔn)備對(duì)同一變量加鎖。如果每個(gè)總線(xiàn)事務(wù)處理（讀不命中或?qū)懖幻校┑臅r(shí)間是100個(gè)時(shí)鐘周期，而且忽略對(duì)已調(diào)入Cache中的鎖進(jìn)行讀寫(xiě)的時(shí)間以及占用該鎖的時(shí)間。（1）假設(shè)該鎖在時(shí)間為0時(shí)被釋放，并且所有處理器都在旋轉(zhuǎn)等待該鎖。問(wèn)：所有10個(gè)處理器都獲得該鎖所需的總線(xiàn)事務(wù)數(shù)目是多少？（2）假設(shè)總線(xiàn)是非常公平的，在處理新請(qǐng)求之前，要先全部處理好已有的請(qǐng)求。并且各處理器的速度相同。問(wèn)：處理10個(gè)請(qǐng)求大概需要多少時(shí)間？10.4同步解當(dāng)i個(gè)處理器爭(zhēng)用鎖的時(shí)候，它們都各自完成以下操作序列，每一個(gè)操作產(chǎn)生一個(gè)總線(xiàn)事務(wù)：訪(fǎng)問(wèn)該鎖的i個(gè)LL指令操作試圖占用該鎖（并上鎖）的i個(gè)SC指令操作1個(gè)釋放鎖的存操作指令因此對(duì)于i個(gè)處理器來(lái)說(shuō)，一個(gè)處理器獲得該鎖所要進(jìn)行的總線(xiàn)事務(wù)的個(gè)數(shù)為2i+1。由此可知，對(duì)n個(gè)處理器，總的總線(xiàn)事務(wù)個(gè)數(shù)為：對(duì)于10個(gè)處理器來(lái)說(shuō)，其總線(xiàn)事務(wù)數(shù)為120個(gè)，需要12000個(gè)時(shí)鐘周期。10.4同步本例中問(wèn)題的根源：鎖的爭(zhēng)用、對(duì)鎖進(jìn)行訪(fǎng)問(wèn)的串行性以及總線(xiàn)訪(fǎng)問(wèn)的延遲。旋轉(zhuǎn)鎖的主要優(yōu)點(diǎn)：總線(xiàn)開(kāi)銷(xiāo)或網(wǎng)絡(luò)開(kāi)銷(xiāo)比較低，而且當(dāng)一個(gè)鎖被同一個(gè)處理器重用時(shí)具有很好的性能。如何用旋轉(zhuǎn)鎖來(lái)實(shí)現(xiàn)一個(gè)常用的高級(jí)同步原語(yǔ)：柵欄柵欄強(qiáng)制所有到達(dá)該柵欄的進(jìn)程進(jìn)行等待，直到全部的進(jìn)程到達(dá)柵欄，然后釋放全部的進(jìn)程，從而形成同步。10.4同步柵欄的典型實(shí)現(xiàn)

用兩個(gè)旋轉(zhuǎn)鎖：用來(lái)保護(hù)一個(gè)計(jì)數(shù)器，它記錄已到達(dá)該柵欄的進(jìn)程數(shù)；用來(lái)封鎖進(jìn)程直至最后一個(gè)進(jìn)程到達(dá)該柵欄。一種典型的實(shí)現(xiàn)其中：lock和unlock提供基本的旋轉(zhuǎn)鎖變量count記錄已到達(dá)柵欄的進(jìn)程數(shù)total規(guī)定了要到達(dá)柵欄的進(jìn)程總數(shù)10.4同步lock（counterlock）； //確保更新的原子性

if（count==0）release=0；//第一個(gè)進(jìn)程則重置release count=count+1； //到達(dá)進(jìn)程數(shù)加1 unlock（counterlock）； //釋放鎖

if（count==total）{ //進(jìn)程全部到達(dá)

count=0； //重置計(jì)數(shù)器

release=1； //釋放進(jìn)程 ｝

else{ //還有進(jìn)程未到達(dá)

spin（release=1）； //等待別的進(jìn)程到達(dá) ｝10.4同步對(duì)counterlock加鎖保證增量操作的原子性。release用來(lái)封鎖進(jìn)程直到最后一個(gè)進(jìn)程到達(dá)柵欄。spin（release=1）使進(jìn)程等待直到全部的進(jìn)程到達(dá)柵欄。實(shí)際情況中會(huì)出現(xiàn)的問(wèn)題柵欄通常是在循環(huán)中使用，從柵欄釋放的進(jìn)程運(yùn)行一段后又會(huì)再次返回柵欄，這樣有可能出現(xiàn)某個(gè)進(jìn)程永遠(yuǎn)離不開(kāi)柵欄的狀況(它停在旋轉(zhuǎn)操作上)。一種解決方法當(dāng)進(jìn)程離開(kāi)柵欄時(shí)進(jìn)行計(jì)數(shù)（和到達(dá)時(shí)一樣），在上次柵欄使用中的所有進(jìn)程離開(kāi)之前，不允許任何進(jìn)程重用并初始化本柵欄。但這會(huì)明顯增加?xùn)艡诘难舆t和競(jìng)爭(zhēng)。10.4同步另一種解決辦法采用sense_reversing柵欄，每個(gè)進(jìn)程均使用一個(gè)私有變量local_sense，該變量初始化為1。sense_reversing柵欄的代碼

優(yōu)缺點(diǎn)：使用安全，但性能比較差。對(duì)于10個(gè)處理器來(lái)說(shuō)，當(dāng)同時(shí)進(jìn)行柵欄操作時(shí)，如果忽略對(duì)Cache的訪(fǎng)問(wèn)時(shí)間以及其它非同步操作所需的時(shí)間，則其總線(xiàn)事務(wù)數(shù)為204個(gè)，如果每個(gè)總線(xiàn)事物需要100個(gè)時(shí)鐘周期，則總共需要20400個(gè)時(shí)鐘周期。10.4同步local_sense=!local_sense；

//local-sense取反

lock（counterlock）；

//確保更新的原子性

count++； //到達(dá)進(jìn)程數(shù)加1 unlock（counterlock）； //釋放鎖

if（count==total）{ //進(jìn)程全部到達(dá)

count=0； //重置計(jì)數(shù)器

release=local_sense； //釋放進(jìn)程 ｝

else{ //還有進(jìn)程未到達(dá)

spin（release==local_sense）；//等待信號(hào) ｝10.4同步當(dāng)競(jìng)爭(zhēng)不激烈且同步操作較少時(shí)，我們主要關(guān)心的是一個(gè)同步原語(yǔ)操作的延遲。即單個(gè)進(jìn)程要花多長(zhǎng)時(shí)間才完成一個(gè)同步操作?；镜男D(zhuǎn)鎖操作可在兩個(gè)總線(xiàn)周期內(nèi)完成：一個(gè)讀鎖一個(gè)寫(xiě)鎖我們可用多種方法改進(jìn)，使它在單個(gè)周期內(nèi)完成操作。同步操作最嚴(yán)重的問(wèn)題：進(jìn)程進(jìn)行同步操作的串行化。它大幅度地增加了完成同步操作所需要的時(shí)間。

線(xiàn)程級(jí)并行性（ThreadLevelParallelism，簡(jiǎn)稱(chēng)TLP）線(xiàn)程是進(jìn)程內(nèi)的一個(gè)相對(duì)獨(dú)立且可獨(dú)立調(diào)度和指派的執(zhí)行單元，它比進(jìn)程要“輕巧”得多。只擁有在運(yùn)行過(guò)程中必不可少的一點(diǎn)資源，如：程序計(jì)數(shù)器、一組寄存器、堆棧等。線(xiàn)程切換時(shí)，只需保存和設(shè)置少量寄存器的內(nèi)容，開(kāi)銷(xiāo)很小。線(xiàn)程切換只需要幾個(gè)時(shí)鐘周期。進(jìn)程的切換一般需要成百上千個(gè)處理器時(shí)鐘周期。10.5同時(shí)多進(jìn)程10.5同時(shí)多進(jìn)程實(shí)現(xiàn)多線(xiàn)程有兩種主要的方法：細(xì)粒度（fine-grained）多線(xiàn)程在每條指令之間都能進(jìn)行線(xiàn)程的切換，從而使得多個(gè)線(xiàn)程可以交替執(zhí)行。通常以時(shí)間片輪轉(zhuǎn)的方法實(shí)現(xiàn)這樣的交替執(zhí)行，在輪轉(zhuǎn)的過(guò)程中跳過(guò)當(dāng)時(shí)處于停頓的線(xiàn)程。CPU必須在每個(gè)時(shí)鐘周期都能進(jìn)行線(xiàn)程的切換。主要優(yōu)點(diǎn)：既能夠隱藏由長(zhǎng)時(shí)間停頓引起的吞吐率的損失，又能夠隱藏由短時(shí)間停頓帶來(lái)的損失。主要缺點(diǎn)：減慢了單個(gè)線(xiàn)程的執(zhí)行10.5同時(shí)多進(jìn)程粗粒度（coarse-grained）多線(xiàn)程

線(xiàn)程之間的切換只發(fā)生在時(shí)間較長(zhǎng)的停頓出現(xiàn)時(shí)。例如：第二級(jí)Cache不命中。減少了切換次數(shù)，也不太會(huì)降低單個(gè)線(xiàn)程的執(zhí)行速度。缺點(diǎn)：減少吞吐率損失的能力有限，特別是對(duì)于較短的停頓來(lái)說(shuō)更是如此。原因：由粗粒度多線(xiàn)程的流水線(xiàn)建立時(shí)間的開(kāi)銷(xiāo)造成的。由于實(shí)現(xiàn)粗粒度多線(xiàn)程的CPU只執(zhí)行單個(gè)線(xiàn)程的指令，因此當(dāng)發(fā)生停頓時(shí)，流水線(xiàn)必須排空或暫停。停頓后切換的新線(xiàn)程也有個(gè)填滿(mǎn)流水線(xiàn)的過(guò)程，填滿(mǎn)后才能不斷地流出指令執(zhí)行結(jié)果。10.5同時(shí)多進(jìn)程同時(shí)多線(xiàn)程技術(shù)SimultaneousMultiThreading，簡(jiǎn)稱(chēng)SMT一種在多流出、動(dòng)態(tài)調(diào)度的處理器上同時(shí)開(kāi)發(fā)線(xiàn)程級(jí)并行和指令級(jí)并行的技術(shù)。提出SMT的主要原因現(xiàn)代多流出處理器通常含有多個(gè)并行的功能單元，而單個(gè)線(xiàn)程不能有效地利用這些功能單元。通過(guò)寄存器重命名和動(dòng)態(tài)調(diào)度機(jī)制，來(lái)自各個(gè)獨(dú)立線(xiàn)程的多條指令可以同時(shí)流出，而不用考慮它們之間的相互依賴(lài)關(guān)系，其相互依賴(lài)關(guān)系將通過(guò)動(dòng)態(tài)調(diào)度機(jī)制得以解決。10.5.1將線(xiàn)程級(jí)并行轉(zhuǎn)換為指令級(jí)并行10.5同時(shí)多進(jìn)程一個(gè)超標(biāo)量處理器在4種情況下的資源使用情況：

不支持多線(xiàn)程技術(shù)的超標(biāo)量處理器由于缺乏足夠的指令級(jí)并行而限制了流出槽的利用率。支持粗粒度多線(xiàn)程的超標(biāo)量處理器通過(guò)線(xiàn)程的切換部分隱藏了長(zhǎng)時(shí)間停頓帶來(lái)的開(kāi)銷(xiāo)，提高了硬件資源的利用率。只有發(fā)生停頓時(shí)才進(jìn)行線(xiàn)程切換，而且新線(xiàn)程還有個(gè)啟動(dòng)期，所以仍然可能有一些完全空閑的時(shí)鐘周期。10.5同時(shí)多進(jìn)程支持細(xì)粒度多線(xiàn)程的超標(biāo)量處理器線(xiàn)程的交替執(zhí)行消除了完全空閑的時(shí)鐘周期。由于在每個(gè)時(shí)鐘周期內(nèi)只能流出一個(gè)線(xiàn)程的指令，ILP的限制導(dǎo)致了一些時(shí)鐘周期中依然存在不少空閑流出槽。支持同時(shí)多線(xiàn)程的超標(biāo)量處理器在同一個(gè)時(shí)鐘周期中可以讓多個(gè)線(xiàn)程使用流出槽。理想情況下，流出槽的利用率只受限于多個(gè)線(xiàn)程對(duì)資源的需求和可用資源間的不平衡。10.5同時(shí)多進(jìn)程不支持多線(xiàn)程的情況10.5同時(shí)多進(jìn)程多線(xiàn)程的3種情況

10.5同時(shí)多進(jìn)程開(kāi)發(fā)的基礎(chǔ):

動(dòng)態(tài)調(diào)度的處理器已經(jīng)具備了開(kāi)發(fā)線(xiàn)程級(jí)并行所需的許多硬件設(shè)置。動(dòng)態(tài)調(diào)度超標(biāo)量處理器有一組很多的虛擬寄存器，可以用作各獨(dú)立線(xiàn)程的寄存器組。由于寄存器重命名機(jī)制給各寄存器提供了唯一的標(biāo)識(shí)，多個(gè)線(xiàn)程的指令可以在數(shù)據(jù)路徑上混合執(zhí)行，而不會(huì)導(dǎo)致各線(xiàn)程之間源操作數(shù)和目的操作數(shù)的混亂。多線(xiàn)程可以在一個(gè)亂序執(zhí)行的處理器的基礎(chǔ)上實(shí)現(xiàn)，只要為每個(gè)線(xiàn)程設(shè)置重命名表、分別設(shè)置各自的程序計(jì)數(shù)器、并為多個(gè)線(xiàn)程提供指令確認(rèn)的能力。10.5同時(shí)多進(jìn)程同時(shí)多線(xiàn)程只有在細(xì)粒度的實(shí)現(xiàn)方式下才有意義細(xì)粒度調(diào)度方式會(huì)對(duì)單個(gè)線(xiàn)程的性能產(chǎn)生不利的影響可以通過(guò)采用優(yōu)先線(xiàn)程的方法來(lái)盡可能地減少。這種方法既能保持多線(xiàn)程在性能上的優(yōu)勢(shì)，又對(duì)單個(gè)線(xiàn)程的性能影響比較少。多個(gè)線(xiàn)程的混合執(zhí)行不可避免地會(huì)影響單個(gè)線(xiàn)程的執(zhí)行速度10.5.2同時(shí)多線(xiàn)程處理器的設(shè)計(jì)10.5同時(shí)多進(jìn)程為提高單個(gè)線(xiàn)程的性能，應(yīng)該為指定的優(yōu)先線(xiàn)程盡可能多地向前取指（或許在分支指令的兩條路徑上都要向前取指）；在分支預(yù)測(cè)失敗和預(yù)取緩沖器不命中的情況下清空取指單元。但是這樣限制了其他線(xiàn)程可用來(lái)調(diào)度的指令條數(shù)，從而降低了吞吐率。所有的多線(xiàn)程處理器都必須在這里尋求一種折衷方案。10.5同時(shí)多進(jìn)程只要一有可能，處理器就運(yùn)行指定的優(yōu)先線(xiàn)程。從取指階段開(kāi)始就優(yōu)先處理優(yōu)先線(xiàn)程：只要優(yōu)先線(xiàn)程的指令預(yù)取緩沖區(qū)未滿(mǎn)，就為它們優(yōu)先取指。只有當(dāng)優(yōu)先線(xiàn)程的緩沖區(qū)填滿(mǎn)以后才為其它線(xiàn)程預(yù)取指令。當(dāng)有兩個(gè)優(yōu)先線(xiàn)程時(shí)，意味著需要并發(fā)預(yù)取兩條指令流，這給取指部件和指令Cache都增添了復(fù)雜度。指令流出單元也要優(yōu)先考慮指定的優(yōu)先線(xiàn)程，只有當(dāng)優(yōu)先線(xiàn)程停頓不能流出的時(shí)候才考慮其它線(xiàn)程。10.5同時(shí)多進(jìn)程設(shè)計(jì)同時(shí)多線(xiàn)程處理器時(shí)面臨的其它主要問(wèn)題：需要設(shè)置更大的寄存器組，用來(lái)保存多個(gè)線(xiàn)程的現(xiàn)場(chǎng)。不能影響時(shí)鐘周期，特別是在關(guān)鍵路徑上如指令流出和指令完成：指令流出時(shí)，有更多的候選指令需要考慮；指令完成時(shí)，選擇提交哪些指令可能會(huì)比較困難。需要保證由于并發(fā)執(zhí)行多個(gè)線(xiàn)程帶來(lái)的Cache沖突和TLB沖突不會(huì)導(dǎo)致明顯的性能下降。

10.5同時(shí)多進(jìn)程需要重視的兩個(gè)實(shí)際情況：在許多情況下，多線(xiàn)程所導(dǎo)致的潛在額外性能開(kāi)銷(xiāo)是很小的，簡(jiǎn)單的線(xiàn)程切換選擇算法就足夠好了；目前的超標(biāo)量處理器的效率是比較低的，還有很大的改進(jìn)余地，即使增加一些開(kāi)銷(xiāo)也是值得的。在超標(biāo)量處理器上增添8個(gè)線(xiàn)程的同時(shí)多線(xiàn)程能力時(shí)獲得的性能提高（單位：指令數(shù)/每拍）

10.5.3同時(shí)多線(xiàn)程處理器的性能SMT與基本的超標(biāo)量處理器在幾個(gè)主要指標(biāo)上的對(duì)比10.5同時(shí)多進(jìn)程兩個(gè)特點(diǎn)超標(biāo)量處理器本身功能十分強(qiáng)大，它具有很大的一級(jí)Cache、二級(jí)Cache以及大量的功能單元。僅僅采用指令級(jí)并行，不可能利用全部的硬件性能，因此超標(biāo)量處理器的設(shè)計(jì)者不可能不考慮使用諸如同時(shí)多線(xiàn)程這樣的技術(shù)來(lái)開(kāi)發(fā)線(xiàn)程級(jí)并行。同時(shí)多線(xiàn)程的能力也很強(qiáng)大，可以支持8個(gè)線(xiàn)程，并為兩個(gè)線(xiàn)程同步取指。將超標(biāo)量和同時(shí)多線(xiàn)程結(jié)合起來(lái)，在指令級(jí)并行基礎(chǔ)上進(jìn)一步開(kāi)發(fā)線(xiàn)程級(jí)并行，可以獲得顯著的性能提高。目前流行的高性能并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)通?？梢苑殖梢韵?類(lèi)：并行向量處理機(jī)（PVP）對(duì)稱(chēng)式共享存儲(chǔ)器多處理機(jī)（SMP）分布式共享存儲(chǔ)器多處理機(jī)（DSM）大規(guī)模并行處理機(jī)（MPP）機(jī)群計(jì)算機(jī)（Cluster）10.6大規(guī)模并行處理機(jī)MPP10.6.1并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)10.6大規(guī)模并行處理機(jī)MPP并行向量處理機(jī)CrayC-90和CrayT-90是這類(lèi)機(jī)器的代表。PVP系統(tǒng)一般由若干臺(tái)高性能向量處理機(jī)（VP）構(gòu)成。這些向量處理機(jī)是專(zhuān)門(mén)設(shè)計(jì)和定制的，擁有很高的向量處理性能。PVP中經(jīng)常采用專(zhuān)門(mén)設(shè)計(jì)的高帶寬的交叉開(kāi)關(guān)網(wǎng)絡(luò)，把各VP與共享存儲(chǔ)器模塊SM連接起來(lái)。這樣的機(jī)器通常不使用Cache，而是使用大量的向量寄存器和指令緩沖器。對(duì)稱(chēng)式共享存儲(chǔ)器多處理機(jī)和分布式共享存儲(chǔ)器多處理機(jī)10.6大規(guī)模并行處理機(jī)MPP大規(guī)模并行處理機(jī)IntelParagon和IBMSP2是這類(lèi)機(jī)器的代表。MPP往往是超大規(guī)模的計(jì)算機(jī)系統(tǒng)。具有以下特點(diǎn)：處理結(jié)點(diǎn)使用商用微處理器，而且每個(gè)結(jié)點(diǎn)可以有多個(gè)微處理器；具有較好的可擴(kuò)放性，能擴(kuò)展成具有成百上千個(gè)處理器；系統(tǒng)中采用分布非共享的存儲(chǔ)器，各結(jié)點(diǎn)有自己的地址空間；采用專(zhuān)門(mén)設(shè)計(jì)和定制的高性能互連網(wǎng)絡(luò)；采用消息傳遞的通訊機(jī)制。10.6大規(guī)模并行處理機(jī)MPP機(jī)群計(jì)算機(jī)一種價(jià)格低廉、易于構(gòu)建、可擴(kuò)放性極強(qiáng)的并行計(jì)算機(jī)系統(tǒng)。它由多臺(tái)同構(gòu)或異構(gòu)的獨(dú)立計(jì)算機(jī)通過(guò)高性能網(wǎng)絡(luò)或局域網(wǎng)互連在一起，協(xié)同完成特定的并行計(jì)算任務(wù)。BerkeleyNOW和SP2是這類(lèi)機(jī)器的代表。機(jī)群的主要特點(diǎn)每個(gè)結(jié)點(diǎn)都是一臺(tái)完整的計(jì)算機(jī)，擁有本地磁盤(pán)和操作系統(tǒng)，可以作為一個(gè)單獨(dú)的計(jì)算資源供用戶(hù)使用。機(jī)群的各個(gè)結(jié)點(diǎn)一般通過(guò)商品化網(wǎng)絡(luò)連接在一起；網(wǎng)絡(luò)接口以松散耦合的方式連接到結(jié)點(diǎn)的I/O總線(xiàn)。

屬性PVPSMPMPPDSM機(jī)群結(jié)構(gòu)類(lèi)型MIMDMIMDMIMDMIMDMIMD處理器類(lèi)型專(zhuān)用定制商用商用商用商用互連網(wǎng)絡(luò)定制交叉開(kāi)關(guān)總線(xiàn)、交叉開(kāi)關(guān)定制網(wǎng)絡(luò)定制網(wǎng)絡(luò)商用網(wǎng)絡(luò)（以太網(wǎng)、ATM）通信機(jī)制共享變量共享變量消息傳遞共享變量消息傳遞地址空間單地址空間單地址空間多地址空間單地址空間多地址空間系統(tǒng)存儲(chǔ)器集中共享集中共享分布非共享分布共享分布非共享訪(fǎng)存模型UMAUMANORMANUMANORMA代表機(jī)器CrayC-90，CrayT-90，NECSX4，銀河1號(hào)IBMR50，SGIPowerChallenge，DECAlpha服務(wù)器8400，曙光1號(hào)IntelParagon，IBMSP2，IntelTFLOPS，曙光-1000/2000StanfordDASH，CrayT3D，SGI/CrayOrigin2000BerkeleyNOW，AlphaFarm，DigitalTrucluster5類(lèi)機(jī)器特征比較10.6大規(guī)模并行處理機(jī)MPPMPP的出現(xiàn)和發(fā)展從20世紀(jì)80年代末開(kāi)始，MPP系統(tǒng)逐漸地顯示出代替和超越向量計(jì)算多處理機(jī)系統(tǒng)的趨勢(shì)。早期的MPP：IntelParagon(1992年)、KSR1.CrayT3D(1993年)、IBMSP2(1994年)等。（分布存儲(chǔ)的MIMD計(jì)算機(jī)）MPP的高端機(jī)器：1996年Intel公司的ASCIRed1997年SGICray公司的T3E900（萬(wàn)億次浮點(diǎn)運(yùn)算的高性能并行計(jì)算機(jī)）10.6.2大規(guī)模并行處理機(jī)MPP10.6大規(guī)模并行處理機(jī)MPP在這個(gè)時(shí)期，消息傳遞的大規(guī)模并行處理系統(tǒng)得到了迅速發(fā)展。從90年代后期開(kāi)始，基于消息傳遞的MPP系統(tǒng)慢慢地從主流的并行處理市場(chǎng)退出。隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，機(jī)群系統(tǒng)和MPP系統(tǒng)的界限越來(lái)越模糊。90年代后期以來(lái)高性能計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)發(fā)展的一個(gè)趨勢(shì)，新涌現(xiàn)的高性能計(jì)算機(jī)系統(tǒng)大多數(shù)都是由可擴(kuò)放的高速互連網(wǎng)絡(luò)連接的基于RISC微處理器的對(duì)稱(chēng)多處理機(jī)機(jī)群。機(jī)群系統(tǒng)已經(jīng)成了構(gòu)建超大規(guī)模并行計(jì)算機(jī)系統(tǒng)的主要模式，MPP則是在慢慢地退居二三線(xiàn)了。

10.6大規(guī)模并行處理機(jī)MPPMPP系統(tǒng)概述MPP結(jié)構(gòu)的一個(gè)重要特性：可擴(kuò)放性處理器的數(shù)量可擴(kuò)放至數(shù)千個(gè)處理器。主存、I/O能力和帶寬也能隨處理器數(shù)量的增長(zhǎng)而成比例地增長(zhǎng)。MPP主要采用了以下技術(shù)來(lái)提高系統(tǒng)的可擴(kuò)放性。使用物理上分布的主存體系結(jié)構(gòu)，使分布式主存的總?cè)萘亢涂値捘茈S處理結(jié)點(diǎn)數(shù)量的增加而增加。處理能力、主存與I/O能力平衡發(fā)展。計(jì)算能力與并行性平衡發(fā)展。MPP模型Intel/SandiaASCIOptionRedIBMSP2SGI/CrayOrigin2000典型配置9072個(gè)處理器1.8Tflop/s（NSL）400個(gè)處理器100Gflop/s（MHPCC）128個(gè)處理器51Gflop/s（NCSA）推出日期1996年12月1994年9月1996年10月CPU類(lèi)型200MHz，200Mflop/sPentiumPro67MHz，267Mflop/sPOWER2200MHz，400Mflop/sMIPSR10000節(jié)點(diǎn)結(jié)構(gòu)數(shù)據(jù)存儲(chǔ)2個(gè)處理器，32～256MB主存，共享磁盤(pán)1個(gè)處理器，64MB～2GB本地主存，1GB～14.5G本地磁盤(pán)2個(gè)處理器，64MB～256MB分布共享主存和共享磁盤(pán)互連網(wǎng)絡(luò)分離二維網(wǎng)孔多級(jí)網(wǎng)絡(luò)胖超立方體網(wǎng)格訪(fǎng)存模型NORMANORMACC-NUMA節(jié)點(diǎn)OS輕量級(jí)內(nèi)核（LWK）完全AIX（IBMUNIX）微內(nèi)核CellularIRIX編程語(yǔ)言基于PUMAPortals的MPIMPI和PVMPowerC,PowerFortran其他編程模型NX,PVM,HPFHPF,LindaMPI,PVM3種大型MPP的特點(diǎn)（分別代表構(gòu)造大型系統(tǒng)的不同方法）

一些典型的MPP系統(tǒng)的特性

結(jié)構(gòu)特性IBMSP2CrayT3DCrayT3EIntelParagonIntel/SandiaOptionRed典型配置400個(gè)節(jié)點(diǎn)100Gflop/s512個(gè)節(jié)點(diǎn)153Gflop/s512個(gè)節(jié)點(diǎn)1.2Tflop/s400個(gè)節(jié)點(diǎn)40Gflop/s4536個(gè)節(jié)點(diǎn)1.8Tflop/s推出日期1994年1993年1996年1992年1996年CPU類(lèi)型67MHz267Mflop/sPOWER2150MHz150Mflop/sAlpha21064300MHz600Mflop/sAlpha2116450MHz100Mflop/sInteli860200MHz200Mflop/sPentiumPro節(jié)點(diǎn)結(jié)構(gòu)數(shù)據(jù)存儲(chǔ)1CPU64MB～2GB本地存儲(chǔ)器，1～4.5GB本地磁盤(pán)2CPU64MB主存，50GB共享磁盤(pán)4～8CPU256MB～16GBDSM主存，共享磁盤(pán)1～2CPU16～128MB本地存儲(chǔ)器，40GB共享磁盤(pán)2CPU32～256MB本地存儲(chǔ)器，共享磁盤(pán)互連網(wǎng)絡(luò)多級(jí)網(wǎng)絡(luò)三維環(huán)繞三維環(huán)繞二維網(wǎng)孔分離二維網(wǎng)孔訪(fǎng)存模型NORMANUMANCC—NUMANORMANORMA10.6大規(guī)模并行處理機(jī)MPP結(jié)構(gòu)特性IBMSP2CrayT3DCrayT3EIntelParagonIntel/SandiaOptionRed結(jié)構(gòu)特性IBMSP2CrayT3DCrayT3EIntelParagonIntel/SandiaOptionRed節(jié)點(diǎn)OS完全AIX（IBMUNIX）微內(nèi)核基于Chorus的微內(nèi)核微內(nèi)核輕量級(jí)內(nèi)核（LWK）編程模型消息傳遞共享變量、消息傳遞、PVM共享變量、消息傳遞、PVM消息傳遞基于PUMAPortals消息傳遞編程語(yǔ)言MPI、PVM、HPF、LindaMPI、HPFMPI、HPFNX、MPI、PVMNX、PVM、HPF點(diǎn)到點(diǎn)通信延遲40μs2μsN/A30μs10μs點(diǎn)到點(diǎn)帶寬35MB/s150MB/s480MB/s175MB/s380MB/sT1的結(jié)構(gòu)SUN公司于2005年作為服務(wù)器處理器發(fā)布的多核多處理器。同時(shí)采用了多線(xiàn)程和多核技術(shù)，全面提高吞吐率。每個(gè)T1處理器中有8個(gè)處理器核，每個(gè)核最多支持4個(gè)線(xiàn)程。每個(gè)處理器核中都有一條6段的單流出流水線(xiàn)。

（類(lèi)似于前面介紹的5段流水線(xiàn)，只是增加了一個(gè)段，用于進(jìn)行線(xiàn)程切換。)10.7多處理機(jī)實(shí)例1：T110.7多處理機(jī)實(shí)例1：T1采用細(xì)粒度多線(xiàn)程，在每個(gè)時(shí)鐘周期都可以切換到新的線(xiàn)程，而且在調(diào)度時(shí)可以跳過(guò)那些因流水線(xiàn)延遲或Cache不命中而處于等待狀態(tài)的線(xiàn)程。T1處理器只有在所有其4個(gè)線(xiàn)程都處于等待或停頓時(shí)才會(huì)出現(xiàn)空閑狀態(tài)。load和分支指令會(huì)導(dǎo)致3個(gè)時(shí)鐘周期的延遲，不過(guò)它們都可以通過(guò)執(zhí)行其他線(xiàn)程而被隱藏。T1的組成結(jié)構(gòu)有8個(gè)核，每個(gè)核中都帶有一個(gè)第一級(jí)Cache。8個(gè)核通過(guò)一個(gè)交叉開(kāi)關(guān)與4個(gè)第二級(jí)（L2）Cache相連。

用目錄表法來(lái)實(shí)現(xiàn)Cache內(nèi)容的一致性。10.7多處理機(jī)實(shí)例1：T1T1的主要特性特征SunT1多處理器和多線(xiàn)程支持每芯片8個(gè)核，每核4個(gè)線(xiàn)程。細(xì)粒度線(xiàn)程調(diào)度。8個(gè)核共享一個(gè)浮點(diǎn)運(yùn)算部件。支持片內(nèi)多處理器。流水線(xiàn)結(jié)構(gòu)簡(jiǎn)單的按序6段流水線(xiàn)，load和分支的延遲為3個(gè)時(shí)鐘周期。一級(jí)Cache16KB指令Cache，8KB數(shù)據(jù)Cache。64字節(jié)塊大小。在無(wú)競(jìng)爭(zhēng)的情況下，L1不命中的開(kāi)銷(xiāo)是23個(gè)時(shí)鐘周期。二級(jí)Cache4個(gè)獨(dú)立的二級(jí)Cache，每個(gè)750KB且和存儲(chǔ)體相連。64字節(jié)塊大小。在無(wú)競(jìng)爭(zhēng)的情況下，L2不命中的開(kāi)銷(xiāo)是110個(gè)時(shí)鐘周期。初始版本90nm工藝，最高時(shí)鐘頻率1.2GHz，電源功率79W，300M個(gè)晶體管，圓片面積大小379mm2。T1的性能基準(zhǔn)測(cè)試程序：TPC-C、SPECJBB、SPECWeb99在以下不同情況下L2Cache的不命中率容量分別為：1.5MB、3MB和6MB塊大小分別：32B和64B10.7多處理機(jī)實(shí)例1：T1在不同容量和塊大小的情況下（與上圖同），L2Cache的不命中延遲10.7多處理機(jī)實(shí)例1：T1T1的每線(xiàn)程CPI、每核CPI以及有效的IPC（每個(gè)時(shí)鐘周期完成的指令數(shù)）

基準(zhǔn)測(cè)試程序每線(xiàn)程CPI每核CPI8個(gè)核的有效CPI8個(gè)核的有效IPCTPC-C7.21.80.2254.4SPECJBB5.61.400.1755.7SPECWeb996.61.650.2064.8有效IPC=8÷每核CPI

10.7多處理機(jī)實(shí)例1：T14種多核處理器的性能對(duì)比特征SUNT1AMDOpteronIntelPentiumDIBMPower5核8222每個(gè)核每時(shí)鐘周期發(fā)射的指令1334多線(xiàn)程Fine-grainedNoSMTSMTCache16/864/6412kuops/1664/32一級(jí)I/DinKBpercore3MBshared1MB/core1MB/core二級(jí)：1.9MBshared二級(jí)Percore/shared三級(jí)：36MB10.7多處理機(jī)實(shí)例1：T1特征SUNT1AMDOpteronIntelPentiumDIBMPower5三級(jí)（off-chip）存儲(chǔ)器帶寬峰值（DDR2DRAMS）34.4GB/s8.6GB/s4.3GB/s17.2GB/sMIPS峰值9600720096007600FLOPS12004800(w.SSE)6400(w.SS