B-деревья без явного задания параметров кэша

Материал из WEGA
Перейти к навигации Перейти к поиску

B-деревья без явного задания параметров кэша — Cache-oblivious B-trees

Ключевые слова и синонимы

Деревья поиска без явного задания параметров кэша; словари без явного задания параметров кэша

Постановка задачи

Память в компьютерах устроена иерархическим образом, причем время доступа к каждому уровню значительно различается. Таким образом, скорость доступа зависит исключительно от того, на каком самом внутреннем уровне находятся данные, к которым осуществляется доступ. При анализе работы алгоритмов стандартная RAM-модель (или модель фон Неймана) не способна воспроизвести этот эффект; поэтому для более точного моделирования ситуации были введены модели с внешней памятью. Чаще всего в качестве такой модели используется модель ввода-вывода [1], также называемая моделью внешней памяти или моделью обращений к диску. Модель ввода-вывода аппроксимирует иерархию памяти при помощи моделирования двух уровней, из которых внутренний уровень имеет размер M, внешний имеет неограниченный размер, а перенос данных между уровнями осуществляется блоками по B последовательных элементов. Стоимость алгоритма равна количеству выполняемых им переносов содержимого памяти.


Модель памяти без явного задания параметров кэша, предложенная Фриго и др. [18], изящно обобщает модель ввода-вывода на многоуровневую модель, обладающую следующим свойством: алгоритм не может знать значения B и M. Более точно, алгоритм без явного задания параметров кэша представляет собой алгоритм, формулируемый в рамках RAM-модели, но анализируемый в рамках модели ввода-вывода, причем анализ будет действительным при любых значениях B и M. Предполагается, что замещение содержимого кэша выполняется автоматически при помощи оптимальной автономной стратегии замещения. Поскольку анализ является допустимым при любых значениях B и M, он выполняется для всех уровней одновременно.


Мы будем рассматривать эффективные структуры данных без явного задания параметров кэша для задачи упорядоченного словаря, т.е. задачи хранения элементов с ключами из упорядоченной совокупности с поддержкой поиска, вставки, удаления и поиска в нужном диапазоне. В самом общем случае поиск представляет собой поиск предшественника, возвращающий элемент с максимальным ключом, меньшим или равным искомому ключу.

Основные результаты

Первый словарь без явного задания параметров кэша предложил Прокоп [21], который показал, как расположить статическое бинарное дерево в памяти таким образом, чтобы поиск занимал [math]\displaystyle{ O(log_B \; n) }[/math] переносов содержимого памяти. Это расположение, часто называемое расположением ван Эмде Боаса (Van Emde Boas layout) из-за того, что оно напоминает классическую структуру данных дерево ван Эмде Боаса (Van Emde Boas tree, vEB tree), также гарантирует, что поиск в диапазоне занимает [math]\displaystyle{ O(log_B \; n + k/B) }[/math] переносов содержимого памяти [2], где k – размер выходного значения. Обе границы являются оптимальными для поиска на основе сравнения.


Первый динамический словарь без явного задания параметров кэша был предложен Бендером и др. [10]. Используя вариант расположения ван Эмде Боаса, алгоритм управления плотностью Итая и др. [10] и сбалансированные по весам B-деревья [5], авторы пришли к следующим результатам:


Теорема 1 ([10]). Существует структура словаря без явного задания параметров кэша, поддерживающая поиск за [math]\displaystyle{ O(log_B \; n) }[/math] переносов содержимого памяти, а вставку и удаление – за амортизированные [math]\displaystyle{ O(log_B \; n) }[/math] переносов содержимого памяти.


Теорема 2 ([10]). Существует структура словаря без явного задания параметров кэша, поддерживающая поиск за [math]\displaystyle{ O(log_B \; n) }[/math] переносов содержимого памяти, вставку и удаление – за амортизированные [math]\displaystyle{ O(log_B \; n + (log^2 \; n)/B) }[/math] переносов, а поиск в диапазоне – за [math]\displaystyle{ O(log_B \; n + k/B) }[/math] переносов, где k – размер выходного значения.


Позднее Бендер и др. [7] разработали структуру без явного задания параметров кэша для поддержки связанных списков, обеспечивающую вставку и удаление элементов за O(1) переносов содержимого памяти, а сканирование k последовательных элементов – за амортизированные O(k/B) переносов. Объединив эту структуру со структурой из теоремы 1, можно получить следующий результат.


