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

В системе ПараЛаб в качестве методов упорядочения данных представлены пузырьковая сортировка, сортировка Шелла, быстрая сортировка.

1.1.1. Алгоритм пузырьковой сортировки

Напомним кратко общую схему данного метода упорядочения данных [1]. Алгоритм основан на применении базовой операции “сравнить и переставить” (compare-exchange), состоящей в сравнении той или иной пары значений из сортируемого набора данных и перестановки этих значений, если их порядок не соответствует условиям сортировки:

// операция “сравнить и переставить”

if ( a[i] > a[j] ) {

temp = a[i];

a[i] = a[j];

a[j] = temp;

}

На первой итерации алгоритма осуществляется последовательное сравнение всех соседних элементов; в результате прохода по упорядочиваемому набору данных в последнем (верхнем) элементе оказывается максимальное значение (“всплывание пузырька”); далее для продолжения сортировки этот уже упорядоченный элемент не рассматривается и действия алгоритма повторяются:

// пузырьковая сортировка

for ( i=1; i<n; i++ ){

for ( j=0; j<n-i; j++ )

<сравнить и переставить элементы (a[j],a[j+1])>

}

Алгоритм пузырьковой сортировки в прямом виде достаточно сложен для распараллеливания: сравнение пар соседних элементов происходит строго последовательно. Для организации параллельных вычислений обычно используется модификация алгоритма пузырьковой сортировки – метод чет-нечетной перестановки [23]. Суть модификации состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода – в зависимости от четности или нечетности номера итерации сортировки для обработки выбираются элементы с четными или нечетными индексами соответственно, сравнение выделяемых значений всегда осуществляется с их правыми соседними элементами, т.е. на всех нечетных итерациях сравниваются пары:

(a₁, a₂), (a₃, a₄),…, (a_n-1, a_n) (при четном n),

на четных итерациях обрабатываются элементы

(a₂, a₃), (a₄, a₅),…, (a_n-2, a_n-1) (при нечетном n).

После n-кратного повторения подобных итераций сортировки исходный набор данных оказывается упорядоченным.

Параллельное обобщение этого алгоритма не вызывает затруднений, так как сравнение элементов в парах происходит независимо и может выполняться одновременно. Сначала рассмотрим схему вычислений, когда на каждый процессор приходится один элемент исходного массива. Предположим, что процессоры соединены  в кольцо и элементы a_i расположены на процессорах p_i (i=1, 2,…, n). Тогда сравнение пары значений a_i и a_i+1 1≤ i <n, располагаемых на процессорах P_i и P_i+1 соответственно, можно организовать следующим образом:

- выполнить взаимообмен имеющихся на процессорах P_i и P_i+1 значений (с сохранением на этих процессорах исходных элементов);

- сравнить на каждом процессоре P_i и P_i+1 получившиеся одинаковые пары значений ai и a_i+1; результаты сравнения используются для разделения данных между процессорами – на одном процессоре (например, Pi) остается меньший элемент, другой процессор (т.е P_i+1) запоминает для дальней обработки большее значение пары

a_i =min(a_i , a_i+1 ),    a_i+1 =max(a_i , a_i+1).

Рассмотренная параллельная схема может быть надлежащим образом адаптирована и для случая p<n, когда количество процессоров является меньшим числа упорядочиваемых значений. В данной ситуации каждый процессор будет содержать уже не единственное значение, а часть (блок размера n/p) сортируемого набора данных. Эти блоки обычно упорядочиваются в самом начале сортировки на каждом процессоре в отдельности при помощи какого-либо быстрого алгоритма (предварительная стадия параллельной сортировки). Далее, следуя схеме одноэлементного сравнения, взаимодействие пары процессоров P_i и P_i+1 для совместного упорядочения содержимого блоков A_i и A_i+1 и может быть осуществлено следующим образом:

- выполнить взаимообмен блоков между процессорами P_i и P_i+1;

- объединить блоки A_i и A_i+1 на каждом процессоре в один отсортированный блок двойного размера (при исходной упорядоченности блоков и процедура их объединения сводится к быстрой операции слияния упорядоченных наборов данных);

- разделить полученный двойной блок на две равные части и оставить одну из этих частей (например, с меньшими значениями данных) на процессоре P_i, а другую часть (с большими значениями соответственно) – на процессоре P_i+1.

Следует отметить, что сформированные в результате такой процедуры блоки на процессорах P_i и P_i+1 совпадают по размеру с исходными блоками A_i и A_i+1 и все значения, расположенные на процессоре P_i, являются меньшими значений на процессоре P_i+1.

