Модель ввода-вывода

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

Модель внешней памяти; модель обращений к диску

Определение

Модель ввода-вывода рассматривает компьютер, состоящий из процессора, внутренней памяти (RAM) и внешней памяти (диск) (рис. 1). Внутренняя память имеет ограниченный размер и способна хранить M элементов данных. Внешняя память имеет потенциально неограниченный размер и разделена на блоки, содержащие по B последовательных элементов данных. Все вычисления производятся над данными во внутренней памяти. Данные записываются во внутреннюю память и переписываются обратно во внешнюю память при помощи операций ввода-вывода, явно выполняемых алгоритмом. Каждая подобная операция читает или записывает один блок данных из внешней памяти или в нее. Сложностью алгоритма в данной модели считается количество операций ввода-вывода.

Рис. 1. Модель ввода-вывода: CPU = процессор, Memory = память, Disk = диск

Рис. 2. Модель с параллельными дисками

Модель с параллельными дисками (parallel disk model, PDM) [10] представляет собой расширение модели ввода-вывода, в которой внешняя память состоит из [math]\displaystyle{ D \ge 1 \; }[/math] параллельных дисков (рис 2). В этой модели отдельная операция ввода-вывода может читать или записывать до D независимых блоков, если все они располагаются на разных дисках.

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

Несколько границ сложности особенно важны почти для всех алгоритмов и структур данных, эффективных с точки зрения модели ввода-вывода. Граница поиска в [math]\displaystyle{ \Theta (log_B \; n) }[/math] операций ввода-вывода, достижимая при использовании B-дерева [4], равна стоимости поиска элемента в упорядоченном наборе из n элементов, использующего только сравнения.

Таким образом, она эквивалентна границе поиска во внутренней памяти, составляющей [math]\displaystyle{ \Theta (log \; n) }[/math].

Сканирование списка из n последовательных элементов данных, очевидно, требует [math]\displaystyle{ \left \lceil \frac{n}{B} \right \rceil }[/math] операций ввода-вывода или, в модели PDM, [math]\displaystyle{ \left \lceil \frac{n}{DB} \right \rceil }[/math] операций. Такая граница сканирования обычно определяется как «линейное количество операций ввода-вывода», поскольку она эквивалентна временной границе O(n), необходимой для выполнения того же действия во внутренней памяти.

Граница сортировки [math]\displaystyle{ sort(n) = \Theta \bigg( ( \frac{n}{B}) \; log_{\frac{M}{B} } \; (\frac{n}{B}) \bigg) }[/math] операций ввода-вывода обозначает стоимость сортировки n элементов, использующей только сравнения. Таким образом, она эквивалентна границе сортировки во внутренней памяти, составляющей [math]\displaystyle{ \Theta (n \; log \; n) }[/math]. В модели PDM граница сортировки составляет [math]\displaystyle{ \Theta \bigg( ( \frac{n}{DB}) \; log_{\frac{M}{B} } \; (\frac{n}{B}) \bigg) }[/math]. Эта граница может быть достигнута при помощи различных алгоритмов сортировки, включая алгоритмы внешнего слияния [1, 6] и сортировки распределением [1, 5].

Возможно, наибольший интерес представляет граница перестановки, а именно – стоимость перегруппировки n элементов в заданном порядке, составляющая [math]\displaystyle{ \Theta (min(sort(n), n)) \; }[/math] [1] или [math]\displaystyle{ \Theta (min(sort(n), \frac{n}{D})) \; }[/math] в модели PDM [10]. Для всех практических целей она совпадает с границей сортировки. Отметим контраст с использованием внутренней памяти, при котором с поправкой на константный коэффициент перестановка имеет ту же стоимость, что и линейное сканирование. Поскольку почти все нетривиальные алгоритмические задачи включают задачу перестановки, в результате только самые простые задачи могут быть решены при помощи [math]\displaystyle{ O(scan(n)) \; }[/math] операций ввода-вывода; большинство задач требуют [math]\displaystyle{ \Omega (perm(n)) \; }[/math], что, в сущности, представляет собой нижнюю границу [math]\displaystyle{ \Omega (sort(n)) \; }[/math]. Таким образом, в то время как алгоритмы на базе внутренней памяти, стремящиеся к линейному времени, должны максимально избегать использования сортировки как инструмента, алгоритмы на базе внешней памяти могут использовать сортировку, не опасаясь значительного превышения нижней границы. Это делает разработку оптимальных алгоритмов на базе ввода-вывода потенциально более простой, чем разработка алгоритмов на базе внутренней памяти. Однако это компенсируется тем обстоятельством, что, в отличие от работы во внутренней памяти, граница сортировки не равна границе поиска, умноженной на n, из чего следует, что алгоритмы, основанные на опросе поисковой структуры на базе дерева O(n) раз, обычно не переводятся в эффективные с точки зрения операций ввода-вывода алгоритмы. Буферные деревья [3] обеспечивают амортизированную границу поиска в [math]\displaystyle{ O \bigg( ( \frac{1}{B}) \; log_{\frac{M}{B} } \; (\frac{n}{B}) \bigg) }[/math] операций ввода-вывода, но могут использоваться только в случае, если вся последовательность обновлений и запросов известна заранее, и потому представляют собой ограниченное решение данной задачи.

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

Применение

