关于三篇经典论文的总结

疫情原因，体系结构课程要求写三篇经典论文的读书报告。。

Amdahl’s Law

  十年前预言家们已经预言单处理机已经达到了它的限制，并且真正有意义的改进可以通过将多处理机相连来协作解决达到。处理机指的是以分离元件制造的计算机(冯诺依曼模型)。CPU=control+datapath(1971年Intel的4004将它们都做到了一个芯片上)。多处理机有两种连接方式：将多个通用目的计算机以多个存储器相连或者将多个专用的计算机以几何相关的存储器相连并由一个或多个指令流控制。这篇文章基于斯坦福大学商学院的研究数据，给出关于家务管理的例子。十年以来它的计算负载一直保持在占可执行指令的百分之四十，在特殊的环境下它能够减少到两倍，但是它根本不可能减少到三倍，因为顺序执行的指令不可能服从并行处理技术(有些是可以并行执行的，有些不可能去并行执行)。整体性能提升受五到七倍的上限限制。无论并行执行那一部分分配多少个处理机加速(并行执行那一部分时间可以缩到尽可能短，比顺序执行所需的时间还要短)，但总体运行时间还是得受限于顺序执行那一部分。如果家务管理部分是由单个处理机完成(占百分之四十)，非家务管理部分将会是家务管理部分性能的三到四倍。总的来说，通过上面举的例子，尽可能达到高度并行处理的速率的努力是白费的，除非顺序执行的速率也和并行执行那部分的速率达到同一个量级，这样整体的速率才能得到提高。

Slave Memories and Dynamic Storage Allocation

  文中fast core memory/slave memory指的是Cache，slow core memory指的是Main memory，Magnetic drums指的是磁盘。在这些系统中以块为单位和内存进行数据交换是高效的。如果仅仅是将block调到cache中却不使用是浪费的。Cache能够保证这些字在接下来的是可用的，而不是去以更长的时间访问主存。因为Cache的存储空间大小只是主存的一小部分，所以字不能一直保存在Cache中，需要使用一些算法来保证这些字被逐步地覆盖(组相联和全相联映射还需要考虑替换策略，即应用如LRU这样的替换算法)。在比较理想的情况下，一部分字能够在Cache中保持足够长的时间，起到明显的加速作用。Cache在现代处理器中又分为Instruction Cache和Data Cache，可以减少访问指令和数据的时间(不需要到低一级的存储器中去找)。如果指令出现在小的循环体中，因为局部性原理，就可以获得相当可观的访问速度。假设主存有32K个字，十六个地址位；Cache有32个字，五个地址位。Cache每个line/slot的长度等于主存数据的16个bits加上11个bits的标签字段。主存存储单元地址对32取余后，根据余数将存储单元内容放到对应Cache的插槽上，而存储单元地址的高11个bit作为Cache的tag字段，来区分映射到同一个插槽的是主存上的哪一个块。比如说主存的地址字段为$10259 = 320 \cdot2^5+19$，对32(字的数量)取余后结果为19，那么这个地址对应的存储单元的内容就会被放到Cache的19号插槽上对应的16bits的数据部分，地址中的tag字段为320。如果写操作发生了，会存在一致性的问题，就需要在写Cache的同时要写主存，这也就是write through策略。

  下面讨论应用更大的Cache(32K个插槽)的分时系统的应用场景，大量的用户程序在辅存中等待激活。为了支持进程之间的Isolation，需要引入分段机制。当一个程序被激活时，直到它已经完成或者处理I/O中断，或者是直到它的时间片被用尽的时候才切换到另一个程序。工作集的概念，每次程序被激活时不需要将所有块都调入Cache中，这样是浪费的，只需要调入需要用到的部分即可。在Cache中分别增加1bit的控制位(valid bit和dirty bit)。当基址寄存器中的内容切换时(意味着新的程序被激活了)，需要扫描Cache看是否存在不一致的问题(控制位会使得扫描过程完成得更快)。只有当valid bit和dirty bit同时为1时，才需要将当前的block写回到Main memory中，这也就是write back策略。可以将Cache划分为多个段，这需要提供多个base register，这也意味着Cache中有些部分可以是不允许被更改的，比如说系统经常需要用到的部分。假设有七个基址寄存器，每个寄存器表示主存中程序块的起始地址，那么在Cache中可以使用四个控制位。前三个bit用来标识使用的基址寄存器号(全0时表示字已经调入Cache中但还未被使用)，第四个bit是脏位。从表面上看，这种方案为两级核心存储系统提供了基础，又没有过高的硬件复杂度。

