高等计算机系统结构多处理器系统

高等计算机系统结构

多处理器系统

（第八讲）

程旭

2010年5月31日

北京大学计算机科学技术系计算机系统结构教研室

UniprocessorPerformance(SPECint)

一/13X

10000

FromHennessyandPatterson,Computer

Architecture:AQuantitativeApproach,4th卡??%/year

edition,2006

O

81000

Z

/♦/

L

L

,

X52%/year

V

>

w>

>

8100

1。

0」

晅

10

25%/year/

1I❖

197819801982198419861988199019921994199619982000200220042006

•VAX:25%/year1978to1986

•RISC+x86:52%/year1986to2002

•RISC+x86:??%/year2002topresent

北京大学计算机科学技术系计算机系统结构教研室

Dejavualloveragain?

“・・・today'sprocessors...arenearinganimpasseastechnologies

approachthespeedoflight.”

DavidMitchell,TheTransputer:TheTimeIsNow(1989)

Transputerhadbadtiming(UniprocessorperformanceT)

=>Procrastinationrewarded:2Xseq.perf./1.5years

“Wearededicatingallofourfutureproductdevelopmenttomulticore

designsThisisaseachangeincomputing”

PaulOtellini,President,Intel(2005)

AllmicroprocessorcompaniesswitchtoMP(2XCPUs/2yrs)

nProcrastinationpenalized:2Xsequentialperf./5yrs

Manufacturer/YearAMDP07Intelf07IBM/907Sun「07

Processors/chip4228

Threads/Processor1128

Threads/chip42464

北京大学计算机科学技术系计算机系统结构教研室

OtherFactorsnMultiprocessors

Growthindata-intensiveapplications

Databases,fileservers,

■Growinginterestinservers,serverperf.

Increasingdesktopperf.lessimportant

Outsideofgraphics

Improvedunderstandinginhowtouse

multiprocessorseffectively

EspeciallyserverwheresignificantnaturalTLP

Advantageofleveragingdesigninvestmentby

replication

Ratherthanuniquedesign

北京大学计算机科学技术系计算机系统结构教研室

并行计算机

定义：“Aparallelcomputerisacollectionof

processingelementsthatcooperateandcommunicateto

solvelargeproblemsfast”

AlmasiandGottlieb,HighlyParallelComputing,1989

■并行计算机的一些问题：

•资源分配：

处理单元有多少？

■处理单元的性能如何？

存储多大？

数据访问、通信和同步

d处理单元之间如何协作和通信？

互联是什么类型？

数据如何在处理器之间传输？

编程人员使用什么样的原语？

・性能和可扩展性

d上述因素如何影响性能？

d如何支持可扩展性？

北京大学计算机科学技术系计算机系统结构教研室

并行处理器的“信仰”

六十年代以来计算机设计人员的梦想：增加处

理器数量以提升性能与设计更快的处理器

由于“单处理器不能继续发展”，因而导致创造出

许多针对具体编程模型的机器组成

例如，由于受制于光速限制，单处理器的速度将

不再提升：1972,…，1989

近乎宗教的狂热：必须确信无疑！

•九十年代，一些著名公司，如Thinking

Machines、KendallSquare,…等退出商业领

域，这种狂热有所降温

论据变为：可扩展性能机遇的“拉动”，而非

“单处理器性能稳定”的“推动”

北京大学计算机科学技术系计算机系统结构教研室

什么级别的并行性?

位级并行性：1970到1985左右

•4位、8位、16位、32位处理器

指令级并行(ILP):1985到今天

•流水技术

超标量

•超长指令字

•乱序执行

•指令级并行性的限制？

进程级或线程级并行性；是否能够成为通用计算的

主流？

北京大学计算机科学技术系计算机系统结构教研室

并行体系结构

“Aparallelcomputerisacollectionof

processingelementsthatcoopq痛eand

communicatetosolvelargeproblems

fast.

ParallelArchitecture=Computer

Architecture+Communication

Architecture

并行体系结构用通信体系结构（………

挈理犍平翁耀architecture）对传统的体

;而象（硬件/软件接口）

•组成结构支持有效实现上述抽象

北京大学计算机科学技术系计算机系统结构教研室

本系结构历史

