高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)

第八章多處理器計(jì)算機(jī)結(jié)構(gòu)

石教英

回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件VI.0

<1Introduction

?觀點(diǎn)一?單處理器無(wú)前途，只有走多處理

器這條路。

?反觀點(diǎn)■一在1985-1995十年間，單處理器機(jī)

器速度提高率為50年代初使用晶體管以來(lái)最

高。認(rèn)為單處理器前途無(wú)限。(實(shí)質(zhì)為微處

理器)。

?折衷觀點(diǎn)■一并行機(jī)毫無(wú)疑問(wèn)將在未來(lái)起更

大作用，但不是現(xiàn)在(butnotnow)。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

并行機(jī)在未來(lái)作用更大的理由

?因?yàn)槲⑻幚砥骺赡苋詫⒅髟椎幚砥鳈C(jī)器，因此除

了提高微處理器速度之外，合乎邏輯的提高速度方

法是將多個(gè)微處理器連接在一起，這比設(shè)計(jì)專(zhuān)用處

理器要便宜得多。

?1985年以來(lái)，曾給微處理器帶來(lái)高速性能的體系

結(jié)構(gòu)創(chuàng)新步伐是否仍能保持下去。我們?cè)诘?章中

已看到，現(xiàn)代多發(fā)射處理器已變得無(wú)法相信的復(fù)雜

因此，期望通過(guò)增加復(fù)雜度和硅片面積來(lái)提高性能

的勢(shì)頭將有所減弱。

?影響并行機(jī)普遍使用的主要障礙--軟件問(wèn)題已出

現(xiàn)緩慢的但不斷的進(jìn)展。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

作者觀點(diǎn)

?微處理器速度的高速進(jìn)展至少將維持到

進(jìn)入下以世紀(jì)。但是一旦微處理器進(jìn)展

速度放慢之后，多處理器系統(tǒng)結(jié)構(gòu)將更

有吸引力。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

如何介紹多處理器系統(tǒng)結(jié)構(gòu)

?多處理器系統(tǒng)結(jié)構(gòu)的內(nèi)容極其豐富，分支很多，

很多的新思想出現(xiàn)了，又消失了，并且是失敗

多于成功。因此不可能完整地介紹這一領(lǐng)域，

避免經(jīng)不起時(shí)間考驗(yàn)。

?重點(diǎn)介紹多處理器設(shè)計(jì)的主流--中、小規(guī)模多

處理器，級(jí)處理器數(shù)＜100。

?介紹一點(diǎn)處理器數(shù)＞100的大規(guī)模并行機(jī)，因?yàn)?

-至少在90年代中期，此類(lèi)機(jī)器的未來(lái)系統(tǒng)結(jié)構(gòu)

并為確定。

-市場(chǎng)生命力值得懷疑。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

.2并行系統(tǒng)結(jié)構(gòu)分類(lèi)

?分類(lèi)目的

-了解多處理器的不同設(shè)計(jì)方案；

-理解多處理器系統(tǒng)結(jié)構(gòu)是如何逐步發(fā)展到今天

主流形式的。

?多處理器的基本思想，可追溯到計(jì)算機(jī)的早

期階段。

-提高性能

-提高可靠性

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

Flynn分類(lèi)法■■指令劉、數(shù)據(jù)流并行性

?SISD?一單處理器

?SIMD-■一Singleinstructionmemoryand

controlprocessor,Multipledatamemories

(eachprocessorhasitsowndata

memory)(多為專(zhuān)用處理器)

?MISD■一未實(shí)現(xiàn)，無(wú)產(chǎn)品，但可能將來(lái)會(huì)有。

?MIMD■一每一處理器取它自己的指令，運(yùn)行

于它自己的data,處理器多為現(xiàn)成的微處理

器。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

發(fā)展歷史（1）

?歷史上最早成功的多處理器機(jī)為SIMD

-connectionmachine64K1bitprocessors

-IlliacIV64個(gè)64bitprocessors

?作為通用機(jī),0年代重新崛起

-Thinkingmachine,MasPar

?但再次回落，理由

-不靈活，不適用于很多問(wèn)題，當(dāng)scaledown時(shí),

性/價(jià)比變差。

-無(wú)法利用高性價(jià)比的微處理器，而必須設(shè)計(jì)專(zhuān)

用processor。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

發(fā)展歷史（2）

?SIMD多處理器作為專(zhuān)用機(jī)，特別是在image

和signal處理領(lǐng)域的arrayprocessor,仍有

前途。

?近年來(lái)，MIMD作為通用多處理器系統(tǒng)結(jié)構(gòu)

的主要技術(shù)正在崛起。

-靈活性，既可作單用戶機(jī)，面向解決單個(gè)的高

性能應(yīng)用；也可運(yùn)行多任務(wù)多道程序，或用于

上述兩種混合方式。

-可利用高性價(jià)比的微處理器。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

MIMD分類(lèi)

?可根據(jù)處理器個(gè)數(shù)分類(lèi)，單處理器個(gè)數(shù)直接

影響到存儲(chǔ)器組織和互連網(wǎng)策略。而處理器

個(gè)數(shù)的多少也將隨事件發(fā)生變化。

?根據(jù)存儲(chǔ)器組織來(lái)分類(lèi)：

