Параллельная сортировка Бэтчера

Алгоритм сортировки Бэтчера не является наиболее эффективным алгоритмом сортировки, однако он обладает одним важным компенсирующим качеством: все сравнения и/или обмены, определяемые данной итерацией алгоритма можно выполнять одновременно. С такими параллельными операциями сортировка осуществляется за .

Например, 1024 элемента можно рассортировать методом Бэтчера всего за 55 параллельных шагов. Схема сортировки Бэтчера несколько напоминает сортировку Шелла, но сравнения выполняются по-новому, а потому цепочки операций обмена записей не возникает. Поскольку в алгоритме Бэтчера, по существу, происходит слияние пар рассортированных подпоследовательностей, его можно назвать обменной сортировкой со слиянием.

Алгоритм Бэтчера (обменная сортировка со слиянием). Записи перекомпоновываются в пределах того же пространства в памяти. После завершения сортировки их ключи будут упорядочены:. Предполагается, что.

1)[начальная установка .] Установить, где— наименьшее целое число, такое, что. (Шаги 2-5 будут выполняться с.)

2)[начальная установка .] Установить.

3)[цикл по .] Для всех, таких, чтои, выполнять шаг 4.

Затем перейти к шагу 5. (Здесь через обозначена операция "поразрядное логическое И" над представлениями целых чисели; все биты результата равны 0, кроме тех битов, для которых в соответствующих разрядахинаходятся 1. Так. К этому моменту— нечётное кратное(т.е. частное от делениянанечётно), а— степень двойки, так что. Отсюда следует, что шаг 4 можно выполнять при всех нужных значенияхв любом порядке или даже одновременно.)

4)[Сравнение/обмен .] Если, поменять местами записи.

5)[Цикл по .] Если, установитьи возвратиться к шагу 3.

6)[Цикл по ] (К этому моменту перестановкабудет-упорядочена.) Установить. Если, возвратиться к шагу 2.

2. Вычисление корня алгебраического или трансцендентного уравнения

Пусть дано уравнение . Требуется на отрезкенайти корень при условии. Для построения алгоритма ветви используется метод хорд, заключающийся в следующем (рисунок N1). Криваязаменяется хордой, определяется

Рисунок 1. Метод хорд.

точка , после чего проводится хордаопределяетсяи т. д., пока.

Для реализации задачи на процессоров, т.е. для построения параллельного алгоритма изветвей, отрезокразбивается наподотрезков на границах которых вычисляется. Это определяет подотрезокдлиной, содержащий корень. Точкии— соседние, в них значения функции имеют разные знаки (рисунок N1).

После отрезка рассматривается отрезок, где

(1)

Отрезок разбивается начастей, повторяется описанная процедура, получается отрезоки т. д., пока длина отрезка не станет меньше заданного значения. Параллельный счет оправдан, когда объём вычислений значениянамного превосходит объём вычислений границ отрезкапо (1).

Аналогичный результат получается и при использовании метода Ньютона.

3. Решение системы линейных алгебраических уравнений методом простой итерации

Система уравнений размерностизаписывается в виде, где— матрицы;и— векторы;— единичная матрица.

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

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

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

Лекция 5.