ВУЗ:
Составители:
15
асинхронно. Механизм блокировок и семафоров используется для контроля доступа к
общей памяти
2.5 Объединение (агломерация) элементарных задач
На этом этапе проектирования производится объединение (укрупнение) ЭЗ. После
этапов разбиения и определения коммуникаций алгоритм, состоящий из ЭЗ является аб-
страктным в том смысле, что не может быть реализован на любой мультипроцессорной
системе. Например он может быть малоприемлем, если создает очень много задач малого
размера, а процессоры входящие в систему неэффективны при выполнении таких задач.
Поэтому на этой стадии просматриваются решения принятые на этапах разбиения и
определения коммуникаций с целью получения параллельного алгоритма, который эф-
фективно выполнялся бы на некотором классе мультипроцессорных систем. Нужно рас-
смотреть где полезно скомбинировать задачи полученные на этапе разбиения так, чтобы
обеспечить в результате наименьшее число задач, каждая из которых имеет наи-
больший размер.
Также на этом этапе нужно оценить где при выполнении алгоритма заслуживает
внимания размножение данных и/или операций с целью получения конечного результата
за минимальное время. При агломерации получаемое число задач сокращается (в идеаль-
ном случае одна задача на процессор), но еще может быть больше числа процессоров в
системе. В этом случае проектирование предусматривает следующий шаг - распределение
задач по процессорам. Соответственно на этапе агломерации нужно стремиться, чтобы в
результате была одна задача на процессор.
Три, как правило, взаимоконфликтующих цели преследуются при агломерации и раз-
множении данных и/или операций:
- сокращение стоимости коммуникаций за счет объединения взаимосвязанных ЭЗ ( ло-
кализация коммуникаций );
- сохранение гибкости по отношению к масштабируемости ( изменению размерности
задачи) и распределению задач по процессорам;
- сокращении стоимости инженерной разработки программного обеспечения ( софта ).
Рассмотрим каждую из них.
Локализация
коммуникаций. На этапе разбиения алгоритма на ЭЗ усилия сосредо-
тачивались на получении как можно большего числа задач. Это полезно, так как позволя-
ет рассмотреть широкий круг возможностей удобных для параллельного выполнения.
Однако, следует заметить, что получение большого числа задач при разбиении не обяза-
тельно дает эффективный параллельный алгоритм. Самое негативное влияние на выпол-
нение параллельного алгоритма ( по времени ), оказывают коммуникации. На большинст-
ве параллельных систем приходится останавливать вычисления чтобы послать или при-
нять сообщения. Поэтому значительно улучшится скорость вычисления, если сократить
время на коммуникации. Ясно, что это можно достичь пересылкой меньшего объема дан-
ных между задачами, выполняющимися параллельно. Возможно менее очевидно, но
со-
кратить время на коммуникации можно и при использовании меньшего числа сообщений
при тех же объемах данных. Это объясняется тем, что каждая коммуникация требует вре-
мя не только пропорциональное объему пересылаемых данных, но имеет фиксированные
начальные затраты времени по ее установлению. В дополнение к коммуникационным
асинхронно. Механизм блокировок и семафоров используется для контроля доступа к общей памяти 2.5 Объединение (агломерация) элементарных задач На этом этапе проектирования производится объединение (укрупнение) ЭЗ. После этапов разбиения и определения коммуникаций алгоритм, состоящий из ЭЗ является аб- страктным в том смысле, что не может быть реализован на любой мультипроцессорной системе. Например он может быть малоприемлем, если создает очень много задач малого размера, а процессоры входящие в систему неэффективны при выполнении таких задач. Поэтому на этой стадии просматриваются решения принятые на этапах разбиения и определения коммуникаций с целью получения параллельного алгоритма, который эф- фективно выполнялся бы на некотором классе мультипроцессорных систем. Нужно рас- смотреть где полезно скомбинировать задачи полученные на этапе разбиения так, чтобы обеспечить в результате наименьшее число задач, каждая из которых имеет наи- больший размер. Также на этом этапе нужно оценить где при выполнении алгоритма заслуживает внимания размножение данных и/или операций с целью получения конечного результата за минимальное время. При агломерации получаемое число задач сокращается (в идеаль- ном случае одна задача на процессор), но еще может быть больше числа процессоров в системе. В этом случае проектирование предусматривает следующий шаг - распределение задач по процессорам. Соответственно на этапе агломерации нужно стремиться, чтобы в результате была одна задача на процессор. Три, как правило, взаимоконфликтующих цели преследуются при агломерации и раз- множении данных и/или операций: - сокращение стоимости коммуникаций за счет объединения взаимосвязанных ЭЗ ( ло- кализация коммуникаций ); - сохранение гибкости по отношению к масштабируемости ( изменению размерности задачи) и распределению задач по процессорам; - сокращении стоимости инженерной разработки программного обеспечения ( софта ). Рассмотрим каждую из них. Локализация коммуникаций. На этапе разбиения алгоритма на ЭЗ усилия сосредо- тачивались на получении как можно большего числа задач. Это полезно, так как позволя- ет рассмотреть широкий круг возможностей удобных для параллельного выполнения. Однако, следует заметить, что получение большого числа задач при разбиении не обяза- тельно дает эффективный параллельный алгоритм. Самое негативное влияние на выпол- нение параллельного алгоритма ( по времени ), оказывают коммуникации. На большинст- ве параллельных систем приходится останавливать вычисления чтобы послать или при- нять сообщения. Поэтому значительно улучшится скорость вычисления, если сократить время на коммуникации. Ясно, что это можно достичь пересылкой меньшего объема дан- ных между задачами, выполняющимися параллельно. Возможно менее очевидно, но со- кратить время на коммуникации можно и при использовании меньшего числа сообщений при тех же объемах данных. Это объясняется тем, что каждая коммуникация требует вре- мя не только пропорциональное объему пересылаемых данных, но имеет фиксированные начальные затраты времени по ее установлению. В дополнение к коммуникационным 15
Страницы
- « первая
- ‹ предыдущая
- …
- 13
- 14
- 15
- 16
- 17
- …
- следующая ›
- последняя »