-集中共享存儲(chǔ)器式系統(tǒng)結(jié)構(gòu)(centralized

shared-memoryarchitecture)

-分布存儲(chǔ)器式系統(tǒng)結(jié)構(gòu)(distributed-memory

architecture)

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

集中共享存儲(chǔ)器式系統(tǒng)結(jié)構(gòu)

（在90年代中期）由幾十個(gè)處理器組成。由三個(gè)特

八占、、.?

?處理器數(shù)量不大一■從而所有處理器可共享一

個(gè)集中式存儲(chǔ)器，處理器和存儲(chǔ)器通過(guò)總線互

連。

?采用大容量Cache—可使采用單一總線和單

一存儲(chǔ)器滿足數(shù)目不多處理器對(duì)存儲(chǔ)器的要求。

?每一處理器訪問(wèn)存儲(chǔ)器的時(shí)間是相等的（一

致的）■一故稱為UMA（uniformmemory

access）機(jī)器。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

集中共享存儲(chǔ)器多處理器的基本結(jié)構(gòu)（P638）

OneorOneorOneorOneor

morelevelsmorelevelsmorelevelsmorelevels

ofcacheofcacheofcacheofcache

MainmemoryI/O系統(tǒng)

.

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

分布存儲(chǔ)器體系結(jié)構(gòu)

支持大量處理器組成的多處理器體系結(jié)構(gòu)，有

以下三大特點(diǎn)：

?處理器個(gè)數(shù)多一?從而導(dǎo)致存儲(chǔ)器必須為分布式

的，即每一處理器配備一個(gè)存儲(chǔ)器，否則不能

滿足整個(gè)系統(tǒng)對(duì)帶寬的要求；

?機(jī)器規(guī)模在不斷縮小■…因?yàn)樘幚砥餍阅懿粩嗵?/p>

高，所以個(gè)數(shù)可減少，單與集中共享存儲(chǔ)器型

比還是要多。同時(shí)也因?yàn)樘幚砥魉俣忍岣撸瑢?duì)

存儲(chǔ)器帶寬要求也不斷提高；

?要高帶寬的互連網(wǎng)絡(luò)。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

分布存儲(chǔ)器多處理器的基本結(jié)構(gòu)（Ep639）

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

說(shuō)明:

?Nodemayactuallyeachcontaina

smallnumber(2-)ofprocessors,

whichmaybecalledclusteringof

multipleprocessors.

?為簡(jiǎn)單起見(jiàn)，這里指one-processor-per

nodestyleo

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

分布存儲(chǔ)器的優(yōu)缺點(diǎn)

?優(yōu)點(diǎn)

-cost-effectivewaytoscalethememory

bandwidth,ifmostofaccessesareto

localmemoryinthenode.

-Itreducesthelatencyforaccesstothe

localmemory.

?缺點(diǎn)

-處理器之間數(shù)據(jù)通信復(fù)雜，延遲時(shí)間增加。

（分布存儲(chǔ)器導(dǎo)致處理器之間通信的兩種

范式。）

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

多處理器體系結(jié)構(gòu)的存儲(chǔ)器結(jié)構(gòu)模型及對(duì)應(yīng)的

通信模型

rCentralizedsharedmemory

―：--------^Distributed

shared-memory

DistributedJshared-memory

memory-j---------------------

〔MultipleMessynchronized

computer

^asynchronized

□:存儲(chǔ)器結(jié)構(gòu)模型：通信模型

大規(guī)模多處理器必須采用分布式存儲(chǔ)器，即每一處理

器帶一個(gè)存儲(chǔ)器。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

分布式存儲(chǔ)器結(jié)構(gòu)模型(1)

?Distributedsharedmemory(DSMor

scalablesharedmemory)

-olgicaluniformaddressspacebutphysical

distributedmemory,soanyoneoftheprocessorscan

accessanyoneofthememories.

-Sharedmemorymeanssharingtheaddressspace,

whichisdifferentfromcentralizedsharedmemory.

-UMA(uniformmemoryaccess)?一centralizedshare

memory.

-NUMA(non-uniformmemoryaccess)--distributed

sharedmemory.

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

分布式存儲(chǔ)器結(jié)構(gòu)模型(2)

?multiplecomputers

一Addressspaceconsistsofmultiple

privateaddressspaceso邏輯上不連續(xù)，

遠(yuǎn)程處理器無(wú)法訪問(wèn)。

一每一結(jié)點(diǎn)(processor-memory)模塊是一

單獨(dú)的計(jì)算機(jī)，故稱為多計(jì)算機(jī)結(jié)構(gòu)。

-上一章介紹的NOW計(jì)劃，每一結(jié)點(diǎn)實(shí)質(zhì)

上是一工作站或PC,由LAN連接而成。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

通信模型

?共享存儲(chǔ)器通信模型(sharedmemory)

-對(duì)應(yīng)與統(tǒng)一地址空間組織，因?yàn)檫@一統(tǒng)一的地

址空間可用作隱含的數(shù)據(jù)通信機(jī)制，即直接用

load、store共享變量即可。

?消息傳遞模型(messagepassing)

-對(duì)應(yīng)于多重地址空間組織。這里處理器見(jiàn)得數(shù)

