Меню Закрыть

III Алгоритмы и параллелизм (часть вторая)

image_pdfimage_print

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

Вычисления с многократной точностью

Будем называть числа числами с многократной точностью (длинными числами), если их разрядность превосходит разрядную сетку вычислительной системы. Так, для 32-битной системы к этому классу относят числа разрядностью больше 32, для 64-битной – числа длиннее 64-х разрядов. Числа с многократной точностью используются достаточно широко. Так, в криптографии современные методы используют числа длиной до 4096 битов. Эта длина удваивается каждые несколько лет.

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

Операции побитовой обработки

Операции побитовой обработки (&, |, ~, ^) могут выполняться параллельно. В этом случае при неограниченном параллелизме время выполнения операции совпадает со временем выполнения операции над одним элементом массива. Соответствующий граф имеет высоту, равную 1, и степень параллелизма равна числу элементов массива n. В этом случае при последовательном выполнении общее время равно \(T_{1}=n*t\), где \(n\) – число «цифр», a \(t\) – время выполнения операции для одной цифры. Время выполнения операции в случае n ядер равно \(T_{n}=t\) и ускорение составляет \(n\).

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

Сложение чисел. Последовательное и параллельное выполнение

Для сложения чисел с многократной точностью используется алгоритм сложения «в столбик».

Граф сложения чисел с многократной точностью для 4-х «цифр» числа представлен на рис. 7.

Последовательное выполнение

Для последовательных вычислений алгоритм имеет вид:

Carry=0;
for (i = 0; i< n; ++i)
{
с = x[i] + y[i] + Carry;
Carry = CalcCarry (x[i], y[i], Carry);
z[i] = c;
)
z[i] = Carry;

При последовательном выполнении требуется \(n\) операций,

каждая операция соответствует вычислению тела цикла, т.е.

\[T_{s}=n\](4)

Параллельное выполнение

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

Рис. 7. Граф алгоритма сложения «в столбик»

Шаг 1. Вычисления делаем для всех «цифр» числа без учета переноса. Формируем для каждой итерации значение результата без учета переноса и значение переноса. Формируем булеву переменную, общую для всех итераций, равную Истине, если перенос есть хотя бы в одной итерации.

Наличие очередных шагов по коррекции «цифр» результата определяется наличием хотя бы одного переноса.

Наилучший вариант. Переносов нет ни для одной цифры – в этом случае дополнительные шаги не требуются, высота графа равна 1.

Наихудший случай. Одно слагаемое равно максимально возможному значению для выбранной системы счисления «цифры», а второе слагаемое – не менее 1.

Алгоритм сложения. Спекулятивное выполнение

Предложен алгоритм, в котором при сложении в каждом разряде предполагается наличие и отсутствие переноса. Соответственно вычисляется 2 результата для каждого разряда. Перенос для разряда также вычисляется с учетом отсутствия и наличия переноса в предыдущем разряде. Таким образом, для каждого разряда получаем 2 значения переноса.

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

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

Использование метода Карацубы-Офмана (КОА) для умножения чисел

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

\[x=x_{1}*2^{n/2}+x_{0}, y=y_{1}*2^{n/2}+y_{0}\].        (6)

Вычислим значения:

\[A=x_{0}*y_{0} \] ;

\[B=( x_{0}+x_{1} )(y_{0}*y_{1} )\];  (7)

\[C=x_{1}*y_{1}\].

В этом случае значение произведения равно:

\[x*y=C2^{n}+(B-A-C)2^{n/2}+A\]. (8)

Заметим, что \(A+C=x_{0}*y_{0} + x_{1}*y_{1}\), а значение \(B=x_{0}*y_{0} +x_{1}*y_{1} +x_{1}*y_{0} +x_{0}*y_{1} \), т.е. \(B–A–C>= 0\).

Определим количество операций при последовательном вычислении:

\[T_{S}=T_{A}+T_{C}+T\](9)

Для вычисления значения \(A\) и \(C\) требуется \(T_{A}=T_{C}=n^{2}*(t_{m}+t_{a})/4\). Для вычисления значения \(B\) и \(B–A–C\) соответственно требуется

\[T_{B}=2*(n/2+1)t_{a}+(n/2+1)^{2}*(t_{a}+t_{m}), T_{B-A-C}=T_{B}+(n+1)t_{a} \].

Общее время выполнения в последовательном режиме равно:

\[T_{KOA}=n_{2}(t_{m}+t_{a})/2+2(n/2+1)t_{a}+(n/2+1)^{2}(t_{a}+t_{m})+2nt_{a}\]. (10)

Схема параллельного вычисления для \(р≥4\) представлена в таблице 3.

Таблица 3

Параллельное вычисление произведения. Алгоритм Карацубы-Офмана

Ядро процессора
ZL=XL*YL ZH=XH*YH XL+XH YL+YH
ZL+ZH D=(XL+XH)*(YL+YH)
E=D-(ZL+ZH)
Z+=E

 

Операции, которые выполняются параллельно, определены в одной строке таблицы. В этом случае время выполнения параллельного алгоритма равно:

