Введение
Модель вычислений
Сеть процессов Кана (KPN, или сеть процессов) — это распределенная модель вычислений, в которой группа детерминированных последовательных процессов взаимодействует посредством неограниченных каналов типа «первый пришел — первый ушел». Модель требует, чтобы чтение из канала было блокирующим, а запись — неблокирующим. Благодаря этим ключевым ограничениям, полученная сеть процессов демонстрирует детерминированное поведение, не зависящее от времени вычислений и задержек связи. Сети процессов Кана изначально разрабатывались для моделирования параллельных программ, но оказались полезными для моделирования встраиваемых систем, высокопроизводительных вычислительных систем, систем обработки сигналов, систем потоковой обработки, языков программирования потоковых данных и других вычислительных задач. KPN были введены Жилем Каном в 1974 году.
A Kahn process network (KPN, or process network) is a distributed model of computation in which a group of deterministic sequential processes communicate through unbounded first in, first out channels. The model requires that reading from a channel is blocking while writing is non blocking. Due to these key restrictions, the resulting process network exhibits deterministic behavior that does not depend on the timing of computation nor on communication delays. Kahn process networks were originally developed for modeling parallel programs, but have proven convenient for modeling embedded systems, high performance computing systems, signal processing systems, stream processing systems, dataflow programming languages, and other computational tasks. KPNs were introduced by Gilles Kahn in 1974.
Модель исполнения
KPN – это распространенная модель для описания систем обработки сигналов, в которых бесконечные потоки данных инкрементно преобразуются процессами, выполняющимися последовательно или параллельно. Несмотря на наличие параллельных процессов, для реализации этой модели не требуется многозадачность или параллелизм. В KPN процессы взаимодействуют посредством неограниченных FIFO-каналов. Процессы читают и записывают атомарные элементы данных, также называемые токенами, в каналы и из каналов. Запись в канал является неблокирующей, то есть она всегда выполняется успешно и не приводит к остановке процесса, в то время как чтение из канала является блокирующим, то есть процесс, пытающийся прочитать из пустого канала, будет заблокирован и сможет продолжить работу только при наличии достаточного количества элементов данных (токенов) в канале. Процессам запрещено проверять наличие токенов во входном канале без их извлечения. К одному FIFO-каналу не может одновременно обращаться несколько процессов для чтения или записи. Для заданной истории входных данных (токенов) процесс должен быть детерминированным, то есть всегда выдавать один и тот же результат (токены). Время или порядок выполнения процессов не должны влиять на результат, поэтому проверка входных каналов на наличие токенов запрещена.
Обработка семантики запуска в виде сетей Петри
Предполагая, что процесс P в вышеуказанном KPN сконструирован таким образом, что он сначала считывает данные из канала A, затем из канала B, выполняет вычисления и затем записывает данные в канал C, модель выполнения процесса может быть представлена сетью Петри, показанной справа. Единственный токен в ресурсном месте PE запрещает одновременное выполнение процесса для разных входных данных. Когда данные поступают в канал A или B, токены помещаются в места FIFO A и FIFO B соответственно. Переходы в сети Петри соответствуют соответствующим операциям ввода-вывода и вычислениям. После записи данных в канал C ресурс PE возвращается к своей начальной разметке, что позволяет считывать новые данные.
Ограниченность каналов
Канал строго ограничен, если для любого возможного выполнения в нем не более неиспользованных токенов. KPN строго ограничен, если все его каналы строго ограничены. Количество неиспользованных токенов зависит от порядка выполнения (планирования) процессов. Спонтанный источник данных может генерировать произвольное количество токенов в канал, если планировщик не выполняет процессы, потребляющие эти токены. Реальное приложение не может иметь FIFO неограниченного размера, поэтому планирование и максимальная емкость FIFO должны быть учтены при практической реализации. Максимальную емкость FIFO можно реализовать несколькими способами: границы FIFO могут быть математически вычислены на этапе проектирования, чтобы избежать переполнения. Однако это возможно не для всех KPN. Проверка, является ли KPN строго ограниченным, является неразрешимой задачей. Более того, в практических ситуациях граница может зависеть от данных. Границы FIFO могут увеличиваться динамически по мере необходимости. Можно использовать блокирующие операции записи, чтобы процесс блокировался при заполнении FIFO. К сожалению, такой подход может привести к искусственному тупику, если разработчик не определит безопасные границы для FIFO (Parks, 1995). Для гарантии получения корректного результата может потребоваться локальное обнаружение потенциальных проблем во время выполнения.
The number of unconsumed tokens depends on the execution order (scheduling) of processes. A spontaneous data source could produce arbitrarily many tokens into a channel if the scheduler would not execute processes consuming those tokens. A real application can not have unbounded FIFOs and therefore scheduling and maximum capacity of FIFOs must be designed into a practical implementation. The maximum capacity of FIFOs can be handled in several ways:
FIFO bounds can be mathematically derived in design to avoid FIFO overflows. This is however not possible for all KPNs. It is an undecidable problem to test whether a KPN is strictly bounded by Moreover, in practical situations, the bound may be data dependent. FIFO bounds can be grown on demand. Blocking writes can be used so that a process blocks if a FIFO is full. This approach may unfortunately lead to an artificial deadlock unless the designer properly derives safe bounds for FIFOs (Parks, 1995). Local artificial detection at run time may be necessary to guarantee the production of the correct output.
Закрытые и открытые системы
Закрытая КПН не имеет внешних входных или выходных каналов. Процессы, не имеющие входных каналов, являются источниками данных, а процессы, не имеющие выходных каналов, – потребителями данных. В открытой КПН каждый процесс имеет как минимум один входной и один выходной канал.
Монотонность
Процессы KPN монотонны. Чтение большего количества токенов может привести только к записи большего количества токенов. Токены, прочитанные в будущем, могут влиять только на токены, записанные в будущем. В KPN существует полный порядок событий внутри сигнала. Однако между событиями в разных сигналах нет отношения порядка. Таким образом, KPN частично упорядочены, что классифицирует их как модель без временных ограничений.
Приложения
Из-за высокой выразительности и лаконичности, сети процессов Кана (KPN) в качестве базовой модели вычислений используются в нескольких академических инструментах моделирования для представления потоковых приложений, обладающих определенными свойствами (например, ориентированными на потоки данных и основанными на потоках). Фреймворк Daedalus с открытым исходным кодом, поддерживаемый Лейденским центром встроенных исследований при Лейденском университете, принимает последовательные программы, написанные на языке C, и генерирует соответствующую KPN. Полученную KPN можно, например, использовать для систематического сопоставления KPN с платформой на основе FPGA. Массивно-параллельный процессорный массив Ambric Am2045 представляет собой KPN, реализованную в кремнии. Его 336 32-битных процессоров соединены программируемой межсоединительной сетью из выделенных FIFO. Таким образом, его каналы имеют строгую ограниченную емкость и используют блокирующие записи. AI Engine в некоторых устройствах AMD Xilinx Versal являются строительными блоками сети процессов Кана.