第10章多處理機(jī)

張晨曦編著華中科技大學(xué)計(jì)算機(jī)學(xué)院2013年5月10.1引言10.2對(duì)稱式共享存儲(chǔ)器體系結(jié)構(gòu)10.3分布式共享存儲(chǔ)器體系結(jié)構(gòu)10.4同步10.5同時(shí)多線程10.6多處理機(jī)實(shí)例第10章多處理機(jī)10.1.1并行計(jì)算機(jī)體系結(jié)構(gòu)的分類1.按照Flynn分類法，可把計(jì)算機(jī)分成單指令流單數(shù)據(jù)流(SISD)單指令流多數(shù)據(jù)流(SIMD)多指令流單數(shù)據(jù)流(MISD)多指令流多數(shù)據(jù)流(MIMD)10.1引言第十章多處理機(jī)2.MIMD已成為通用多處理機(jī)體系結(jié)構(gòu)的選擇，原因：(1)MIMD具有靈活性；(2)MIMD可以充分利用商品化微處理器在性能價(jià)格比方面的優(yōu)勢(shì)。3.根據(jù)系統(tǒng)中處理器個(gè)數(shù)的多少，可把現(xiàn)有的MIMD 機(jī)器分為兩類

(每一類代表了一種存儲(chǔ)器的結(jié)構(gòu)和互連策略)(1)集中式共享存儲(chǔ)器結(jié)構(gòu)這類機(jī)器有時(shí)被稱為SMP機(jī)器(Symmetricshared-memoryMultiProcessor)UMA機(jī)器(UniformMemoryAccess)10.1引言集中(對(duì)稱)共享存儲(chǔ)器計(jì)算機(jī)(2)分布式存儲(chǔ)器結(jié)構(gòu)每個(gè)結(jié)點(diǎn)包含：處理器存儲(chǔ)器I／O在許多情況下，分布式存儲(chǔ)器結(jié)構(gòu)優(yōu)于集中式共享存儲(chǔ)器結(jié)構(gòu)10.1引言分布式存儲(chǔ)器計(jì)算機(jī)分布式存儲(chǔ)器結(jié)構(gòu)的優(yōu)點(diǎn)主要缺點(diǎn)10.1引言如果大多數(shù)的訪問是針對(duì)本結(jié)點(diǎn)的局部存儲(chǔ)器，則可降低對(duì)存儲(chǔ)器和互連網(wǎng)絡(luò)的帶寬要求；局部存儲(chǔ)器的訪問延遲低。處理器之間的通信較為復(fù)雜，且各處理器之間的

訪問延遲較大。需要高帶寬的互連。簇：超結(jié)點(diǎn)10.1.2通信模型和存儲(chǔ)器的結(jié)構(gòu)模型1.地址空間的組織方案(兩種)(1)物理上分離的多個(gè)存儲(chǔ)器作為一個(gè)邏輯上共享的存儲(chǔ)空間進(jìn)行編址。這類機(jī)器的結(jié)構(gòu)被稱為:10.1引言分布式共享存儲(chǔ)器結(jié)構(gòu)(DSM:DistributedShared-Memory)可縮放共享存儲(chǔ)器結(jié)構(gòu)(SSM:ScalableShared-Memory)NUMA機(jī)器

(NUMA:Non-UniformMemoryAccess)(2)整個(gè)地址空間由多個(gè)獨(dú)立的地址空間構(gòu)成，它們?cè)谶壿嬌弦彩仟?dú)立的，遠(yuǎn)程的處理器不能對(duì)其直接尋址。每一個(gè)處理器-存儲(chǔ)器模塊實(shí)際上是一個(gè)單獨(dú)的計(jì)算機(jī)，這種機(jī)器也稱為多(地址空間)計(jì)算機(jī)。10.1引言共享地址空間的機(jī)器利用Load和Store指令中的地址隱含地進(jìn)行數(shù)據(jù)通訊。多個(gè)地址空間的機(jī)器通過處理器間顯式地傳遞消息完成。消息傳遞機(jī)器2.兩種通信模型10.1引言消息傳遞機(jī)器根據(jù)簡(jiǎn)單的網(wǎng)絡(luò)協(xié)議，通過傳遞消息來請(qǐng)求某些服務(wù)或傳輸數(shù)據(jù)，從而完成通信。例如：一個(gè)處理器要對(duì)遠(yuǎn)程存儲(chǔ)器上的數(shù)據(jù)進(jìn)行訪問或操作：

(1)發(fā)送消息，請(qǐng)求傳遞數(shù)據(jù)或?qū)?shù)據(jù)進(jìn)行操作；遠(yuǎn)程進(jìn)程調(diào)用(RPC，RemoteProcessCall)(2)目的處理器接收到消息以后，執(zhí)行相應(yīng)的操作或代替遠(yuǎn)程處理器進(jìn)行訪問，并發(fā)送一個(gè)應(yīng)答消息將結(jié)果返回。10.1引言同步消息傳遞

請(qǐng)求處理器發(fā)送一個(gè)請(qǐng)求后一直要等到應(yīng)答結(jié)果才繼續(xù)運(yùn)行。異步消息傳遞

發(fā)送方不先經(jīng)請(qǐng)求就直接把數(shù)據(jù)送往數(shù)據(jù)接受方。3.通信機(jī)制的性能指標(biāo)(3個(gè))(1)通信帶寬

理想狀態(tài)下的通信帶寬受限于處理器、存儲(chǔ)器和互連網(wǎng)絡(luò)的帶寬。

10.1引言(2)通信延遲理想狀態(tài)下通信延遲應(yīng)盡可能地小。

通信延遲＝發(fā)送開銷+跨越時(shí)間+傳輸延遲+接收開銷(3)通訊延遲的隱藏如何才能較好地將通信和計(jì)算或多次通信之間重疊起來，以實(shí)現(xiàn)通訊延遲的隱藏。通常的原則：只要可能就隱藏延遲。通信延遲隱藏是一種提高性能的有效途徑，但它對(duì)操作系統(tǒng)和編程者來講增加了額外的負(fù)擔(dān)。10.1引言4.不同通信機(jī)制的優(yōu)點(diǎn)

