Проектирование параллельных алгоритмов в задачах идентификации. Вашкевич Н.П - 15 стр.

асинхронно. Механизм блокировок и семафоров используется для контроля доступа к
общей памяти
                2.5 Объединение (агломерация) элементарных задач
      На этом этапе проектирования производится объединение (укрупнение) ЭЗ. После
этапов разбиения и определения коммуникаций алгоритм, состоящий из ЭЗ является аб-
страктным в том смысле, что не может быть реализован на любой мультипроцессорной
системе. Например он может быть малоприемлем, если создает очень много задач малого
размера, а процессоры входящие в систему неэффективны при выполнении таких задач.
      Поэтому на этой стадии просматриваются решения принятые на этапах разбиения и
определения коммуникаций с целью получения параллельного алгоритма, который эф-
фективно выполнялся бы на некотором классе мультипроцессорных систем. Нужно рас-
смотреть где полезно скомбинировать задачи полученные на этапе разбиения так, чтобы
обеспечить в результате наименьшее число задач, каждая из которых имеет наи-
больший размер.
      Также на этом этапе нужно оценить где при выполнении алгоритма заслуживает
внимания размножение данных и/или операций с целью получения конечного результата
за минимальное время. При агломерации получаемое число задач сокращается (в идеаль-
ном случае одна задача на процессор), но еще может быть больше числа процессоров в
системе. В этом случае проектирование предусматривает следующий шаг - распределение
задач по процессорам. Соответственно на этапе агломерации нужно стремиться, чтобы в
результате была одна задача на процессор.
   Три, как правило, взаимоконфликтующих цели преследуются при агломерации и раз-
множении данных и/или операций:
   - сокращение стоимости коммуникаций за счет объединения взаимосвязанных ЭЗ ( ло-
       кализация коммуникаций );

  - сохранение гибкости по отношению к масштабируемости ( изменению размерности
       задачи) и распределению задач по процессорам;

  - сокращении стоимости инженерной разработки программного обеспечения ( софта ).

Рассмотрим каждую из них.
      Локализация коммуникаций. На этапе разбиения алгоритма на ЭЗ усилия сосредо-
тачивались на получении как можно большего числа задач. Это полезно, так как позволя-
ет рассмотреть широкий круг возможностей удобных для параллельного выполнения.
Однако, следует заметить, что получение большого числа задач при разбиении не обяза-
тельно дает эффективный параллельный алгоритм. Самое негативное влияние на выпол-
нение параллельного алгоритма ( по времени ), оказывают коммуникации. На большинст-
ве параллельных систем приходится останавливать вычисления чтобы послать или при-
нять сообщения. Поэтому значительно улучшится скорость вычисления, если сократить
время на коммуникации. Ясно, что это можно достичь пересылкой меньшего объема дан-
ных между задачами, выполняющимися параллельно. Возможно менее очевидно, но со-
кратить время на коммуникации можно и при использовании меньшего числа сообщений
при тех же объемах данных. Это объясняется тем, что каждая коммуникация требует вре-
мя не только пропорциональное объему пересылаемых данных, но имеет фиксированные
начальные затраты времени по ее установлению. В дополнение к коммуникационным



                                         15