Информационная система "Конференции"

Тезисы докладов

Информационные технологии

В теории параллелизма известно большое разнообразие моделей параллелизма. Чтобы унифицировать и классифицировать их, последнеие десятилетия стали активно применяться методы теории категорий [2]. Основная идея данного подхода заключается в следующем. Объекты категорий представляют процессы, а морфизмы соответствуют взаимосвязям между поведениями процессов. Чаще всего взаимосвязи устанавливаются в виде пары сопряженных функторов или корефлексии (особого вида сопряжения).

Особое место среди параллельных систем занимают системы реального времени, поведение которых в значительной степени зависит от количественных временных характеристик. Для систем реального времени важны как модели вычислений, так и модели времени. В литературе такие системы часто представляются временными автоматами [1] и подобными моделями. Однако все эти формализмы базируются на интерливинговой семантике и не позволяют моделировать параллелизм естественным образом (напрямую).

Цель данной работы - построить временные расширения хорошо известной модели параллелизма с семантикой "истинного параллелизма" - систем переходов с независимостью [3], и определить для них семантику помеченных областей. Время моделируется при помощи наборов целочисленных задержек, связанных с каждым переходом. Задержки являются минимальными моментами глобального времени, после которых данный переход может выполниться. При этом i-е выполнение перехода может произойти не раньше, чем момент времени указанный в i-й задержке, и количество срабатываний перехода не может быть больше, чем количество связанных с ним задержек. Само выполнение перехода является мгновенным. Для построения семантики определяются категории моделей категории, и строится цепь корефлексий от категории временных систем переходов с независимостью до категории помеченных областей.

Литература
[1] Alur, R., Dill, D. The theory of timed automata. Theoretical Computer Science 126, (1994), 183-235.
[2] MacLane, S. Categories for the working mathematician. GTM, Springer-Verlag, 1971.
[3] Sassone, V., Nielsen, M., Winskel, G. Models for concurrency: towards a classification. Theoretical Computer Science, 170, (1996), 297-384.

Дополнительные материалы:

Полный текст доклада

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:48:14)