A.共享存儲(chǔ)器通信(Load/Store)的主要優(yōu)點(diǎn)(1)與常用的集中式多處理機(jī)使用的通信機(jī)制兼容。(2)易于編程——與傳統(tǒng)的編程模式一致(3)當(dāng)通信數(shù)據(jù)較小時(shí)，通信開銷較低，帶寬利用較好。(4)通過硬件控制的Cache減少了遠(yuǎn)程通信的頻度，減少了通信延遲以及對(duì)共享數(shù)據(jù)的訪問沖突。10.1引言B.消息傳遞通信機(jī)制的主要優(yōu)點(diǎn)(1)硬件較簡(jiǎn)單。(2)通信是顯式的，從而引起編程者和編譯程序的注意，著重處理開銷大的通信(本地Load/Store,遠(yuǎn)程MSG)。在共享存儲(chǔ)器上支持消息傳遞相對(duì)簡(jiǎn)單在消息傳遞的硬件上支持共享存儲(chǔ)器就困難得多。所有對(duì)共享存儲(chǔ)器的訪問均要求操作系統(tǒng)提供地址轉(zhuǎn)換和存儲(chǔ)保護(hù)功能，即將存儲(chǔ)器訪問轉(zhuǎn)換為消息的發(fā)送和接收。10.1引言10.1.3并行處理面臨的挑戰(zhàn)并行處理面臨著兩個(gè)重要的挑戰(zhàn)：程序中有限的并行性相對(duì)較高的通信開銷系統(tǒng)加速比=10.1引言例10.1如果想用100個(gè)處理器達(dá)到80的加速比，求原計(jì)算程序中串行部分所占比例。解2.第二個(gè)挑戰(zhàn)：多處理機(jī)中遠(yuǎn)程訪問的延遲較大

在現(xiàn)有的機(jī)器中，處理器之間的數(shù)據(jù)通信大約需要50～10000個(gè)時(shí)鐘周期。

1.第一個(gè)挑戰(zhàn)：有限的并行性

使機(jī)器要達(dá)到好的加速比十分困難10.1引言機(jī)器通信機(jī)制互連網(wǎng)絡(luò)處理機(jī)數(shù)量典型遠(yuǎn)程存儲(chǔ)器訪問時(shí)間SPARCCenter共享存儲(chǔ)器總線≤201μsSGIChallenge共享存儲(chǔ)器總線≤361μsCrayT3D共享存儲(chǔ)器3維環(huán)網(wǎng)32－20481μsConvexExemplar共享存儲(chǔ)器交叉開關(guān)＋環(huán)8－642μsKSR-1共享存儲(chǔ)器多層次環(huán)32－2562-6μsCM-5消息傳遞胖樹32－102410μsIntelParagon消息傳遞2維網(wǎng)格32－204810-30μsIBMSP-2消息傳遞多級(jí)開關(guān)2－51230-100μs遠(yuǎn)程訪問一個(gè)字的延遲時(shí)間例一臺(tái)32個(gè)處理器的計(jì)算機(jī)，對(duì)遠(yuǎn)程存儲(chǔ)器訪問時(shí)間為2000ns。除了通信以外，假設(shè)計(jì)算中的訪問均命中局部存儲(chǔ)器。當(dāng)發(fā)出一個(gè)遠(yuǎn)程請(qǐng)求時(shí)，本處理器掛起。處理器時(shí)鐘時(shí)間為10ns，如果指令基本的CPI為1.0(設(shè)所有訪存均命中Cache)，求在沒有遠(yuǎn)程訪問的狀態(tài)下與有0.5%的指令需要遠(yuǎn)程訪問的狀態(tài)下，前者比后者快多少?

解有0.5%遠(yuǎn)程訪問的機(jī)器的實(shí)際CPI為CPI＝基本CPI＋遠(yuǎn)程訪問率×遠(yuǎn)程訪問開銷＝1.0＋0.5%×遠(yuǎn)程訪問開銷

10.1引言遠(yuǎn)程訪問開銷＝遠(yuǎn)程訪問時(shí)間/時(shí)鐘時(shí)間＝2000ns/10ns＝200個(gè)時(shí)鐘∴CPI＝1.0＋0.5%×200＝2.0它為只有局部訪問的機(jī)器的2.0／1.0＝2倍，因此在沒有遠(yuǎn)程訪問的狀態(tài)下的機(jī)器速度是有0.5%遠(yuǎn)程訪問的機(jī)器速度的2倍。

問題的解決并行性不足：采用并行性更好的算法遠(yuǎn)程訪問延遲的降低：靠體系結(jié)構(gòu)支持和編程技術(shù)

10.1引言3.并行程序的計(jì)算／通信比率(類似于單機(jī)訪存頻度)反映并行程序性能的一個(gè)重要的度量計(jì)算與通信的比率計(jì)算／通信比率隨著處理數(shù)據(jù)規(guī)模的增大而增加；隨著處理器數(shù)目的增加而降低。10.1引言10.2對(duì)稱(集中)式共享存儲(chǔ)器體系結(jié)構(gòu)多個(gè)處理器共享一個(gè)存儲(chǔ)器。當(dāng)處理器規(guī)模較小時(shí)，這種機(jī)器十分經(jīng)濟(jì)。支持對(duì)共享數(shù)據(jù)和私有數(shù)據(jù)的Cache緩存.私有數(shù)據(jù)供一個(gè)單獨(dú)的處理器使用，而共享數(shù)據(jù)供多個(gè)處理器使用。共享數(shù)據(jù)進(jìn)入Cache產(chǎn)生了一個(gè)新的問題Cache的一致性問題第十章多處理機(jī)(1)不一致產(chǎn)生的原因（Cache一致性問題）I／O操作Cache中的內(nèi)容可能與由I／O子系統(tǒng)輸入輸出形成的存儲(chǔ)器對(duì)應(yīng)部分的內(nèi)容不同。共享數(shù)據(jù)不同處理器的Cache都保存有對(duì)應(yīng)存儲(chǔ)器單元的內(nèi)容。

例兩個(gè)處理器的讀寫10.2.1多處理機(jī)Cache一致性10.2對(duì)稱式共享存儲(chǔ)器體系結(jié)構(gòu)(2)存儲(chǔ)器的一致性（非正式定義）

如果對(duì)某個(gè)數(shù)據(jù)項(xiàng)的任何讀操作均可得到其最新寫入的值，則認(rèn)為這個(gè)存儲(chǔ)系統(tǒng)是一致的。

What:返回給讀操作的是什么值When:什么時(shí)候才能將已寫入的值返回給讀操作需要滿足以下滿足條件①處理器P對(duì)X進(jìn)行一次寫之后又對(duì)X進(jìn)行讀，讀和寫之間沒有其它處理器對(duì)X進(jìn)行寫，則讀的返回值總是寫進(jìn)的值。

存儲(chǔ)系統(tǒng)行為的兩個(gè)不同方面10.2對(duì)稱式共享存儲(chǔ)器體系結(jié)構(gòu)②一個(gè)處理器對(duì)X進(jìn)行寫之后，另一處理器對(duì)X進(jìn)行讀，讀和寫之間無其它寫，則讀X的返回值應(yīng)為寫進(jìn)的值。③對(duì)同一單元的寫是順序化的，即任意兩個(gè)處理器對(duì)同一單元的兩次寫，從所有處理器看來順序都應(yīng)是相同的。假設(shè)直到所有的處理器均看到了寫的結(jié)果，一次寫操作才算完成；允許處理器無序讀，但必須以程序規(guī)定的順序進(jìn)行寫。

10.2對(duì)稱式共享存儲(chǔ)器體系結(jié)構(gòu)在一致的多處理機(jī)中，Cache提供兩種功能：共享數(shù)據(jù)的遷移(拷貝到本地Cache)

