Модель ввода-вывода: различия между версиями

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

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

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

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

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

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