據(jù)通信需要顯式地通過(guò)傳遞消息來(lái)進(jìn)行。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

兩類(lèi)messagepassing機(jī)制

?Synchronousmessagepassing

-從讀數(shù)據(jù)角度看，這里message可看作為RPC

(遠(yuǎn)程過(guò)程調(diào)用)，由processor發(fā)送請(qǐng)求，等

到接到應(yīng)答后才能繼續(xù)往下進(jìn)行數(shù)據(jù)獲取。

?Asynchronousmessagepassing

-從寫(xiě)數(shù)據(jù)角度來(lái)看，若生產(chǎn)數(shù)據(jù)的處理器知道

哪一個(gè)處理器需要這一數(shù)據(jù)，一旦數(shù)據(jù)準(zhǔn)備好，

不必等請(qǐng)求信號(hào)到來(lái)，就將數(shù)據(jù)送往對(duì)方，這

樣發(fā)送過(guò)程可以立即連續(xù)不斷地進(jìn)行下去。

一標(biāo)準(zhǔn)消息傳遞庫(kù)(MessagePassingInterface,

MPI)已制定此類(lèi)庫(kù)函數(shù)，通常以犧牲性能來(lái)滿

足接口通用性的要求。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

通信性能的度量指標(biāo)(1)

度量任何一種通信機(jī)制性能的三個(gè)指標(biāo)

?通信帶寬

-理想情況下，通信帶寬受處理器、存儲(chǔ)器和互

連網(wǎng)絡(luò)等的限制，而與通信機(jī)制無(wú)關(guān)。如中分

帶寬(bisectionbandwidth)由互連網(wǎng)絡(luò)決定。

結(jié)點(diǎn)的近/出帶寬受結(jié)點(diǎn)的系統(tǒng)結(jié)構(gòu)和通信機(jī)制

的影響。

-通信機(jī)制如何影響結(jié)點(diǎn)的通信帶寬？決定于通

信機(jī)制占用結(jié)點(diǎn)哪些資源，占用資源時(shí)間長(zhǎng)短,

例如資源占用對(duì)通信帶寬的影響與消息的長(zhǎng)短

有關(guān)。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

通信性能的度量指標(biāo)(2)

?通信延時(shí)(communicationlatency)

-理強(qiáng)情況下，延時(shí)越短越好。由上一章知道，

通信延時(shí)二senderoverhead+Timeofflight+

Transportlatency+receiveroverhead

-發(fā)送端和接收端的額外開(kāi)銷(xiāo)由通信機(jī)制及其實(shí)

現(xiàn)技術(shù)決定。

-Latency的重要性：決定性能好壞，決定多處理

器編程的難易。

一開(kāi)銷(xiāo)(overhead)與資源占用(occupancy)

緊密相關(guān)；通信機(jī)制的很多特性，如目的地址

的表示，保護(hù)機(jī)制的實(shí)現(xiàn)等將直接影響

overhead和occupancy,直接影響到^高日

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

通信性能的度量指標(biāo)(3)

?通信延時(shí)的隱藏(communicationlatency

hiding)

-指通過(guò)通信機(jī)制使通信和計(jì)算或與其他處理重

疊進(jìn)行，把延時(shí)隱藏掉。

-測(cè)量方法：bymeasuringtherunningtimeon

machineswiththesamecommunication

latencybutdifferentsupportforlatencyhiding.

-在8.6-8.7再介紹latencyhiding

-latencyhiding無(wú)疑是一好思想，但也給軟件帶

來(lái)額外負(fù)擔(dān)，最終將影響編程實(shí)現(xiàn)。所以最好

的方法是降低latency。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

Advantagesofcommunicationmechanism(1)

?ForSharedmemory

-compatibilitywithmechanismusedin

centralizedmultiprocessors

-easyprogramming,simplifycompilerdesign

-loweroverheadforcommunicationandbetter

useofbandwidth,duetoimplicitnatureof

communicationandimplementmemory

protectioninhardwareinsteadofinOS.

-Theabilitytousehardware,controlledcaching

toreducethefrequencyofremote

communicationbysupportingautomatic

cachingofbothsharedandprivatedata.

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

Advantagesofcommunicationmechanism(2)

?ForMessagepassing

-Thehardwarecanbesimpler

-communicationisexplicit,forcing

programmersandcompilerstopay

attentiontocommunication.

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

前述存儲(chǔ)器組織與通信模型的對(duì)應(yīng)關(guān)系:

?兩種存儲(chǔ)器組織

-■singleaddresspace(distributedsharedmemory)

-?privateaddressspaces(multiplecomputer)

?兩種通信模型

-□sharememory

-Omessagepassing

?對(duì)應(yīng)關(guān)系

-□on■

-Oon?

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

新的通信機(jī)制

?Omessagepassingon?singleaddresspace

-理由是傳遞信息實(shí)質(zhì)上是把地址空間中一塊數(shù)

據(jù)拷貝到地址空間中的另一位置。

?Dsharememoryon?privateaddressspaces

-在實(shí)現(xiàn)messagepassing硬件上沒(méi)有統(tǒng)一地址空

間，從而無(wú)法簡(jiǎn)單地實(shí)現(xiàn)sharedmemory方式通

信，需要通過(guò)操作系統(tǒng)來(lái)完成地址翻譯工作和