降低了對(duì)遠(yuǎn)程共享數(shù)據(jù)的訪問延遲。共享數(shù)據(jù)的復(fù)制(多個(gè)機(jī)器都需要的數(shù)據(jù)拷貝到各自的Cache)

不僅降低了訪存的延遲，也減少了訪問共享數(shù)據(jù)所產(chǎn)生的沖突。

小規(guī)模多處理機(jī)不是采用軟件而是采用硬件技術(shù)實(shí)現(xiàn)Cache一致性。10.2.2實(shí)現(xiàn)一致性的基本方案10.2對(duì)稱式共享存儲(chǔ)器體系結(jié)構(gòu)(1)Cache一致性協(xié)議對(duì)多個(gè)處理器維護(hù)一致性的協(xié)議。(2)關(guān)鍵：跟蹤記錄共享數(shù)據(jù)塊的狀態(tài)(3)共享數(shù)據(jù)狀態(tài)跟蹤記錄技術(shù)目錄(directory)物理存儲(chǔ)器中共享數(shù)據(jù)塊的狀態(tài)及相關(guān)信息均被保存在一個(gè)稱為目錄的地方。監(jiān)聽(snooping)每個(gè)Cache除了包含物理存儲(chǔ)器中塊的數(shù)據(jù)拷貝之外，也保存著各個(gè)塊的共享狀態(tài)信息。10.2對(duì)稱式共享存儲(chǔ)器體系結(jié)構(gòu)Cache通常連在共享存儲(chǔ)器的總線上，各個(gè)Cache控制器通過監(jiān)聽總線來判斷它們是否有總線上請(qǐng)求的數(shù)據(jù)塊。兩種更新協(xié)議(1)寫作廢協(xié)議在一個(gè)處理器寫某個(gè)數(shù)據(jù)項(xiàng)之前保證它對(duì)該數(shù)據(jù)項(xiàng)有唯一的訪問權(quán)。無論是在監(jiān)聽還是目錄模式下，唯一的訪問權(quán)保證了在進(jìn)行寫后不存在其它的可讀或者可寫的拷貝存在，即別的拷貝都作廢了。

例：在寫回Cache的條件下，監(jiān)聽總線中寫作廢協(xié)議的實(shí)現(xiàn)。10.2對(duì)稱式共享存儲(chǔ)器體系結(jié)構(gòu)在寫回cache的條件下，監(jiān)聽總線中寫作廢協(xié)議的實(shí)現(xiàn)處理器行為總線行為CPUACache內(nèi)容CPUBCache內(nèi)容主存X單元內(nèi)容0CPUA讀XCache失效00CPUB讀XCache失效000CPUA將X單元寫1作廢X單元11CPUB讀XCache失效111(2)寫更新協(xié)議當(dāng)一個(gè)處理器寫某數(shù)據(jù)項(xiàng)時(shí)，通過廣播使其它Cache中所有對(duì)應(yīng)的該數(shù)據(jù)項(xiàng)拷貝進(jìn)行更新。例在寫回Cache的條件下，監(jiān)聽總線中寫更新協(xié)議的實(shí)現(xiàn)。

處理器行為總線行為CPUACache內(nèi)容CPUBCache內(nèi)容主存X單元內(nèi)容0CPUA讀XCache失效00CPUB讀XCache失效000CPUA將X單元寫1廣播寫X單元111CPUB讀X111(3)寫更新和寫作廢協(xié)議性能上的差別主要來自：對(duì)同一數(shù)據(jù)的多個(gè)寫而中間無讀操作的情況，寫更新協(xié)議需進(jìn)行多次寫廣播操作，而在寫作廢協(xié)議下只需一次作廢操作。對(duì)同一塊中多個(gè)字進(jìn)行寫，寫更新協(xié)議對(duì)每個(gè)字的寫均要進(jìn)行一次廣播，而在寫作廢協(xié)議下僅在對(duì)本塊第一次寫時(shí)進(jìn)行作廢操作。從一個(gè)處理器寫到另一個(gè)處理器讀之間的延遲通常在寫更新模式中較低。而在寫作廢協(xié)議中，需要讀一個(gè)新的拷貝。10.2對(duì)稱式共享存儲(chǔ)器體系結(jié)構(gòu)大多數(shù)多處理機(jī)系統(tǒng)都采用寫作廢協(xié)議10.2.3監(jiān)聽協(xié)議及其實(shí)現(xiàn)基本實(shí)現(xiàn)技術(shù)10.2對(duì)稱式共享存儲(chǔ)器體系結(jié)構(gòu)小規(guī)模多處理機(jī)中實(shí)現(xiàn)寫作廢協(xié)議的關(guān)鍵利用總線進(jìn)行作廢操作：把要作廢的地址放到總線上（一個(gè)放，多個(gè)讀）。其它處理器一直監(jiān)聽總線。寫順序化：對(duì)于寫直達(dá)Cache，因?yàn)樗袑懙臄?shù)據(jù)同時(shí)被寫回主存，則從主存中總可以取到最新的數(shù)據(jù)值。對(duì)于寫回Cache，得到數(shù)據(jù)的最新值會(huì)困難一些，因?yàn)樽钚轮悼赡茉谀硞€(gè)Cache中，也可能在主存中。寫缺失時(shí)，除了作廢其它處理器相應(yīng)的cache塊，還要從存儲(chǔ)器取出該數(shù)據(jù)據(jù)塊。增加Cache中塊的標(biāo)志位，用于實(shí)現(xiàn)監(jiān)聽過程

狀態(tài)：

有效位（valid）——無副本(為了作廢方便)共享（shared）——至少一個(gè)副本，clean獨(dú)占（exclusive）——唯一副本，dirty。寫操作使共享變成獨(dú)占。如果沒有別的寫，永遠(yuǎn)是獨(dú)占；反之變共享。便于決定是否廣播？

Cache塊的擁有者：擁有唯一的Cache塊副本的處理器。

因?yàn)槊看慰偩€任務(wù)均要檢查Cache的地址位，這可能與CPU對(duì)Cache的訪問沖突?？赏ㄟ^下列兩種技術(shù)之一降低沖突：復(fù)制標(biāo)志位采用多級(jí)包容Cache（許多系統(tǒng)采用）10.2對(duì)稱式共享存儲(chǔ)器體系結(jié)構(gòu)監(jiān)聽協(xié)議舉例為簡(jiǎn)單起見，對(duì)于對(duì)共享塊的Writehit和Writemiss不加區(qū)分，都按Writemiss處理寫作廢，寫回法10.2對(duì)稱式共享存儲(chǔ)器體系結(jié)構(gòu)

存儲(chǔ)器分布于各結(jié)點(diǎn)中，所有的結(jié)點(diǎn)通過網(wǎng)絡(luò)互連。訪問可以是本地的，也可是遠(yuǎn)程的?？梢圆恢С諧ache一致性：規(guī)定共享數(shù)據(jù)不進(jìn)入Cache，僅私有數(shù)據(jù)才能保存在Cache中。優(yōu)點(diǎn)：所需的硬件支持很少(因?yàn)檫h(yuǎn)程訪問存取量?jī)H是一個(gè)字(或雙字)而不是一個(gè)Cache塊)10.3分布式共享存儲(chǔ)器體系結(jié)構(gòu)第十章多處理機(jī)缺點(diǎn)：