并行4

历史上，并行体,系结构与编程模型紧密结合

•出现大量不同1狗结构，不可预测到底会如何发展

应用软件上^

脉动阵列\系统软件/

->ASIMD

体系结构

\〜消息传递

数据流

共享主存

•发展方向的不讨所定性严重影响了并行软件的开发！

北京大学计算机科学技术系计算机系统结构教研室

TwoModelsforCommunicationandMemory

Architecture

Communicationoccursbyexplicitlypassingmessages

amongtheprocessors:

message-passingmultiprocessors(akamulticomputers)

•Modernclustersystemscontainmultiplestand-alonecomputers

communicatingviamessages

2.Communicationoccursthroughasharedaddressspace(via

loadsandstores):

sharn&memorymultiprocessorseither

•UMA(UniformMemoryAccesstime)forshared

address,centralizedmemoryMP

•NUMA(Non-UniformMemoryAccesstime

multiprocessor)forsharedaddress,distributed

memoryMP

■Inpast,confusionwhether^^sharing^^meanssharingphysical

memory(SymmetricMP)orsharingaddressspace

北京大学计算机科学技术系计算机系统结构教研室

Centralizedvs.

DistributedMemory

CentralizedMemoryDistributedMemory

北京大学计算机科学技术系计算机系统结构教研室

CentralizedMemory

Multiprocessor

•Alsocalledsymmetricmultiprocessors(SMPs)

becausesinglemainmemoryhasasymmetric

relationshiptoallprocessors

•Largecaches=>singlememorycansatisfymemory

demandsofsmallnumberofprocessors

•Canscaletoafewdozenprocessorsbyusinga

switchandbyusingmanymemorybanks

•Althoughscalingbeyondthatistechnically

conceivable,itbecomeslessattractiveasthe

numberofprocessorssharingcentralizedmemory

increases

北京大学计算机科学技术系计算机系统结构教研室

DistributedMemoryMultiprocessor

•Pro:Cost-effectivewaytoscalememory

bandwidth

•Ifmostaccessesaretolocalmemory

•Pro:Reduceslatencyoflocalmemory

accesses

•Con:Communicatingdatabetween

processorsmorecomplex

•Con:Softwaremustbeawareofdata

placementtotakeadvantageofincreased

memoryBW

北京大学计算机科学技术系计算机系统结构教研室

ChallengesofParallelProcessing

Bigchallengeis%ofprogramthatisinherently

sequential

•Whatdoesitmeantobeinherentlysequential?

Suppose80Xspeedupfrom100processors.What

fractionoforiginalprogramcanbesequential?

a.10%

5%

1%

<1%

北京大学计算机科学技术系计算机系统结构教研室

SymmetricMultiprocessors

ProcessorProcessor

CPU-Memorybus

I

bridge

I/Obus

Memory

I/OcontrollerI/OcontrollerI/Ocontroller

symmetric

.

•AllmemoryisequallyfarGraphics

awayfromallprocessorsoutput

•AnyprocessorcandoanyI/ONetworks

(setupaDMAtransfer)

北京大学计算机科学技术系

当今的并行体系结构

对“计算机体系结构”进行扩展以支持通

信和协作

•10:指令系统体系结构

・新：通信体系结构

■定义

决定性抽象、边界和原语（接口）

•实现接口的组成结构（硬件或软件）

今天，编译程序、库和操作系统是重要桥梁

北京大学计算机科学技术系计算机系统结构教研室

当代并行计算机系统分层构架

CAD数据库科学建模并行应用

多道程序共享地址消息传递数据并行编程模型

编译器或库

通信抽象

用户/系统边界

操作系统支持

硬件/软件边界

通信硬件

物理通信介质

北京大学计算机科学技术系计算机系统结构教研室

藜构架

•编程模型

d多道程序（Multiprogramming）：许多工作、之间没有

通信

/共享地址空间：通过存储器通信

/消息传递：发送和接收信息（信报）

/数据并行：多个代理同时对不同的数据集合进行操作，

然后同时在全局交换信息（共享或消息传递）

•通信抽象：

d共享地址空间：例如，load,store,atomicswap

/消息传递：例如，send,receive的库调用

