Детерминированность пары графов является наиболее важной их характеристикой. Это так уже хотя бы потому, что определить недетерминированность системы намного сложнее, чем ее недостоверность, поскольку зависаний системы не происходит и все данные считываются, но результат не является верным, детерминированным.
“Детерминированность” означает такое свойство, что, хотя модули были запущены асинхронно и параллельно, результат любого действия графа зависит единственно от первоначальной конфигурации данных и преобразований, выполненных модулями над данными. Для каждого первоначального состояния вычисление пары графов всегда достигает одного и того же конечного состояния, т.е. при одинаковом запуске системы и при известных исходных данных результат преобразований будет всегда один и тот же.
Очевидно, что последовательный граф детерминирован, так как отсутствует параллелизм. Пара графов детерминирована, если для каждой пары параллельных модулей в графе, скажем X и Y, X и Y не находятся в конфликте. Под “не в конфликте” мы понимаем, что не существует ничего, что требовало бы упорядочения выполнения какой-либо части X или Y для обеспечения правильной работы в целом. Если два модуля X и Y, которые находятся на одном уровне древовидной структуры графа управления, параллельны, то не должно существовать никаких конфликтов между X и Y или любым потомком X и любым потомком Y, если таковые имеются. Рассмотрим граф на рис.4, древовидная структура которого отображена на рис.5. После того, как мы удостоверимся, что a 2 и a 3 не конфликтуют друг с другом, и то же для a 4 и a 5, возникает необходимость проверить конфликтует ли a 2 с b 1 или b 2 и так далее, и конфликтует ли a 2 с c 1, c 2 или d 1, d 2 и так далее. Нет необходимости проверять наличие конфликтов с c 1 и c 2 или d 1, d 2 и d 3 так как они необязательны.
Конфликтная ситуация для двух параллельных модулей может существовать если:
а). Модули X и Y такие, что X может читать из памяти в тот момент времени, в который Y пишет в тот же элемент памяти (конфликт чтение/запись);
б). Два модуля X и Y могут одновременно писать в противообласть (конфликт типа запись/запись);
в). Модуль пишет в противообласть, которая может оказаться условием проверки в тот же момент времени (конфликт тест/ запись).
Чтобы иметь возможность проверить детерминированность пары графов мы сначала должны определить все параллельные модули графа управления, а затем проверить существуют ли между ними конфликты. Это можно сделать следующим образом. Если два модуля X и Y находятся на одном уровне древовидной структуры и в графе управления не существует пути между X и Y, то X и Y параллельны. Это записывается X*Y. Если X*Y и один из них, скажем Y, имеет потомков, то X и любой потомок Y могут быть параллельны. Если X*Y и оба из них имеют потомков, то любой потомок X и любой потомок Y могут быть параллельны.
Результат, приводимый ниже, указывает количество параллельных пар модулей, которые могут возникнуть из произвольного графа управления, показанного на рис.4, выведенные, используя этот метод:
a2 * a3 a2 * a5 a4 * a5 a5 * a6
a5 * a8 a5 * a9 a6 * a8 a7 * a8
a7 * a9 a8 * a10 a9 * a10
Если нет конфликтов между всеми параллельными модулями, то пара графов детерминирована.
Лекция № 6
Выделение параллелизма.
Одним из ключевых требований является преобразование исходного графа в граф, в котором, при условии детерминированности, набор модулей, которые могут работать параллельно, максимален. Самый безопасный путь, чтобы избежать недетерминированности,- это расположить все модули последовательно, что неэффективно. Простейший путь получения максимальной эффективности - это сделать все модули параллельными, но это может вызвать недетерминированность. Оптимальным решением является схема с максимальным параллелизмом, который не вызывает недетерминированности. Алгоритмы воссоздания такого нового графа управления организованы следующим образом:
Шаг 1: Возьмите любые два модуля, скажем м1 и м2, из одного уровня дерева графа управления. Если существует путь, скажем из м1 в м2, в первоначальном графе управления, и одно из описанных ниже условий (а), (б), выполняется, то включите дугу их м1 в м2 в новый граф управления. Повторяйте рекурсивный процесс, пока все модули не будут рассмотрены:
а). Ни один из них не является модулем проверки и существует путь между м1 и м2 в графе данных; или оба м1 и м2 используют одну противообласть в графе данных;
б). Один из них, скажем м1, является модулем проверки и м1 находится в противообласти м2; или непроверяющий модуль Х является потомком м1, и существует путь между Х и м2 в графе данных; или непроверяющий модуль Х является потомком м1, и оба Х и м2 имеет неразделенную противообласть в графе данных; или модуль проверки Х является потомком м1 и м2 имеет Х в своей противообласти.
Шаг 2: Удалите все лишние дуги. Если существует дуга из модуля м1 в модуль м2, а также существует другой путь из м1 в м2, то говорят, что первоначальная дуга лишняя.
Шаг 3: Связать START со всеми изолированными и левыми висячими модулями. Затем связать END со всеми правыми висячими модулями.