存儲(chǔ)器保護(hù)工作。新的研究方向是Virtual

SharedMemory.

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

未來(lái)趨勢(shì)的估計(jì)

?傳統(tǒng)上對(duì)分布存儲(chǔ)結(jié)構(gòu)多處理器講，通信方式采用

消息傳遞型，原因有：實(shí)現(xiàn)簡(jiǎn)單，以及很多人不相

信在分布式存儲(chǔ)結(jié)構(gòu)上可實(shí)現(xiàn)共享地址空間。

?最新進(jìn)展：在90年代后半期，幾乎每一分布存儲(chǔ)

多處理器均采用sharedmemory通信機(jī)制。

?對(duì)于MPP（處理器多于100個(gè)）究竟采用何種硬件

通信機(jī)制號(hào)，尚無(wú)定論，即：sharedmemory,

messagepassing,hybridapproaches均有可能。

?雖然目前應(yīng)用總線作為互連網(wǎng)絡(luò)的集中存儲(chǔ)結(jié)構(gòu)多

處理器機(jī)器主宰市場(chǎng)，但從長(zhǎng)遠(yuǎn)看，技術(shù)發(fā)展趨勢(shì)

是中規(guī)模的分布存儲(chǔ)結(jié)構(gòu)計(jì)算機(jī)。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

多處理器系統(tǒng)結(jié)構(gòu)的目標(biāo)

?并行處理?提IWJ響應(yīng)時(shí)間

—程序本身并行性多少

-網(wǎng)絡(luò)延時(shí)

?多任務(wù)處理--提高throughput

-事務(wù)處理數(shù)據(jù)庫(kù)

-UDD?

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

并行處理的挑戰(zhàn)

?使并行處理成為一項(xiàng)富有挑戰(zhàn)性工作的

兩個(gè)困難：

-在程序中可利用的并行性有限；

-通信代價(jià)過(guò)高（指延時(shí)過(guò)長(zhǎng)）。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

例1：加速比與程序并行性的關(guān)系(Ep644)

?Achieveaspeedupof80with100

processors,whatfractionoftheoriginal

computationcanbesequential?

?解:

0=

Fparallel+Fparallel00

Fparallel=0.9975

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

例2通信代價(jià)的影響（Ep645）

?已知：

-32-processormachine,witheachprocessor

cycletime=10ns;

-remotereferencetime=2000ns;

-allreferencesexceptthoseinvolving

communicationhitinlocalmemory;

-baseCPI=1;

-0.5%oftheinstructionsinvolvearemote

reference.

解：CPlcommunication"1+0.5%x2000/10=2.0

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件vi.o

解決上述困難的途徑

?對(duì)程序并行性：

-在軟件中引入新的并行算法，提高并行性;

?對(duì)通信代價(jià)：

-byarchitectureandbyprogrammer來(lái)降

襁遠(yuǎn)程訪問(wèn)的latency;

?通過(guò)硬件機(jī)制(如cachingshareddata)來(lái)

降低遠(yuǎn)程訪問(wèn)的頻率；

?通過(guò)軟件機(jī)制，如restructuringthedatato

makemoreaccesseslocalo

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

本章的重點(diǎn)：降低遠(yuǎn)程latency的技術(shù)

?Howcachingbeusedtoreduceremote

accessfrequency.

-Caching帶來(lái)coherence和consistence問(wèn)題。

?Synchronization（處理器間通信的同步問(wèn)題）

?latencyhidingtechniques

?memoryconsistencymodelforshared

memory0

?實(shí)際介紹如何解決以下三大問(wèn)題：

一cachecoherence

-cacheconsistence

-synchronization

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

.3CentralizedShared-MemoryArchitecture

?集中共享存儲(chǔ)結(jié)構(gòu)可行性的關(guān)鍵問(wèn)題：

-如何解決那么多processor訪問(wèn)memory的帶寬

問(wèn)題。

?80年代起，小規(guī)模的集中共享存儲(chǔ)體系結(jié)構(gòu)

多處理器逐漸成為可行！理由是：

-采用大容量cache降低每個(gè)單處理器對(duì)存儲(chǔ)器帶

寬的要求；

-微處理器技術(shù)成熟，processor可用現(xiàn)成的微處

理器實(shí)現(xiàn)，而不必專(zhuān)門(mén)設(shè)計(jì)，性價(jià)比大為提高；

-小規(guī)模并行使集中共享存儲(chǔ)器成為可能。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

發(fā)展趨勢(shì)

?早期

一每塊印制板上一個(gè)processor+cache;

,目前

-每塊印制板上幾個(gè)（如4個(gè)）processor+

caches;

?下世紀(jì)初

-在每一芯片上集成幾個(gè)processor

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

上述關(guān)鍵技術(shù)問(wèn)題的解決方法

?應(yīng)用大Cache存放兩類(lèi)數(shù)據(jù)：（其它處理器

不用的）privatedata+shareddata;

?如何理解上述Cachingprivatedata和

shareddata?

一Forcachingprivatedata----singleprocessor的

行為類(lèi)似于單處理器的計(jì)算機(jī)；

-Forcachingshareddata可采用將幾個(gè)處理器

共享數(shù)據(jù)部分做成幾個(gè)copies分別存入各個(gè)