d关于这一论题的争论（易于编程、可扩展能力）

北京大学计算机科学技术系计算机系统结构教研室

共享地址模型小结

每个处理器可以指定（name）该机器中所有

的物理位置

每个进程可以指定（name）它与其他进程共

享的所有数据

数据通过load和store传输

数据大小：字节、字、…或cache块

使用虚拟存储技术来将虚拟地址映射到本地或

远程的物理地址

存储层次模型要求：通信将数据移动到本地处

理器的cache（就象load把数据从存储器移动

至Ucache）

•通信时，时延、带宽、可扩展性？

北京大学计算机科学技术系计算机系统结构教研室

共享地址空间模型

机器的物理地址空间

进程组的虚拟地址空间的通信/p私用

通过共享地址完成/n

北京大学计算机科学技术系计算机系统结构教研室

共享地址/存储多处理器模型

■通过Load和Store通信

•最老的、也是使用最广的模型

基于时间共享：多处理器上的多进程与共享

单处理器

■进程：单一虚拟地址空间和单或多线程控制

•多进程可以重叠（共享），但是所有线程共享同一

进程地址空间

一个线程对共享地址空间的写操作对其他线程

的读操作是可见的

•通常模型：共享代码、私有栈、一些共享堆、和一

些私用堆

北京大学计算机科学技术系计算机系统结构教研室

示例：小规模多处理器设计

■存储器：具有相同访问时间(uniformaccess

time：UMA)和总线互联、I/O

北京大学计算机科学技术系计算机系统结构教研室

…Iy可扩展性

Network

111J^L$

ppp

“舞厅式”“闺房式”

•互联网络是问题所在:成本（交叉开关）或带宽（总线）

•舞厅式：带宽仍可扩展，但比交叉开关的成本更低

到存储器的时延是统一的，但统一为最大时延

•分布存储器和非统一存储器访问（non-uniformmemoryaccess

：NUMA）

在通用网络上，构造成简单的信报（消息）事务之外的共享地址空间（

例如，读请求（read-request）、读响应（read-response））

•高速缓存共享（特别是非本地）的数据？

北京大学计算机科学技术系计算机系统结构教研室

SMP互联

处理器连到存储器并且连到I/O

基于总线：所有的存储位置具有相同的访问时间，

因而SMP=府祢多处理器(SymmetricMP)

•随着处理器和I/O的增加，共享限制带宽

交叉开关：扩展的成本很高

多级网络(与具有更高带宽的交叉开关相比，扩展

的成本较低)

“舞厅式”设计:所有的处理器在网络的一侧，所

有的存储器在网络的另一侧

北京大学计算机科学技术系计算机系统结构教研室

大规模多处理器系统设计

■注:利用非统一访问时间(nonuniformaccess

time：numa)和向抗庭的互联网络来实现分布(

分布存储)

北京大学计算机科学技术系计算机系统结构教研室

消息传递模型

所有计算机（CPU、存储器、I/O设备）用显式I/O操作来

完成通信

•本质上是NUMA,但利用I/O设备集成，而非存储系统

Send指定本地缓冲器+远程计算机的接收进程

Receive指定远程计算机的发送进程+存放数据的本地

缓冲器

•通常，send包括进程标志（tag）并且receive遵从基于该标

志的规则：单一匹配、任意匹配

同步（Synch）:当send完成、当缓冲器空闲、当请求接受（

requestaccepted）、receive等待发送

■Send+receive=＞存储器■存储器拷贝，每个原语都提

供本地地址，并且进行成对同步!

北京大学计算机科学技术系计算机系统结构教研室

消息传递抽象

AddressY

北京大学计算机科学技术系计算机系统结构教研室

消息传递模型（续）

Send+receive=＞即使在单处理器上运行,

也进行存储器■存储器拷贝，利用操作系统

同步

信息传递的历史：

•由于只能发送数据给最临近的结点，因而网拓

扑结构非常重要

•典型的同步：阻塞发送与接收

•后来，具有非阻塞发送的DMA,DMA负责将

接收数据放在缓冲器中直到处理器真地开始接

收，然后将数据传输到本地存储器

•后来，通过软件库来实现任意通信

北京大学计算机科学技术系计算机系统结构教研室