(1)實(shí)現(xiàn)透明的軟件Cache一致性的編譯機(jī)制能力有限。(2)沒有Cache一致性，機(jī)器就不能利用取出同一塊中的多個(gè)字的開銷接近于取一個(gè)字的開銷這個(gè)優(yōu)點(diǎn)，這是因?yàn)楣蚕頂?shù)據(jù)是以Cache塊為單位進(jìn)行管理的。當(dāng)每次訪問要從遠(yuǎn)程存儲(chǔ)器取一個(gè)字時(shí)，不能有效利用共享數(shù)據(jù)的空間局部性。(3)諸如預(yù)取等延遲隱藏技術(shù)對(duì)于多個(gè)字的存取(coalesced)更為有效，比如針對(duì)一個(gè)Cache塊的預(yù)取。10.3分布式共享存儲(chǔ)器體系結(jié)構(gòu)解決Cache一致性問題的關(guān)鍵：尋找替代監(jiān)聽協(xié)議的一致性協(xié)議。目錄協(xié)議在每個(gè)結(jié)點(diǎn)增加目錄存儲(chǔ)器，用于存放目錄對(duì)每個(gè)結(jié)點(diǎn)增加目錄表后的分布式存儲(chǔ)器的系統(tǒng)結(jié)構(gòu)10.3分布式共享存儲(chǔ)器體系結(jié)構(gòu)(1)目錄協(xié)議必須實(shí)現(xiàn)兩種基本操作處理讀失效處理對(duì)共享、干凈塊的寫對(duì)共享塊寫失效的處理是這兩個(gè)操作的簡(jiǎn)單組合

(2)目錄必須跟蹤記錄每個(gè)存儲(chǔ)塊的狀態(tài)存儲(chǔ)塊的狀態(tài)有三種：10.3.1基于目錄的Cache一致性及其實(shí)現(xiàn)10.3分布式共享存儲(chǔ)器體系結(jié)構(gòu)共享

在一個(gè)或多個(gè)處理器上具有這個(gè)塊的副本，且主存中的值是最新值（所有Cache均相同）。未緩沖所有處理器的Cache都沒有該塊的拷貝。專有僅有一個(gè)處理器上有該塊的副本，且已對(duì)該塊進(jìn)行了寫操作，而主存的拷貝仍是舊的。這個(gè)處理器稱為該塊的擁有者。

10.3分布式共享存儲(chǔ)器體系結(jié)構(gòu)(3)由于寫作廢操作的需要，還必須記錄哪些處理器有該塊的拷貝方法：對(duì)每個(gè)主存塊設(shè)置一個(gè)位向量當(dāng)該塊被共享時(shí)，每個(gè)位指出與之對(duì)應(yīng)的處理器是否有該塊的拷貝。當(dāng)該塊為專有時(shí)，可根據(jù)位向量來尋找其擁有者。10.3分布式共享存儲(chǔ)器體系結(jié)構(gòu)結(jié)點(diǎn)之間發(fā)送的消息及其作用10.3分布式共享存儲(chǔ)器體系結(jié)構(gòu)目錄狀態(tài)轉(zhuǎn)換圖對(duì)基于目錄的Cache一致性的多種改進(jìn)有限映射目錄鏈?zhǔn)浇Y(jié)構(gòu)目錄基于目錄的Cache一致性協(xié)議是完全由硬件實(shí)現(xiàn)的。

此外，還可以用軟硬結(jié)合的辦法實(shí)現(xiàn)。10.3分布式共享存儲(chǔ)器體系結(jié)構(gòu)10.4同步

通常是使用硬件提供的有關(guān)同步指令，通過用戶級(jí)軟件例程建立的。10.4.1基本硬件原語在多處理器同步中，主要功能是一組能自動(dòng)讀出后并進(jìn)行寫存儲(chǔ)單元的硬件原語。它們能夠自動(dòng)讀／修改單元。通常情況下，用戶不直接使用基本的硬件原語，原語主要供系統(tǒng)程序員用來編制同步庫函數(shù)。

第十章多處理機(jī)功能：將一個(gè)存儲(chǔ)單元的值和一個(gè)寄存器的值進(jìn)行交換。建立一個(gè)鎖，鎖值為“0”表示開鎖，

為“1”表示上鎖。處理器加鎖時(shí)，將對(duì)應(yīng)于該鎖的存儲(chǔ)單元的值

交換為某個(gè)寄存器的值“1”。如果返回值為“0”，

存儲(chǔ)單元的值此時(shí)已置換為“1”，防止了別的進(jìn)

程競(jìng)爭(zhēng)該鎖。

實(shí)現(xiàn)同步的關(guān)鍵:操作的原子性1.典型操作:原子交換（atomicexchange）10.4同步2.測(cè)試并置定（test_and_set）先測(cè)試一個(gè)值，如果符合條件則修改其值。3.讀取并加1（fetch_and_increment）它返回存儲(chǔ)單元的值并自動(dòng)增加該值。4.使用指令對(duì)

LL(loadlinked或loadlocked)的取指令

SC(storeconditional)的特殊存指令10.4同步例實(shí)現(xiàn)對(duì)由R1指出的存儲(chǔ)單元進(jìn)行原子交換操作try：movR3,R4；送交換值llR2,0(R1)；loadlinkedscR3,0(R1)；storeconditionalbeqzR3,try；存失敗轉(zhuǎn)移movR4,R2；將取的值送往R4最終R4和由R1指向的單元值進(jìn)行原子交換，在ll和sc之間如有別的處理器插入并修改了存儲(chǔ)單元的值，sc將返回“0”并存入R3中，從而使指令序列再重新循環(huán)。10.4同步

ll／sc機(jī)制的一個(gè)優(yōu)點(diǎn)：可用來構(gòu)造別的同步原語

例如：原子的fetch-and-incrementtry：

llR2,0(R1)；loadlinked

addiR2,R2,＃1；增加

scR2,0(R1)；storeconditional

beqzR2,try；存失敗轉(zhuǎn)移指令對(duì)的實(shí)現(xiàn)必須跟蹤地址

由ll指令指定一個(gè)寄存器，該寄存器存放著一個(gè)

單元地址，這個(gè)寄存器常稱為連接寄存器。10.4同步10.4.2用一致性實(shí)現(xiàn)鎖采用多處理機(jī)的一致性機(jī)制來實(shí)現(xiàn)旋轉(zhuǎn)鎖。旋轉(zhuǎn)鎖

