Читайте также:
|
|
В зависимости от размера (объёма вычислений) ветвей различают несколько уровней распараллеливания:
1. Разрядный - вычисления выполняются параллельно над многими разрядами чисел; этот уровень распараллеливания реализуется аппаратно в подавляющем большинстве современных процессоров универсальных ЭВМ.
2. Командный - параллельно выполняются отдельные команды; на этом уровне возможно автоматическое распараллеливание, реализуемое при компиляции или интерпретации алгоритмов средствами систем программирования и операционных систем.
3. Подпрограммный - параллельные ветви составляют программные модули, чаще всего оформленные в виде отдельных подпрограмм.
4. Программный - параллельно выполняются крупные программные блоки общего задания.
5. Задачный - параллельные ветви представлены взаимно независимыми самостоятельными программами.
Чем крупнее параллельные блоки, тем труднее использовать автоматическое распараллеливание. Поэтому крупноблочное распараллеливание возлагается на разработчиков программного обеспечения.
Рассмотрим пример параллельного программирования на основе полинома четвертой степени
y = a0 + a1X + a2X2 + a3X3 + a4X4. (1)
Обычно для ускорения вычислений при обычном программировании его представляют по схеме Горнера [4]:
8 7 6 5 4 3 2 1
y = a0 + X(a1 + X(a2 + X(a3 + Xa4))).
Пусть такт - время выполнения одной арифметической операции. Тогда вычисления будут выполнены за 8 тактов. При такой записи распараллелить не представляется возможным. По формуле (1) это сделать можно:
1-й: а1Х и Х2; 2-й: а0+а1X, и а2Х2 и Х3;
3-й: а3Х3, Х4+а2Х2; 4-й: +а3Х3 и а4Х4;
5-й: + а4Х4,
т.е. потребовалось лишь 5 тактов для вычисления всех значений функции y(x). Эффективность вычислений зависит от архитектуры вычислительной системы, поэтому программисты обязательно должны знать эти особенности и использовать их при проектировании.
Среди других рекомендаций по разработке параллельных алгоритмов можно назвать следующие:
· распараллеливание целесообразно для потенциально многообещающих частей программы: циклы, и особенно внешние;
· желательно равномерное распределение вычислительных работ по ветвям алгоритма.
Циклические процессы могут быть 4-х типов:
1) скаляр-скаляр; 2) скаляр-вектор;
3) вектор-скаляр; 4) вектор-вектор.
Например, в процессе типа вектор-скаляр выполняется типовая операция for i:= 1 to N do S:=S+A[i]*B[i].
Для распараллеливания может быть использован метод каскадных сумм (рис.2).
A1*B1 A2B2 A3B3 A4B4 ... AnBn
+ +... +
+
Рисунок 2. Схема метода каскадных сумм.
Число ярусов (число тактов) будет равно большему числу (целому), ближайшему к log2N.
Для реализации параллельного программирования созданы специальные языки, т.е. лингвистическое обеспечение. Их особенность в том, что они содержат указатели параллельных ветвей – ключевые слова PARBEGIN - PAREND.
Примеры языков параллельного программирования: ADA, MODULA-2, FORTRAN параллельный.
Для примера рассмотрим алгоритмы, обеспечивающие вычисление значения экспоненты ex:
ex = exp (x) = 1 + x + x2/2! + x3/3! + и т.д.
допустим, необходимо вычислить с точностью EPS.
Алгоритмы (последовательный и параллельный) выглядят следующим образом:
последовательный параллельный
S:=1; a:=1; n:=1; S:=1+X; a:=1; b:=X;
WHILE a>=EPS do m:=2; n:=1; y:=X**2;
BEGIN a:=a*X/n; WHILE b>= EPS do
S:=S+a; BEGIN z:=y/m;
n:=n+1 PARBEGIN
END; BEGIN a:=a*z/n;
S:=S+a; END;
b:=b*z/(n+2); m:=m+2;
Дата добавления: 2014-12-15; просмотров: 27 | Поможем написать вашу работу | Нарушение авторских прав |