Cтраница 2
Сети Бэтчера были первым более-менее приемлемым решением этой задачи, а некоторые исследователи даже полагали, что сети Бэтчера оптимальны. Сети слияния Бэтчера оптимальны, так что любая сеть сортировки с существенно меньшим числом компараторов может быть построена только в рамках подхода, отличного от рекурсивной сортировки слиянием. [16]
Один метод сортировки для многопроцессорной системы получается из модификации сортировки Шелла, которая гарантирует, что на любом просмотре нет сравнений, которые используют один и тот же аргумент. Этот метод описан здесь благодаря Бэтчеру [1] и тесно связан с той работой, которая проводится в области сортирующих сетей. [17]
Связь между идеальным тасованием и сетями Бэт-чера позволяет завершить наши исследования сетей сортировки анализом одной забавной версии рассматриваемого алгоритма. Если мы перетасуем линии нечетно-четного слияния Бэтчера, то получим сети, в которых компараторы соединяют смежные линии. На этом рисунке дано еще одно представление той же неветвящейся программы, которая предлагает еще более унифицированный шаблон: она использует только операции полного тасования. [18]
В заключение мы рассмотрим параллельную сортировку ( parallel sorting) на тот случай, когда сортируемый файл распределяется между независимыми параллельными процессорами. Мы дадим определение простой модели параллельной машины, а затем выясним, при каких условиях метод Бэтчера обеспечит эффективное решение этой проблемы. [19]
Теория сетей сортиронкн развивалась достаточно интересна ( аи. Сети Бзтчсри были первым ба1 ] ее-мен ее приемлемым решением этой задачи, а некоторые исследователи лаже полагали, что сети Бэтчера оптимальны. Сет слияния Вэтчера опти мальвы, тип что любая сеть сортировки с суше-огненно меньшим числом компараторов может бить построена только н рам как подкола, отличиогп от рскурсиннон сортироьки слиянием. Задача нахождения оптимальны сетей сортировки не поп-нергалась исследованиям до гех пор. [20]
Сети Бэтчера были первым более-менее приемлемым решением этой задачи, а некоторые исследователи даже полагали, что сети Бэтчера оптимальны. Сети слияния Бэтчера оптимальны, так что любая сеть сортировки с существенно меньшим числом компараторов может быть построена только в рамках подхода, отличного от рекурсивной сортировки слиянием. S ( Ajtai, Kolmos и Szemeredy) - это всего лишь математические умозаключения, не имеющие практического применения, так что сети Бэтчера все еще считаются одними из наиболее подходящих для практического применения. [21]
Этот пример показывает, что в некоторых случаях можно обеспечить эффективную работу процессоров при решении задач сортировки файлов сверхбольших размеров. Чтобы знать, как это сделать наилучшим образом неизбежно потребуется проанализировать множество различных алгоритмов для данного типа параллельной машины и исследовать поведение используемой машины на модели при различных значениях ее параметров. Более того, может потребоваться совершенно другой подход к проблеме параллельной обработки данных. Тем не менее, предположение о том, что увеличение числа процессоров приводит к увеличению стоимости обмена данными между ними, является основополагающим для параллельных вычислений, а сети Бэтчера представляет собой эффективное средство управления такого рода затратами, что имеет место как на низком уровне, в чем мы имели возможность убедиться в разделе 11.2, так и на высоком уровне, в чем мы смогли убедиться в настоящем разделе. [22]