處理器環(huán)繞一個(gè)鎖不停地旋轉(zhuǎn)而請(qǐng)求獲得該鎖。1.無Cache一致性機(jī)制在存儲(chǔ)器中保存鎖變量，處理器可以不斷地通過一個(gè)原子操作請(qǐng)求加鎖，比如先交換，再測(cè)試返回值從而知道鎖的狀況。釋放鎖的時(shí)候，處理器可簡(jiǎn)單地將鎖置為“0”。10.4同步liR2，＃1lockit：exchR2,0(R1)；原子交換bnezR2，lockit；是否已加鎖?2.機(jī)器支持Cache一致性將鎖緩沖進(jìn)入Cache，并通過一致性機(jī)制使鎖值保

持一致。

10.4同步

優(yōu)點(diǎn)可使“環(huán)繞”的進(jìn)程對(duì)本地Cache塊進(jìn)行操作；可利用鎖訪問的局部性，即處理器最近使用過的鎖不久又會(huì)使用。改進(jìn)旋轉(zhuǎn)鎖(獲得第一條好處)

使其環(huán)繞過程僅對(duì)本地Cache中鎖的拷貝進(jìn)行讀，直到它返回“0”確認(rèn)鎖可用，然后再進(jìn)行加鎖交換操作。使用鎖完畢后新競(jìng)爭(zhēng)又開始進(jìn)行。10.4同步

lockit：lwR2，0(R1)；取鎖值bnezR2，lockit；鎖不可用liR2，＃1；存入鎖值exchR2，0(R1)；交換bnezR2，lockit;如鎖不為0轉(zhuǎn)移上面給出了對(duì)于三個(gè)處理器競(jìng)爭(zhēng)鎖的操作。一旦處理器存入“0”釋放鎖，所有別的Cache對(duì)應(yīng)塊均被作廢，必須取新的值來更新它們鎖的拷貝。一個(gè)處理器Cache會(huì)先獲得未加鎖值并執(zhí)行交換操作，當(dāng)別的Cache失效處理完后，它們會(huì)發(fā)現(xiàn)已被加鎖，所以又必須不停地測(cè)試環(huán)繞。10.4同步表10.5三個(gè)處理機(jī)對(duì)鎖的使用步驟處理器P0處理器P1處理器P2鎖狀態(tài)總線/目錄操作1占有鎖環(huán)繞測(cè)試lock=0環(huán)繞測(cè)試lock=0Shared無2將鎖置為0（收到作廢命令）(收到作廢命令)ExclusiveP0發(fā)鎖變量作廢消息3

Cache失效Cache失效Shared總線/目錄處理P2Cache失效,鎖從P0寫回4

總線/目錄忙則等待Lock=0SharedP2Cache失效處理5

Lock=0執(zhí)行交換，導(dǎo)致Cache失效SharedP1Cache失效處理6

執(zhí)行交換，導(dǎo)致Cache失效

交換完畢，返回0置lock=1Exclusive總線/目錄處理P2Cache失效,發(fā)作廢消息7

交換完畢，返回1進(jìn)入關(guān)鍵處理段Shared總線/目錄處理P2Cache失效，寫回8

環(huán)繞測(cè)試lock=0

無10.4同步

ll／sc原語的另一個(gè)狀態(tài)：讀寫操作明顯分開。

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

lockit：

llR2，0(R1)；load-linked

bnezR2，lockit

；鎖無效

liR2,，＃1；加鎖值

scR2，0(R1)；存

beqzR2，lockit

；如存失敗轉(zhuǎn)移

第一個(gè)分支形成環(huán)繞的循環(huán)體，第二個(gè)分支解決了兩個(gè)同時(shí)請(qǐng)求鎖的處理器競(jìng)爭(zhēng)問題。盡管旋轉(zhuǎn)鎖機(jī)制簡(jiǎn)單并且具有強(qiáng)制性，但難以將它擴(kuò)展到處理器數(shù)量很多的情況。10.4同步10.4.3同步性能問題簡(jiǎn)單旋轉(zhuǎn)鎖不能很好地適應(yīng)可伸縮性。大規(guī)模機(jī)器中所有的處理器會(huì)產(chǎn)生出大量的競(jìng)爭(zhēng)問題。例10.3：設(shè)總線上有10個(gè)處理器同時(shí)準(zhǔn)備對(duì)同一變量加鎖。假設(shè)每個(gè)總線事務(wù)處理(讀失效或?qū)懯?是100個(gè)時(shí)鐘周期，忽略實(shí)際的Cache塊鎖的讀寫時(shí)間以及加鎖的時(shí)間，求10個(gè)處理器請(qǐng)求加鎖所需的總線事務(wù)數(shù)目。設(shè)時(shí)間為0時(shí)鎖已釋放并且所有處理器在旋轉(zhuǎn)，求處理這10個(gè)請(qǐng)求時(shí)間為多長(zhǎng)?假設(shè)總線在新的請(qǐng)求到達(dá)之前已服務(wù)完掛起的所有請(qǐng)求，并且處理器速度相同。10.4同步解當(dāng)i個(gè)處理器競(jìng)爭(zhēng)鎖的時(shí)候，他們完成下列操作序列，每一個(gè)操作產(chǎn)生一個(gè)總線事務(wù)：訪問該鎖的i個(gè)LL指令操作；試圖鎖住該鎖的i個(gè)SC指令操作；1個(gè)釋放鎖的存操作指令。因此對(duì)n個(gè)處理器，總線事務(wù)的總和為：n∑(2i+1)=n(n+1)+n=n2+2ni=1對(duì)于10個(gè)處理器有120個(gè)總線事務(wù)，需要12000個(gè)時(shí)鐘周期。10.4同步本例中問題的根源是鎖的競(jìng)爭(zhēng)、存儲(chǔ)器中鎖訪問的串行性以及總線訪問的延遲。旋轉(zhuǎn)鎖的主要優(yōu)點(diǎn):對(duì)于總線或網(wǎng)絡(luò)開銷較低10.4同步并行循環(huán)的程序中另一個(gè)常用的同步操作:柵欄柵欄強(qiáng)制所有到達(dá)的進(jìn)程進(jìn)行等待，直到全部的進(jìn)程到達(dá)柵欄，然后釋放全部的進(jìn)程，從而形成同步。

柵欄的典型實(shí)現(xiàn)用兩個(gè)旋轉(zhuǎn)鎖

(1)用來記錄到達(dá)柵欄的進(jìn)程數(shù)

(2)用來封鎖進(jìn)程直至最后一個(gè)進(jìn)程到達(dá)柵欄柵欄的實(shí)現(xiàn)要不停地探測(cè)指定的變量，直到它滿足規(guī)定的條件。

一種典型的實(shí)現(xiàn)，其中l(wèi)ock和unlock提供基本的旋轉(zhuǎn)鎖，total是要到達(dá)柵欄的進(jìn)程總數(shù)。10.4同步Lock(counterlock)；

／*確保更新的原子性*／if(count=0)release=0；／*第一個(gè)進(jìn)程則重置release*／count=count+1；／*到達(dá)進(jìn)程記數(shù)*／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加鎖保證增量操作的原子性，變量count記錄著已到達(dá)柵欄的進(jìn)程數(shù)，變量release用來封鎖進(jìn)程直到最后一個(gè)進(jìn)程到達(dá)柵欄。