Теорема 3 ([7, 10]). Существует структура словаря без явного задания параметров кэша, поддерживающая поиск за [math]\displaystyle{ O(log_B \; n) }[/math] переносов содержимого памяти, вставку и удаление – за амортизированные [math]\displaystyle{ O(log_B \; n) }[/math] переносов, а поиск в диапазоне – за амортизированные [math]\displaystyle{ O(log_B \; n + k/B) }[/math] переносов, где k – размер выходного значения.


Был предложен длинный список расширений базовой структуры словаря без явного задания параметров кэша.


Бендер и др. [11], а также Бродал и др. [16] предложили довольно близкие идеи для воспроизведения результата теоремы 2, однако использовали значительно более простые структуры вместо сбалансированных по весам B-деревьев. На базе экспоненциальных деревьев Бендер и др. [8] предложили вариант, поддерживающий запросы и обновления за [math]\displaystyle{ O(log_B \; n) }[/math] переносов в худшем случае. Они также предложили решение с частичной устойчивостью, в котором поиск (во всех версиях структуры) и обновление (в последней версии структуры) требовали амортизированные [math]\displaystyle{ O(log_B (m + n)) \; }[/math] переносов содержимого памяти, где m – количество версий, а n – количество элементов в версии, находящейся в данный момент в работе. Бендер и др. [14] расширили модель без явного задания параметров кэша на параллельный вариант и сформулировали три предложения по использованию B-деревьев без явного задания параметров кэша в этом варианте. Бендер и др. [12] предложили структуры словаря без явного задания параметров кэша, использующие компромисс между более быстрой операцией вставки и более медленным поиском. Франческини и Гросси [17] показали, как добиться стоимости запросов и обновлений [math]\displaystyle{ O(log_B \; n) }[/math] в худшем случае, используя O(1) дополнительной памяти помимо той, что требуется для хранения n элементов. Были представлены расширения словаря на другие типы данных – такие как строки [13, 15] и геометрические данные [3, 4, 6].


Было показано [9], что наилучная возможная мультипликативная константа в границе поиска [math]\displaystyle{ \Theta(log_B \; n) }[/math] для поиска на основе сравнения различается в модели ввода-вывода и в модели без явного задания параметров кэша.

Применение

Словари решают фундаментальную проблему структурирования данных, являясь компонентом решений исключительно высокого числа вычислительных задач. Словари для внешней памяти полезны в ситуациях, когда основное время выполнения тратится на обращения к памяти; словари без явного задания параметров кэша выделяются среди других своей способностью оптимизировать доступ ко всем уровням неизвестной иерархии памяти. Это может пригодиться, например, при разработке программ, которые будут работать на различных или неизвестных архитектурах (таких как библиотечные програмы или программы для гетерогенных распределенных вычислений – например, сетевых коллективных вычислений и проектов наподобие SETI@home). Даже на единственной и известной архитектуре параметры памяти, доступные вычислительному процессу, могут быть непостоянными, если несколько процессов конкурируют за одни и те же ресурсы памяти. Поскольку алгоритмы без явного задания параметров кэша оптимизированы для всех значений параметров, они потенциально способны лучше адаптироваться к подобным изменениям, а также к различным размерам входных данных, вынуждающих использовать различные уровни памяти.

Открытые вопросы

Для обсуждаемой задачи упорядоченного одномерного словаря один из важных открытых вопросов касается поиска структуры данных, обеспечивающей все перечисленные в теореме 3 границы для худшего случая.

Экспериментальные результаты

Словари без явного задания параметров кэша эмпирически рассматривались в работах [11, 13, 16, 20, 22]. В целом считается, что методы без явного задания параметров кэша легко могут превзойти по эффективности RAM-алгоритмы, хотя иногда не в такой степени, как алгоритмы, специально приспособленные для конкретной иерархии памяти и размера задачи. С другой стороны, алгоритмы без явного задания параметров кэша хорошо работают на всех уровнях иерархии памяти, а также более устойчивы к изменению размеров задач.

См. также

Литература

1. Aggarwal, A., Vitter, J.S.: The Input/Output complexity of sorting and related problems. Commun. ACM 31(9), 1116-1127 (1988)

2. Arge, L., Brodal, G.S., Fagerberg, R.: Cache-oblivious data structures. In: Mehta, D., Sahni, S. (eds.) Handbook on Data Structures and Applications. CRC Press, Boca Raton (2005)

