Сети процессов Кана

Сеть процессов Кана ( KPN , или сеть процессов ) — это распределенная модель вычислений , в которой группа детерминированных последовательных процессов взаимодействует через неограниченные каналы «первым пришел — первым вышел» . Модель требует, чтобы чтение из канала было блокирующим , а запись неблокируемой . Из-за этих ключевых ограничений результирующая сеть процессов демонстрирует детерминированное поведение , которое не зависит ни от времени вычислений, ни от задержек связи .

Сети процессов Кана изначально были разработаны для моделирования параллельных программ, но оказались удобными для моделирования встроенных систем , высокопроизводительных вычислительных систем, систем обработки сигналов , систем потоковой обработки , языков программирования потоков данных и других вычислительных задач. KPN были представлены Жилем Каном в 1974 году.

Сеть процессов Кана с тремя процессами (вершинами) и тремя каналами связи (ребрами). Во время своего выполнения процесс P читает из каналов A и B и записывает в канал C.

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

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

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

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

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

как сети

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

Предполагая, что процесс P в приведенной выше KPN сконструирован таким образом, что он сначала считывает данные из канала A , затем из канала B , что-то вычисляет, а затем записывает данные в канал C , модель выполнения процесса можно смоделировать с помощью сети Петри , показанной справа. . Один токен в месте ресурса PE запрещает одновременное выполнение процесса для разных входных данных. Когда данные поступают в канал A или B , токены помещаются в места FIFO A и FIFO B соответственно. Переходы сети Петри связаны с соответствующими операциями ввода-вывода и вычислениями. Когда данные записаны в канал C , ресурс PE снова заполняется своей первоначальной маркировкой, позволяя читать новые данные.

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

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

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

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

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

Свойства

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

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

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

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

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

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

не Закрытая КПН имеет внешних входных и выходных каналов. Процессы, не имеющие входных каналов, выступают в качестве источников данных, а процессы, не имеющие выходных каналов, действуют как приемники данных. В открытой КПН каждый процесс имеет хотя бы один входной и выходной канал.

Детерминизм

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

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

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

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

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

Приложения

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

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

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

Механизм искусственного интеллекта в некоторых версиях AMD Xilinx является строительным блоком сети процессов Кана.

См. также

• Синхронный поток данных
• Коммуникация последовательных процессов
• Программирование на основе потока
• Программирование потоков данных

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

• Ли, Э.А.; Паркс, ТМ (1995). «Сети процессов потока данных» (PDF) . Труды IEEE . 83 (5): 773–801. дои : 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 . дои : 10.1007/11423348_6 . ISBN  978-3-540-32265-8 .