Caches,達(dá)到降低帶寬的要求。避免讀取同一數(shù)

據(jù)的競(jìng)爭(zhēng)。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

新的問(wèn)題：cachecoherence（cache一致性）

?I/O系統(tǒng)的Cachecoherence問(wèn)題

-從Cache看，或從I/O系統(tǒng)看memory,可能

存在數(shù)據(jù)的不一致性。

?WhatisMultiprocessorcachecoherence?

-多處理器系統(tǒng)中，兩個(gè)不同處理器的

Cache看memory,同樣存在數(shù)據(jù)的不一致

性。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

例：多處理器Cache不一致性

TimeEventCacheCacheMemory

contentsforcontentsforcontentsfor

CPUACPUALocationX

01

1CPUAreadsX11

2CPUBreadsX111

3CPUAstores0intoX010

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

寫(xiě)操作與進(jìn)程遷移引起Cache不一致

直寫(xiě)回寫(xiě)

P1P2

X，

H

x，X

從P2遷移至1]P1,從P1遷移到P2,

在P1上讀到X在P2上讀到X

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

Cachecoherence定義

Amemorysystemiscoherentifany

readofadataitemreturnsthemost

recentlywrittenvalueofthatdataitem.

（每次讀出的數(shù)據(jù)項(xiàng)的值是最近改寫(xiě)過(guò)的值）

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

上述定義的缺點(diǎn)

?簡(jiǎn)單化和含糊，設(shè)計(jì)存儲(chǔ)系統(tǒng)的兩種行為,

這兩種行為對(duì)于正確編寫(xiě)shared-memory

program很關(guān)鍵。

?Coherence問(wèn)題

-指讀出的是什么樣的值。（強(qiáng)調(diào)讀出值的一致

性）強(qiáng)調(diào)值的異同，故稱一致性。

?Consistency問(wèn)題

-指改寫(xiě)過(guò)的值何時(shí)能正確地讀出（強(qiáng)調(diào)何時(shí)能

正確讀出。強(qiáng)調(diào)時(shí)間概念，故稱連貫性。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

正確的一致性定義包含3條：（Ep656）

?Amemorysystemisconherenctif：

-同一處理器（P）對(duì)同一單元（X）先寫(xiě)后讀，且

在寫(xiě)讀之間無(wú)其它處理器寫(xiě)該單元，則（P讀出

的）返回給P的值等于P所寫(xiě)入的值。--保證程

序的按序性（即使單處理器也應(yīng)遵守）。

一兩個(gè)不同處理器分別對(duì)某單元（X）先寫(xiě)后讀，若

讀寫(xiě)之間的時(shí)間間隔足夠長(zhǎng)，且無(wú)其它寫(xiě)操作

發(fā)生在上述寫(xiě)讀之間，則返回（讀出）的值應(yīng)

等于寫(xiě)入的值。-一定義了存儲(chǔ)器一致性的含義。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

正確的一致性定義⑵

-兩個(gè)不同處理器先后按序?qū)懩硢卧?X),則所有

其它處理器看到的是同一次序?qū)懭胫?。如果?/p>

寫(xiě)入“1”，后寫(xiě)入“2”，則其它處理器決不

能先讀出“2”，后讀出“1”。稱為寫(xiě)操作

的串行化(writeserialization)

上述三個(gè)性質(zhì)足夠保證memorycoherenceo

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

Consistency問(wèn)題既重要也復(fù)雜

?復(fù)雜性：

-無(wú)法要求度（X單元）操作立即得到其它

處理器剛剛寫(xiě)入（X）的值。因?yàn)樽x操作

離寫(xiě)結(jié)束時(shí)間非常短的話，不可能讀出剛

寫(xiě)入的值。

-何時(shí)能讀出剛寫(xiě)入的值的問(wèn)題是與

memoryconsistencymodel有關(guān)的。（詳

見(jiàn)8.6節(jié)）

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

在8?6節(jié)前的約定：

?寫(xiě)操作在其他處理器未看到（未能讀出）寫(xiě)

入的結(jié)果之前，不能算作完成。

?處理器不能改變寫(xiě)操作的次序，既不能與其

它存儲(chǔ)器訪問(wèn)操作更換次序；即可改變讀次

序，單寫(xiě)操作的次序必須嚴(yán)格按程序規(guī)定的

順序進(jìn)行。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

BasicschemesforEnforcingCoherence

實(shí)現(xiàn)coherence的基本思想

-Caching,即在相關(guān)處理器的Caches中保留共

享數(shù)據(jù)的copy。

?因此多處理器的Cache應(yīng)提供兩種功能：

-共享數(shù)據(jù)的遷移(migration)：通過(guò)moveshared

datatolocalcache,并且usetheshareddatainlocal

cache,來(lái)達(dá)到降低訪問(wèn)共享數(shù)據(jù)的latency。

-共享數(shù)據(jù)的復(fù)制(replication)：指一旦某數(shù)據(jù)在

某一Cache被改寫(xiě)后，應(yīng)及時(shí)將改寫(xiě)值復(fù)制到其

它Cache中去。保證多個(gè)處理器可同時(shí)讀出共享

數(shù)據(jù)。達(dá)到降低latency(遠(yuǎn)程調(diào)用)和減少對(duì)共享

