Процесс Кан сети (KPN или технологические сети) - это распределенная модель вычислений, в которой группа детерминированных последовательных процессов взаимодействует через неограниченный FIFO каналов. Результирующая технологическая сеть демонстрирует детерминированное поведение, которое не зависит от различных задержек вычислений или связи. Модель была первоначально разработана для моделирования распределенных систем, но доказала свое удобство для моделирования систем обработки сигналов. Таким образом, KPN нашли множество приложений для моделирования встроенных систем, систем высокопроизводительных вычислений и других вычислительных задач. KPN были впервые введены Жилем Каном.
Технологическая сеть Кана из трех процессов без обратной связи. Ребра A, B и C - каналы связи. Один из процессов называется процессом P.KPN - это общая модель для описания систем обработки сигналов, в которых бесконечные потоки данных постепенно преобразуются процессами, выполняющимися последовательно или параллельно. Несмотря на параллельные процессы, для выполнения этой модели не требуется многозадачность или параллелизм.
В KPN процессы взаимодействуют через неограниченные каналы FIFO. Процессы считывают и записывают атомарные элементы данных или, альтернативно, называемые токенами из каналов и в каналы. Запись в канал неблокирующая, т.е. она всегда успешна и не останавливает процесс, в то время как чтение из канала блокируется, т.е. процесс, который читает из пустого канала, остановится и может продолжаться только тогда, когда канал содержит достаточное количество элементов данных (токенов). Процессам не разрешается проверять входной канал на наличие токенов, не потребляя их. FIFO не может использоваться несколькими процессами, и несколько процессов не могут работать в одном FIFO. Учитывая конкретную историю ввода (токена) для процесса, процесс должен быть детерминированным, чтобы он всегда давал одни и те же выходные данные (токены). Время или порядок выполнения процессов не должны влиять на результат, поэтому тестирование входных каналов для токенов запрещено.
Предполагая, что процесс P в KPN выше построен так что сначала он считывает данные из канала A, затем из канала B, что-то вычисляет, а затем записывает данные в канал C, модель выполнения процесса может быть смоделирована с помощью сети Петри, показанной справа. Единый токен в месте ресурса PE запрещает одновременное выполнение процесса для разных входных данных. Когда данные поступают в канал A или B, токены помещаются в места FIFO A и FIFO B соответственно. Переходы сети Петри связаны с соответствующими операциями ввода-вывода и вычислениями. Когда данные были записаны в канал C, ресурс PE снова заполняется своей начальной маркировкой, позволяя читать новые данные.
Процесс можно смоделировать как конечный автомат, находящийся в одном из двух состояний:
Предполагая, что конечный автомат считывает программные элементы, связанные с процессом, он может читать три вида токенов, а именно «вычислить», «прочитать» и «записать токен». Кроме того, в состоянии ожидания он может вернуться в активное состояние только путем чтения специального «токена получения», который означает, что канал связи, связанный с ожиданием, содержит читаемые данные.
Канал строго ограничен , если он имеет не более неиспользованные токены для любого возможного выполнения. KPN строго ограничен , если все каналы строго ограничены .
Количество неиспользованных токенов зависит от порядка выполнения. (планирование ) процессов. Спонтанный источник данных может произвести произвольное количество токенов в канал, если планировщик не будет выполнять процессы, потребляющие эти токены.
В реальном приложении не может быть неограниченных FIFO, и поэтому планирование и максимальная емкость FIFO должны быть реализованы на практике. Максимальная емкость FIFO может быть обработана несколькими способами:
Закрытая KPN не имеет внешних входных или выходных каналов. Процессы, у которых нет входных каналов, действуют как источники данных, а процессы, у которых нет выходных каналов, действуют как приемники данных. В открытом KPN каждый процесс имеет как минимум один входной и выходной канал.
Процессы KPN являются детерминированными. Для одной и той же истории ввода они всегда должны выдавать один и тот же результат. Процессы можно моделировать как последовательные программы, которые выполняют чтение и запись в порты в любом порядке и количестве, пока сохраняется свойство детерминизма. Как следствие, модель KPN является детерминированной, так что следующие факторы полностью определяют выходы системы:
Следовательно, синхронизация процессов не влияют на выходы системы.
Процессы KPN являются монотонными, что означает, что им требуется только частичная информация входного потока, чтобы произвести частичную информацию выходного потока. Монотонность допускает параллелизм. В KPN существует общий порядок событий внутри сигнала. Однако нет никакого отношения порядка между событиями в разных сигналах. Таким образом, KPN только частично упорядочены, что классифицирует их как.
Благодаря высокой выразительности и лаконичности, KPN в качестве основы модели вычислений применяются в нескольких инструментах академического моделирования для представления потоковых приложений, которые имеют определенные свойства (например, ориентированные на поток данных, потоковое).
Фреймворк Daedalus с открытым исходным кодом, поддерживаемый Leiden Embedded Research Center в Лейденском университете, принимает последовательные программы, написанные на C, и генерирует соответствующий KPN. Этот KPN может, например, использоваться для систематического сопоставления KPN с платформой на основе FPGA.
Ambric Am2045 массив массивно-параллельных процессоров - это KPN, реализованная в реальных кристаллах. Его 336 32-разрядных процессоров соединены программируемым межсоединением выделенных FIFO. Таким образом, его каналы строго ограничены блокирующей записью.