通信模型

■共享存储

•处理器通过共享地址空间进行通信

•易于在小规模机器上实现

・优点：

d单处理器和小规模多处理器系统选用的模型

d易于编程

d低时延

d易于使用硬件控制的高速缓冲存储技术

■消息传递

•处理器具有私用存储器，通过消息进行通信

・优点：

d使用硬件少，易于设计

d注意点在费时的非本地操作

在两种硬件的基础上可能支持两种软件模型

北京大学计算机科学技术系计算机系统结构教研室

Flynn'sTaxonomyM.J.Flynn,"VeryHigh-SpeedComputers",

Proc,oftheIEEE,V54,1900-1909,Dec.1966.

■Flynnclassifiedbydataandcontrolstreamsin1966

SingleInstruction,SingleSingleInstruction,

Data(SISD)MultipleDataSIMD

(Uniprocessor)(singlePC:Vector,CM-2)

MultipleInstruction,MultipleInstruction,

SingleData(MISD)MultipleDataMIMD

(????)(Clusters,SMPservers)

SIMD=Data-LevelParallelism

MIMD=Thread-LevelParallelism

MIMDpopularbecause

•Flexible:Nprogramsor1multithreadedprogram

Cost-effective:sameMPUindesktop&MIMDmachine

北京大学计算机科学技术系计算机系统结构教研室

流行的Flynn分类

SISD(SingleInstructionSingleData)

•单处理器

MISD(MultipleInstructionSingleData)

•???

SIMD(SingleInstructionMultipleData)

•示例：llliac-IV>CM-2

编程模型简单

d低开销

d灵活

全部都是定制的集成电路

MIMD(MultipleInstructionMultipleData)

•例如：SunEnterprise5000>CrayT3D、SGIOrigin

/灵活

使用商业化的微处理器

北京大学计算机科学技术系计算机系统结构教研室

数据并行模型

多个同样操作并行作用于一个大的规则数据结构（例

如，数组）的每个元素

1个控制处理器广播到多个PEs

•当计算机很大时，需要分布完成多个重复PE的控制部分

PE具有条件标志，因而可以实

现调步

■数据分布在每个存储器中

八十年代早期，VLSI=>SIMD

的食洁.

PE采用工2个1位PE+片载存储器

数据并行编程语言给出数据在处

理器上的布局

北京大学计算机科学技术系计算机系统结构教研室

数据并行模型

向量处理器具有类似的ISA,但是没有数据放

置的限制

SIMD产生的数据并行编程语言

VLSI的发展产生了单片FPU和整个高速处理器

(SIMD的吸引力弱)

SIMD编程模型发展为

单程序多数据(SPMD)模型

•所有的处理器执行同样的程序

•数据并行编程语言仍有用，立即完成所有的通信：

大批同步(BulkSynchronous)一些在一个全

局栅栏(barrier)之后完成所有通信的阶段

北京大学计算机科学技术系计算机系统结构教研室

并行体系结构逐步集中

在通信帮助下，将完整计算机连接到一个可扩展网

络（“闺房式”）

不同的编程模型对通信帮助的需求不同

•共享地址空间:与存储器紧密集成以捕获与其他处理器

相互作用的存储器事件+以接受其他结点的请求

消息传递:发送消息快速，并对到来消息响应：标志比

较、分配缓冲器、传输数据、等待接收置入

•数据并行:快速全局同步

高性能Fortran（HPF）共享存储、数据并行;

消息传递接口（MPI）消息传递库；

都可以在许多机器上工作，有多种不同实现

北京大学计算机科学技术系计算机系统结构教研室

基本论题

刻画并行机器的3个要点

•命名(Naming)

•同步(Synchronization)

•时延和带宽(LatencyandBandwidth)

北京大学计算机科学技术系计算机系统结构教研室

基本论题之一：命名

命名：如何快速求解大问题

•哪些数据需要共享

如何对它进行寻址

•哪些操作可以访问数据

•处理器之间如何引用

■命名的选择影响编译产生的代码:通过load记住

的地址或对消息传递跟踪处理器号和本地虚拟地

址

命名的选择影响数据的重复:通过装载cache存储

层次或通过软件重复和一致性