數(shù)據(jù)的競(jìng)爭(zhēng)。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

實(shí)現(xiàn)思路

?在小規(guī)模多處理器系統(tǒng)中，采用硬件解決方法，而

不是軟件方法；

?引進(jìn)維護(hù)Cachecoherence的協(xié)議，稱為cache-

coherenceprotocolo

?實(shí)現(xiàn)cache-coherenceprotocol的關(guān)鍵是：跟蹤共

享數(shù)據(jù)塊的狀態(tài)。

?存在兩類(lèi)protocols,對(duì)應(yīng)兩種不同的跟蹤共享狀態(tài)

的技術(shù)：基于目錄的利監(jiān)聽(tīng)技術(shù)。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

兩類(lèi)一致性協(xié)議

?Directorybased(基于目錄)

-把物理存儲(chǔ)器中數(shù)據(jù)塊的共享狀態(tài)放在一個(gè)稱

為目錄的結(jié)構(gòu)之中。(8.4節(jié)介紹)

?Snooping(監(jiān)聽(tīng))

-數(shù)據(jù)塊的共享狀態(tài)分散保留在每一擁有該數(shù)據(jù)

塊copy的Cache種，即不存在集中保留共享狀

態(tài)的結(jié)構(gòu)。由于Cache通常是與共享存儲(chǔ)器總線

相連接，所有Cache控制器監(jiān)控(monitor)or

監(jiān)聽(tīng)(snoop)總線,去發(fā)現(xiàn)它們(cache)是

否擁有總線請(qǐng)求的數(shù)據(jù)塊。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

?Cachecontroller

snooping

Bus

Addresstag

?Snoopingprotocol在采用微處理器+Cache的共享

存儲(chǔ)多處理器系統(tǒng)中日益受到歡迎。因?yàn)閰f(xié)議可利

甬已存在的物理連接(bustomemory)達(dá)到查詢

Cache狀態(tài)的目的。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

兩種監(jiān)聽(tīng)協(xié)議（1）

?Writeinvalidateprotocol（寫(xiě)時(shí)無(wú)效協(xié)議）

-在進(jìn)行寫(xiě)操作時(shí)，該item在所有其它Cache中的

copies均無(wú)效。所以一旦寫(xiě)過(guò)某計(jì)em,則所有處

理器從其cache中讀該item時(shí)均發(fā)生miss（因?yàn)?/p>

已無(wú)效，需從共享存儲(chǔ)器中重新讀出），即需

取最新寫(xiě)入的copy。若兩個(gè)處理器要同時(shí)寫(xiě)同

一item時(shí)，只有一個(gè)贏得寫(xiě)的權(quán)利（以后在介紹,

如何決定輸贏），而另一個(gè)處理必須得到該數(shù)

據(jù)的新copy后再寫(xiě)，因此這一protocoI能強(qiáng)制性

的實(shí)現(xiàn)寫(xiě)串行化。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

例：回寫(xiě)Cache和寫(xiě)無(wú)效snoopingprotocol

ProcessorBusactivityContentsofContentsofContentsof

ActivityCPUA'sCPUB，sMemory

cachecacheLocationX

0

CPUACachemiss

00

ReadsXforX

CPUBCachemiss

000

ReadsXforX

CPUAwritesInvalidation

10

A1toXforX

CPUBCachemiss

111

ReadsXforX

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

兩種監(jiān)聽(tīng)協(xié)議（2）

?Writeupdateorwritebroadcastprotocol

（寫(xiě)時(shí)更新或?qū)憦V播協(xié)議）

-當(dāng)某item被寫(xiě)后，該數(shù)據(jù)的所有copies均

同時(shí)更新。為保證不超出存儲(chǔ)器訪問(wèn)帶寬,

必須辨識(shí)被寫(xiě)的數(shù)據(jù)是否是共享數(shù)據(jù)，只

有那些共享數(shù)據(jù)被寫(xiě)后才需廣播，改寫(xiě)其

需所有copies,否則就沒(méi)有必要這樣做。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

例：回寫(xiě)cache和寫(xiě)時(shí)更新監(jiān)聽(tīng)協(xié)議

ProcessorBusactivityContentsofContentsofContentsof

ActivityCPUA'sCPUB5sMemory

cachecacheLocationX

0

CPUACachemiss

00

ReadsXforX

CPUBCachemiss

000

ReadsXforX

CPUAwritesWritebroadcast

111

A1toXOfX

CPUB

111

ReadsX

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

兩種協(xié)議性能的定性分析

?對(duì)同一字的多次寫(xiě)操作，

-多次寫(xiě)廣播；（更新協(xié)議）

-只要一次無(wú)效化操作；（寫(xiě)無(wú)效）

?Cache數(shù)據(jù)塊由多字組成的話，對(duì)塊中每一字進(jìn)

行寫(xiě)操作：

-每次都要寫(xiě)廣播；（更新協(xié)議）

-只在第一次寫(xiě)塊中任一字時(shí)，需要產(chǎn)生一無(wú)效

信號(hào)；（寫(xiě)無(wú)效）

?從一個(gè)處理器寫(xiě)數(shù)到另一處理器讀出寫(xiě)入的數(shù)的

延時(shí)：

-寫(xiě)廣播完成后，讀命中

