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

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

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

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

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

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

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

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

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

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

Канал строго ограничен, если он имеет не более неиспользованных токенов для любого возможного исполнения. KPN строго ограничен , если все каналы строго ограничены .${\displaystyle б}$${\displaystyle б}$${\displaystyle б}$${\displaystyle б}$

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

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

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

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

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

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

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

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

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

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

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

Механизмы искусственного интеллекта в некоторых процессорах AMD Xilinx Versals являются строительными блоками сети процессов Kahn. ^[7]

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

• Ли, Э.А.; Паркс, Т.М. (1995). "Сети обработки потоков данных" (PDF) . Труды IEEE . 83 (5): 773–801. doi :10.1109/5.381846. ISSN  0018-9219 . Получено 13.02.2019 .
• Josephs, Mark B. (2005). "Models for Data-Flow Sequential Processes". В Abdallah, Ali E.; Jones, Cliff B.; Sanders, Jeff W. (ред.). Communicating Sequential Processes. Первые 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.