ным, попадают в эту категорию.) Но если данные, к которым производится доступ, разбросаны в разных местах крупного файла, то система виртуальной памяти начнет испытывать перегруз {thrash), затрачивая все свое время на доступ к данным во внешней памяти, результаты которого будут катастрофическими.

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

С другой стороны, использование виртуальной памяти может привести к недопустимым непроизводительным затратам системных ресурсов, так что расчет на собственные явные методы (подобные тем, которые рассматривались выше) может оказаться наилучшим способом получить максимум от высокопроизводительных внешних запоминающих устройств. Одна из основных характеристик изученных выше методов заключается в том, что они разрабатывались с расчетом, чтобы максимально возможное число независимых частей компьютерной системы работало с максимальной эффективностью и ни одна из частей при этом не простаивала. Когда в качестве подобных независимых частей рассматривать процессоры, мы приходим к идее параллельных вычислений, которая рассматривается в разделе 11.5.

Упражнения

> 11.45. Показать, какие отрезки порождаются методом выборки с замещением с очередью по приоритетам размером 4, примененным к ключам EASYQOUE S Т IO N.

о 11.46. Как отражается использование метода выборки с замещением на файле, который был порожден посредством применения метода выборки с замещением к заданному файлу?

11.47. Эмпирически определить среднее число отрезков, порожденных посредством применения метода выборки с замещением с очередью по приоритетам размером 10000 к файлам с произвольной организацией при Л= 10 10*, 10 и 10.

11.48. Каким будет число отрезков в худшем случае при использовании метода выборки с замещением для генерации отрезков начального распределения для файла, содержащего N записей, с использованием очереди по приоритетам размером М, при M<N?

> 11.49. Показать, как выполняется сортировка ключей EASYQUESTION WITHPLENTYOFKEYSb результате применения многофазного слияния в стиле примера, показанного на диафамме рис. 11.15.

о 11.50. В примере многофазного слияния на рис. 11.15 мы поместили два фиктивных отрезка на магнитную ленту с 7 отрезками. Найдите другие способы распределения фиктивных отрезков на лентах и выберите среди них такой, который обеспечивает минимальное по стоимости слияние.

11.51, Начертить таблицу, соответствующую рс. 11.13, с целью определить максимальное число отрезков, которые могут быть слиты с помощью сбалансированного трехпутевого слияния с пятью проходами по данным (с использованием шести устройств).

11.52. Начертить таблицу, соответствующую рис. 11.16, с целью определить максимальное число отрезков, которые могут быть слиты с помощью метода многофазного слияния с теми же затратами, что и пять проходов по всей совокупности данных (с использованием шести устройств).

о 11.53. Напишите программу, вычисляющую число проходов, выполняемых многофазным слиянием, и эффективное количество проходов, выполняемых методом многофазного слияния для заданного числа устройств и заданного числа начальных блоков. Используйте эту программу для распечатки таблицы этих затрат для каждого метода для Г = 3, 4, 5, 10 и 100 и \0\ 10 10 и 10

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

11.55. Реализовать выборку с замещением, воспользовавшись интефейсом, определенным в упражнении 11.38.

11.56. Чтобы получить программную реализацию сортировки-слияния, используйте сочетание решений упражнений 11.38 и 11.55. Используйте полученную программу для сортировки файла максимально возможных в вашей системе размеров, воспользовавшись многофазным слиянием. Если возможно, определите как отражается на времени выполнения программы увеличение числа устройств.

11.57. Как нужно обходиться с файлами небольших размеров в рамках реализации быстрой сортировки применительно к файлу сверхбольших размеров в среде виртуальной памяти?

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

11.59. Разработать программную реализацию рекурсивной многопутевой сортировки слиянием, в основу которой положено /:-путевое слияние, которую можно использовать для сортировки сверхбольших файлов в среде виртуальной памяти (см. упражнение 8.11).

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

11.5. Параллельная процедура сортировки-слияния

Как сделать так, чтобы несколько независимых процессоров работали совместно, решая одну задачу сортировки? Управляют ли процессоры внешними запоминаюши-ми устройствами или сами являются самостоятельными вычислительными системами - от этого во многом зависит алгоритм функционирования высокопроизводительных вычислительных систем. Проблема параллельных вычислений в последнее время широко изучается. Разработано множество типов вычислительных машин параллельного действия, предложены разнообразные модели параллельных вычислений. Во всех этих случаях проблема сортировки выступает как эффективное средство тестирования и того, и другого.

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

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

N записей, подлежащих сортировке

Р процессоров, способных принять (N/P) записей.

Мы присваиваем этим процессорам метки О, 1, Р- I и полагаем, что файл, который служит входом, помещен в память локальных процессоров (то есть, в каждом процессоре содержатся N/P записей). Цель сортировки заключается в переупорядочении записей таким образом, чтобы N/P наименьших записей находились в памяти процессора О, N/P следующих наименьших записей находились в памяти процессора 1 и так далее, в отсортированном порядке. Как мы увидим далее, существует зависимость между Р и общим временем выполнения - мы хотим получить количественную оценку этой зависимости с целью сравнения различных стратегий.

Предлагаемая модель - одна из многих возможных моделей параллельной обработки данных и для нее характерны многие из упрощений в смысле практического применения, какие имеют место в предложенной нами модели внешней сортировки (раздел 11.3). И в самом деле, рассматриваемая модель не учитывает одну из наиболее важных проблем, которая весьма актуальна для параллельной обработки данных: ограничения, которые накладываются на обмен данными между процессорами.

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