The Wayback Machine - https://web.archive.org/web/20221028230713/https://baike.sogou.com/kexue/d10325.htm

外部存储器算法

编辑

在计算中，外部存储器算法或核心外算法是设计用来处理太大而不能一次装入计算机主存储器的数据的算法。这种算法必须进行优化，以便有效地获取和访问存储在慢速大容量存储器(辅助存储器)中的数据，例如硬盘或磁带驱动器，或者当存储器位于计算机网络上时。[1][2] 外部存储器算法在外部存储器模型中进行分析。

1 模型编辑

左侧的内部缓存有M/B块大小为B的数据，总大小为M。右侧的外部存储是无限的。

外部存储器算法是在一个被称为外部存储器模型(或输入/输出模型，或磁盘访问模型)的理想化计算模型中进行分析的。外部存储器模型是一个类似内存机器模型的抽象机器，但是除了主存储器之外还有一个高速缓存。该模型捕捉到这样一个事实，即高速缓存中的读写操作比主存储器中的快得多，并且读取长的连续块比使用磁盘读写头随机读取快得多。外部存储器模型中算法的运行时间由所需的内存读写次数来定义。[3] 该模型是由Alok Aggarwal 和 Jeffrey Vitter于1988年推出的。[4] 外部存储器模型与高速缓存无关模型相关，但是外部存储器模型中的算法可能知道块大小和高速缓存大小。因此，该模型有时被称为缓存感知模型。[5]

该模型由一个处理器组成，该处理器具有大小为M的内部存储器或高速缓存，连接到一个无界的外部存储器。内部和外部存储器都被分成大小为B的块。一个输入/输出或存储器传输操作包括将一个B连续元素块从外部移动到内部存储器，并且算法的运行时间由这些输入/输出操作的数量决定。[4]

2 算法编辑

外部内存模型中的算法利用了这样一个事实，即从外部内存中检索一个对象会检索整个大小的块  。这个属性有时被称为局部性。

在以下元素中搜索元素   对象在外部存储器模型中是可能的，使用带有分支因子的B树  。使用B树，可以在中实现搜索、插入和删除   时间(大0符号)。从理论上讲，这是这些操作可能的最小运行时间，所以使用B树是渐近最优的。[4]

外部排序是在外部内存设置中进行排序。外部排序可以通过分发排序(类似于快速排序)或通过  -方式合并排序。两种变体都实现了的渐近最优运行时间   分类 N 物体。这个界限也适用于外部存储器模型中的快速傅立叶变换。[2]

排列问题是重新排列   元素转换成特定的排列。这可以通过排序来完成，这需要上面的排序运行时，或者按顺序插入每个元素，而忽略局部性的好处。因此，置换可以在   时间到了。

3 应用程序编辑

外部存储器模型捕获存储器层次结构，其不在用于分析数据结构的其他常见模型(例如随机存取机)中建模，并且外部存储器模型对于证明数据结构的下限是有用的。该模型还可用于分析那些在内存中无法容纳的数据集上运行的算法。[4]

一个典型的例子是地理信息系统，特别是数字高程模型，其中整个数据集很容易超过几千兆字节甚至万亿字节的数据。

这种方法超越了通用处理器，还包括图形处理器计算和经典数字信号处理。在图形处理器上进行通用计算（GPGPU）中，使用小内存容量(与更熟悉的系统内存相比，后者通常简称为RAM)的强大显卡（GPUs）时，CPU到GPU的内存传输相对较慢(与计算带宽相比)。

参考文献

  • [1]

    ^Vitter, J. S. (2001). "External Memory Algorithms and Data Structures: Dealing with MASSIVE DATA". ACM Computing Surveys. 33 (2): 209–271. CiteSeerX 10.1.1.42.7064. doi:10.1145/384192.384193..

  • [2]

    ^Vitter, J. S. (2008). Algorithms and Data Structures for External Memory (PDF). Foundations and Trends in Theoretical Computer Science. Series on Foundations and Trends in Theoretical Computer Science. 2. Hanover, MA: Now Publishers. pp. 305–474. CiteSeerX 10.1.1.140.3731. doi:10.1561/0400000014. ISBN 978-1-60198-106-6..

  • [3]

    ^Zhang, Donghui; Tsotras, Vassilis J.; Levialdi, Stefano; Grinstein, Georges; Berry, Damon Andrew; Gouet-Brunet, Valerie; Kosch, Harald; Döller, Mario; Döller, Mario; Kosch, Harald; Maier, Paul; Bhattacharya, Arnab; Ljosa, Vebjorn; Nack, Frank; Bartolini, Ilaria; Gouet-Brunet, Valerie; Mei, Tao; Rui, Yong; Crucianu, Michel; Shih, Frank Y.; Fan, Wenfei; Ullman-Cullere, Mollie; Clark, Eugene; Aronson, Samuel; Mellin, Jonas; Berndtsson, Mikael; Grahne, Gösta; Bertossi, Leopoldo; Dong, Guozhu; et al. (2009). "I/O Model of Computation". Encyclopedia of Database Systems. Springer Science+Business Media. pp. 1333–1334. doi:10.1007/978-0-387-39940-9_752. ISBN 978-0-387-35544-3..

  • [4]

    ^Aggarwal, Alok; Vitter, Jeffrey (1988). "The input/output complexity of sorting and related problems". Communications of the ACM. 31 (9): 1116–1127. doi:10.1145/48529.48535..

  • [5]

    ^Demaine, Erik (2002). Cache-Oblivious Algorithms and Data Structures (PDF). Lecture Notes from the EEF Summer School on Massive Data Sets. Aarhus: BRICS..

阅读 34
版本记录

  • 暂无