Расширенный метод редукции графов с анализом КЧ
 

Метод редукции графов для определения среднего T и дисперсии D времени процесса предложен Байцером [3]. Феррари [4] предлагает дополнить его анализом чувствительности величин T и D к параметрам графа, вычисляя соответствующие част-ные производные методом малых приращений. В работе [5] метод редукции графа расширен набором подстановок и пересчетных соотношений, позволяющих получать в однократном процессе редукции сразу все необходимые КЧ, вычисленные по точным формулам аналитического дифференцирования.
Метод редукции графа заключается в последовательной замене типовых фраг-ментов графа на более простые фрагменты, эквивалентные в смысле времени прохож-дения через них исследуемого процесса. Пересчетные формулы, по которым определя-ются параметры вершин и дуг заменяющего фрагмента через параметры заменяемого, достаточно легко выводятся в предположении статистической независимости всех за-держек в вершинах и случайных переходов. Обычно редукция завершается стягивани-ем графа в одну вершину, параметры которой T и D являются искомыми характеристи-ками длительности всего процесса.
Метод редукции, предложенный в [5], содержит расширенный набор типовых замен. Наряду со «свертыванием цепочки вершин», «размыканием петли», «параллель-ным объединением» и т. д. он позволяет трансформировать некоторые циклы специ-ального вида, присущие процессам в вычислительных системах и характеризуемые за-висимостью переходов. Кроме того, в этом варианте метода состав всех пересчетных соотношений расширен дополнительными соотношениями, по которым рассчитывают-ся частные производные параметров заменяющего подграфа по всем параметрам заме-няемого подграфа. Эти дополнительные соотношения получены путем формального дифференцирования основных пересчетных соотношений. Они позволяют на каждом шаге редукции (с учетом правил дифференцирования суперпозиции функций многих переменных) вместе с параметрами нового подграфа вычислять их частные производ-ные по изначально заданным параметрам исходного графа.
Таким образом, в результате редукции графа вместе с показателями T и D опре-деляются значения их частных производных по всем n параметрам исходного графа (абсолютные КЧ), а также относительные КЧ, имеющие вид:

Метод эффективно реализован программой COIN1 (COefficients of INfluence – коэффициенты влияния), которая написана на Borland C++ 3.1. Она позволяет выпол-нять редукцию полных графов с отмеченными начальной и конечной вершинами. Входные данные для программы представляются в текстовом файле, выходные данные отображаются в графической форме и выводятся в текстовый файл.

 
назад

вперед