搜索
第二章并行硬件和并行软件1背景知识2串行硬件和软件输入输出程序一次只执行单个任务3“经典”的冯·诺依曼结构4主存（Mainmemory）主存中有许多区域，每个区域都可以存储指令和数据。每个区域都有一个地址，可以通过这个地址来访问相应的区域及区域中存储的数据和指令。5中央处理单元(CPU)中央处理单元分为控制单元和算术逻辑单元（ArithmeticLogicUnit，ALU）。控制单元负责决定应该执行程序中的哪些指令。ALU负责执行指令。add2+26关键术语寄存器——CPU中的数据和程序执行时的状态信息存储在特殊的快速存储介质中程序计数器——控制单元中一个特殊的寄存器，用来存放下一条指令的地址。总线——指令和数据通过CPU和主存之间的互连结构进行传输。这种互连结构通常是总线，总线中包括一组并行的线以及控制这些线的硬件。7memoryCPUfetch/read当数据或指令从主存传送到CPU时，我们称数据或指令从内存中取出或者读出。8memoryCPUwrite/store当数据或指令从CPU传送到主存中时，我们称数据或指令写入或者存入内存中。9冯·诺依曼瓶颈主存和CPU之间的分离称为冯·诺依曼瓶颈。这是因为互连结构限定了指令和数据访问的速率。程序运行所需要的大部分数据和指令被有效地与CPU隔离开。10一个操作系统“进程”进程是运行着的程序的一个实例。一个进程包括如下实体:可执行的机器语言程序.一块内存空间.操作系统分配给进程的资源描述符.安全信息.进程状态信息.11多任务大多数现代操作系统都是多任务的。这意味着操作系统提供对同时运行多个程序的支持。这对于单核系统也是可行的，因为每个进程只运行一小段时间（几毫秒），亦即一个时间片。在一个程序执行了一个时间片的时间后，操作系统就切换执行其他程序12多任务在一个多任务操作系统中，如果一个进程需要等待某个资源，例如需要从外部的存储器读数据，它会阻塞。这意味着，该进程会停止运行，操作系统可以运行其他进程。例如：航班预定系统在一个用户因为等待座位图而阻塞时，可为另一个用户提供可用的航线查询。13线程线程包含在进程中。线程为程序员提供了一种机制，将程序划分为多个大致独立的任务，当某个任务阻塞时能执行其他任务。此外，在大多数系统中，线程间的切换比进程间的切换更快。14一个进程和两个线程the“master”thread（主线程）startingathreadIscalledforking（派生）terminatingathreadIscalledjoining（合并）15对冯·诺依曼模型的改进16缓存(Cache)CPUCache是一组相比于主存，CPU能更快速地访问的内存区域。CPUCache位于与CPU同一块的芯片或者位于其他芯片上，但比普通的内存芯片能更快地访问。17局部性原理程序访问完一个存储区域往往会访问接下来的区域，这个原理称为局部性。空间局部性——访问附近的位置时间局部性——访问在不久的将来18局部性原理floatz[1000];…sum=0.0;for(i=0;i1000;i++)sum+=z[i];19缓存的分层（level）L1L2L3最小&最快最大&最慢20Cache命中（hit）L1L2L3xsumyztotalA[]radiusr1centerfetchx21Cache缺失（miss）L1L2L3ysumr1ztotalA[]radiuscenterfetchxx主存22与缓存有关的问题当CPU向Cache中写数据时，Cache中的值与主存中的值就会不同或者不一致(inconsistent)。有两种方法来解决这个不一致性问题：写直达(write-through)和写回(write-back)23与缓存有关的问题在写直达(write-through)Cache中，当CPU向Cache写数据时，高速缓存行会立即写入主存中。在写回(write-back)Cache中，数据不是立即更新到主存中，而是将发生数据更新的高速缓存行标记成脏（dirty）。当发生高速缓存行替换时，标记为脏的高速缓存行被写入主存中。24缓存映射全相联(fullyassociative)Cache——每个高速缓存行能够放置在Cache中的任意位置。直接映射(directedmapped)Cache——每个高速缓存行在Cache中有唯一的位置。n路组相联(n-waysetassociated)——每个高速缓存行都能放置到Cache中n个不同区域位置中的一个。25n路组相联当内存中的行（多于一行）能被映射到Cache中的多个不同位置（全相联和n路组相联）时，需要决定替换或者驱逐Cache中的哪一行。x26例子假设主存有16行，分别用0～15标记，Cache有4行，用0～3标记。在全相联映射中，主存中的0号行能够映射到Cache中的0、1、2、3任意一行。在直接映射Cache中，可以根据主存中高速缓存行的标记值除以4求余，获得在Cache中的索引。因此主存中0、4、8号行会映射到Cache的0号行，主存中的1、5、9号行映射到Cache的1号行，以此类推。27虚拟内存(1)如果运行一个大型的程序，或者程序需要访问大型数据集，那么所有的指令或者数据可能在主存中放不下。利用虚拟存储器（或虚拟内存），使得主存可以作为辅存的缓存。28虚拟内存(2)虚拟内存通过在主存中存放当前执行程序所需要用到的部分，来利用时间和空间局部性.29虚拟内存(3)交换空间（swapspace）——那些暂时用不到的部分存储在辅存的块中，称为交换空间。页(page)——数据块和指令块.页通常比较大.大多数系统采用固定大小的页，从4～16kB不等.30虚拟内存(4)programAprogramBprogramCmainmemory31虚拟页号在编译程序时，给程序的页赋予虚拟页号。当程序运行时，创建一张将虚拟页号映射成物理地址的表。程序运行时使用到虚拟地址，这个页表就用来将虚拟地址转换成物理地址。假如页表的创建由操作系统管理，那么就能保证程序使用的内存不会与其他程序使用的内存重叠32页表假如虚拟地址有32位，页大小是4KB=4096字节，那么可以用12位来标识页中的每个字节。因此，可以用虚拟地址的低12位来定位页内字节，而剩下的位用来定位页。表2-233思考题在表2-2中，虚拟地址由12位字节偏移量和20位的虚拟页号组成。如果一个程序运行的系统上拥有这样的页大小和虚拟地址空间，这个程序有多少页？34转译后备缓冲区（TLB）尽管多个程序可以同时使用主存了，但使用页表会增加程序总体的运行时间。为了解决这个问题，处理器有一种专门用于地址转换的缓存，叫做转译后备缓冲区（TranslationLookasideBuffer，TLB）。35转译后备缓冲区(2)TLB在快速存储介质中缓存了一些页表的条目（通常为16～512条）。页面失效——假如想要访问的页不在内存中，即页表中该页没有合法的物理地址，该页只存储在磁盘上，那么这次访问称为页面失效（pagefault）。36指令级并行(ILP)指令级并行(InstructionLevelparallelism，ILP)通过让多个处理器部件或者功能单元同时执行指令来提高处理器的性能。37指令级并行(2)有两种主要方法来实现指令级并行：流水线和多发射。流水线——指将功能单元分阶段安排。多发射——指让多条指令同时启动。38流水线39流水线例子(1)举一个关于计算的例子，假如我们想要将浮点数9.87×104和6.54×103相加，我们可以使用如下步骤：40流水线例子(2)如果每次操作花费1纳秒,那么加法操作需要花费7纳秒for循环需要花费7000纳秒.41流水线例子(3)——另一个方案将浮点数加法器划分成7个独立的硬件或者功能单元。第一个单元取两个操作数，第二个比较指数，以此类推。假设一个功能单元的输出是下面一个功能单元的输入，那么加法功能单元的输出是规格化结果功能单元的输入。42流水线例子(4)——另一个方案43流水线例子(5)——另一个方案在时间5后，流水循环每1纳秒产生一个结果，而不再是每7纳秒一次。所以，执行for循环的总时间从7000纳秒降低到1006纳秒，提高了近7倍。44思考题2当讨论浮点数加法时，我们简单地假设每个功能单元都花费相同的时间。如果每个取命令与存命令都耗费2纳秒，其余的每个操作耗费1纳秒。a.在上述假设下，每个浮点数加法要耗费多少时间？b.非流水线1000对浮点数的加法要耗费多少时间？c.流水线1000对浮点数加法要耗费多少时间？45思考题2d.如果操作数/结果存储在不同级的内存层级上，那么取命令与存命令所要耗费的时间可能会差别非常大。假设从一级缓存上取数据/指令要耗费2纳秒，从二级缓存上取数据/指令要耗费5纳秒，从主存取数据/指令要耗费50纳秒。当执行某条指令，取其中一个操作数时，发生了一次一级缓存失效，那么流水线会发生什么情况？如果又发生二级缓存失效，又会怎样？46思考题2的答案a.b.9×1000=9000nanoseconds47思考题2的答案c.9+999×2=2019ns48思考题2的答案d.49多发射(1)多发射处理器通过复制功能单元来同时执行程序中的不同指令。adder#1adder#2z[0]z[2]z[1]z[3]for(i=0;i1000;i++)z[i]=x[i]+y[i];50多发射(2)静态多发射——如果功能单元是在编译时调度的，则称该多发射系统使用静态多发射动态多发射——如果是在运行时间调度的，则称该多发射系统使用动态多发射。一个支持动态多发射的处理器称为超标量(superscalar)。51预测（speculation）为了能够利用多发射，系统必须找出能够同时执行的指令。其中一种最重要的技术是预测（speculation）。在预测技术中，编译器或者处理器对一条指令进行猜测，然后在猜测的基础上执行代码。52预测(2)z=x+y;if(z0)w=x;elsew=y;Z应该是正数如果系统预测错误，需要回退机制，然后执行w=y.53硬件多线程指令级并行是很难利用的，因为程序中有许多部分之间存在依赖关系。硬件多线程(hardwaremultithreading)为系统提供了一种机制，使得当前执行的任务被阻塞时，系统能够继续其他有用的工作。例如，如果当前任务需要等待数据从内存中读出，那么它可以通过执行其他线程而不是继续当前线程来发掘并行性.54硬件多线程(2)细粒度(fine-grained)——在细粒度多线程中，处理器在每条指令执行完后切换线程，从而跳过被阻塞的线程。优点:能够避免因为阻塞而导致机器时间的浪费.缺点:执行很长一段指令的线程在执行每条指令的时候都需要等待.55硬件多线程(3)粗粒度(coarsegrained)——只切换那些需要等待较长时间才能完成操作（如从主存中加载）而被阻塞的线程。优点:不需要线程间的立即切换.缺点:处理器还是可能在短阻塞时空闲，线程间的切换也还是会导致延迟.56硬件多线程(4)同步多线程(SimultaneousMultithreading，SMT)——是细粒度多线程的变种。它通过允许多个线程同时使用多个功能单元来利用超标量处理器的性能。如果我们指定“优先”线程，那么能够在一定程度上减轻线程减速的问题。57并行硬件并行硬件58并行硬件因为有多个复制的功能单元，所以多发射和流水线可以认为是并行硬件。但是，这种并行性通常对程序员是不可见的，所以我们仍把它们当成基本的冯·诺依曼结构的扩展。我们的原则是，并行硬件应该是仅限于对程序员可见的硬件。换句话说，如果能够通过修改源代码而开发并行性或者必须修改源代码来开发并行性，那么我们认为这种硬件是并行硬件59Flynn分类法SISDSingleinstructionstreamSingledatastream(SI