\[T_{PKO}=n_{2}(t_{m}+t_{a})/4+(n/2+1)^{2}(t_{a}+t_{m})+(n+2)t_{a}+2nt_{a}\](11)  Ускорение и эффективность для алгоритма Карацубы-Офмана:

\[S_{PKO}=\frac{n_{2}(t_{m}+t_{a})/2+2(n/2+1)t_{a}+(n/2+1)^{2}(t_{a}+t_{m})+2nt_{a}}{n_{2}(t_{m}+t_{a})/4+(n/2+1)^{2}(t_{a}+t_{m})+(n+2)t_{a}+2nt_{a}}\];(12)

\[E_{PKO}=S_{PKO}/4\].

Матричные вычисления

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

Сложение матриц

Пусть заданы 2 матрицы \(А\) и \(В\) размерностью \(m*n\) (\(m\) строк, \(n\) столбцов). В результате сложения получим матрицу \(С\) размерностью \(m*n\):

\(C[i][j] = A[i][j] + B[i][j],         (i = 0..m,j = 0..n)\). (13)

Последовательное вычисление:

for (i = 0; i < m; ++i)
for (j = 0; j < n; ++j)
C[i][j] = A[i][j] + B[i][j];

При последовательных вычислениях требуется \(n*m\) операций сложения.

Циклы независимы.

Чтобы упростить параллельное выполнение вложенных циклов, преобразуем фрагмент программы, приведенный выше, в эквивалентный фрагмент программы:

for (k = 0; k < m * n; ++k)
{
i=k/n;j=k%n;
C[i][j] = A[i][j] + B[i][j];
}

Если строки матриц расположены непосредственно друг за другом, то последний фрагмент программы может быть преобразован так:

for (k = 0;k<m *n;++k)
{
С[k] = А[k] + B[k];
}

Для неограниченного параллелизма все операции можно выполнять параллельно и ускорение составляет \(m* n\).

Если есть процессор, содержащий р ядер, то для выполнения цикла потребуется \((m*n+p–1)/p\) операций.

Если предположить, что \(m * n\) кратно числу ядер \(p\), то ускорение равно \(p\), а эффективность равна 1.

Умножение матрицы на вектор (Алгоритм MVM)

Пусть \(A\) — матрица \(m*n\) (\(m\) строк, \(n\) столбцов).

Пусть \(B\) — вектор, содержащий n элементов.

В результате получаем вектор \(C\) c числом элементов, равным \(m\):

\[C_{i}=\sum_{j=0}^{n-1}A_{ij} *B_{j}, (i=0..m-1)\](5.31)

Фрагмент программы для последовательных вычислений:

for (i = 0; i<m; ++i)
{
C [i] = 0;
for (i = 0;j < n; ++j) С [i] += A[i][j] * B[j];
}

Умножение матриц (Алгоритм МММ)

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

Пусть заданы матрицы \(А\)и \(B\) размерностью \(n * n\) (\(n\) строк и столбцов). Вычислить матрицу \(C\) размерностью \(n * n\).

\[C[i][j]=\sum_{k=0}^{n}A[i][k] *B[k][j], (i=0..n-1, j=0..n-1)\]

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

for (i = 0; i< n; ++i)
for (j = 0;j<n; j++)
{
C[i][j] = 0;
for (k = 0; k< n; ++k)
C[i][j]+=A[i][k] *B[k][j];
}

Выводы

  1. Функции с эффективным использованием Кеша эффективнее как для C++, так и для С#.
  2. Параллельные вычисления для умножения матриц для языка C++ практически не ускоряют вычисления, для С# – ускоряют примерно в 1.5 раза.
  3. Функции для C++ работают быстрее соответствующих функций для C# в 2 и более раз.
  4. Если параметр скорости является критическим, соответствующие функции лучше писать на языке C++, а не на С#. Использование динамических библиотек позволяет применять их в C++ и C# проектах.

Алгоритмы сортировки

Существует очень много методов сортировки [18]. В пособии рассматриваются два метода: подсчета и быстрой сортировки. Выбор методов связан с необходимостью получения параллельного варианта каждого из методов.

Сортировка методом подсчета (CS)

Для метода подсчета используется два варианта.

Первый вариант применяется, если диапазон изменения данных для сортировки заранее известен и он небольшой. В этом случае используются счетчики для каждого возможного значения. Число счетчиков совпадает с множеством значений исходных данных для сортировки. Например, если известно, что исходные данные занимают по одному байту и это положительные числа, то диапазон значений равен 0..255. Число счетчиков равно 256 независимо от числа элементов в массиве.

Второй вариант применяется для неизвестного или слишком большого диапазона значений, в этом случае число счетчиков равно числу элементов в массиве. Далее рассмотрен второй вариант.

Последовательный алгоритм CS

Напоминаем суть метода. Для каждого элемента массива подсчитывается, сколько элементов предшествует ему. Для этого сначала обнуляется содержимое счетчиков для каждого элемента. Затем текущий элемент сравнивается со всеми предшествующими.