實(shí)際情況中會(huì)出現(xiàn)的問題可能反復(fù)使用一個(gè)柵欄，柵欄釋放的進(jìn)程運(yùn)行一段后又會(huì)再次返回柵欄，這樣有可能出現(xiàn)某個(gè)進(jìn)程永遠(yuǎn)離不開柵欄的狀況(它停在旋轉(zhuǎn)操作上)。10.4同步例如：OS調(diào)度進(jìn)程，可能一個(gè)進(jìn)程速度較快，當(dāng)它第二次到達(dá)柵欄時(shí)，第一次的進(jìn)程還掛在柵欄中未能離開。這樣所有的進(jìn)程在這個(gè)柵欄的第二次使用中都處于無限等待狀態(tài)，因?yàn)檫M(jìn)程的數(shù)目永達(dá)不到total。10.4同步一種解決方法當(dāng)進(jìn)程離開柵欄時(shí)進(jìn)行計(jì)數(shù)，在上次柵欄使用中的所有進(jìn)程離開之前不允許任何進(jìn)程重用并初始化本柵欄。另一種解決辦法sense_reversing柵欄，每個(gè)進(jìn)程均使用一個(gè)私有變量local_sense，初始化為1。10.4同步Local_sense=!Local_sense；／*local-sense取反*／lock(counterlock)；／*確保增加的原子性*／count++；／*記算到達(dá)進(jìn)程數(shù)*／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同步例10.4假設(shè)總線上10個(gè)處理器同時(shí)執(zhí)行一個(gè)柵欄，設(shè)每個(gè)總線事務(wù)需100個(gè)時(shí)鐘周期，忽略Cache塊中鎖的讀、寫實(shí)際花費(fèi)的時(shí)間，以及柵欄實(shí)現(xiàn)中非同步操作的時(shí)間，計(jì)算10個(gè)處理器全部到達(dá)柵欄，被釋放及離開柵欄所需的總線事務(wù)數(shù)。設(shè)總線完全公平，整個(gè)過程需多長(zhǎng)時(shí)間?答：下表給出一個(gè)處理器通過柵欄發(fā)出的事件序列，設(shè)第一個(gè)獲得總線的進(jìn)程并未擁有鎖。10.5同步表10.6第i個(gè)處理器通過柵欄產(chǎn)生的事件序列

事件數(shù)量對(duì)應(yīng)源代碼說明LLiLock(counterlock)；所有處理器搶鎖SCiLock(counterlock)；所有處理器搶鎖LD1count=count+1；一個(gè)成功LLi-1Lock(counterlock)；不成功的處理器再次搶鎖SD1count=count+1；獲得專有訪問產(chǎn)生的失效SD1unlock(counterlock)；獲得鎖產(chǎn)生的失效LD2spin(release=local_sense)；讀釋放：初次和最后寫產(chǎn)生的失效10.4同步當(dāng)競(jìng)爭(zhēng)不激烈且同步操作較少時(shí)，我們主要關(guān)心的是一個(gè)同步原語操作的延遲?；镜男D(zhuǎn)鎖操作可在兩個(gè)總線周期內(nèi)完成：一個(gè)讀鎖，一個(gè)寫鎖。我們可用多種方法改進(jìn)形成在一個(gè)單周期內(nèi)完成操作。同步操作最嚴(yán)重的問題：進(jìn)程的串行性當(dāng)出現(xiàn)競(jìng)爭(zhēng)時(shí)，就會(huì)出現(xiàn)串行性問題。它極大地增加了同步操作的時(shí)間。

總線的使用是這個(gè)問題關(guān)鍵所在。在基于目錄的Cache一致性機(jī)器中，串行性問題也同樣嚴(yán)重。10.4同步10.4.4大規(guī)模機(jī)器的同步所希望的同步機(jī)制：在無競(jìng)爭(zhēng)的條件下延遲較小在競(jìng)爭(zhēng)激烈時(shí)串行性小1.軟件實(shí)現(xiàn)旋轉(zhuǎn)鎖

(1)旋轉(zhuǎn)鎖實(shí)現(xiàn)的主要問題當(dāng)多個(gè)進(jìn)程檢測(cè)并競(jìng)爭(zhēng)鎖時(shí)引起的延遲

(2)一種解決辦法:當(dāng)加鎖失敗時(shí)就人為地推延這些進(jìn)程的等待時(shí)間。

(3)具有指數(shù)延遲的旋轉(zhuǎn)鎖代碼10.4同步

liR3，1；R3＝初始延遲值；lockit：llR2，0(R1)；loadlinkedbnezR2，lockit；無效addiR2，R2，1；取到加鎖值scR2，0(R1)；storeconditionalbnezR2，gotit；存成功轉(zhuǎn)移sllR3，R3，1；將延遲時(shí)間增至2倍pauseR3；延遲R3中時(shí)間值jlockitgotit：使用加鎖保護(hù)的數(shù)據(jù)

當(dāng)sc失敗時(shí)，進(jìn)程推延R3個(gè)時(shí)間單位。10.4同步先討論采用數(shù)組進(jìn)行的軟件實(shí)現(xiàn)。為此我們給出一種更好的柵欄實(shí)現(xiàn)代碼。前面柵欄機(jī)制實(shí)現(xiàn)中，所有的進(jìn)程必須讀取

release標(biāo)志，形成沖突。通過組合樹來減小沖突組合樹是多個(gè)請(qǐng)求在局部結(jié)合起來形成樹的一種分級(jí)結(jié)構(gòu)。降低沖突的原因：將大沖突化解成為并行的多個(gè)小沖突。

鎖實(shí)現(xiàn)的另一種技術(shù)是排隊(duì)鎖10.4同步組合樹采用預(yù)定義的n叉樹結(jié)構(gòu)用變量k表示扇入數(shù)目，實(shí)際中k=4效果較好。當(dāng)k個(gè)進(jìn)程都到達(dá)樹的某個(gè)結(jié)點(diǎn)時(shí)，則發(fā)信號(hào)進(jìn)入樹的上一層。當(dāng)全部進(jìn)程到達(dá)的信號(hào)匯集在根結(jié)點(diǎn)時(shí)，釋放所有的進(jìn)程。采用sense_reversing技術(shù)來給出下面的基于組合樹的柵欄代碼。10.4同步structnode｛

／*組合樹中一個(gè)結(jié)點(diǎn)*／intcounterlock；intcount

；intparent；｝；structnodetree［0..p-1］；

