2015-05-10
776
Критерий выделения параллельных ветвей для машин класса МКМД (MIMD)
При распараллеливании последовательного алгоритма, основным критерием при выделении в задаче параллельных является взаимная независимость операций входящих в алгоритм по входным и выходным данным.
Для того, чтобы проиллюстрировать вышесказанное рассмотрим небольшой пример:
Пусть имеется фрагмент текста исходной, последовательной программы.
| № операций | Операторы |
| A=1; B=3; C=8; D=A+B*5; X=6/(D*C-2*A); Y=8*X/B; Z=4+A+D; |
Сразу необходимо обратить ваше внимание на то, что в правой колонке написаны операторы, а в левой колонке номера операций. В действительности, при распараллеливании, всегда распараллеливаются операции, а не операторы. В нашем случае, ввиду отсутствия циклов и других управляющих операторов, номера операторов и операций совпадают.
Определим теперь исходя из критерия взаимонезависимости по данным, какие из операций могут выполнятся параллельно, а какие нет. Для этого просто составим таблицу использования данных.
|
|
|
Таблица 3.1
| Переменная | Номера операций | ||||||
| A | O | I | I | I | |||
| B | O | I | I | ||||
| C | O | I | |||||
| D | O | I | I | ||||
| X | O | I | |||||
| Y | O | ||||||
| Z | O |
-где I-означает что переменная является входной, а O-выходной в данной операции.
Для того чтобы выделить параллельные ветви в нашем фрагменте программы, надо определить взаимозависимость операций по данным. Во первых, параллельно не могут выполнятся операции где одни и те же переменные создаются (являются выходными) и используются (являются входными). Например: операции 2 и 4. Во вторых, при любом раскладе, данные не могут быть использованы до того, как они были инициализированы. Последнее условие влияет на распределение операций по ярусам графа ЯПФ. Все эти условия можно учесть, используя таблицу 3.1. Например: операция 5 может идти только после операции 2 из-за использования переменной B в операции 4 при вычислении D.
Ниже представлен получившийся граф ЯПФ фрагмента нашей программы (см. рис 3.1).
 |
Рис. 3.1. Граф ЯПФ
В действительности, дело с выявлением параллельных ветвей обстоит не так уж просто. Достаточно вспомнить «многокилометровые» программные тексты с множеством условных операторов, циклов и многомерных структур данных. Далее, в следующем пункте, приведено более подробное описание критерия выделения параллельных ветвей в программе и описание алгоритма автоматизации этого процесса.