3. Arge, L., Brodal, G.S., Fagerberg, R., Laustsen, M.: Cache-oblivious planar orthogonal range searching and counting. In: Proc. 21st ACM Symposium on Computational Geometry, pp. 160-169. ACM, New York (2005)

4. Arge, L., de Berg, M., Haverkort, H.J.: Cache-oblivious R-trees. In: Proc. 21st ACM Symposium on Computational Geometry, pp. 170-179. ACM, New York (2005)

5. Arge, L., Vitter, J.S.:Optimal external memory interval management. SIAM J. Comput. 32(6), 1488-1508 (2003)

6. Arge, L., Zeh, N.: Simple and semi-dynamic structures for cache-oblivious planar orthogonal range searching. In: Proc. 22nd ACM Symposium on Computational Geometry, pp. 158-166. ACM, New York (2006)

7. Bender, M., Cole, R., Demaine, E., Farach-Colton, M.: Scanning and traversing: Maintaining data for traversals in a memory hierarchy. In: Proc. 10th Annual European Symposium on Algorithms. LNCS, vol. 2461, pp. 139-151. Springer, Berlin (2002)

8. Bender, M., Cole, R., Raman, R.: Exponential structures for cache-oblivious algorithms. In: Proc. 29th International Colloquium on Automata, Languages, and Programming. LNCS, vol. 2380, pp. 195-207. Springer, Berlin (2002)

9. Bender, M.A., Brodal, G.S., Fagerberg, R., Ge, D., He, S., Hu, H., Iacono, J., Lopez-Ortiz, A.: The cost of cache-oblivious searching. In: Proc. 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 271-282. IEEE Computer Society Press, Los Alamitos (2003)

10. Bender, M.A., Demaine, E.D., Farach-Colton, M.: Cache-oblivious B-trees. SIAM J. Comput. 35(2), 341-358 (2005). Conference version appeared at FOCS (2000)

11. Bender, M.A., Duan, Z., Iacono, J., Wu, J.: A locality-preserving cache-oblivious dynamic dictionary. J. Algorithms 53(2), 115-136 (2004). Conference version appeared at SODA (2002)

12. Bender, M.A., Farach-Colton, M., Fineman,J.T., Fogel,Y.R., Kuszmaul, B.C., Nelson, J.: Cache-oblivious streaming B-trees. In: Proc. 19th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 81-92. ACM, New York (2007)

13. Bender, M.A., Farach-Colton, M., Kuszmaul, B.C.: Cache-oblivious string B-trees. In: Proc. 25th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 233-242. ACM, New York (2006)

14. Bender, M.A., Fineman, J.T., Gilbert, S., Kuszmaul, B.C.: Concurrent cache-oblivious B-trees. In: Proc. 17th Annual ACM Symposium on Parallel Algorithms, pp. 228-237. ACM, New York (2005)

15. Brodal, G.S., Fagerberg, R.: Cache-oblivious string dictionaries. In: SODA: ACM-SIAM Symposium on Discrete Algorithms, pp. 581-590. ACM Press, New York (2006)

16. Brodal, G.S., Fagerberg, R., Jacob, R.: Cache-oblivious search trees via binary trees of small height. In: Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 39-48 ACM, New York (2002)

17. Franceschini, G., Grossi, R.: Optimal worst-case operations for implicit cache-oblivious search trees. In: Proc. Algorithms and Data Structures, 8th International Workshop, WADS. LNCS, vol. 2748, pp. 114-126. Springer, Berlin (2003)

18. Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 285-298. IEEE Computer Society Press, Los Alamitos (1999)

19. Itai, A., Konheim, A.G., Rodeh, M.: A sparse table implementation of priority queues. In: Automata, Languages and Programming, 8th Colloquium. LNCS, vol. 115, pp. 417-431. Springer, Berlin (1981)

20. Ladner, R.E., Fortna, R., B.-Nguyen, H.: A comparison of cache aware and cache oblivious static search trees using program instrumentation. In: Experimental Algorithmics. LNCS, vol. 2547, pp. 78-92. Springer, Berlin (2000)

21. Prokop, H.: Cache-oblivious algorithms. Master's thesis, Massachusetts Institute of Technology (1999)

22. Rahman, N., Cole, R., Raman, R.: Optimised predecessor data structures for internal memory. In: Proc. Algorithm Engineering, 5th International Workshop, WAE. LNCS, vol. 2141, pp. 67-78. Springer, Berlin (2001)

Источник — http://pco.iis.nsk.su/wega/index.php?title=B-деревья_без_явного_задания_параметров_кэша&oldid=15643