ПОНЯТИЕ О МАТРИЦЕ ЛОГИЧЕСКОЙ НЕСОВМЕСТИМОСТИ. ВНЕШНИЕ И ВНУТРЕННИЕ ЗАМЫКАНИЯ В ИНФОРМАЦИОННО-ЛОГИЧЕСКОМ ГРАФЕ.
При оценке возможности параллельного выполнения программных модулей важную роль играют логически несовместимые операторы. Рассмотрим множество вершин, принадлежащих ветви Т i-го логического оператора. Это множество назовем МTi. Аналогично построим множество вершин для дуги F — это множество вершин, принадлежащих ветви F i-го логического оператора множество MFi. В множества МTi и MFi сама вершина i не входит. Если вершина j и могут выполняться либо один, либо другой соответствующие им операторы при однократном выполнении алгоритма, то эти операторы называются логически несовместимыми. При реализации алгоритма в логическом операторе i выполняется либо ветвь Т, либо ветвь F, Следовательно, при планировании параллельных вычислений надо исключать планирование параллельного выполнения операторов, принадлежащих разным ветвям, т.е. попросту исключить их из планирования. Однако встречаются ситуации, когда ветви F и Т пересекаются, т. е. . Если , то существует внутреннее замыкание i-го логического оператора. В этом случае операторы , могут планироваться для параллельного выполнения. Вершина имеющая наименьший номер, называется минимальной внутренне замкнутой вершиной i-гo логического оператора и обозначается inzi Следует отметить, что замыкание логических путей может осуществляться за счет внешних информационных связей. Целесообразно рассмотреть внешнее замыкание для ветвей Т и F отдельно. Это связано с тем, что при рассмотрении возможности параллельного выполнения операторов, включенных в логические ветви, необходимо учитывать результаты как внешнего, так и внутреннего замыканий совместно, имея в виду при этом, что возможно внешнее замыкание только одной ветви. Если существует информационный путь в вершину от начальной вершины граф-схемы, то вершина Z называется внешне замкнутой в ветви Т для i-го логического оператора. Если таких вершин несколько, то вершину Z с минимальным номером называют минимальной внешне замкнутой вершиной в ветви Т для i-го логического оператора. Обозначим эту вершину как ezTi = Xi. Аналогично определяется внешнее замыкание ветви F, обозначающееся ezFi. Если множество содержит внешнее замыкание ezT=xj, то подмножество называется внешне замкнутым для ветви Т логического оператора Li. Если множество содержит внешнее замыкание ezF=xj, то подмножество называется внешне замкнутым для ветвиF логического оператора Li. При рассмотрении влияния внешних и внутренних замыканий на оценку возможности распараллеливания операторов необходимо учесть: — что для распараллеливания операторов, принадлежащих путям логического оператора, достаточно одного внешнего замыкания при наличии внутреннего; — что внутреннее замыкание, как правило, порождает операторы, которые можно выполнять параллельно; что для определения множества MZi, всех замкнутых операторов i-го логического оператора требуется вычислить объединение множеств ;
Популярное: ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (396)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |