Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Методы распараллеливания

Читайте также:
  1. C) Методы стимулирования поведения деятельности
  2. II. Методы и источники изучения истории; понятие и классификация исторического источника.
  3. II. Методы исследования
  4. II. Методы исследования
  5. II. МЕТОДЫ, ПОДХОДЫ И ПРОЦЕДУРЫ ДИАГНОСТИКИ И ЛЕЧЕНИЯ
  6. II. МЕТОДЫ, ПОДХОДЫ И ПРОЦЕДУРЫ ДИАГНОСТИКИ И ЛЕЧЕНИЯ
  7. III. Латентная преступность: понятие и методы выявления.
  8. III. Методы развития речи учащихся
  9. III. Основные методы биологических исследований.
  10. III. Процедурные методы анализа

 

В зависимости от размера (объёма вычислений) ветвей различают несколько уровней распараллеливания:

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-й: а01X, и а2Х2 и Х3;

3-й: а3Х3, Х42Х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 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав