Инструменты пользователя

Инструменты сайта


examination:avs:question18

Параллелизм независимых ветвей.

Один из наиболее распространенных видов параллелизма. Суть заключается в том, что при решении большой задачи могут быть выделены отдельные независимые ветви, которые при наличии соответствующего устройства могут выполняться параллельно и независимо друг от друга.

Двумя независимыми ветвями программы называются такие части программы, при выполнении которых выполняется следующие условия:

  1. ни одна из входных для ветви программы величин не является выходной величиной другой ветви, что означает отсутствие функциональной связи;
  2. для обеих ветвей программы не должна производиться запись в одни и те же ячейки памяти, то есть отсутствует связь по использованию одних и тех же полей оперативной памяти.
  3. условия выполнения одной ветви не зависит от результатов или признаков, полученных при выполнении другой ветви, то есть это означает независимость по управлению.
  4. обе ветви должны выполняться по разным блокам программы, что означает программную независимость

Параллелизм независимых ветвей иллюстрирует ярусно – параллельная форма программы.

На рисунке программа в виде совокупности ветвей, которые расположены в нескольких ярусах. Кружки с цифрами - ветви программы. Около кружков обычно ставится длинна ветви. Стрелки обозначают входные данные и результаты обработки. На этом же графе могут быть указаны связи по управлению.

Выигрыш во времени обработки существенно колеблется в зависимости от последовательности выполнения ветвей каждым процессором. Поэтому процессор должен это учитывать при выборе новой ветви.

При решении задачи каждый процессор перед началом выполнения новой ветви должен иметь информацию о том, что данные для этой ветви готовы. Для того, чтобы с помощью нескольких обрабатывающих устройств решить задачу, имеющую независимые ветви, необходима соответствующая организация процессора, который определяет пути решения задачи и вырабатывает необходимую информацию о готовности каждой ветви. Это относительно легко реализовать, когда известна длительность вычисления каждой ветви. На практике это бывает редко, поэтому организация оптимального (близкого к оптимальному) графика работы – чрезвычайно сложная задача.

Практически трудно избегать простоев, которые возникают из – за отсутствия данных для той или иной ветви. Производительность снижается.

Существуют сложности, связанные с выделением независимых ветвей, при разработки программы. Хорошо поддаются параллельной обработке такого типа задачи матричной алгебры, линейного программирования, спектральной обработки сигналов, прямое и обратное быстрое преобразование Фурье (БПФ).

examination/avs/question18.txt · Последние изменения: 2014/01/15 08:10 (внешнее изменение)