北京大学计算机科学技术系计算机系统结构教研室

基本论题之一：命名（续）

■全局物理地址空间:

在单一操作中，任何处理器都能产生、寻址和访问它

•存储器可以在任何地方：

通过虚拟地址变换来处理它

全局虚拟地址空间：如果每个进程的地址空间可以被

配置成包括该并行程序的所有共享数据

分段共享地址空间：

对位置进行命名

V进程号，地址》

对并行程序的所有进程都统一

北京大学计算机科学技术系计算机系统结构教研室

基本论题之二：同步

■为了协作，进程必须协调

消息传递是一种具有数据发送或抵达

的隐含协调

■共享地址

=＞为显式协调需要额外操作：

例如，写一个标志、唤醒线程、中断

一个处理器

北京大学计算机科学技术系计算机系统结构教研室

基本论题之三：时延和带宽

■带宽

•通信中需要高带宽

・受制于网络、存储器和处理器

•通信的开销在许多机器中是一大问题

■时延

•由于处理器需要等待，因而影响性能

•由于需要考虑许多问题来重叠通信和计算，因而也影响易于

编程性

■时延隐藏

•一种机制如何帮助隐藏时延？

•示例：把消息发送与计算重叠，预取数据，切换到其他任务

北京大学计算机科学技术系计算机系统结构教研室

小规模多处理器系统

Cache的功效:

•增加带宽与总线/存储器

•减少访问的时延

•对私有数据和共享数据都非常有效

■cache一致性如何？

北京大学计算机科学技术系计算机系统结构教研室

Cache一致性问题

时间事件CPUA的CPUB的位置X的

Cache内容Cache内容存储器内容

01

1A读X11

2B读X111

3A将0存入X010

北京大学计算机科学技术系计算机系统结构教研室

嘉:性的含义如何?

•任何读操作都必须返回最近写的内容

•太严格，也太难实现

较好:

•任何写操作的结果最终都会被任何一次读操作看见

•所有的写操作都以正确的次序可见（序列化

serialization）

保证上述要求的两个原则：

如果P写x且P1读x,且读和写之间足够远，那么

P的写效果将被P1看见

•对单一位置的写操作是序列化的：

以一确定次序可见

♦将看见最后的写

d否则将以不合逻辑的次序看见多次写

（在较新的数值写后，还看见较旧的数值）

北京大学计算机科学技术系计算机系统结构教研室

可能的硬件一致性解决方案

■SnoopingSolution(SnoopyBus):

•Sendallrequestsfordatatoallprocessors

•Processorssnooptoseeiftheyhaveacopyandrespond

accordingly

•Requiresbroadcast,sincecachinginformationisatprocessors

•Workswellwithbus(naturalbroadcastmedium)

•Dominatesforsmallscalemachines(mostofthemarket)

■Directory-BasedSchemes

•Keeptrackofwhatisbeingsharedinonecentralizedplace

•Distributedmemory=>distributeddirectoryforscalability

(avoidsbottlenecks)

・Sendpoint-to-pointrequeststoprocessorsvianetwork

•ScalesbetterthanSnooping

•ActuallyexistedBEFORESnooping-basedschemes

北京大学计算机科学技术系计算机系统结构教研室

基本窥探的协议

■WriteInvalidateProtocol:

Multiplereaders,singlewriter

・Writetoshareddata:aninvalidateissenttoallcaches

whichsnoopandinvalidateanycopies

•ReadMiss:

/Write-through:memoryisalwaysup-to-date

dWrite-back:snoopincachestofindmostrecent

copy

■WriteBroadcastProtocol(typicallywritethrough):

・Writetoshareddata:broadcastonbus,processors

snoop,andupdateanycopies

•Readmiss:memoryisalwaysup-to-date

■Writeserialization:busserializesrequests!

・Busissinglepointofarbitration

北京大学计算机科学技术系计算机系统结构教研室

窥探协议的一个例子

Invalidationprotocol,write-backcache

Eachblockofmemoryisinonestate:

•Cleaninallcachesandup-to-dateinmemory(Shared)

・ORDirtyinexactlyonecache(Exclusive)

•ORNotinanycaches

Eachcacheblockisinonestate(trackthese):

•Shared:blockcanberead