Рассмотренная процедура обычно именуется в литературе как операция “сравнить и разделить” (compare-split). Для пояснения такого параллельного способа сортировки на рис. 1 приведен пример упорядочения данных при n=8, p=4 (т.е. блок значений на каждом процессоре содержит n/p =2 элементов). В первом столбце таблицы приводится номер и тип итерации метода, перечисляются пары процессоров, для которых параллельно выполняется операция “сравнить и разделить”; взаимодействующие пары процессоров выделены в таблице двойной рамкой. Для каждого шага сортировки показано состояние упорядочиваемого набора данных до и после выполнения итерации.

Вычислительная трудоемкость алгоритма определяется выражением:

Tp  =6 (n/p)² +2n

Первая часть выражения определяет сложность начальной сортировки блоков с использованием алгоритма пузырьковой сортировки. Вторая часть отражает суммарную сложность всех итераций алгоритма чет-нечетной перестановки блоков (для слияния двух упорядоченных блоков размера n/p необходимо 2(n/p) операций).

Download Lab_3

Общая схема организации таких вычислений может быть представлена следующим образом:

• разделение процесса вычислений на части, которые могут быть выполнены одновременно;

• распределение вычислений по процессорам;

• обеспечение взаимодействия параллельно выполняемых вычислений.

Возможные способы получения методов параллельных вычислений:

• разработка новых параллельных алгоритмов;

• распараллеливание последовательных алгоритмов.

Условия эффективности параллельных алгоритмов:

• равномерная загрузка процессоров (отсутствие простоев);

• низкая интенсивность взаимодействия процессоров (независимость).

В системе ПараЛаб реализованы широко применяемые параллельные алгоритмы для решения ряда сложных вычислительных задач из разных областей научно-технических приложений: алгоритмы сортировки данных, матричного умножения и обработки графов.

Выбор задачи.

Для выбора задачи из числа реализованных в системе выберите пункт меню Задача и выделите левой клавишей мыши одну из строк: Сортировка, Матричное умножение, Обработка графов. Выбранная задача станет текущей в активном окне.

Download Lab_2

• моделирования многопроцессорных вычислительных систем с различной топологией сети передачи данных;

• получения визуального представления о вычислительных процессах и операциях передачи данных, происходящих при параллельном решении разных вычислительных задач;

• построения оценок эффективности изучаемых методов параллельных вычислений.

Проведение такого практикума может быть организовано на “обычных” однопроцессорных компьютерах, работающих под управлением операционных систем MS Windows 2000 или MS Windows XP (режим многозадачной имитации параллельных вычислений). Кроме режима имитации, в системе ПараЛаб обеспечивается удаленный доступ к имеющейся многопроцессорной вычислительной системе для выполнения экспериментов в режиме “настоящих” параллельных вычислений для сопоставления результатов имитации и реальных расчетов.

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

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

Возможности системы. ПараЛаб – программный комплекс, который позволяет проводить как реальные параллельные вычисления на многопроцессорной вычислительной системе, так и имитировать такие эксперименты на одном последовательном компьютере с визуализацией процесса решения сложной вычислительной задачи.

При проведении имитационных экспериментов ПараЛаб предоставляет возможность для пользователя:

• определить топологию параллельной вычислительной системы для проведения экспериментов, задать число процессоров в этой топологии, установить производительность процессоров, выбрать характеристики коммуникационной среды и способ коммуникации;

• осуществить постановку вычислительной задачи, для которой в составе системы ПараЛаб имеются реализованные параллельные алгоритмы решения, выполнить задание параметров задачи;

• выбрать параллельный метод для решения выбранной задачи;

• установить параметры визуализации для выбора желаемого темпа демонстрации, способа отображения пересылаемых между процессорами данных, степени детальности визуализации выполняемых параллельных вычислений;

• выполнить эксперимент для параллельного решения выбранной задачи; при этом в системе ПараЛаб может быть сформировано несколько различных заданий для проведения экспериментов с отличающимися типами многопроцессорных систем, задач или методов параллельных вычислений, для которых выполнение эксперимента может происходить одновременно (в режиме разделения времени); одновременное выполнение эксперимента для нескольких заданий позволяет наглядно сравнивать динамику решения задачи различными методами, на разных топологиях, с разными параметрами исходной задачи. При выполнении серии экспериментов, требующих длительных вычислений, в системе имеется возможность их проведения в автоматическом режиме с запоминанием результатов в журнале вычислений [1-3].

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

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

Downlaod Lab_1