计算机架构100问

ca中的100个问题

1. 如何创建计算机？ 1.1 能否在框图中构建计算机结构(画计算机datapath？） 1.2 从逻辑门的角度画计算机架构 1.3 指令的执行过程是什么？
2. 计算机是如何被控制的？(ISA)
3. 如何提高计算机的性能？ （pipelining -> data harzards -> forward, branch prediction, caches, and parallelism）
4. ISA有哪些分类(data operations, data transfers, sequencing)
5. processor execution model是指什么？（atomic, sequence，visible?）
6. program storage model指什么？
7. 计算机函数调用的过程是什么？(如何维护栈空间，caller saved register, callee saved register）
8. 常见的指令有哪些类型？（X86/ARM/JVM/PTX/PPC/SPARC）
9. 从哪些角度看指令？（Machine types, ISA classes, Addressing modes, Instruction width, CISC vs RISC） 10.如何从数据结构的角度理解？Address modes？

https://baike.baidu.com/pic/间接搜址/1035629/87adab44aed4f0621f7b71c8701a18bfb5d?fr=lemma#aid=1&pic=8718367adab44aed4f0621f7b71c8701a18bfb5d

11. basic machine types有哪些？（Memory-to-memory machines, register machines, 等)综合体等)
12. BASIC ISA classes有哪些？（Accumulator/GPR loadstore/GPR reg-mem/Stack/Comparison）
13. 问题11，每个ISA执行过程是什么，机器代表什么？
14. 指令宽度有哪些讲究？长指令和长指令有哪些优缺点？ARM/X86的指令长度是多少？
15. General purpose register machines dominate机器的优点是什么？
16. CISC 与 RISC ，从编译设计和硬件架构设计两个维度进行评论？
17. 请在图纸上画哪个？single-cycle处理器框图结构，描述不同类型指令的处理过程。
18. 请分析single-cycle处理器的最大速度瓶颈在哪里？
19. 清画出single-cycle处理器的门级电路结构，并说明跳转指令执行电路的关键设计。
20. mid-exam 问题需要一一完成。
21. single-cycle处理器是如何资源的？(大锅饭，大家都花同样的时间)
22. multi-cycle 如何改进处理器？
23. pipeline核心秘诀是什么？ （非pipeline是怎么浪费的？pipeline如何提高) 细粒度划分资源，避免浪费。
24. 为什么要pipeline？生活中有哪些例子(？
25. 从单一活动，从single-cyle到pipeline，如果保证latency不变，时钟频率如何变化？
26. pipeline处理器，对于单个事物latency它是如何影响的？
27. pipeline处理器对事物的吞吐率有什么影响？满载和非满载的吞吐率有什么区别？
28. pipeline处理器能跑多快？计算公式是什么？
29. pipeline的开销？ （需要register存储pipeline每个阶段的费用)
30. 现实中的pipeline会出现哪些问题？（stage长短不一，pipeline通常不满载，register开销大）
31. pipeline中存在那些冲突？（资源竞争，数据依赖，控制）
32. pipeline的RAW冲突中的情况如何？forwar能解决？ 什么样的情况？forward解决不了？ (米饭必须煮熟，如果米饭还没煮熟，也就是数据还没有生产出来，forward也无法解决）
33. WAR为什么会有冲突？pipeline中不存在？（WAR，读完前辈，后辈才能写)
34. pipeline为什么会有冲突？ISA承诺：sequential & atomic, ==> parallel & multi-cycle）
35. pipeline中hazards怎么检测？ (流水线每个环节都有一张表:那个指令？使用哪些资源？输入哪些信息？需要哪些资源。理论上，这张表可以完成hazard测试。或者改变维度，为每个指令建立一个表，运行到流水线环节，使用这些资源，需要这些资源，中间的结果等等。
36. 编译器插入nop指令，解决hazards方法有哪些缺点？(可移植性？ 更换处理器后的功能？性能？
37. branch hazards&data hazards有什么共同点？(一是依靠前面的计算结果，二是依靠前面的计算结果，但发生的阶段不同)
38. branch delay slot怎样克服？(思路1: 将slot使用时，执行与分制无关的指令； 思路2： 减少slot，加快决制决策； 思路3： 分支预测）
39. branch delay slot— 思路1有什么问题？ (如果流水线长(十几条流水线)，很难找到很多指令slot塞满）
40. 1-bit branch predictor与2-bit branch predictor本质区别？ (2-bit branch predictor更中庸，不急跳变，有状态观察)
41. branch predictor结构的实现是什么？（pc – valid — predict bits — branch target）
42. exception(non-normal)与interrupts(external)主要区别是？exception 与interrupts有哪些？ （exception: divide by zero/misaligned mem access/page fault/mem protect violation, interrupts: keyboard/disk drive ready/ arrival of network packet）
43. exception 与 interrupts有哪些类型？(synchronous/asynchronous, user request/coerced, maskable/non-maskable, within/between instructions, resume/terminate)
44. 手绘加法器(列出加法进位过程，绘制相应的抽象电路)
45. 如何优化加法进位路径长？ 算法有哪些？
46. 为什么要有补码，如何从十进制的角度理解补码？
47. 手绘乘法器(列出乘法的等式过程，并绘制相应的抽象电路)
48. 浮点数和定点数的优缺点？(精度、范围、误差？
49. 如何从可视化的角度理解浮点数？ 给定点数，如何手算转换为浮点数？
50. 精度计算中各种舍入方式的特点是什么？(rounding to zero/even… 四舍五入等。 (从误差积累的角度考虑…)
51. 小数加减乘定点数，列式子计算？ (类似于十进制，先忽略小数点，完成后一起算账)
52. 如何分别做浮点数的加减乘，列式子计算？ （加减，要对阶。乘除，位数的乘法，指数的加法）
53. leading zero算法？在什么场景下需要？ 它的作用是什么？(浮点数加减和浮点数乘除在哪个环节？leading zero算法）
54. 如何做十进制转二进制，手动列式子计算？
55. 如何做计算机除法？ 手动列式子计算？
56. 如何将定点数转化为浮点数？简述过程(如何用十进制比喻)
57. 如何将浮点数转换为定点数？简述过程(如何用十进制比喻)
58. 为什么要有计算机？alignment？能举个例子吗？(总线宽度/cacheLine/页表）
59. 为什么会引出传输？burst概念，如何提高效率？(批量传输，减少请求次数，即请求一次传输多个数据)何时使用？burst？（cache，DMA，访问压缩数据)
60. 为什么存在于传输中？OOO概念？(能做的先做，会做的slot使用)发送方在什么场景下产生OOO请求（RAW）？收到OOO应该做什么操作？（bucket sort）
61. 试着画储存树的结构？（processID->page->cache->bus->…）
62. 为什么指令在乱序执行后必须按顺序提交？在这些情况下，不能按顺序提交？在这些情况下，必须按顺序提交？(branch/exception/interrupt)
63. 访存（mem acc instruction/ load/store），从算法的角度看其实什么？（search）
64. cache能加速的依据是什么？（locality）cache对程序员的启发是什么？（程序访问数据时，要注意locality和alignment，locality和alignment好的程序性能高）
65. 把cache抽象成搜索算法后（每个line是一个村子），搜索目标是什么？（X省.X村.yy人，搜索对象是X省.X村，因为该村的所有人都在一个cacheLine中）搜索对象是什么？（cache中存在的所有村子），该搜索树长的是什么样子？请画出来。
66. cache抽象成搜索算法后，有那些搜索TAG算法？（linear, hash, linear+hash）
67. 从搜索算法角度，如何理解cache的淘汰算法？（搜索最老的，搜索用的最少的等等）
68. [那些外设]从容量/latency/throughput角度，罗列常见外设与接口？
69. [怎么连接]处理器与外设之间如何连接？（Buses, serial） 68.1 并行传输bus与串行传输的对比？ （并行：线间的skew/synchronization，线间的干扰，外界对线上的干扰[电容/电阻/电感]） （串行：无需同步，外界对线上的干扰，差分，校准，时钟恢复，均衡等）
70. 串行传输常见问题及解决方法？（校准，时钟恢复，均衡）
71. 处理器和外设如何交互？（I/O instruction, memory mapped, DMA）
72. 处理器和外设在什么时候交互？（polling， interrupts）。两者有什么特点？（polling比较快，但比较费； interrupts相比慢[需要OS参与，更慢]，但便宜）
73. polling和interrupts在系统层面的对立和统一？（polling， 在CPU底层也是interrupts）
74. interrupts从数据结构角度看，本质是什么?(是一个查表的过程，从中断号，到中断服务程序）
75. buses 和 serial的接收方的时钟分别怎么获取？（分别有什么优缺点，有什么开销？）
76. buses 与 serial的应用场景，发展趋势？（serial: off-chip, buses: on-chip. on-chip上address/data/req等解耦）
77. I/O 交互中，I/O instruction有什么优缺点？（费指令，指令译码代价大； 慢： 一次只访问一个register，cache/burst等无法发挥作用）
78. I/O 交互中，I/O memory address有什么优缺点？（cons: 占用memory空间； pros： 访问I/O与访问memory的指令归一化，电路简单）
79. I/O交互中，为什么引出DMA？（释放CPU数量）DMA应用场景中I/O交互类型是什么？DMA是如何工作的？（从哪里来，去哪里，多少东西？怎么干）
80. 通信中，出现冲突怎么办？（collision detect）重现错误怎么办？(差错控制)怎么发起通信？（master/slave）要不要主持人？(… …)
81. cache，mem中的address/port/bank的冲突分别是啥样的，画图表示？
82. cache set-associative架构中，set_id产生的哈希函数有那些？为什么常用异或运算？
83. mem address在计算cache tag(line in all space)/word in line/ byte in word中，是如何分工的？
84. 手写direct-mapped/set-associative/fully-associative软件模拟代码，硬件电路结构。评价这几种方式的优缺点。
85. 手写LRU/PLRU软件伪代码，硬件电路结构。评价几种方式的优缺点。 84.1 cache的容量怎么计算？ 84.2 cache的性能怎么度量？ 84.3 cache的miss率，容量和速度之间的大致曲线是怎样的？
86. write-through/ write-back的行为，优缺点？（WT:简单&慢，WB:复杂&快， WB需要维护valid/dirty等状态）今天主流的做法？（WB）write-back有什么要特别注意的？（flush？）
87. 请解释allocate-on-write? （根据locality原则，近期写过的，近期也会读。cacheLine是一层楼，目前写的只有一个房间，因此在allocate-on-write时，先要把这一层楼读回来，然后更新该房间，到此才算是一个新的楼层）
88. 为什么要把I-CACHE与D-CACHE分开？I-CACHE有什么特点？(RO, read on every cycle)
89. 为什么要引出virtual mem？ （1 物理的不够；2 物理的浪费(holes)； 3 物理的相互干扰） 89.1 32-bit的机器，供4GB，所有程序共4GB的空间，够用么？总空间不够了怎么办？程序间互相覆盖了怎么办？（每个程序都有4GB的虚拟空间） 89.2 ·
90. virtual mem的核心思想是什么？（Indirection） 89.1. virtual memory是怎么解决内存不够用的问题？这个方法的代价是什么？（映射到硬盘。该方法速度慢。） 89.2 virtual memory是怎么解决空洞问题？ （资源细分，然后见缝插针。这点思路像流水线提高CPU利用率。资源细化调度思路） 89.3 virtual memory是怎么解决程序安全的问题？（应用程序只管控虚拟地址，每个应用程序的MAP由操作系统管理，具体使用那些物理地址交给操作系统管理）
91. virtual memory是怎么工作的，基本流程如何？ 90.1 如果PA在DDR中，其流程是怎样的？（VA, VA->PA, 用PA从DDR中抓取数据） 90.2 如果PA不在DDR中，其流程是怎样的？（从DISK拿数据到DDR中，然后再从DDR中抓数据返回，同时刷新VA-PA的映射）
92. 最朴素的page table是怎样的？fine 与 coarse page table的优缺点？coarse page table在一个table内部是怎么寻址的？
93. 32-bit机器中，256M和8GB的两个情形下的ram，其映射过程是咋样的？这两种映射过程分别有什么特点（8GB中，ram有33位地址，空间比va大，一个程序用不完Pa，也是机器位宽拓展到64 bit原因）
94. page的walk through从搜索算法角度怎么看？（先搜在那个page，再搜在page内那个offset，层次化搜索）
95. page fault在什么情况下会产生？（page table指向diskl时，即该page不在DDR中，类似cache中的miss） 94.1 产生后的处理流程是怎样的？（向OS报告–>OS除旧–>OS迎新–>OS更新表–>OS返回。 除旧[如果page dirty，需要writeback]，迎新[新的读回来后要刷新映射表table]） 94.2 各个阶段分别花多长时间？（向OS报告100–>OS除旧4000w–>OS迎新4000w–>OS更新表1000–>OS返回10000）
96. page替换有哪些常见的算法？如何评价各个算法？ 95.1 page的替换算法与cache的替换算法在本质上有什么异同？
97. virtual address中，memory protection如何实现？（粗粒度看，映射到不同的page。映射到不同的PA ？ ） 96.0 page protetion flag是如何实现的，有哪些权限？权限越界时会发生什么？（细粒度看，映射到同一page，但权限有限制，r/rwx/COW（copy on write)/rx） 96.1 memory sharing如何实现？（两个程序的VA，映射到同一个PA） 96.2 linux 的program address space是如何实现的？（virtual space与physical space都是按照这个流程实现的么？Kernal/stack/libraries/heap/data/text） 96.3 什么是false sharing？ （共享同一个房间，但不是同一个床位）
98. 为什么需要TLB？（） 97.1 引入TLB后，整体的工作流程是什么样的？（这两个维度是完全相互独立的：TLB是否hit？ Page是否在RAM？）
99. Page Table 能不能放在disk中？（不能） 如果不能放在disk中，当程序过多时RAM不够用怎么办？如何能减少page table size？（fine -> coarse）
100. Page table Size能不能压缩？ 99.1 引入indirection为何能压缩省RAM？（level-1的一定放在RAM，level-2/3可以放在DISK中） 99.2 Multi-level page table核心思想是什么？ 99.3 Multi-level page table为什么具有可行性？（sparse memory） 99.4 从算法角度如何看Multi-level page? (树的剪枝) 100 PIPT, VIVT, VIPT各种架构的原理？ 优缺点？ （VIVT： 快，多进程之间无法共享虚拟cache； PIPT：慢，先必须查看TLB； VIPT：Virtually indexed, Physically tagged）