•ORExclusive:cachehasonlycopy,itswriteable,and

dirty

・ORInvalid:blockcontainsnodata

Readmisses:causeallcachestosnoopbus

■Writestocleanlinearetreatedasmisses

北京大学计算机科学技术系计算机系统结构教研室

Snoopy-Cache状态机T

CPUReadhit

Statemachine

forCPUCPUReadShared

Invalidread/only)

requestsPlacereadmiss

onbus

foreachCPUreadmiss

CPUWriteWrite-backblotk

cacheblockWritebackbibckCPUReadmiss

PlaceWritePlacereadmiss

Missonbusonbus

CPUWrite

CacheBlockPlaceWriteMissonBus

StateExclusive

(read/write)

CPUreadhitCPUWriteMiss

CPUwritehitWritebackcacheblock

Placewritemisson

bus

北京大学计算机科学技术系计算机系统结构教研室

Snoopy-Cache状态机-H

State

machine

forbus

requests

foreach

cacheblock

北京大学计算机科学技术系计算机系统结构教研室

PIBusMemory

stepStateAddrValueStateAddrValueActionProc.AddrValueAddrValue

|P1Write10toA1

P1:ReadA1

P2:ReadA1

P2:Write20toA1

P2:Write40toA2

CPURead

AssumesinitialcachestateRemoteWrite血

orMiss/

isinvalidandA1andA2map(f

rivaiiaj叫Sharedj

tosamecacheblock,UyRead\

butA1#A2、

,missonbus

Write

/CPUWrite

Remotemissonbus

WriteRemoteRead/y^PlaceWrite

orMissWriteBack/ZMissonBus

WriteBack

Q

clusivejy^

CPUreadhit\

CPUwritehit

北京大学计算机科学技术系计算机系统结构教研室

示例（续一）

P1P2BusMemory

stepStateAddrValueStateAddrValueActionProc.AddrValueAddrValue

P1:Write10toA1Excl.A110WrMsP1A1

P1:ReadA1

P2:ReadA1

P2:Write20toA1

P2:Write40toA2

Assumesinitialcachestate

isinvalidandA1andA2map

tosamecacheblock,

butA1WA2.

Activearrow=

CPUwritehit

北京大学计算机科学技术系计算机系统结构教研室

示例（续二）

P1P2BusMemory

stepStateAddrValueStateAddrValueActionProc.AddrValueAddrValue

P1:Write10toA1ExcLA110P1A1

P1:ReadA1Excl.A110

P2:ReadA1

P2:Write20toA1

P2:Write40toA2

AssumesinitialcachestateRemoteWriteCPUReadhit

isinvalidandA1andA2maporMiss

Shared

tosamecacheblock,Invalid

Read

butA1*A2missonbus

Write

RemotemissonbusCPUWrite

Write

RemoteReadPlaceWrite

orMissMissonBus

WriteBack

WriteBack

Excusive

CPUreadhit

CPUwritehit

北京大学计算机科学技术系计算机系统结构教研室

示例（续三）

P1P2BusMemory

stepStateAddrValueStateAddrValueActionProc.AddrValueAddrValue

P1:Write10toA1Excl.A110WrMsP1A1

P1:ReadA1Excl.A110

P2:ReadA1Shar.A1RdMsP2A1

Shar.A110WrBkP1A11010

Shar.A110RdDaP2A11010

P2:Write20toA110

P2:Write40toA210

10

AssumesinitialcachestateRemoteWriteCPUReadhit

isinvalidandA1andA2maporMiss

Shared

tosamecacheblock,Invalid

Read

butA1*A2.missonbus

Write

RemotemissonbusCPUWrite

WriteRemoteRead^/PlaceWrite

orMissWriteBack/MissonBus

WriteBack

Exclusive

CPUreadhit

CPUwritehit

北京大学计算机科学技术系计算机系统结构教研室

示例（续四）

P1P2BusMemory

stepState/AddrValueStateAddrValuiActiorProc.AddrValueAddValu

\P1Write10toA1ExcLA110Wr7WsP1A1

IP1:ReadA1ExcLA110

P2:ReadA1Shar.A1BdMsP2A1

Shar.A110WrBkP1A11010

Shar.A110