Понятие о матрице логической несовместимости. Внешние и внутренние замыкания в матрице

При оценке возможности параллельного выполнения про­граммных модулей важную роль играют логически несовмести­мые операторы. Рассмотрим множество вершин, принадлежащих ветви Т i-го логического оператора. Это множество назовем МTi. Аналогично построим множество вершин для дуги F — это множество вершин, принадлежащих ветви F i -го логического оператора множество MFi. В множества МTi и MFi сама вершина i не входит.

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

При реализации алгоритма в логическом операторе i выполня­ется либо ветвь Т, либо ветвь F, Следовательно, при планировании параллельных вычислений надо исключать планирование парал­лельного выполнения операторов, принадлежащих разным ветвям, т.е. попросту исключить их из планирования. Од­нако встречаются ситуации, когда ветви F и Т пересекаются, т. е. .

Если , то существует внутреннее за­мыкание i-го логического оператора. В этом случае операторы , могут планироваться для па­раллельного выполнения. Вершина имеющая наименьший но­мер, называется минимальной внутренне замкнутой вершиной i-гo логического оператора и обозначается inz_i

Следует отметить, что замыкание логических путей может осу­ществляться за счет внешних информационных связей. Целесообразно рассмотреть внешнее замыкание для ветвей Т и F отдельно. Это связано с тем, что при рассмотрении возможности параллельного выполнения операторов, включенных в логические ветви, необходимо учитывать результаты как внешнего, так и вну­треннего замыканий совместно, имея в виду при этом, что возможно внешнее замыкание только одной ветви.

Если существует информационный путь в вершину от начальной вершины граф-схемы, то вер­шина Z называется внешне замкнутой в ветви Т для i-го логиче­ского оператора. Если таких вершин несколько, то вершину Z с минимальным номером называют минимальной внешне замкнутой вершиной в ветви Т для i-го логического оператора. Обозначим эту вершину как ezT_i = X_i. Аналогично определя­ется внешнее замыкание ветви F, обозначающееся ezF_i.

Если множество содержит внешнее замыкание ezT=x_j, то подмножество называется внешне замкнутым для ветви Т логиче­ского оператора L_i. Если множество содержит внешнее замыкание ezF=x_j, то подмножество называется внешне замкнутым для ветви F логиче­ского оператора L_i.

При рассмотрении влияния внешних и внутренних замыканий на оценку возможности распараллеливания операторов необходимо учесть:

— что для распараллеливания операторов, принадлежащих пу­тям логического оператора, достаточно одного внешнего замыкания при наличии внутреннего;

— что внутреннее замыкание, как правило, порождает операто­ры, которые можно выполнять параллельно; что для определения множества MZ_i, всех замкнутых опера­торов i-го логического оператора требуется вычислить объединение множеств ;