Computation Structure

Parallel Processing 课程地址: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/c21/c21s1/ 本章讲的是各种并行方案. 并行 并行大体上有如下3种: 指令级并行(ILP) 数据级并行(DLP) 线程级并行(TLP) 指令级并行 指令级并行是让流行线的每个阶段尽可能同时执行多条指令. 数据级并行 数据级并行主要是指像向量加法这种计算, 天生就能拆开运算的! 只需要提供多个ALU就行了, 目前主要是由GPU来做. 线程级并行 首先介绍一下阿姆达尔定律: 一个线程就是在一个core上执行的计算任务. Using multiple independent cores to execute a parallel task is called thread-level parallelism (TLP), where each core executes a separate computation “thread”. 不同的Core之间是通过同一个main memory来交换数据(还有更高效的MPI), 而且每个core都有自己的cache. 为了保证数据的一致性, 在cache和内存之间也有一条bus来监测cache的变化和同步. 例如MESI protocal: https://en.wikipedia.org/wiki/MESI_protocol

System-level Communication 课程地址: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/c20/c20s1/ 本章主要讲的是系统间通信, 按现在来讲就是总线(BUS). 前面讲了很多硬核的物理知识, 证明了单一总线因为传输线反射的问题, 无法做到高频. 后面介绍了PCIe, 原来PCIe是受Network的启发, 也搞了一套点对点的通信协议, 跟网络一样分了几层, 数据也是包装成packet发出去. 跟网络一样, PCIe也可以有多种top, 比如环形, 树形等等.

Concurrency and Synchronization 课程地址: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/c19/c19s1/ 本章主要是讲进程间通信(IPC), 不过是从硬件的角度来看. IPC里面常用的信号量, 其实也只是在共享内存中存入了一个数字, 而所谓的lock, 也只是数量为1的semaphore. 但是如果不同core上的进程同时对同一个内存地址进行写操作的话, 会产生冲突吗? 这个貌似是内存或者总线去解决的, 目前还没找到具体实现, 先mark一下. IPC的一个重要问题是deadlock, 比如进程A和进程B: # 进程A wait(x) wait(y) # 进程B wait(y) wait(x) 当进程A执行完wait(x)后, 进程B被调度, 而且执行了wait(y), 显然这两个进程永远都无法结束. 一个比较直观而且简单的方案是对IPC中需要用到的信号量进行排序, 在进程wait时, 总是先wait顺序在前的信号量.

Devices and Interrupts 课程地址: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/c18/c18s1/ 本章引入外设, 讲解了round-robin调度算法的优缺点. 首先, “IO阻塞"的本质是什么? 当IO请求没有收到回复时, OS在调度到该进程时还是会继续执行等待IO的指令. 虽然每次调度到正在等待IO的进程也花不了多少条指令, 但还是要切换上下文啥的, 为了提高轮询的效率, 我们可以想办法让这些等待IO的进程不会被调度. 我们可以将进程分为不同的状态, 只有状态为0的进程可以被正常调度. 当进程开始等待IO时, 便用 sleep(id) 来改变进程的状态, 其中 id 相当于这个IO资源的标识符, 比如可以有多个进程都在等待键盘的输入. 当相应的IO时间响应后, 再根据这个id去恢复进程的状态. 加了状态的轮询调度感觉也挺合理的! 那么, 轮询能满足所有的任务吗? 当然是不能! 某些特殊的系统, 例如车载系统, 会有一些特别紧急的中断必须要优先执行, 比如紧急制动啥的. 按我们之前的设计, 中断都是在内核态中执行, 而内核态会禁用中断, 所以当需要紧急制动时, 巧好有一个耗时较长的中断在执行, 可能就会引发悲剧! 像这种每个中断都要及时响应或者在一定时间内执行完成的, 一般称为实时调度. 本章介绍了弱优先级抢占和强优先级抢占两种调度算法. 区别就是当前的中断是否能被高优先级的中断中断 (

Virtualizing the Processor 课程地址: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/c17/c17s1/ 本章讲了CPU的"虚拟化", 不过这里的"虚拟化"是指在同一个CPU上执行多个程序, 并且互不干扰, 重点当然就是虚拟内存和MMU啦. 现代CPU都在硬件上实现了内核态和用户态, 所以无法单纯靠软件来实现内核态和用户态的切换, 而是要靠CPU的中断来实现. 当Timer发起一个中断时, 我们调用OS的schedule程序来切换用户程序的上下文, 那么具体需要切换哪些内容呢? 常见的就是所有寄存器的内容, MMU的Context和Page Directory/Page Map的base pointer, 还有其他各种外设的状态等等, 比如该用户程序的输入应该在哪个tty. 这种代码+上下文+所有相关资源的集合便是一个进程(Process). 众所周知, OS提供的底层接口都是在内核态运行, 因为内核态不会受中断的干扰, 所以能够保持调度器一直能正常运行. 但是CPU是禁止程序从用户态直接转移到内核态的, 唯一的办法便是通过中断或者异常. 现代的CPU都运行设置部分中断和异常的Handler, 当用户态程序有中断或异常产生时, 便会跳转到相应的Handler去执行, 而且会无视用户态/内核态的区别. 所以, OS可以指定自己的异常处理Handler, 对于每一个系统调用, 都分配一个illegal-opcode就可以啦!

Virtual Memory 课程地址: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/c16/c16s1/ 本章主要讲了从硬盘加载数据到主存的策略, 从而引出了虚拟内存和页表. Extending the memory hierarchy Virtual Memory Page Map Translation look-aside buffer (TLB) Context Summary

