Вычислительные машины и системы. Ремонтов А.П - 24 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

24
ническая, системная проблема)
3. Перенос алгоритма на структуру.
Эти проблемы возникают на разных этапах построения параллельной ВС. Первая про-
блема связана со спецификой решаемой задачи и выбранного метода решения. Некото-
рые задачи очень хорошо распараллеливаются (например, многие задачи обработки
матриц), некоторые - очень плохо. Вторая - с решением вопросов взаимодействия па-
раллельных процессоров (например, обмен с памятью, межпроцессорный обмен,
синхронизация и др.) Третья - с возможностью реализации выбранного распаралле-
ленного алгоритма на данной параллельной структуре.
Конвейеризация вычислений - разбиение вычислений на последовательные этапы с
целью реализации этих этапов на отдельных ступенях конвейера для повышения произ-
водительности.
Конвейер - устройство, состоящее из N последовательно соединенных частей
(ступеней конвейера), каждая из которых выполняет очередной шаг вычислений за вре-
мя t (такт конвейера). Таким образом, для решения задачи, требующей N шагов, потребу-
ется время, равное t N, однако производительность конвейера может быть достаточно ве-
лика, поскольку освобождающиеся ступени могут заполняться новыми данными. В ре-
зультате на каждом такте конвейер может выдавать очередной результат.
Время решения одной задачи на конвейере:
Т реш = N t .
Производительность конвейера:
P = N'/(T
0
+ Nt);
где N' - количество задач, поступающих на вход конвейера.
Т
0
- время подготовки данных.
Из последней формулы видно, что при Т
0
« N t и N'→ N производитель-
ность конвейера стремится к величине 1 / t (пиковая производительность конвейе-
ра). В то же время, при Т
0
сопоставимом с N t (большое время загрузки и подготовки
конвейера), или при малом N' производительность конвейера будет ниже. Так же, как и в
случае распараллеливания, при конвейеризации возникают проблемы создания алгорит-
ма, создания структуры и перенесения алгоритма на структуру.
При этом к алгоритму предъявляют требования:
- отсутствие (минимальное количество) циклов и развилок ;
- возможность разбиения на шаги одинаковой длительности (и сложности); 
   ническая, системная проблема)
   3.         Перенос алгоритма на структуру.
   Эти проблемы возникают на разных этапах построения параллельной ВС. Первая про-
блема связана со спецификой решаемой задачи и выбранного метода решения. Некото-
рые задачи очень хорошо распараллеливаются (например, многие задачи обработки
матриц), некоторые - очень плохо. Вторая - с решением вопросов взаимодействия па-
раллельных процессоров (например, обмен с памятью, межпроцессорный обмен,
синхронизация и др.) Третья - с возможностью реализации выбранного распаралле-
ленного алгоритма на данной параллельной структуре.
   Конвейеризация вычислений - разбиение вычислений на последовательные этапы с
целью реализации этих этапов на отдельных ступенях конвейера для повышения произ-
водительности.
   Конвейер - устройство, состоящее из N последовательно соединенных частей
(ступеней конвейера), каждая из которых выполняет очередной шаг вычислений за вре-
мя t (такт конвейера). Таким образом, для решения задачи, требующей N шагов, потребу-
ется время, равное t N, однако производительность конвейера может быть достаточно ве-
лика, поскольку освобождающиеся ступени могут заполняться новыми данными. В ре-
зультате на каждом такте конвейер может выдавать очередной результат.
   Время решения одной задачи на конвейере:
   Т реш = N t .
   Производительность конвейера:
   P = N'/(T0 + Nt);
   где N' - количество задач, поступающих на вход конвейера.
   Т0 - время подготовки данных.


   И з п о с ле д н е й фо рм улы в и д н о , ч т о п р и Т 0 « N t и N ' → N производитель-
ность конвейера стремится к величине 1 / t (пиковая производительность конвейе-
ра). В то же время, при Т0 сопоставимом с N t (большое время загрузки и подготовки
конвейера), или при малом N' производительность конвейера будет ниже. Так же, как и в
случае распараллеливания, при конвейеризации возникают проблемы создания алгорит-
ма, создания структуры и перенесения алгоритма на структуру.


   При этом к алгоритму предъявляют требования:

   -    отсутствие (минимальное количество) циклов и развилок ;

   -    возможность разбиения на шаги одинаковой длительности (и сложности);


                                     24

Страницы