# M.3 存储层次结构与保护机制的发展（第 2 章和附录 B）
<!-- source: p1388 -->

计算技术的先驱们虽然已经认识到存储层次结构的必要性，并创造了这一术语，但自动管理两个存储层次的方案，最早由 Kilburn 等人［1962］提出，并在曼彻斯特大学的 Atlas 计算机上实现。这台计算机比 IBM 360 的发布早一年。IBM 原计划在下一代 System/370 中引入这一功能，但 1970 年的 TSS 操作系统未能胜任。370 系列于 1972 年宣布支持虚拟内存；translation lookaside buffer（TLB，快表）这个名称，也是为这台计算机创造的［Case 和 Padegs，<!-- source: p1389 -->1978］。在原文所述时期，只有少数超级计算机、嵌入式处理器和较老的个人计算机没有虚拟内存。

Atlas 和 IBM 360 都提供了页级保护，GE 645 则是第一个提供段页式管理的系统。更早的 Burroughs 计算机通过分段提供虚拟内存，类似于 Intel 8086 的分段地址方案。80286 是第一款具备附录 C 所述保护机制的 80x86 处理器，其设计受到 GE 645 上运行的 Multics 保护软件的启发。随着时间推移，计算机发展出更复杂的机制，其中最复杂的是 capability；它在 20 世纪 70 年代末至 80 年代初受到最广泛的关注［Fabry，1974；Wulf、Levin 和 Harbison，1981］。Wilkes［1982］是 capability 的早期研究者之一，他这样评价：

> 凡是参与过刚才所述这类系统［capability 系统］实现的人，或者尝试向别人解释它的人，大概都会觉得复杂性已经失控。尤其令人失望的是，capability 原本是可以自由传递的票据，这一诱人的想法已经不复存在……
>
> 与传统计算机系统相比，要提供一个保护域很小而且频繁变化的系统，必然要付出代价。这些代价将体现为额外的硬件、更慢的运行速度，以及更多的存储器占用。目前仍不能确定，采用 capability 方法能否将这些代价降低到合理的程度。［第 112 页］

原文撰写时，尽管人们对保护和安全越来越重视，操作系统界和计算机体系结构界对 capability 的兴趣却都已很少。

> **原文交叉引用说明：** 上文原书写作“附录 C”；本版有关虚拟内存与保护机制的说明位于附录 B。此处保留原文编号并注明其差异。

Bell 和 Strecker［1976］在回顾 PDP-11 时指出，地址空间过小，是唯一难以补救的体系结构错误。设计 PDP-11 时，磁芯存储器的容量增长十分缓慢。此外，当时还有约 100 家小型机公司参与竞争；如果每个地址都必须经过 16 位数据通路两次，DEC 的产品就可能失去成本竞争力。因此，设计者决定只比 PDP-11 的前代产品增加 4 个地址位。

IBM 360 的设计者清楚地址长度的重要性，计划将体系结构扩展到 32 位地址。不过，IBM 360 实际只使用了 24 位，因为在 1964 年，较长地址会使低端 360 型号进一步变慢。遗憾的是，设计者没有向软件人员透露这一计划，程序员在高 8 个“未使用”的地址位中存放额外信息，挫败了扩展尝试。20 年后，Apple 在 Motorola 68000 的 24 位地址上犯了类似错误；当后来的 68000 使用完整的 32 位虚拟地址时，Macintosh 就需要一种程序来判定应用是否“32-bit clean”，即能否正确使用完整的 32 位地址。<!-- source: p1390 -->此后的计算机几乎都会检查未使用的位是否确实保持未使用状态；如果这些位的值不正确，就触发陷入。

正如正文所述，系统虚拟机是 IBM 在研究虚拟内存的过程中率先提出的。IBM 第一台支持虚拟内存的计算机，是 1967 年推出的 IBM 360/67。IBM 研究人员编写了 CP-67 程序，使一台机器呈现出多台独立 360 计算机的假象。随后，他们又编写了运行在这些虚拟机上的交互式单用户操作系统 CMS。CP-67 后来发展为 VM/370 产品；在原文撰写时，IBM 为其大型机销售 z/VM［Meyer 和 Seawright，1970；Van Vleck，2005］。