Pipelining the Beta 课程地址: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/c15/c15s1/ 本章主要是讲如何讲前面做的Beta cpu流水线化, 以及如何解决流水线中会遇到的数据冲突/控制逻辑冲突等等. PS: 这章内容是真多 ( 流水线化 冲突 常见的冲突有两种,即数据冲突和控制逻辑冲突. 数据冲突是指当前指令需要的数据暂时还没有写回寄存器或者内存, 控制逻辑冲突是指当要跳转的指令的地址还没计算出来时, 下一个指令的地址应该是多少. 数据冲突 Strategy 1 - Stall Stall就是当指令运行到流水线的某一个阶段时, 如果检测到需要的数据还没有写回寄存器或者内存, 就在这个阶段阻塞住, 而且前面阶段的指令也要同时阻塞住, 阻塞的同时给下一阶段的IR寄存器输出NOP. Strategy 2 - Bypass 虽然每个指令只有在最后的Write Back阶段才会把数据写回寄存器或者内存, 但相关的值在前面的阶段就已经计算出来了, 所以可以直接把这些值bypass到可能需要的地方. 控制逻辑冲突 Stratege 1和2跟前面数据冲突的处理一样, 这里只记录一下第三个做法, 也就是分支预测. 分支预测 Exception and Interruption

Caches and the Memory Hierarchy 课程地址：https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/c14/c14s1/ 本章主要讲了SRAM、DRAM、Flash、HDD的原理和现代CPU的缓存架构。 存储设备 PS: 片上的存储设备一般都有bitline和wordline, wordline用来激活指定的存储单元，bitline用来读/写数据。 SRAM SRAM跟寄存器比较像，都是用正反馈是保持电压。 DRAM DRAM是使用电容来保持电压，体积更小，所以容量更大，但访问速度比SRAM慢，而且需要定时刷新存储的数据。 Flash Flash是使用MOSFET来存储数据，在栅极下加了一层绝缘体，讲电子导入绝缘体，然后根据绝缘体的带电大小来决定数据。 Hard Disk 硬盘（这里指机械硬盘）是用磁化来存储数据。 内存系统 在现代CPU的架构中，主存一般是速度相对较慢但是体积更小的DRAM组成。不过CPU不会直接跟主存交换数据，在中间可能会有其他几层SRAM来充当缓存，以降低内存的平均访问时间。 但从编程的角度看，有这样两种选择。一是完全隐藏缓存的细节，这样写程序时便可以把内存当成一个单独的设备使用；二是公开缓存细节，由programmer去决定哪些数据放在缓存，哪些放在主存。 现在除了超算，基本都是选择隐藏缓存的细节。 Cache策略 既然要隐藏缓存的细节，那么需要用硬件或者软件来自动控制哪些数据应该放在缓存，当缓存命中时，直接返回给CPU，未命中时，缓存应当自主去主存读数据然后缓存起来并返回给CPU. 下面来讨论一下具体的缓存策略. 前提 在模拟测试中, 可以发现这样一个事实: Direct-Mapped Full-Associative Set-Associative Policies Replacement Policies Write Policy Summary

Compilers 课程地址：https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/c11/ 本章就是讲了一些简单的编译原理的内容，内容比较简单，就不多记录了。 控制流图(CFG)是常用的IR

Procedures and Stacks 课程地址：https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/c12/c12s1/ 本章的主要内容是讲解了为什么需要Procedures和Stacks, 应该是第一次这么清晰的理解栈（ Procedures Procedures就是一组指令的集合，目的是为了重用指令，节约空间。当然，在高级变成语言里面都叫函数或者方法。 这里从汇编的角度来考虑如何实现Procedure, 一个最简单的办法是将Procedure在编译的时候展开，这样虽然重用了指令，但是并没有节省空间，而且无法递归调用！ 另一个比较好的做法是记录Procedure的开始位置，在需要调用的时候只需要把PC设置成Procedure的地址就可以了，这样即能重用指令，也能节省空间，还能递归调用！不过问题也随之而来，当Procedure运行完后，如何知道应该返回到哪里继续执行呢？Procedure所需要的参数该如何传递呢？ 首先，在执行分支指令的时候，会自动计算$PC + 4$并存在指定的寄存器，所以我们可以在Procedure里面拿到要返回的地址。其次，我们可以固定几个寄存器来传递参数，比如R3 ~ R6。这样做的话，似乎可以正确执行procedure, 但是，一旦有递归调用，那这些指定的寄存器都会被覆盖，当递归最后一层结束后返回上一层时，整个调用链就“断掉”了！ 而且，当procedure的参数变多时，寄存器根本不够用！ Stacks 有了上述的问题之后，让我们再来思考一下procedure的调用需要那些工作来完成。 首先我们需要知道Procedure的参数、返回值以及结束后PC的值，其次是procedure里面的局部变量应该存在哪里，因为在procedure执行完后，这些局部变量应该要被完全清除。我们的目标是在procedure执行过程中不会影响caller的数据，在执行完成后回到caller的时候，各个寄存器除了存放返回值的那个外，都应该是调用procedure前的状态！我们把这些在每次procedure调用时都需要记录的东西称为Activation Record。 下图演示了在递归调用时，Activation Record应该是如何变化的。 这不就是先进后出的Stack嘛！然后就是一系列的有关于Stack的定义了。 Stack frame 现在我们用Stack来解决之前的问题了！ 我们可以把procedure的参数，局部变量，以及procedure要使用的寄存器的内容都存到stack了！除此之外，我们还需要一些特殊的记录，比如procedure执行完后该返回的地址以及一个可以随时在栈中寻址的指针。然后，约定一个顺序来存这些数据就可以了！ 栈中一个procedure的相关数据都在连续的区块中，我们称这个区块为stack frame. 然后约定好caller和callee的职责，就可以开心地使用procedure啦！ Compile procedure 如下是将C的一个递归调用编译成汇编的例子。 Summary