|
2.2. Математическая модель модифицированной ГЕРТ-сети ГЕРТ-сети были использованы автором для оценки времени выполнения расчетов на кластере с параллельной и последовательной архитектурой обмена данными[54; 78] и анализа времени выполнения задачи на неспециализированном гетерогенном кластере Condor [42]. В процессе применения были выявлены следующие недостатки ГЕРТсетей: трудоемкость аналитического расчета средних и крупных сетей, отсутствие универсальных программных средств расчета ГЕРТ-сетей; детерминированность всех параметров ГЕРТ-сети (в силу 02 (2.14)); отсутствие методов выявления факторов, оказывающих наибольшее влияние на результат; наличие только двух параметров дуг (вероятность активации узла и функция распределения времени его выполнения), отсутствие «дополнительных переменных» и операций над ними. Результатом работы по изменению математической модели ГЕРТ-сети стала сеть, получившая название «модифицированная ГЕРТ-сеть» или МГЕРТ-сеть. При описании полученной модели сети, где это возможно, мы будем ссылаться на соответствующие утверждения и определения из математической модели ГЕРТ-сети. Все определения и термины, введенные в параграфе 2.1.1, а также с номерами (2.1)-(2.8) относятся и к МГЕРТ-сетям. Ограничения 1 и 3, введенные в параграфе 2.1.3 переносятся в модель МГЕРТ-сети без изменений. Обозначим их ограничения А и В. В силу ограничения 1 (или А), далее мы будем рассматривать только МГЕРТ-сети с одним источником. 49 |
Указанный выше алгоритм был модифицирован группой сотрудников Рязанской государственной радиотехнической академии [41; 76]. Для того чтобы получить численное значение закона распределения выходной величины ГЕРТ-сети, производится преобразование W-функций в соответствующие им характеристические функции. Полученные функции интерполируются многочленом Лагранжа второй степени с равностоящими узлами. Полученное выражение позволяет рассчитать на ЭВМ значение закона распределения времени выполнения ГЕРТ-сети в точке. Порядок вычислительных затрат равен 0 (пь n2) + O(q) + 0 (п3), где щ число дуг ГЕРТ-сети, п2—число узлов интерполяции, q число определяемых значений плотности вероятности, п3суммарное число петель порядков г, г=1, 2,..., п. 2.2 Математическая модель модифицированной ГЕРТ-сети ГЕРТ-сети были использованы автором для оценки времени выполнения расчетов на кластере с параллельной и последовательной архитектурой обмена данными [36; 60], анализа времени выполнения задачи на неспециализированном гетерогенном кластере Condor [24] и анализа времени изготовления деталей на конвейере, допускающем некоторый процент брака [25]. В процессе применения были выявлены следующие недостатки ГЕРТ-сетей: трудоемкость аналитического расчета средних и крупных сетей, отсутствие универсальных программных средств расчета ГЕРТ-сетей; детерминированность всех параметров ГЕРТ-сети (в силу 0 2 (2.14)); отсутствие методов выявления факторов, оказывающих наибольшее влияние на результат; наличие только двух параметров дуг (вероятность активации узла и функция распределения времени его выполнения), отсутствие «дополнительных переменных» и операций над ними. 37 Результатом работы по изменению математической модели ГЕРТ-сети стала сеть, получившая название «модифицированная ГЕРТ-сеть» или МГ-сеть. При описании полученной модели сети, где это возможно, мы будем ссылаться на соответствующие утверждения и определения из математической модели ГЕРТ-сети. Все определения и термины, введенные в параграфе 2.1.1, а также с номерами (2.1)-(2.8) относятся и к МГ-сетям. Для наглядности будем обозначать ограничения МГ-сети ON’ (буква «О» номер штрих). Ограничения 1 и 3, введенные в параграфе 2.1.3 переносятся в модель МГ-сети без изменений (О Г и 0 3 ’). В силу ограничения 1 (ОГ), далее мы будем рассматривать только МГ-сети с одним источником. Математическая модель МГ-сети изначально создавалась с учетом того, что следующим этапом будет разработка программного обеспеченья для расчета таких сетей. В основе модели лежит идея «трассировки» реализаций с отбором наиболее вероятных из них. Данный подход позволяет заменить требование детерминированности структуры сети и параметров ее дуг (0 2 ) на требование детерминированности структуры сети и вычислимости параметров выходящих дуг после активации узла, из которого они выходят. Ограничение 2’ (0 2 ’). (2.30) Для каждого узла i МГ-сети, если узел i активирован, то параметры всех выходящих из него дуг вычислимы. Алгоритм расчета МГ-сети допускает использования всех шести типов узлов. Для расчета параметров узлов с ANDи IOR-входами требуется предварительно не только рассчитать параметры всех входящих дуг, но и знать параметры узла, «породившего» процесс параллельного выполнения событий. 38 |