Технологические сети Кан - Kahn process networks

Технологические сети Кан (КПН, или же технологические сети) это распределен модель вычисления где группа детерминированных последовательных процессы общаются через неограниченные ФИФО каналы. Результирующая технологическая сеть демонстрирует детерминированное поведение, которое не зависит от различных задержек вычислений или связи. Модель изначально разрабатывалась для моделирования распределенные системы но доказал свое удобство для моделирования обработка сигналов системы. Таким образом, KPN нашли множество применений в моделировании. встроенные системы, высокопроизводительные вычисления системы и другие вычислительные задачи. KPN были впервые введены Жиль Кан.[1]

Технологическая сеть Кана из трех процессов без обратной связи. Ребра A, B и C - каналы связи. Один из процессов называется процессом P.

Модель исполнения

KPN - это общая модель для описания обработка сигналов системы, в которых бесконечные потоки данных постепенно преобразуются процессами, выполняющимися последовательно или параллельно. Несмотря на параллельные процессы, многозадачность или же параллелизм не требуются для выполнения этой модели.

В KPN процессы обмениваются данными через неограниченный ФИФО каналы. Процессы чтения и записи атомарные элементы данных или иначе называется жетоны, от и до каналов. Запись на канал - это неблокирующий, т.е. всегда успешно и не останавливает процесс, а чтение из канала блокировка, т.е. процесс, который читает из пустого канала, остановится и может продолжиться только тогда, когда канал содержит достаточно элементов данных (жетоны). Процессам не разрешается проверять входной канал на наличие токенов, не потребляя их. FIFO не может использоваться несколькими процессами, и несколько процессов не могут работать в одном FIFO. Учитывая конкретную историю ввода (токена) для процесса, процесс должен быть детерминированным, чтобы он всегда давал одни и те же выходные данные (токены). Время или порядок выполнения процессов не должны влиять на результат, поэтому тестирование входных каналов для токенов запрещено.

Примечания к процессам

  • Процесс не должен читать какие-либо входные данные или иметь какие-либо входные каналы, так как он может действовать как чистый источник данных.
  • Процесс не должен записывать какой-либо вывод или иметь какие-либо каналы вывода
  • Тестирование входных каналов на пустоту (или неблокирующее чтение) можно разрешить в целях оптимизации, но это не должно влиять на результаты. Это может быть полезно и / или возможно сделать что-то заранее, а не ждать канала. Например, предположим, что было два чтения из разных каналов. Если первое чтение остановилось (ожидание токена), но второе чтение могло быть прочитано токеном напрямую, было бы полезно сначала прочитать вторую, чтобы сэкономить время, потому что само чтение часто занимает некоторое время (например, время для памяти размещение или копирование).

Семантика запуска процесса как сети Петри

Семантика запуска процесса P, смоделированного с помощью Сеть Петри отображается на изображении выше

Предполагающий процесс п в приведенном выше KPN построена так, что сначала считывает данные из канала А, затем канал B, что-то вычисляет, а затем записывает данные в канал C, модель выполнения процесса может быть смоделирована с помощью Сеть Петри показано справа.[2] Единственный токен в PE ресурс place запрещает одновременное выполнение процесса для разных входных данных. Когда данные поступают на канал А или же B, жетоны размещаются по местам ФИФО А и ФИФО В соответственно. Переходы сети Петри связаны с соответствующими операциями ввода-вывода и вычислениями. Когда данные были записаны в канал C, PE ресурс снова заполняется первоначальной маркировкой, позволяющей считывать новые данные.

Процесс как конечный автомат

Конечный автомат процесса

Процесс можно смоделировать как конечный автомат, находящийся в одном из двух состояний:

  • Активный; процесс вычисляет или записывает данные
  • Ждать; процесс заблокирован (ожидает) данных

Предполагая, что конечный автомат считывает программные элементы, связанные с процессом, он может читать три вида токенов: «вычислить», «прочитать» и «записать токен». Кроме того, в Ждать заявить, что он может только вернуться к Активный состояние путем чтения специального «Get token», что означает, что канал связи, связанный с ожиданием, содержит читаемые данные.

Характеристики

Ограниченность каналов

Канал строго ограниченный к если у него самое большее неиспользованные токены для любого возможного выполнения. КПН - это строго ограниченный к если все каналы строго ограничены .

Количество неиспользованных токенов зависит от порядка исполнения (планирование) процессов. Спонтанный источник данных может произвести произвольное количество токенов в канал, если планировщик не будет выполнять процессы, потребляющие эти токены.