Пример фрагмента программы для вычисления значений счетчиков приведен ниже:

for (i=1; i < n; ++i)
for (j = 0;j < i; ++j)
if (а[j] <= a[i]) s[i] += 1; else s[j] += 1;

После вычисления счетчиков можно «поставить» элементы на место, используя для результата новый массив:

for (i = 0;i < n; ++i)
b[s[i]] = a[i];

Определим число операций для последовательного алгоритма.

Для последовательного выполнения цикла вычисления счетчиков требуется \(1 + 2 +…+ n — 1\)или \(n(n — 1)/2\) операций.

Для цикла записи элементов массива в заданные позиции требуется в последовательном режиме п операций.

Общее время выполнения алгоритма в последовательном режиме равно:

\[T_{CS}^{1}=\frac{n(n-1)}{2}+n\](5.36)

Параллельный алгоритм СS1. Неограниченный параллелизм

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

Определим время выполнения этого алгоритма в параллельном режиме.

Для параллельного выполнения первого цикла в случае наличия \(n – 1\) ядра требуется \(n – 1\) операция.

Для цикла записи элементов массива в заданные позиции требуется 1 операция для \(n\) ядер.

Если предположить, что время выполнения циклического участка для первого и второго циклов примерно одинаково, то общее время для параллельного режима составляет:

\[T_{CS1}^{\infty}=1\](5.37)

Показатели ускорения и эффективности:

\[S_{CS1}^{\infty}=\frac{n+1}{2}; E_{PS1}^{\infty}=\frac{n+1}{2n}\].  (5.38)

 Алгоритм быстрой сортировки

Алгоритм разработан английским ученым Чарльзом Хоаром. Суть алгоритма состоит в том, что сначала выбирается так называемый опорный элемент. Весь сортируемый массив делится на две части. Первая часть содержит элементы, значения которых меньше или равны опорному, вторая часть – элементы больше опорного. Далее для первой и второй частей рекурсивно вызывается функция сортировки. Сортировка продолжается до тех пор, пока в каждой части есть хотя бы два элемента.

Для распределения данных обычно используется такой алгоритм. Для всех элементов, начиная с самого левого левее опорного, выполняется сравнение с опорным. В результате находим элемент больше опорного. Для всех элементов правее опорного, начиная с конца массива, находим элемент меньше опорного. Элементы левой и правой частей меняются местами. Просмотр продолжается до тех пор, пока есть элементы в левой и правой части. Парадокс этого алгоритма состоит в том, что он использует обмен данными, как «пузырек», при этом «пузырек» – самый неэффективный, по сравнению с простыми методами, именно за счет этой операции! Таким образом, комбинация неэффективных методов может привести к эффективному методу! В этом случае вычислительная сложность \(O (log(n))\).

Реализация последовательного алгоритма (QS)

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

Реализация параллельного алгоритма

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

  1. Разделение массива на 2 части по опорному элементу (последовательно).
  2. Обработка каждой части параллельно.
Смешанный алгоритм

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

Комбинированный метод предполагает использование простого метода для небольшого числа элементов и метода быстрой сортировки – для большого.

Алгоритм поиска простых чисел

(Решето Эратосфена)

Алгоритмы поиска простых чисел важны при решении многих задач. Практически все несимметричные криптографические алгоритмы используют простые числа. Есть много алгоритмов их поиска. Одним из самых быстрых и древних алгоритмов является алгоритм Эратосфена. В качестве параллельного алгоритма для релизации решета используем идею из (http://software.Intel.com/ en-us/articles/parallel-reduce/), взятую из примеров к библиотеке Intel Threading Building Blocks (http://www.threadingbuilding-blocks.org/).

Идея алгоритма

  1. Четные числа не рассматриваются, только нечетные.
  2. Находятся все простые числа в диапазоне \(3..n\) до ближайшего нечетного \(sqrt (n)\) с помощью классического метода решета Эратосфена (последовательно).
  3. Диапазон чисел \(sqrt (n) + 2..n\) делится на заданное число порций (по числу ядер процессора), и в каждой порции числа ищем параллельно.

Теоретическая оценка производительности

Согласноnтеореме о распределении простых чисел, количество простых чисел для диапазона чисел \(1.. n\) приблизительно равно

\(π(n) = n /1n (n))\).

Пусть необходимо найти все простые для данного n. Пусть время нахождения всех простых чисел при использовании последовательного алгоритма равно 1. Тогда время нахождения одного простого числа в среднем равно \(1/π(n) = ln (n)/n\).

  1. Карацуба, А.А. Умножение многозначных чисел на автоматах / А.А. Карацуба, Ю.П.
    Офман // Доклады Академии Наук СССР. – 1962. -Т. 145, № 2. – 293-294 с.
  2. Качко, Е.Г. Параллельное программирование: Учебное пособие / Е.Г. Качко. –
    Харьков:Изд-во «Форт», 2011. – 528 с.
  3. Кнут Д. Искусство программирования ЭВМ. Т. 3. Сортировка и поиск. Мир. — М.,
    1978. — 844 с

Связанные записи