／*樹中各結(jié)點(diǎn)*／intlocal_sense；intrelease；barrier(intmynode)｛lock(tree[mynode].counterlock)；／*保護(hù)計(jì)數(shù)器*／count++；／*計(jì)數(shù)的累加*／unlock(tree[mynode].conterlock)；／*解鎖*／if(tree[mynode].count==k)｛／*本結(jié)點(diǎn)全部到達(dá)*／if(tree[mynode].parent)>=0｛barrier(tree[mynode］.parent)；

｝else｛release=local_sense；｝tree[mynode].count＝0；｝

／*為下次重用初始化*／else｛spin(release=local_sense)；｝；｝；local_sense=!local_sense；barrier(mynode)；10.4同步2.硬件原語支持

介紹兩種硬件同步原語：(1)排隊(duì)鎖可以排隊(duì)記錄等待的進(jìn)程，當(dāng)鎖釋放時(shí)送出一個(gè)已確定的等待進(jìn)程。

第一個(gè)針對(duì)鎖第二個(gè)針對(duì)柵欄和要求進(jìn)行計(jì)數(shù)或提供明確索引的某些用戶級(jí)操作10.4同步硬件實(shí)現(xiàn)

在基于目錄的機(jī)器上，通過硬件向量等方式來進(jìn)行排隊(duì)和同步控制。在基于總線的機(jī)器中要將鎖從一個(gè)進(jìn)程顯式地傳給另一個(gè)進(jìn)程，軟件實(shí)現(xiàn)會(huì)更好一些。在第一次取鎖變量失效時(shí)，失效被送入同步控制器。同步控制器可集成在存儲(chǔ)控制器中(基于總線的系統(tǒng))或集成在目錄控制器中。排隊(duì)鎖的工作過程10.4同步如果鎖空閑，將其交給該處理器；如果鎖忙，控制器產(chǎn)生一個(gè)結(jié)點(diǎn)請(qǐng)求記錄，并將鎖忙的標(biāo)志返回給處理器，然后該處理器不停地進(jìn)行檢測(cè)。當(dāng)該鎖被釋放時(shí)，控制器從等待的進(jìn)程排隊(duì)中選出一個(gè)使用鎖，這可以通過更新所選進(jìn)程Cache中的鎖變量來完成。10.4同步例10.5如果在排隊(duì)鎖的使用中，失效時(shí)進(jìn)行鎖更新，求10個(gè)處理器完成lock和unlock所需的時(shí)間和總線事務(wù)數(shù)。假設(shè)條件與前面例子相同。解對(duì)n個(gè)處理器，每個(gè)處理器都初始加鎖產(chǎn)生1個(gè)總線事務(wù)，其中1個(gè)成功獲得鎖并在使用后釋放鎖，第1個(gè)處理器將有n+1個(gè)總線事務(wù)。每一個(gè)后續(xù)的處理器需要2個(gè)總線事務(wù)：1個(gè)獲得鎖，另1個(gè)釋放鎖。因此總線事務(wù)的總數(shù)為(n+1)+2(n-1)=3n-1。注意這里的總線事務(wù)總數(shù)隨處理器數(shù)量成線性增長(zhǎng)，而不是前面旋轉(zhuǎn)鎖那樣成二次方增長(zhǎng)。對(duì)10個(gè)處理器，共需要29個(gè)總線事務(wù)或2900個(gè)時(shí)鐘周期。10.4同步首先，需要識(shí)別出對(duì)鎖進(jìn)行初次訪問的進(jìn)程，從而對(duì)其進(jìn)行排隊(duì)操作。第二，等待進(jìn)程隊(duì)列可通過多種機(jī)制實(shí)現(xiàn)，在基于目錄的機(jī)器中，隊(duì)列為共享集合，需用類似目錄向量的硬件來實(shí)現(xiàn)排隊(duì)鎖的操作。最后，必須有硬件來回收鎖，因?yàn)檎?qǐng)求加鎖的進(jìn)程可能被切換時(shí)切出，并且有可能在同一處理器上不再被調(diào)度切入。

排隊(duì)鎖功能實(shí)現(xiàn)中有一些要考慮的關(guān)鍵問題10.4同步

為減少柵欄記數(shù)時(shí)所需的時(shí)間，從而減小瓶頸的串行度，引進(jìn)一種原語Fetch_and_increment，它可以原子地取值并增量。使用fetch_and_increment可以很好地改進(jìn)柵欄的實(shí)現(xiàn)。例7.6：寫出fetch_and_increment柵欄的代碼。條件與前面假設(shè)相同，并設(shè)一次fetch_and_increment操作也需100個(gè)時(shí)鐘周期。計(jì)算10個(gè)處理器通過柵欄的時(shí)間，及所需的總線周期數(shù)。(2)柵欄實(shí)現(xiàn)10.4同步解下面的程序段給出柵欄的代碼。對(duì)n個(gè)處理器，這種實(shí)現(xiàn)需要進(jìn)行n次fetch_and_increment操作，訪問count變量的n次cache失效和釋放時(shí)的n次Cache失效，這樣總共需要3n個(gè)總線事務(wù)。對(duì)10個(gè)處理器，總共需要30個(gè)總線事務(wù)或3000個(gè)時(shí)鐘周期。這里如同排隊(duì)鎖那樣，時(shí)間與處理器個(gè)數(shù)成線性增長(zhǎng)。

當(dāng)然，實(shí)現(xiàn)組合樹柵欄時(shí)也可采用fetch_and_increment來降低樹中每個(gè)結(jié)點(diǎn)的串行競(jìng)爭(zhēng)。10.4同步

local_sense=!local_sense；