Atlas 论文发表几年后，Wilkes 发表了第一篇阐述缓存概念的论文［1965］：

> 本文讨论这样一种用法：以一套容量约为 32,000 字的高速磁芯存储器，辅助一套容量约为一百万字的低速磁芯存储器，使实际应用中的有效访问时间更接近高速存储器，而不是低速存储器。［第 270 页］

这篇仅有两页的论文描述了直接映射缓存。它虽然是第一篇讨论缓存的公开论文，但最早的实现可能是剑桥大学建造的一种直接映射指令缓存。该缓存采用隧道二极管存储器，这是当时最快的存储器。Wilkes 说，缓存存储器的想法是 G. Scarott 提出的。

这篇论文发表后，IBM 启动了一个项目，最终造出了第一台采用缓存的商用计算机 IBM 360/85［Liptay，1968］。Gibson［1967］描述了如何从存储器流量和未命中率两方面测量程序行为，并展示了不同程序的未命中率差异。他以 20 个程序为样本，每个程序都有 300 万次访存，还使用平均存储器访问时间比较有缓存和无缓存的系统。这一先例已有 40 多年的历史，但直到 20 世纪 90 年代初，许多人仍在使用未命中率进行比较。

Conti、Gibson 和 Pitkowsky［1968］介绍了 360/85 的实际性能。在论文中的 11 个程序里，360/91 仅有 3 个程序优于 360/85，尽管 360/85 的时钟周期更长（80 ns 对 60 ns）、存储器交叉访问的路数更少（4 路对 16 路）、主存也更慢（1.04 微秒对 0.75 微秒）。这篇论文也是第一篇使用 cache 一词的论文。

其他研究者很快扩充了缓存领域的文献。Strecker［1976］发表了第一篇比较不同缓存设计的论文，研究 PDP-11 的缓存。Smith［1982］随后发表了一篇全面的综述，使用了空间局部性和时间局部性这两个术语，成为许多计算机设计者的参考资料。虽然大多数研究依赖仿真，Clark［1983］却使用硬件监测器，连续数天记录 VAX-11/780 的缓存未命中。Clark 和 Emer［1985］后来又比较了地址转换的仿真结果和硬件测量结果。

<!-- source: p1391 -->

Hill［1987］提出了附录 B 中用于解释缓存未命中的“三 C”分类。Jouppi［1998］回顾时说，Hill 的三 C 模型直接促成了他发明 victim cache：既利用较快的直接映射缓存，又避免冲突未命中的大部分代价。Sugumar 和 Abraham［1993］认为，三 C 模型中的基准缓存应该采用最优替换算法；这样既能消除基于最近最少使用（LRU）替换的未命中分类异常，也能将冲突未命中进一步划分为映射造成的未命中，以及非最优替换算法造成的未命中。

Kroft［1981］发表了最早讨论非阻塞缓存的论文之一。他后来解释说［Kroft，1998］，自己是 Control Data Corporation 第一位设计带缓存计算机的人；在将旧概念用于新机制时，他想到可以让双端口缓存在发生一次未命中之后，继续处理其他访问。

Baer 和 Wang［1988］开展了最早的一批多级包含性研究。随后，Wang、Baer 和 Levy［1989］发表了多级缓存性能评估的早期论文。再后来，Jouppi 和 Wilton［1994］提出了片上多级缓存的多级排他性方案。

除 victim cache 外，Jouppi［1990］还研究了利用流缓冲区进行预取的方法。Farkas、Jouppi 和 Chow［1995］扩展了这项工作，使流缓冲区能在按序处理器中与非阻塞 load 和推测执行良好配合。后来 Farkas 等人［1997］又表明，乱序处理器虽然更能容忍不可预测的延迟，仍能从流缓冲区中获益。他们还进一步优化了流缓冲区的存储器带宽需求。

20 世纪 90 年代的编译器与操作系统的体系结构支持研讨会（ASPLOS）及国际计算机体系结构研讨会（ISCA）论文集，充满了关于缓存的论文。事实上，有些爱开玩笑的人声称，ISCA 真正的全称是 International Cache Architecture Symposium，即“国际缓存体系结构研讨会”。