The Future of Microprocessors

  这篇文章分五部分对微处理器的发展过程进行阐述。

  现代计算机的微处理器的性能呈指数级增长主要归因于：随着时间的推移晶体管器件变得更快，以及因为集成电路上可容纳的晶体管数量的增加，硬件设计师能够利用更多的晶体管来从软件中获得更多的并行性。文章中提到说是从”软件”中提取并行性，我首先想到的是Data-Level Parallelism和Task-Level Parallelism，以及它们的底层实现，TLP(Thread-Level Parallelism)，每个core里都提供多个寄存器组和PC寄存器，这样就可以支持多线程来提高处理器的性能从而达到线程级并行。除此之外，比如ILP(Instruction-Level Parallelism)和DLP(Data-Level Parallelism)也同样可以提高处理器的性能。指令集并行可以通过流水线和多发射等技术，数据级并行可以通过支持向量寄存器(Vector Register)来达到数据级并行，这些并行都是软件程序员不可见的。因为向后兼容所带来的经济效益，导致这种抽象维护了几十年。随着时间的推移，CPU和主存的速度相差了三个数量级，随后Cache产生了，文中中还提到了寄存器是由编译器来管理的。

  在处理器内部还可以进行一些改进，比如说应用多发射技术(多发射又分为动态多发射和静态多发射)来增加每个时钟周期所发射的指令数(比如动态地查找在每个时钟周期并行执行的指令)，或者是将流水线细分为多个阶段来增加流水线的深度从而提高时钟频率。这些技术在程序员的角度，看不到重叠执行也看不到乱序执行。除此之外，程序员和编译器也可以通过调整指令的顺序或者是数据的分布，来高效地利用流水线或者是并行架构、Cache(局部性原理)。更重要的是，在这些改进之后，以前的代码仍然可以正确执行，只不过它们的运行速度低于峰值。

  很不幸的是，硬件设计师难以利用这些技术来提高现代处理器的速度了。因为指令流在指令之间只存在有限数量的并行指令，因此超标量处理器在超过4发射之后就很难在大多数应用中带来性能的提升了。从文章图2中看出ILP最近几年的性能提高趋于缓和了。另外，超标量处理器每个时钟周期内利用多条指令将会非常昂贵，因为需要额外复杂的逻辑来动态地找到并行的指令，这样的复杂度大约和同时发射的指令数的平方成正比。类似地，因为流水线阶段更细地划分，一个阶段甚至无法执行简单的两个整型数相加的指令。此外硬件电路的开销，比如增加的流水线寄存器以及转发部件，或者是增加的多路选择器，这样的开销甚至都超过了30级以上流水线带来的性能提升(tradeoff)。以及包括只有少量研究这些技术的大公司才能支付得起薪水来雇佣足够的工程师。所以，这些因素在一定程度上减缓了处理器性能的发展。

  因为能耗的限制，传统的处理器开发基本上已经停止。Dennard’s Law指出随着设备尺寸的减小，能耗也会下降。在这种情况下，较小的晶体管运行功耗更低。图3展示了因为硬件设计师使用更多晶体管来改进流水线和多发射技术，并以更高的速率切换它们，导致处理器功耗呈指数级增长。但是冷却技术(比如说散热器)并没有能耗增长的速率那么快，照这样下去下一代微处理器就得使用经济上不实用的水冷技术了。因为种种因素对处理器发展的限制，使得Intel和AMD这样主要的处理器制造商调整他们的营销重点，而不是仅仅是时钟频率(同学们在购买电脑的时候应该会注意到，早些年这些主要的制造商主要营销点是处理器的时钟频率的提高)。从微处理器的市场划分的角度，来对它们的性能需求进行研究，进而引出了下一个主题，带宽性能的提升。

  大多数多处理器使用同一个总线相连或者是共享主存等资源，相比较于传统的单处理器，多处理器所需要的功耗更小。因为多个核能够共享硬盘、存储器这样的大元器件以及功耗的供给。因为互联网的发展，数据中心的压力越来越大，尽管将服务器改造成多核以及使它们共享耗电的组件，这些短期的解决方案引出了CMP(Chip Multiprocessor)的发展。CMP将多个传统的超标量处理器整合到一个die上(减少了容量)。在同一个die上的处理器可以共享单个连接系统外的总线，减少了功耗。在要求高吞吐量的服务器中延迟不是关键因素(“latency is unimportant”)，基于CMP的系统设计可以利用这种情况来更进一步地减少功耗。比如使用两路的CMP来代替单处理器，可以得到两倍的吞吐率，但时钟频率慢了一半(相比于单处理，多处理器需要两倍的时间去处理请求)。请求处理时间主要取决于内存和外存性能的限制，而不只是处理器的性能。因为两个请求可以同时处理，整体的吞吐量将会与原来一致(可能出现一些对主存或者磁盘资源的争用)或者更好。通过将单处理器替换成CMP，性能与原来相同，或者变的稍微好一些了(这样的调整仍然能带来好处)。需要注意的是，降低时钟频率意味着降低了能耗(2-way CMP的能耗降低了大约一半，因为能耗和电压的平方成正比，1/4能耗就等于一半电压的平方)！不过这种下降仍然会受到静态损耗和底层晶体管的最低电压的限制。

  典型的服务器的工作负载通常只有少量的指令集并行和Memory stall(这与老师上课提到的影响流水线性能的六个因素相关)，因此大多数与超标量相关的硬件就浪费了。但是利用CMP能充分利用每个core来达到请求级并行，这也是H&P中提到的RLP(Request-Level Parallelism)。可以通过在每个core内部增加多个寄存器组和PC寄存器，应用multithreading技术来获得更高的吞吐量(同时意味着处理请求需要更长的时延)。比如说当前thread在等待I/O时，处理器可以切换到另一个thread去执行，这样在memory stall时执行计算以及同时执行多个内存访问，获得的好处远远超过了系统上较长的请求时延。因为可能涉及到对处理器核的争用，thread的请求时延通常会长一些。Intel的Hyperthreading技术允许两个threads共享多个核。

  许多应用的性能是根据单个任务执行的时延来决定的而不是多个本质上不相关任务的高吞吐量。事实上，大多数用户更关心命令行的响应速度而不是他们的计算机能同时处理多个命令的能力；对于许多计算能力受限的应用，比如模拟和编译，程序员更在意的是程序的执行时间而不是有多少任务在并行执行。在过去，处理器之间的通信非常慢，因此对于程序员来说确保线程在独立的处理器上运行时减少处理器的相互通信很重要(这部分课程往往在研究生级别才会开设，需要程序员投入大量的时间和精力来并行化程序。但在大多数情况下程序员往往只是希望下一代单处理器能够出现并加速他们的程序，而不是投入精力来并行化他们的程序)。结果是多处理器很难与单处理器竞争，除非在非常大的系统中。随着”free”技术(超标量，流水线)带来的性能提升被耗尽，为了提高单个程序的性能，程序员必须切换到更多的并行编程模型来获得更高的性能。只有三个维度的性能提升超越了摩尔定律：时钟频率，超标量指令发射，多处理器(前两个已经受限了)。

  从多芯片系统切换到CMP大大简化了并行编程的问题，多芯片系统线程之间的通信开销需要几百甚至几千个时钟周期，而CMP中共享在Chip中的Cache，每个线程之间通信只需非常少的时钟周期。通信时延减少了，但程序员仍然需要保证内部线程的同步，避免出现死锁或者是不正确的结果。增加支持事务的硬件或者是增加缓冲逻辑(只适用于紧耦合的并行机器)，可以使得应用程序的并行变得更简单。这种并行的转变应该适用于”典型”的程序员而不是只限制在研究生级别的程序员。

  处理器家族的每一代成员只需要增加额外的主题或者在原来的基础上做一些修改即可，而不需要去重新设计处理器核的逻辑，系统主板也只需要做微调。随着CMP的规模增加，主板需要去处理更高的I/O带宽的需求。同样的工程也可以分摊到处理器家族中，比如只需改变处理器数量和时钟频率就可以让相同的硬件以不同的价格或者性能运行。这就是硬件的优势。

  向CMP转变是无法避免的，这种转变不会更改基本的冯诺依曼模型。直到软件工业完全接受并行编程时，这些结构的优势才能被最大化地利用起来。多处理器编程比单处理器更复杂，需要理解新的计算原理、算法和编程工具。

References

• [1] “Validity of the single processor approach to achieving large scale computing capabilities” by DR. GENE M. AMDAHL
• [2] “Slave Memories and Dynamic Storage Allocation” by M. V. WILKES
• [3] “The Future Of Microprocessors” by KUNLE OLUKOTUN AND LANCE HAMMOND, STANFORD UNIVERSITY