Реальное приложение не может иметь неограниченных FIFO, и поэтому планирование и максимальная емкость FIFO должны быть реализованы на практике. Максимальную емкость FIFO можно обрабатывать несколькими способами:

  • Границы FIFO можно вычислить математически, чтобы избежать переполнения FIFO. Однако это возможно не для всех KPN. Проверить, строго ли ограничена KPN .[нужна цитата ] Более того, в практических ситуациях граница может зависеть от данных.
  • Границы FIFO могут быть увеличены по запросу.[3]
  • Блокирующая запись может использоваться, чтобы процесс блокировался, если FIFO заполнен. К сожалению, такой подход может привести к искусственному тупику, если разработчик правильно не выведет безопасные границы для FIFO (Parks, 1995). Локальное искусственное обнаружение во время выполнения может быть необходимо, чтобы гарантировать получение правильного вывода.[4]

Закрытые и открытые системы

А закрытый КПН не имеет внешних входных или выходных каналов. Процессы, у которых нет входных каналов, действуют как источники данных, а процессы, у которых нет выходных каналов, действуют как приемники данных. В открыть КПН у каждого процесса есть как минимум один входной и выходной канал.

Детерминизм

Процессы КПН детерминированный. Для одной и той же истории ввода они всегда должны выдавать один и тот же результат. Процессы можно моделировать как последовательные программы, которые выполняют чтение и запись в порты в любом порядке и количестве, пока сохраняется свойство детерминизма. Как следствие, модель KPN является детерминированной, поэтому следующие факторы полностью определяют выходы системы:

  • процессы
  • сеть
  • начальные токены

Следовательно, синхронизация процессов не влияет на результаты работы системы.

Монотонность

KPN процессы монотонный, что означает, что им нужна только частичная информация входного потока, чтобы произвести частичную информацию выходного потока. Монотонность допускает параллелизм. В КПН есть общий заказ событий[требуется разъяснение ] внутри сигнала.[требуется разъяснение ] Однако нет никакого отношения порядка между событиями в разных сигналах. Таким образом, KPN упорядочены лишь частично, что классифицирует их как неподготовленная модель.

Приложения

Благодаря своей высокой выразительности и лаконичности, KPN в качестве основы модели вычислений применяются в нескольких инструментах академического моделирования для представления потоковых приложений, которые имеют определенные свойства (например, ориентированные на потоки данных, основанные на потоках).

Фреймворк Daedalus с открытым исходным кодом[5] поддерживается Лейденским центром встраиваемых систем в Лейденский университет принимает последовательные программы, написанные на C, и генерирует соответствующий KPN. Этот KPN может, например, использоваться для сопоставления KPN с FPGA на базе платформы систематически.

В Ambric Am2045 массив массивно-параллельных процессоров представляет собой KPN, реализованный в реальном кремнии.[6] Его 336 32-разрядных процессоров соединены программируемым межсоединением выделенных FIFO. Таким образом, его каналы строго ограничены блокирующей записью.

Смотрите также

Рекомендации

  1. ^ Кан, Г. (1974). Розенфельд, Джек Л. (ред.). Семантика простого языка параллельного программирования (PDF). Proc. Конгресс ИФИП по обработке информации. Северная Голландия. ISBN  0-7204-2803-3.
  2. ^ Bernardeschi, C .; De Francesco, N .; Ваглини, Г. (1995). «Семантика сетей Петри для сетей потоков данных». Acta Informatica. 32: 347–374.
  3. ^ Парки, Томас М. (1995). Ограниченное планирование технологических сетей (Кандидат наук.). Калифорнийский университет в Беркли.
  4. ^ Гейлен, Марк; Бастен, Тван (2003). Дегано, П. (ред.). Требования к исполнению технологических сетей Кана. Proc. 12-й Европейский симпозиум по языкам и системам программирования (ESOP). Springer. С. 319–334. CiteSeerX  10.1.1.12.7148.
  5. ^ http://daedalus.liacs.nl Фреймворк LIACS Daedalus
  6. ^ Майк Баттс, Энтони Марк Джонс, Пол Уоссон, «Модель программирования структурных объектов, архитектура, микросхема и инструменты для реконфигурируемых вычислений», Proceedings of FCCM, Апрель 2007 г., IEEE Computer Society

дальнейшее чтение

  • Lee, E.A .; Паркс, Т. (1995). «Технологические сети потока данных» (PDF). Труды IEEE. 83 (5): 773–801. Дои:10.1109/5.381846. ISSN  0018-9219. Получено 2019-02-13.
  • Джозефс, Марк Б. (2005). "Модели для последовательных процессов потока данных". В Али Э. Абдаллахе; Клифф Б. Джонс; Джефф В. Сандерс (ред.). Связь последовательных процессов. Первые 25 лет: Симпозиум по случаю 25-летия CSP, Лондон, Великобритания, 7-8 июля 2004 г. Пересмотренные приглашенные доклады. Конспект лекций по информатике. 3525. Берлин, Гейдельберг: Springer Berlin Heidelberg. С. 85–97. CiteSeerX  10.1.1.60.5694. Дои:10.1007/11423348_6. ISBN  978-3-540-32265-8.