第 2 章采用了 Cantin 和 Hill［2001］收集的 SPEC2000 基准测量结果。该章还使用了其他若干论文的数据，并在相应图注中注明出处：Agarwal 和 Pudar［1993］；Barroso、Gharachorloo 和 Bugnion［1998］；Farkas 和 Jouppi［1994］；Jouppi［1990］；Lam、Rothberg 和 Wolf［1991］；Lebeck 和 Wood［1994］；McCalpin［2005］；Mowry、Lam 和 Gupta［1992］；Torrellas、Gupta 和 Hennessy［1992］。

## 参考文献

<!-- source: p1391 -->

1. Agarwal, A. [1987]. “Analysis of Cache Performance for Operating Systems and Multiprogramming,” Ph.D. thesis, Tech. Rep. No. CSL-TR-87-332, Stanford University, Palo Alto, Calif.

2. Agarwal, A., and S. D. Pudar [1993]. “Column-associative caches: A technique for reducing the miss rate of direct-mapped caches,” 20th Annual Int’l. <!-- source: p1392 --> Symposium on Computer Architecture (ISCA), May 16–19, 1993, San Diego, Calif. (Computer Architecture News 21:2 (May), 179–190).

<!-- source: p1392 -->

3. Baer, J.-L., and W.-H. Wang [1988]. “On the inclusion property for multi-level cache hierarchies,” Proc. 15th Annual Int’l. Symposium on Computer Architecture (ISCA), May 30–June 2, 1988, Honolulu, Hawaii, 73–80.

4. Barham, P., B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, and R. Neugebauer [2003]. “Xen and the art of virtualization,” Proc. of the 19th ACM Symposium on Operating Systems Principles, October 19–22, 2003, Bolton Landing, N.Y.

5. Barroso, L. A., K. Gharachorloo, and E. Bugnion [1998]. “Memory system characterization of commercial workloads,” Proc. 25th Annual Int’l. Symposium on Computer Architecture (ISCA), July 3–14, 1998, Barcelona, Spain, 3–14.

6. Bell, C. G., and W. D. Strecker [1976]. “Computer structures: What have we learned from the PDP-11?” Proc. Third Annual Int’l. Symposium on Computer Architecture (ISCA), January 19–21, 1976, Tampa, Fla., 1–14.

7. Bhandarkar, D. P. [1995]. Alpha Architecture Implementations, Digital Press, Newton, Mass.

8. Borg, A., R. E. Kessler, and D. W. Wall [1990]. “Generation and analysis of very long address traces,” Proc. 17th Annual Int’l. Symposium on Computer Architecture (ISCA), May 28–31, 1990, Seattle, Wash., 270–279.

9. Cantin, J. F., and M. D. Hill [2001]. “Cache performance for selected SPEC CPU2000 benchmarks,” http://www.cs.wisc.edu/multifacet/misc/spec2000cache-data/.

10. Cantin, J., and M. Hill [2003]. “Cache performance for SPEC CPU2000 benchmarks, version 3.0,” http://www.cs.wisc.edu/multifacet/misc/spec2000cache-data/index.html.

11. Case, R. P., and A. Padegs [1978]. “The architecture of the IBM System/370,” Communications of the ACM 21:1, 73–96. Also appears in D. P. Siewiorek, C. G. Bell, and A. Newell, Computer Structures: Principles and Examples, McGraw-Hill, New York, 1982, 830–855.

12. Clark, B., T. Deshane, E. Dow, S. Evanchik, M. Finlayson, J. Herne, and J. Neefe Matthews [2004]. “Xen and the art of repeated research,” Proc. USENIX Annual Technical Conf., June 27–July 2, 2004, Boston, 1135–1144.

13. Clark, D. W. [1983]. “Cache performance of the VAX-11/780,” ACM Trans. on Computer Systems 1:1, 24–37.

14. Clark, D. W., and J. S. Emer [1985]. “Performance of the VAX-11/780 translation buffer: Simulation and measurement,” ACM Trans. on Computer Systems 3:1 (February), 31–62.

15. Compaq Computer Corporation. [1999]. Compiler Writer’s Guide for the Alpha 21264, Order Number EC-RJ66A-TE, June.

