Cтраница 3
В качестве альтернативы для редукции графов, где вычисление выражения инициируется, только когда требуется его значение, можно придумать графовую модель, в которой выражение вычисляется при первой возможности; другими словами, применение функции в такой модели имеет место, как только аргументы этой функции становятся доступными. При этом вычисление начинается при наличии аргументов, а не тогда, когда имеется запрос, а результирующая модель вычислений называется потоковой. Потоковая модель естественным образом является управляемой данными и может рассматриваться как оптимизированная форма энергичной редукции графов. Потоковые реализации описываются в гл. [31]
Потоковые модели стали использоваться для описания динамики кадровых систем сравнительно недавно. Интенсивное развитие современной теории графов позволяет надеяться, что ее результаты будут находить все более широкое применение наряду с другими приложениями и для анализа функционирования кадровых систем. Особенность потоковых моделей состоит в том, что изменение состава кадровой системы рассматривается как результат взаимодействия динамических кадровых потоков. Такой подход позволяет анализировать динамику кадров и строить алгоритмы оптимального управления ими. [32]
Реализация динамического механизма предполагает выполнение некоторых условий, в частности, наступление событий, при которых возможно создание и уничтожение процессов в ходе вычислений. Так, модель CSP [106] поддерживает динамическое порождение процессов без ограничения их числа. В противоположность ей потоковая модель SDF [122] представляет статическое задание ограниченного числа процессов. В языке Occam, воплощающем идеи CSP, число процессов ограничивается. В модели Кана [113] обеспечивается статическое порождение процессов с неограниченным уровнем рекурсивного параллелизма. [33]
Другая часть публикаций касается использования сетевых потоковых моделей линейного и кусочно-линейного программирования ( являющихся приближенными в том плане, что они не учитывают в полной мере уравнений второго закона Кирхгофа) для управления потокораспределением в Единой системе газоснабждения [228] и других многоконтурных ТПС. Имеются также отдельные работы по относительно частным задачам, связанным с оптимизацией выходных параметров источников и распределением между ними суммарной нагрузки. [34]
Понятие события часто используется в различных сетевых моделях вычислений [30, 124], хотя трактуется оно по-разному. Например, в сетях Петри [30] и их расширениях [138] события моделируются переходами. В рассмотренных в § 2.3 потоковых моделях характер событий, связанных с формированием входных и выходных сообщений процессов, определяется метками соответствующих позиций вершин. Так, маркировка входных и выходных позиций вершин М - сети может интерпретироваться как число начальных и особых событий, наступление которых ассоциируется с формированием токенов в компонентах входных и выходных сообщений. [35]
Несмотря на простоту и наглядность этих моделей для описания процессов продвижения кадров, при использовании большинства из них требуется стабильность параметров по времени - гипотеза, которая не часто выполняется на практике. Это довольно сильное условие применимости указанных моделей удается обойти в потоковых моделях кадровых систем. [36]
Хотя публикации [125, 126] по большей части охватывают вопросы разработки моделей выполнения программ во встроенных системах, описываемые в них механизмы взаимодействия параллельных процессов широко применяются и в распределенных системах. В [124, 125] в числе прочих рассматриваются упоминаемые в § 1.2 модели CSP, CCS, Кана, Денниса, SDF и приводятся ссылки на соответствующие источники. В [124] предложен формализм для сравнения моделей вычислений: рассматриваются механизм рандеву в моделях CSP и CCS, асинхронный обмен сообщениями, сети Петри, потоковые модели Денниса, SDF, сети процессов Кана и др., исследуются проблемы детерминизма композиции процессов с частично упорядоченными событиями. [37]
G ( см. § 2.3) соответствует модели распределенных вычислений, в которой процессы взаимодействуют посредством асинхронного обмена сообщениями через буферы. Как уже говорилось, процессы могут иметь как входные, так и выходные либо только входные буферы. Семантически обе модели эквивалентны. Проблема блокировки, или реализуемости потоковых моделей, заключается в таком согласовании параметров буферов ( очередей сообщений), чтобы учесть все допустимые истории процессов программы, когда ни один из них не блокируется из-за отсутствия входных сообщений. Исследование реализуемости вычислений может быть сведено к процедуре разметки М - сети. Напомним, маркировка входных и выходных позиций вершин М - сети соответствует ширине буфера ( см. рис. 2.6 и рис. 2.7), а метки дуг позволяют получить число сообщений ( или глубину буфера), гарантирующее отсутствие зависаний программы при любых допустимых историях процессов. [38]