-寫(xiě)無(wú)效化，讀失配，stall直到得到返回。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

兩種監(jiān)聽(tīng)協(xié)議的比較：

?兩種方法自提出以來(lái)已有10年時(shí)間，目

前寫(xiě)無(wú)效比寫(xiě)更新更為普及。

,由兩種協(xié)議性能的定性分析可知，寫(xiě)無(wú)

效協(xié)議對(duì)bus和memory的帶寬要求較

低，因此成為幾乎所有實(shí)現(xiàn)技術(shù)的選擇。

?在后面主要討論寫(xiě)無(wú)效協(xié)議。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件VI.0

基本實(shí)現(xiàn)技術(shù)（1）

實(shí)現(xiàn)寫(xiě)無(wú)效協(xié)議的關(guān)鍵是“利用總線完成無(wú)

效化”。

?如何實(shí)現(xiàn)無(wú)效化監(jiān)聽(tīng)協(xié)議

-處理器請(qǐng)求總線訪問(wèn)；

-處理器向總線廣播將被無(wú)效的數(shù)據(jù)的地址；

-所有Cache控制器不斷監(jiān)聽(tīng)（snooping）總線，

察看總線上的地址是否與其cache中的地址相符。

若相符，貝1Jcache中該數(shù)據(jù)被無(wú)效化。

-總線訪問(wèn)的順序性（只有先取得總線訪問(wèn)權(quán)限

的處理器才有權(quán)訪問(wèn)總線。）

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

基本實(shí)現(xiàn)技術(shù)（2）

?如何保證寫(xiě)操作的順序性

-因?yàn)閮蓚€(gè)處理器競(jìng)爭(zhēng)同時(shí)寫(xiě)同一location的話,

只有其中一個(gè)可獲得總線的訪問(wèn)權(quán)，則另一處

理器的Cache中的copy無(wú)效，從而使寫(xiě)操作按

順序執(zhí)行。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

基本實(shí)現(xiàn)技術(shù)（3）

?如何找到數(shù)據(jù)項(xiàng)最新（最近）的值？即在哪

一個(gè)Cache中？

-對(duì)write-throughcache很容易,因?yàn)镃ache和

memory的內(nèi)容總是一致的。

一對(duì)write-backcache較復(fù)雜。用snoop方法，每

一Cache控制器snoopseveryaddressonthe

buso若處理器找到它有一dirtycopyofthe

requestedcacheblock,該處理器薪響應(yīng)讀的

請(qǐng)求，提供該block的最新值，將該塊寫(xiě)回存儲(chǔ)

器，并終止存儲(chǔ)器訪問(wèn)。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

基本實(shí)現(xiàn)技術(shù)（4）

?如何實(shí)現(xiàn)snooping?

-利用Cache地址的tag項(xiàng)，即將bus上的地址與其

cachetags比較。

?如何實(shí)現(xiàn)無(wú)效化？

一利用Cacheblock的Validbit可方便地使該block

無(wú)效化。

?如何處理讀miss?即找到該塊的dirtycopy?

-不管讀miss是由無(wú)效化造成還是其他事件造成，

可通過(guò)snooping獲得最新的block的值。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

基本實(shí)現(xiàn)技術(shù)（5）

?如何處理寫(xiě)操作？

-先區(qū)分是否是共享數(shù)據(jù)，再要知道將寫(xiě)的block

的其它c(diǎn)opies是否在其它c(diǎn)ache中。若無(wú)其它

cachedcopies,（即為非共享數(shù)據(jù)），則對(duì)

write-backcacheW,沒(méi)有必要把寫(xiě)操作放到

bus上，從而達(dá)到節(jié)省時(shí)間，又減輕帶寬的負(fù)擔(dān)。

?如何跟蹤一cacheblock是否是共享的？

-在每一block上加一新的狀態(tài)位來(lái)指示該block是

否是共享的（類(lèi)似于validbit或dirtybit）。若寫(xiě)

入的blolk處于共享狀態(tài)，貝ijcache在寫(xiě)后要向

bus送一無(wú)效信號(hào)，并將該block標(biāo)記為private。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

基本實(shí)現(xiàn)技術(shù)（6）

?如何減少由bus檢查cache?addresstag弓I

起的對(duì)CPUcacheaccess的干涉？

-復(fù)制tags:在同一block地址增加兩個(gè)tags。若

tags復(fù)制以后,貝UCPU和snooping的訪問(wèn)可并

行進(jìn)行；

-多級(jí)Cachewithinclusionproperty:

Snoopingactivity可對(duì)次級(jí)Cache進(jìn)行，而大多

數(shù)CPUactivity可對(duì)初級(jí)Cache進(jìn)行。

-由于大多數(shù)高級(jí)微處理器均采用多級(jí)Cache來(lái)降

低對(duì)帶寬的要求，故這一方法已被大多數(shù)設(shè)計(jì)

所采用，有時(shí)還復(fù)制二級(jí)Cache的tags來(lái)進(jìn)一步

減少CPU和snooping的競(jìng)爭(zhēng)。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

小結(jié)

?保證Cache一致性的寫(xiě)時(shí)無(wú)效協(xié)議，意味著：

-必須對(duì)被寫(xiě)Cache塊的其它拷貝進(jìn)行無(wú)效化處理