16. Conti, C., D. H. Gibson, and S. H. Pitkowsky [1968]. “Structural aspects of the System/360 Model 85. Part I. General organization,” IBM Systems J. 7:1, 2–14.

17. Crawford, J., and P. Gelsinger [1988]. Programming the 80386, Sybex, Alameda, Calif.

18. Cvetanovic, Z., and R. E. Kessler [2000]. “Performance analysis of the Alpha 21264-based Compaq ES40 system,” Proc. 27th Annual Int’l. Symposium on <!-- source: p1393 --> Computer Architecture (ISCA), June 10–14, 2000, Vancouver, Canada, 192–202.

<!-- source: p1393 -->

19. Fabry, R. S. [1974]. “Capability based addressing,” Communications of the ACM 17:7 (July), 403–412.

20. Farkas, K. I., P. Chow, N. P. Jouppi, and Z. Vranesic [1997]. “Memory-system design considerations for dynamically-scheduled processors,” Proc. 24th Annual Int’l. Symposium on Computer Architecture (ISCA), June 2–4, 1997, Denver, Colo., 133–143.

21. Farkas, K. I., and N. P. Jouppi [1994]. “Complexity/performance trade-offs with non-blocking loads,” Proc. 21st Annual Int’l. Symposium on Computer Architecture (ISCA), April 18–21, 1994, Chicago.

22. Farkas, K. I., N. P. Jouppi, and P. Chow [1995]. “How useful are non-blocking loads, stream buffers and speculative execution in multiple issue processors?” Proc. First IEEE Symposium on High-Performance Computer Architecture, January 22–25, 1995, Raleigh, N.C., 78–89.

23. Gao, Q. S. [1993]. “The Chinese remainder theorem and the prime memory system,” 20th Annual Int’l. Symposium on Computer Architecture (ISCA), May 16–19, 1993, San Diego, Calif. (Computer Architecture News 21:2 (May), 337–340).

24. Gee, J. D., M. D. Hill, D. N. Pnevmatikatos, and A. J. Smith [1993]. “Cache performance of the SPEC92 benchmark suite,” IEEE Micro 13:4 (August), 17–27.

25. Gibson, D. H. [1967]. “Considerations in block-oriented systems design,” AFIPS Conf. Proc. 30, 75–80.

26. Handy, J. [1993]. The Cache Memory Book, Academic Press, Boston.

27. Heald, R., K. Aingaran, C. Amir, M. Ang, M. Boland, A. Das, P. Dixit, G. Gouldsberry, J. Hart, T. Horel, W.-J. Hsu, J. Kaku, C. Kim, S. Kim, F. Klass, H. Kwan, R. Lo, H. McIntyre, A. Mehta, D. Murata, S. Nguyen, Y.-P. Pai, S. Patel, K. Shin, K. Tam, S. Vishwanthaiah, J. Wu, G. Yee, and H. You [2000]. “Implementation of third-generation SPARC V9 64-b microprocessor,” ISSCC Digest of Technical Papers, 412–413 and slide supplement.

28. Hill, M. D. [1987]. “Aspects of Cache Memory and Instruction Buffer Performance,” Ph.D. thesis, Tech. Rep. UCB/CSD 87/381, Computer Science Division, University of California, Berkeley.

29. Hill, M. D. [1988]. “A case for direct mapped caches,” Computer 21:12 (December), 25–40.

30. Horel, T., and G. Lauterbach [1999]. “UltraSPARC-III: Designing third-generation 64-bit performance,” IEEE Micro 19:3 (May–June), 73–85.

31. Hughes, C. J., P. Kaul, S. V. Adve, R. Jain, C. Park, and J. Srinivasan [2001]. “Variability in the execution of multimedia applications and implications for architecture,” Proc. 28th Annual Int’l. Symposium on Computer Architecture (ISCA), June 30–July 4, 2001, Goteborg, Sweden, 254–265.

32. IEEE. [2005]. “Intel virtualization technology, computer,” IEEE Computer Society 38:5 (May), 48–56.

33. Jouppi, N. P. [1990]. “Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers,” Proc. 17th Annual <!-- source: p1394 --> Int’l. Symposium on Computer Architecture (ISCA), May 28–31, 1990, Seattle, Wash., 364–373.

<!-- source: p1394 -->

