Технологические сети Кана ( KPN или технологические сети ) - это распределенная модель вычислений, в которой группа детерминированных последовательных процессов взаимодействует через неограниченные каналы « первым пришел - первым вышел» ( FIFO ). Результирующая технологическая сеть демонстрирует детерминированное поведение, которое не зависит от различных задержек вычислений или связи. Модель изначально была разработана для моделирования распределенных систем, но доказала свою удобство для моделирования систем обработки сигналов . Таким образом, KPN нашли множество приложений для моделирования встраиваемых систем , высокопроизводительных вычислений.системы и другие вычислительные задачи. KPN были впервые введены Жилем Каном . [1]
Модель исполнения
KPN - это общая модель для описания систем обработки сигналов , в которых бесконечные потоки данных постепенно преобразуются процессами, выполняющимися последовательно или параллельно. Несмотря на параллельные процессы, для выполнения этой модели не требуется многозадачность или параллелизм .
В KPN процессы взаимодействуют через неограниченные каналы FIFO . Процессы считывают и записывают элементарные элементы данных , также называемые токенами , из каналов и в каналы. Запись в канал является неблокирующей , то есть она всегда успешна и не останавливает процесс, в то время как чтение из канала блокируется , то есть процесс, который читает из пустого канала, остановится и может продолжаться только тогда, когда канал содержит достаточное количество элементов данных. ( жетоны ). Процессам не разрешается проверять входной канал на наличие токенов, не потребляя их. FIFO не может использоваться несколькими процессами, и несколько процессов не могут выполнять запись в один FIFO. Учитывая конкретную историю ввода (токена) для процесса, процесс должен быть детерминированным, чтобы он всегда давал одни и те же выходные данные (токены). Время или порядок выполнения процессов не должны влиять на результат, поэтому тестирование входных каналов для токенов запрещено.
Примечания к процессам
- Процессу не нужно читать какие-либо входные данные или иметь какие-либо входные каналы, поскольку он может действовать как чистый источник данных.
- Процесс не должен записывать какие-либо выходные данные или иметь какие-либо выходные каналы.
- Тестирование входных каналов на пустоту (или неблокирующее чтение ) может быть разрешено в целях оптимизации, но это не должно влиять на выходы. Это может быть полезно и / или возможно сделать что-то заранее, а не ждать канала. Например, предположим, что было два чтения из разных каналов. Если первое чтение остановится (ожидание токена), но второе чтение может быть успешным напрямую, может быть полезно сначала прочитать второе, чтобы сэкономить время, потому что само чтение часто занимает некоторое время (например, время для выделения памяти или копирования. ).
Семантика запуска процесса как сети Петри
Предполагая, что процесс P в приведенном выше KPN построен так, что он сначала считывает данные из канала A , затем из канала B , что-то вычисляет, а затем записывает данные в канал C , модель выполнения процесса может быть смоделирована с помощью сети Петри, показанной справа. . [2] Единственный маркер в месте ресурса PE запрещает процессу одновременное выполнение для разных входных данных. Когда данные поступают в канал A или B , токены помещаются в места FIFO A и FIFO B соответственно. Переходы сети Петри связаны с соответствующими операциями ввода-вывода и вычислениями. Когда данные были записаны в канал C , ресурс PE снова заполняется своей начальной маркировкой, позволяя читать новые данные.
Процесс как конечный автомат
Процесс можно смоделировать как конечный автомат, находящийся в одном из двух состояний:
- Активный; процесс вычисляет или записывает данные
- Ждать; процесс заблокирован (ожидает) данных
Предполагая, что конечный автомат считывает программные элементы, связанные с процессом, он может читать три вида токенов: «вычислить», «прочитать» и «записать токен». Кроме того, в Wait состоянии он может только вернуться к активному состоянию путем чтения специального «Get лексема» , который означает , что канал связи , связанный с ожиданием содержит читаемые данные.
Характеристики
Ограниченность каналов
Канал строго ограничен по если у него самое большее неиспользованные жетоны для любого возможного исполнения. КПН будет строго ограничена по если все каналы строго ограничены .
Количество неиспользованных токенов зависит от порядка выполнения ( планирования ) процессов. Спонтанный источник данных может произвести произвольное количество токенов в канал, если планировщик не будет выполнять процессы, потребляющие эти токены.
В реальном приложении не может быть неограниченных FIFO, и поэтому планирование и максимальная емкость FIFO должны быть реализованы на практике. Максимальная емкость FIFO может быть обработана несколькими способами:
- Границы FIFO могут быть получены математически при разработке, чтобы избежать переполнения FIFO. Однако это возможно не для всех KPN. Проверить, строго ли ограничена KPN. [ необходима цитата ] Более того, в практических ситуациях граница может зависеть от данных.
- Границы FIFO могут быть увеличены по запросу. [3]
- Блокирующая запись может использоваться, чтобы процесс блокировался, если FIFO заполнен. К сожалению, такой подход может привести к искусственному тупику, если разработчик должным образом не выведет безопасные границы для FIFO (Parks, 1995). Локальное искусственное обнаружение во время выполнения может быть необходимо, чтобы гарантировать получение правильного вывода. [4]
Закрытые и открытые системы
Закрытая КПН не имеет внешних входных и выходных каналов. Процессы, у которых нет входных каналов, действуют как источники данных, а процессы, у которых нет выходных каналов, действуют как приемники данных. В открытом KPN каждый процесс имеет как минимум один входной и выходной канал.
Детерминизм
Процессы КПН детерминированы . Для одной и той же истории ввода они всегда должны выдавать один и тот же результат. Процессы можно моделировать как последовательные программы, которые выполняют чтение и запись в порты в любом порядке и количестве, пока сохраняется свойство детерминизма. Как следствие, модель KPN является детерминированной, поэтому следующие факторы полностью определяют выходы системы:
- процессы
- сеть
- начальные токены
Следовательно, синхронизация процессов не влияет на выходы системы.
Монотонность
КПН процессы монотонны . Чтение большего количества токенов может привести только к написанию большего количества токенов. Токены, прочитанные в будущем, могут повлиять только на токены, написанные в будущем. В KPN существует общий порядок событий [ требуется пояснение ] внутри сигнала. [ требуется уточнение ] Однако между событиями в разных сигналах нет связи порядка. Таким образом, KPN заказаны только частично, что классифицирует их как бессрочные модели.
Приложения
Благодаря своей высокой выразительности и лаконичности, KPN в качестве основы модели вычислений применяются в нескольких инструментах академического моделирования для представления потоковых приложений, которые имеют определенные свойства (например, ориентированные на потоки данных, основанные на потоках).
Фреймворк Daedalus с открытым исходным кодом [5], поддерживаемый Leiden Embedded Research Center при Лейденском университете, принимает последовательные программы, написанные на C, и генерирует соответствующий KPN. Этот KPN может, например, использоваться для систематического сопоставления KPN с платформой на базе FPGA .
Ambric Am2045 в широком масштабе параллельного процессора массив является КПНО реализован в реальном кремнии. [6] Его 336 32-разрядных процессоров соединены программируемым межсоединением выделенных FIFO. Таким образом, его каналы строго ограничены блокирующей записью.
Смотрите также
Рекомендации
- ^ Кан, Г. (1974). Розенфельд, Джек Л. (ред.). Семантика простого языка параллельного программирования (PDF) . Proc. Конгресс ИФИП по обработке информации. Северная Голландия. ISBN 0-7204-2803-3.
- ^ Бернардески, C .; De Francesco, N .; Ваглини, Г. (1995). «Семантика сетей Петри для сетей с потоками данных» . Acta Informatica . 32 : 347–374.
- ^ Парки, Томас М. (1995). Ограниченное планирование технологических сетей (доктор философии). Калифорнийский университет в Беркли.
- ^ Гейлен, Марк; Бастен, Тван (2003). Дегано, П. (ред.). Требования к исполнению технологических сетей Кана . Proc. 12-й Европейский симпозиум по языкам и системам программирования (ESOP). Springer. С. 319–334. CiteSeerX 10.1.1.12.7148 .
- ^ http://daedalus.liacs.nl Фреймворк LIACS Daedalus
- ^ Майк Баттс, Энтони Марк Джонс, Пол Уоссон, «Модель программирования структурных объектов, архитектура, чип и инструменты для реконфигурируемых вычислений», Труды FCCM, апрель 2007 г., IEEE Computer Society
дальнейшее чтение
- Ли, EA; Парки, TM (1995). «Технологические сети потоков данных» (PDF) . Труды IEEE . 83 (5): 773–801. DOI : 10.1109 / 5.381846 . ISSN 0018-9219 . Проверено 13 февраля 2019 .
- Джозефс, Марк Б. (2005). «Модели для последовательных процессов потока данных». В Абдаллахе Али Э .; Джонс, Клифф Б.; Сандерс, Джефф В. (ред.). Связь последовательных процессов. Первые 25 лет: Симпозиум по случаю 25-летия CSP, Лондон, Великобритания, 7-8 июля 2004 г. Пересмотренные приглашенные доклады . Конспект лекций по информатике. 3525 . Берлин, Гейдельберг: Springer Berlin Heidelberg. С. 85–97. CiteSeerX 10.1.1.60.5694 . DOI : 10.1007 / 11423348_6 . ISBN 978-3-540-32265-8.