В современных компьютерах применяется иерархическая память, включающая несколько уровней кэша, оперативную память (RAM) и один или несколько дисков. По мере увеличения расстояния от процессора возрастают задержки обращений к памяти, а также ее объемы. Для сглаживания этих возрастающих задержек данные перемещаются между уровнями памяти в виде блоков последовательных элементов данных. В результате стоимость обращения к памяти зависит от уровня иерархии, хранящего в этот момент элемент данных – разница между задержками обращения к кэшу L1 и к диску составляет примерно [math]\displaystyle{ 10^6 \; }[/math] – а стоимость последовательности обращений к элементам данных, хранящимся на одном и том же уровне иерархии, зависит от количества блоков, по которым эти элементы распределены.

Традиционно алгоритмы разрабатывались с прицелом на минимизацию количества этапов вычислений; локальность обращений к памяти, необходимая для решения задачи с использованием возможно меньшего количества перемещений между уровнями памяти, в основном игнорировалась. Таким образом, эти алгоритмы хорошо работают на наборах данных небольшой величины, но не пользуются значительным преимуществом кэш-памяти и обычно не справляются с вычислениями во внешней памяти. Поскольку разница в задержке обращений к оперативной памяти и к диску максимально велика, модель ввода-вывода уделяет основное внимание устранению этого «затора». Двухуровневое представление иерархии памяти сохраняет простоту модели и хорошо подходит для анализа тщательно разработанных алгоритмов, обеспечивая наряду с этим неплохую практическую эффективность работы.

Много усилий было вложено в преобразование доказуемо эффективных с точки зрения операций ввода-вывода алгоритмов в высокоэффективные реализации. Можно привести в пример TPIE [8] и STXXL [7] – две библиотеки, содержащие высокооптимизированные и мощные примитивы для реализации алгоритмов, эффективных с точки зрения операций ввода-вывода. Но, несмотря на эти усилия, между теорией и практикой по-прежнему сохраняется значительный разрыв.

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

В сегменте алгоритмов, эффективных с точки зрения операций ввода-вывода, остается немало нерешенных проблем. Самая значимая из них касается графовых и геометрических задач.

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

Техники решения геометрических задач, эффективные с точки зрения операций ввода-вывода, разработаны намного лучше, чем для графовых алгоритмов – по крайней мере, для двумерных случаев. Тем не менее, остаются несколько важных фронтов работ. Возможно, наиболее важным из них является разработка эффективных с точки зрения операций ввода-вывода алгоритмов и структур данных для решения геометрических задач большей размерности. Одна из перспективных задач, которые могут исследоваться в этом контексте, касается применения многомерного поиска по диапазону в приложениях для управления базами данных. Не слишком активно велись исследования в области задач о близости, которые сегодня также вышли на передний план. Потребность в подобных структурах имеется в множестве областей применения, в частности, в географических информационных системах; в последнее время много внимания уделялось многофункциональным структурам данных – то есть структурам, способным эффективно отвечать на разные типы запросов. Большинство существующих структур настроены узкофункционально и способны эффективно поддерживать только один тип запросов.

В обоих случаях, идет ли речь об эффективных с точки зрения операций ввода-вывода графовых алгоритмах или о вычислительной геометрии, остается значительный разрыв между полученными теоретическими результатами и практическими реализациями (хотя над геометрическими алгоритмами работы велись более активно, чем над графовыми). Таким образом, если рассчитывать на какое-либо практическое влияние подобных алгоритмов в этих областях, необходимы дополнительные усилия для преодоления разрыва между эффективными на практике с точки зрения операций ввода-вывода алгоритмами, которые при этом остаются доказуемо эффективными.

См. также

Подробности по теме «Внешние сортировка и перестановка» см. в соответствующей статье. Подробная информация по поводу одномерного и многомерного поиска представлена в статьях B-деревья и R-деревья. Алгоритмы, обеспечивающие эффективность на всех уровнях иерархии памяти, описаны в статье Модель без явного задания параметров кэша.

Литература

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.: External memory data structures. In: Abello, J., Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Massive Data Sets, pp. 313-357. Kluwer Academic Publishers, Dordrecht (2002)

3. Arge, L.: The buffer tree: A technique for designing batched external data structures. Algorithmica 37(1), 1 -24 (2003)

4. Bayer, R., McCreight, E.: Organization and maintenance of large ordered indexes. Acta Inform. 1,173-189 (1972)

5. Nodine, M.H., Vitter, J.S.: Deterministic distribution sort in shared and distributed memory multiprocessors. In: Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 120-129. Velen, June/July 1993

6. Nodine, M.H., Vitter, J.S.: Greed Sort: An optimal sorting algorithm for multiple disks. J. ACM 42(4), 919-933 (1995)

7. STXXL: C++ Standard Library for Extra Large Data Sets. http://stxxl.sourceforge.net. Accessed: 15 March 2008

8. TPIE —A Transparent Parallel I/O-Environment. http://www.cs.duke.edu/TPIE. Accessed: 15 March 2008

9. Vitter, J.S.: External memory algorithms and data structures: Dealing with massive data. ACM Comput. Surv.33(2), 209-271 (2001)

10. Vitter, J.S., Shriver, E.A.M.: Algorithms for parallel memory I: Two-level memories. Algorithmica 12(2-3), 110-147 (1994)