34. Jouppi, N. P. [1998]. “Retrospective: Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers,” in G. S. Sohi, ed., 25 Years of the International Symposia on Computer Architecture (Selected Papers), ACM, New York, 71–73.

35. Jouppi, N. P., and S. J. E. Wilton [1994]. “Trade-offs in two-level on-chip caching,” Proc. 21st Annual Int’l. Symposium on Computer Architecture (ISCA), April 18–21, 1994, Chicago, 34–45.

36. Kessler, R. E. [1999]. “The Alpha 21264 microprocessor,” IEEE Micro 19:2 (March/April), 24–36.

37. Kilburn, T., D. B. G. Edwards, M. J. Lanigan, and F. H. Sumner [1962]. “One-level storage system,” IRE Trans. on Electronic Computers EC-11 (April) 223–235. Also appears in D. P. Siewiorek, C. G. Bell, and A. Newell, Computer Structures: Principles and Examples, McGraw-Hill, New York, 1982, 135–148.

38. Kroft, D. [1981]. “Lockup-free instruction fetch/prefetch cache organization,” Proc. Eighth Annual Int’l. Symposium on Computer Architecture (ISCA), May 12–14, 1981, Minneapolis, Minn., 81–87.

39. Kroft, D. [1998]. “Retrospective: Lockup-free instruction fetch/prefetch cache organization,” in G. S. Sohi, ed., 25 Years of the International Symposia on Computer Architecture (Selected Papers), ACM, New York, 20–21.

40. Kunimatsu, A., N. Ide, T. Sato, Y. Endo, H. Murakami, T. Kamei, M. Hirano, F. Ishihara, H. Tago, M. Oka, A. Ohba, T. Yutaka, T. Okada, and M. Suzuoki [2000]. “Vector unit architecture for emotion synthesis,” IEEE Micro 20:2 (March–April), 40–47.

41. Lam, M. S., E. E. Rothberg, and M. E. Wolf [1991]. “The cache performance and optimizations of blocked algorithms,” Proc. Fourth Int’l. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), April 8–11, 1991, Santa Clara, Calif. (SIGPLAN Notices 26:4 (April), 63–74).

42. Lebeck, A. R., and D. A. Wood [1994]. “Cache profiling and the SPEC benchmarks: A case study,” Computer 27:10 (October), 15–26.

43. Liptay, J. S. [1968]. “Structural aspects of the System/360 Model 85. Part II. The cache,” IBM Systems J. 7:1, 15–21.

44. Luk, C.-K., and T. C Mowry [1999]. “Automatic compiler-inserted prefetching for pointer-based applications,” IEEE Trans. on Computers, 48:2 (February), 134–141.

45. McCalpin, J. D. [2005]. “STREAM: Sustainable Memory Bandwidth in High Performance Computers,” www.cs.virginia.edu/stream/.

46. McFarling, S. [1989]. “Program optimization for instruction caches,” Proc. Third Int’l. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), April 3–6, 1989, Boston, 183–191.

<!-- source: p1395 -->

47. Menon, A., J. Renato Santos, Y. Turner, G. Janakiraman, and W. Zwaenepoel [2005]. “Diagnosing performance overheads in the xen virtual machine environment,” Proc. First ACM/USENIX Int’l. Conf. on Virtual Execution Environments, June 11–12, 2005, Chicago, 13–23.

48. Meyer, R. A., and L. H. Seawright [1970]. “A virtual machine time sharing system,” IBM Systems J. 9:3, 199–218.

49. Mowry, T. C., S. Lam, and A. Gupta [1992]. “Design and evaluation of a compiler algorithm for prefetching,” Proc. Fifth Int’l. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), October 12–15, 1992, Boston (SIGPLAN Notices 27:9 (September), 62–73).

50. Oka, M., and M. Suzuoki [1999]. “Designing and programming the emotion engine,” IEEE Micro 19:6 (November–December), 20–28.

51. Pabst, T. [2000]. “Performance Showdown at 133 MHz FSB—The Best Platform for Coppermine,” www6.tomshardware.com/mainboard/00q1/000302/.