-必須能在Cache失配時(shí)找到有效數(shù)據(jù)，對(duì)直寫(xiě)

cache----總是到memory中去找最新值；對(duì)回寫(xiě)

cache--采用監(jiān)聽(tīng)方法，所有CPU先比較地址，

再發(fā)現(xiàn)是否dirty。是dirty,即最新的數(shù)據(jù)。

?使用監(jiān)聽(tīng)在總線上完成判斷：

-不斷監(jiān)聽(tīng)總線上的地址

-不斷檢查是否與自己cache中地址相負(fù)荷。如果

是，則無(wú)效化。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

五種snoopingprotocols

NameProtocolMemory-writeUniquefeatureMachineusing

typepolicy

WriteWriteWritebackFirstsnooping

onceinvalidateafterfirstprotocoldescribed

writeinliterature

SynapseWriteWritebackExplicitstateSynapsemachine;

N+1invalidateWhereMemoryisfirstcache-coherence

theownermachinesavailable

BerkeleyWriteWritebackOwnedsharedBerkeleySPUR

invalidatestatemachine

IllinoisWriteWritebackCleanprivateState;SGIPowerand

invalidateCansupplydataChallengeseries

fromanycache

withacleancopy

"Firefly"WriteWritebackMemoryupdatedNocurrent

broadcastWhenprivate,onbroadcastmachines;

WritethroughSPARCcenter

Whenshared2000closest

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

Anexampleprotocol

RequestSourceFunction

ReadhitProcessorReaddataincache

WritehitProcessorWritedataincache

ReadmissBusRequestdatafromcacheormemory

WritemissBusRequestdatafromcacheormemory;

performanyneededinvalidates

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

Cache9statetransitionsbasedonrequests

fromCPU(Ep664)

/、CPUreadhit

CPUreadShared

Invalid1Placereadmissonbus

Readonl

s

99qnCPUreadmi

HUCPlTreadmiss

MMcWrite-balock

§3oPlaceread

邕missonbus

CPrite

lacewritemissonbus

Exclusive

CPUwritemiss

Read/writWrite-backcacheblock

Placewritemissonbus

CPUreadhit

CPUwritehit

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件vi.o

ts回

s

e

u回

q

e

r

n

o

O

l.

dV

e件

s課

a構(gòu)

b結(jié)

系

s體

機(jī)

n算

io)計(jì)

t4級(jí)

i4高

s6

np工

abOUIDUI0q4

E七蕓

r(xoosEq—UJ

t

esiso_q￡￡

tuSs-E9=M

tab

s

'e

eth

h

cm

ao

Cfr

兩圖合并之后的Cache塊的狀態(tài)圖

CPUreadhit

Writemissforthisblock

E7Shared、

CPUread/\

InvalidPlacereadmissonbu^\nReadonly)

x

sCPUreadmi

os

電9

xqnWrite-backNdCK

一

-sm」PlacereadmiousCPUreadmiss

qomu

-①oPlaceread

SqnSS

XBSmforblockmissonbus

SOd--

EB。JWriteackblock

Sq

U坦

Mm」/CPUwrite

JExclusiveXPlacewritemissonbus

Read/write)CPUwritemiss

Write-backdata

Placewritemissonbus

CPUreadhit

CPUwritehit回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

8.4Distributedshared-Memory

Architectures

?在這一體系結(jié)構(gòu)下有兩種選擇

一無(wú)Cachecoherence

例子：CrayT3D,注意力集中在可縮放存儲(chǔ)系統(tǒng)

-有Cachecoherence

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件Vl.O

無(wú)Cachecoherence(1)

-memorydistributedamongthenodes

-allnodesareinterconnectedbyanetwork

-accesscanbeeitherlocalorremote,由node中

的控制器根據(jù)地址決定數(shù)據(jù)是在本地存儲(chǔ)器還

是在遠(yuǎn)程存儲(chǔ)器。

-若需遠(yuǎn)程訪問(wèn)，則發(fā)消息給遠(yuǎn)程存儲(chǔ)器的控制

器去訪問(wèn)數(shù)據(jù)；

-這類(lèi)系統(tǒng)是帶cache的，但為避免coherence問(wèn)

題，將那些共享數(shù)據(jù)標(biāo)記為uncacheable,只允

許privatedata存放于Cache。因?yàn)楣蚕頂?shù)據(jù)不

會(huì)在Cache,所以遠(yuǎn)程訪問(wèn)只能案字，而不能按

block進(jìn)行。

回回

高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)課件V1.0

無(wú)Cachecoherence（1）

-仍然可用軟件顯式地將共享數(shù)據(jù)放進(jìn)cache,然后

由軟件來(lái)管理coherence。（通常,cache是由

硬件管理，而不是由軟件管理）

?優(yōu)點(diǎn)：不需要任何硬件

?缺點(diǎn)：

-不能實(shí)現(xiàn)基于compiler的透明的軟件cache

coherence;

-因?yàn)闊o(wú)cachecoherence,喪失了取singlecache

block的優(yōu)點(diǎn)，也喪失了利用共享數(shù)據(jù)的空間局

部性（因?yàn)槊看芜h(yuǎn)程訪問(wèn)只能按字進(jìn)行）

-失去了prefet