／*local_sense變反*／fetch-and-increment(count)；／*原子性更新*／if(count==total){／*進(jìn)程全部到達(dá)*／count=0；／*初始化計(jì)數(shù)器*／release=local_sense；

／*釋放進(jìn)程*／｝else{／*還有進(jìn)程未到達(dá)*／spin(releaze=local_sense)；／*等待信號(hào)*／}10.4同步多線程使多個(gè)線程以重疊的方式共享單個(gè)處理器的功能單元。10.5同時(shí)多線程為實(shí)現(xiàn)共享，處理器必須保存各個(gè)線程的獨(dú)立狀態(tài)。硬件必須能夠較快地完成線程間的切換。線程的切 換應(yīng)該比進(jìn)程的切換要高效的多，進(jìn)程的切換一般 需要成百上千個(gè)處理器時(shí)鐘周期。第十章多處理機(jī)第一種方法：細(xì)粒度多線程技術(shù)它在每條指令間都能進(jìn)行線程的切換，從而導(dǎo)致多個(gè)線程的交替執(zhí)行。

主要優(yōu)點(diǎn)：能夠隱藏由任何或長(zhǎng)或短的阻塞帶來的吞吐率的損失主要缺點(diǎn)：減慢了每個(gè)獨(dú)立線程的執(zhí)行目前有兩種主要的多線程實(shí)現(xiàn)方法10.5同時(shí)多線程第二種方法：粗粒度多線程技術(shù)粗粒度多線程之間的切換只在發(fā)生代價(jià)較高、時(shí)間較長(zhǎng)的阻塞出現(xiàn)時(shí)。缺點(diǎn)：不能有效地減少吞吐率的損失。原因：由粗粒度多線程的流水線建立時(shí)間的開銷造成的。由于實(shí)現(xiàn)粗粒度多線程的CPU只執(zhí)行單個(gè)線程的指令，因此當(dāng)發(fā)生阻塞時(shí)，流水線必須排空或暫停。阻塞后切換的新的線程在指令執(zhí)行產(chǎn)生結(jié)果之前必須先填滿整個(gè)流水線。10.5同時(shí)多線程10.5.1將線程級(jí)并行轉(zhuǎn)換為指令級(jí)并行

同時(shí)多線程技術(shù)是一種在多流出、動(dòng)態(tài)調(diào)度處理器上開發(fā)線程級(jí)并行和指令級(jí)并行的改進(jìn)的多線程技術(shù)。1.產(chǎn)生的主要原因

現(xiàn)代多流出處理器通常含有多個(gè)并行的功能單元，而單個(gè)線程不能有效地利用這些功能單元。通過寄存器重命名和動(dòng)態(tài)調(diào)度機(jī)制，來自各個(gè)獨(dú)立線程的多條指令可以同時(shí)流出，而不考慮他們之間的相互依賴關(guān)系；其相互依賴關(guān)系將通過動(dòng)態(tài)調(diào)度機(jī)制得以解決。10.5同時(shí)多線程2.一個(gè)超標(biāo)量處理器在以下幾種配置時(shí)其性能的差別支持多線程技術(shù)的超標(biāo)量處理器由于缺乏足夠的指令級(jí)并行而限制了流出槽的利用率。支持粗粒度多線程的超標(biāo)量處理器通過線程的切換部分隱藏了長(zhǎng)時(shí)間阻塞帶來的開銷。由于只有當(dāng)發(fā)生阻塞時(shí)才進(jìn)行線程切換，新線程還需要流水線建立時(shí)間，所以會(huì)產(chǎn)生一些完全空閑的時(shí)鐘周期。10.5同時(shí)多線程支持細(xì)粒度多線程的超標(biāo)量處理器線程的交替執(zhí)行消除了完全空閑的流出槽。由于在每個(gè)時(shí)鐘周期內(nèi)只流出一個(gè)線程的指令，指令級(jí)并行的限制仍然導(dǎo)致一個(gè)時(shí)鐘周期內(nèi)存在不少的空閑流出槽。支持同時(shí)多線程的超標(biāo)量處理器通過在一個(gè)時(shí)鐘周期內(nèi)調(diào)度多個(gè)線程使用流出槽，從而同時(shí)實(shí)現(xiàn)線程級(jí)并行和指令級(jí)并行。理想情況下，流出槽的使用率只受限于多個(gè)線程對(duì)資源的需求和可用資源間的不平衡。10.5同時(shí)多線程圖7.16:超標(biāo)量處理器中的4種不同的流出槽使用方法開發(fā)的基礎(chǔ):使用動(dòng)態(tài)調(diào)度技術(shù)的處理器已經(jīng)具有了開發(fā)線程級(jí)并行所需的硬件設(shè)置。動(dòng)態(tài)調(diào)度超標(biāo)量處理器有大量的虛擬寄存器組，可以用來保存每個(gè)獨(dú)立線程的寄存器狀態(tài)。由于寄存器重命名機(jī)制提供了唯一的寄存器標(biāo)識(shí)符，多個(gè)線程的指令可以在數(shù)據(jù)路徑上混合執(zhí)行，而不會(huì)導(dǎo)致各線程間源操作數(shù)和目的操作數(shù)的混亂。多線程技術(shù)可以通過在一個(gè)亂序執(zhí)行的處理器上為每個(gè)線程設(shè)置重命名表、保留各自的PC值、提供多個(gè)線程的指令結(jié)果提交的能力來實(shí)現(xiàn)。10.5同時(shí)多線程10.5.2同時(shí)多線程處理器的設(shè)計(jì)同時(shí)多線程只有在細(xì)粒度的實(shí)現(xiàn)方式下才有意義并發(fā)多個(gè)同優(yōu)先級(jí)的線程必然拉長(zhǎng)單個(gè)線程的執(zhí) 行時(shí)間

通過指定一個(gè)優(yōu)先線程來減小這種影響，從而在整體性能提高的同時(shí)對(duì)單個(gè)指定的線程性能只產(chǎn)生較小的影響。10.5同時(shí)多線程多個(gè)線程的混合執(zhí)行將不可避免地影響單個(gè)線程的執(zhí)行時(shí)間

為提高單個(gè)線程的性能，應(yīng)該為指定的優(yōu)先線程盡可能多地向前取指，并且在分支預(yù)測(cè)失效和預(yù)取緩沖失效的情況下清空取指單元。但是這樣限制了其他線程可用來調(diào)度的指令條數(shù)，從而減少了吞吐率。所有的多線程處理器都必須在這里尋求一種折衷方案。10.5同時(shí)多線程只要一有可能，處理器就運(yùn)行指定的優(yōu)先線程。從取指階段開始就優(yōu)先處理優(yōu)先線程

只要優(yōu)先線程的指令預(yù)取緩沖區(qū)未滿，就為它優(yōu)先取指。只有當(dāng)優(yōu)先線程的緩沖區(qū)填滿以后才為其他線程預(yù)取指令。當(dāng)有兩個(gè)優(yōu)先線程時(shí)，需要并發(fā)預(yù)取兩個(gè)指令流，這給取指部件和指令cache的設(shè)置都增添了復(fù)雜度。

10.5同時(shí)多線程設(shè)計(jì)同時(shí)多線程處理器時(shí)面臨的其他主要問題指令流出單元也要優(yōu)先考慮指定的優(yōu)先線程，只有當(dāng)優(yōu)先線程阻塞不能流出的時(shí)候才考慮其他線程。設(shè)置用來保存多個(gè)上下文所需的龐大的寄存器文件必須保持每個(gè)時(shí)鐘周期的低開銷特別是在關(guān)鍵步驟上需要保證由于并發(fā)執(zhí)行多個(gè)線程帶來的cache沖突不會(huì)導(dǎo)致顯著的性能下降。10.5同時(shí)多線程通過研究這些問題還可以了解到在大多情況下多線程所導(dǎo)致的額外性能開銷是很小的，簡(jiǎn)單的線程切換選擇算法就足夠；目前的超標(biāo)量處理器的效率是比較低的，還有很大的改進(jìn)余地，同時(shí)多線程是獲得吞吐率改進(jìn)的最有前途的方法之一。10.5同時(shí)多線程10.5.3同時(shí)多線程的性能圖7.17表示在超標(biāo)量處理器上增添8個(gè)線程的同 時(shí)多線程能力時(shí)獲得的性能提高圖7.18表示SMT與基本的超標(biāo)量處理器在主要內(nèi) 部指標(biāo)利用率和命中率上的對(duì)比

10.5同時(shí)多線程兩個(gè)特點(diǎn)超標(biāo)量處理器本身功能十分強(qiáng)大，它具有很大的一級(jí)cache、