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

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

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