52. Palacharla, S., and R. E. Kessler [1994]. “Evaluating stream buffers as a secondary cache replacement,” Proc. 21st Annual Int’l. Symposium on Computer Architecture (ISCA), April 18–21, 1994, Chicago, 24–33.

53. Przybylski, S. A. [1990]. Cache Design: A Performance-Directed Approach, Morgan Kaufmann, San Francisco.

54. Przybylski, S. A., M. Horowitz, and J. L. Hennessy [1988]. “Performance tradeoffs in cache design,” Proc. 15th Annual Int’l. Symposium on Computer Architecture (ISCA), May 30–June 2, 1988, Honolulu, Hawaii, 290–298.

55. Reinman, G., and N. P. Jouppi. [1999]. “Extensions to CACTI.”

56. Robin, J., and C. Irvine [2000]. “Analysis of the Intel Pentium’s ability to support a secure virtual machine monitor,” Proc. USENIX Security Symposium, August 14–17, 2000, Denver, Colo.

57. Saavedra-Barrera, R. H. [1992]. “CPU Performance Evaluation and Execution Time Prediction Using Narrow Spectrum Benchmarking,” Ph.D. dissertation, University of California, Berkeley.

58. Samples, A. D., and P. N. Hilfinger [1988]. Code Reorganization for Instruction Caches, Tech. Rep. UCB/CSD 88/447, University of California, Berkeley.

59. Sites, R. L. (ed.) [1992]. Alpha Architecture Reference Manual, Digital Press, Burlington, Mass.

60. Skadron, K., and D. W. Clark [1997]. “Design issues and tradeoffs for write buffers,” Proc. Third Int’l. Symposium on High-Performance Computer Architecture, February 1–5, 1997, San Antonio, Tex., 144–155.

61. Smith, A. J. [1982]. “Cache memories,” Computing Surveys 14:3 (September), 473–530.

62. Smith, J. E., and J. R. Goodman [1983]. “A study of instruction cache organizations and replacement policies,” Proc. 10th Annual Int’l. Symposium on Computer Architecture (ISCA), June 5–7, 1982, Stockholm, Sweden, 132–137.

63. Stokes, J. [2000]. “Sound and Vision: A Technical Overview of the Emotion Engine,” http://arstechnica.com/hardware/reviews/2000/02/ee.ars.

<!-- source: p1396 -->

64. Strecker, W. D. [1976]. “Cache memories for the PDP-11?” Proc. Third Annual Int’l. Symposium on Computer Architecture (ISCA), January 19–21, 1976, Tampa, Fla., 155–158.

65. Sugumar, R. A., and S. G. Abraham [1993]. “Efficient simulation of caches under optimal replacement with applications to miss characterization,” Proc. ACM SIGMETRICS Conf. on Measurement and Modeling of Computer Systems, May 17–21, 1993, Santa Clara, Calif., 24–35.

66. Tarjan, D., S. Thoziyoor, and N. Jouppi [2006]. CACTI 4.0. Technical Report HPL-2006-86, HP Laboratories.

67. Torrellas, J., A. Gupta, and J. Hennessy [1992]. “Characterizing the caching and synchronization performance of a multiprocessor operating system,” Proc. Fifth Int’l. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), October 12–15, 1992, Boston (SIGPLAN Notices 27:9 (September), 162–174).

68. Van Vleck, T. [2005]. “The IBM 360/67 and CP/CMS,” http://www.multicians.org/thvv/360-67.html.

69. Wang, W.-H., J.-L. Baer, and H. M. Levy [1989]. “Organization and performance of a two-level virtual-real cache hierarchy,” Proc. 16th Annual Int’l. Symposium on Computer Architecture (ISCA), May 28–June 1, 1989, Jerusalem, 140–148.

70. Wilkes, M. [1965]. “Slave memories and dynamic storage allocation,” IEEE Trans. Electronic Computers EC-14:2 (April), 270–271.

71. Wilkes, M. V. [1982]. “Hardware support for memory protection: Capability implementations,” Proc. Symposium on Architectural Support for Programming Languages and Operating Systems (ASPLOS), March 1–3, 1982, Palo Alto, Calif., 107–116.

72. Wulf, W. A., R. Levin, and S. P. Harbison [1981]. Hydra/C.mmp: An Experimental Computer System, McGraw-Hill, New York.