外部存储器

将两个数字相加需要多长时间？作为最常用的指令之一，add本身的执行只需要一个周期。因此，如果数据已经加载到寄存器中，它只需要一个周期。

但在一般情况下（*c = *a + *b），我们需要先从内存中获取其操作数：

mov eax, DWORD PTR [rsi]
add eax, DWORD PTR [rdi]
mov DWORD PTR [rdx], eax

当你从内存中获取任何东西时，数据到达之前总是有一些延迟。此外，访存请求并不直接去到其最终的存储位置，而是首先要通过一个复杂的系统，包括地址转换单元和缓存层，这个系统旨在帮助内存管理并减少延迟。

因此，这个问题唯一正确的答案是“看情况”——主要取决于操作数存储的位置：

如果数据存储在主内存（RAM）中，这就需要大约~100ns，或者大约200个周期，来获取它，然后需要另外200个周期来写回。
如果它最近被访问过，它可能已经被缓存（cached）了，获取它的时间会变少，这取决于它多久之前被访问 —— 若数据在最慢的缓存层中，这可能需要大约50个周期，若数据在最快的缓存层中，则可能只需要4-5个周期。
但是，它也可能存储在某种类型的外部存储器（external memory），比如硬盘上，在这种情况下，它需要大约5ms，或者大约 $10^7$ 个周期（！）来访问它。

存储性能的高方差是由于存储硬件并不像CPU芯片那样遵循半导体缩放定律（laws of silicon scaling）导致的。尽管存储仍然通过其他方式在改进，但如果说50年前，存储时间与指令延迟大致处于同一规模，那么现在它已经远远落后了。

为了减少其限制性影响，现代存储系统正变得越来越“分层”，其中较高层会牺牲一部分容量以减少延迟。由于这些特性在层之间可能会有数量级的变化 - 尤其是外部存储类型 - 因此，对许多内存密集型算法而言，在其它任何优化操作之前优化他们的I/O操作变得至关重要。

这促使了一种新的成本模型的创建，叫做外部存储器模型（external memory model），其唯一的基本操作是数据块的读取和写入，其他任何仅涉及有限大小本地存储的数据操作都是零成本的。这催生了一个新领域——外部存储算法（external memory algorithms），我们将在本章中学习。