Войти
| Paradigm | Dataflow |
|---|---|
| Впервые появилось | 2001 |
| Платформа | Независимая от платформы |
| Расширения имен файлов | .cal,.xdf |
| Основные реализации | |
| , | |
CAL (Cal Actor Language ) - это язык программирования высокого уровня для записи (поток данных ) акторов, которые представляют собой операторы с отслеживанием состояния, которые преобразуют входные потоки объектов данных (токенов) в выходные потоки. Клиентские лицензии CAL были скомпилированы для различных целевых платформ, включая одноядерные процессоры, многоядерные процессоры и программируемое оборудование. Он использовался в нескольких прикладных областях, включая видео и обработку, сжатие и криптографию. Рабочая группа MPEG Reconfigurable Video Coding (RVC) приняла CAL как часть своих усилий по стандартизации.
Актерский язык CAL был разработан в 2001 году как часть проект Птолемея II в Калифорнийском университете в Беркли. CAL - это язык потока данных, предназначенный для различных областей приложений, таких как обработка мультимедиа, системы управления, сетевая обработка и т. Д.
Другой распространенной причиной выбора потока данных является то, что целью является эффективная параллельная реализация, чего было бы трудно или невозможно достичь с использованием последовательного языка программирования. Последовательные языки, как известно, трудно распараллелить в целом, поэтому эффективные параллельные реализации обычно требуют значительных указаний от пользователя. Программа потока данных CAL предоставляет простые, понятные и мощные абстракции, которые позволяют специфицировать столько или меньше параллелизма, сколько требуется, позволяя инструментам создавать сложные реализации, которые используют параллельную структуру вычислений.
При программировании в потоке данных программист обычно создает параллельное описание вычислительной системы, которое отличается от обычной последовательной программы. Вместо того, чтобы заниматься пошаговым выполнением алгоритма , программист потока данных создает систему асинхронно взаимодействующих объектов, называемых акторами. Большая часть усилий по программированию направлена на то, чтобы правильно разложить проблему на акторов и разработать соответствующие шаблоны коммуникации между этими акторами.
Акторы выполняют свои вычисления в последовательности шагов, называемых запусками. На каждом из этих шагов:
Следовательно, описание актора включает описание его внешнего интерфейса, портов, структуры его внутреннего состояния, а также шагов, которые он может выполнять, что эти шаги делают (в условия производства и потребления токенов, а также обновление состояния актера), и как выбрать шаг, который актер выполнит следующим. В этом разделе обсуждаются некоторые конструкции языка CAL, которые решают эти проблемы. Действия описывают вещи, которые происходят во время шага, который выполняет актер. Фактически, правильно сказать, что шаг состоит из выполнения действия. Напомним, что когда актер делает шаг, он может потреблять входные токены и производить выходные токены.
Следовательно, шаблоны ввода делают следующее:
Выходная сторона действия немного проще, выходные выражения просто определяют количество и значения выходных токенов, которые будут создаваться на каждом выходном порту при каждом запуске действия. Допускается опускать явное именование порта, к которому применяется входной шаблон или выходное выражение, если действие предоставляет столько входных шаблонов, сколько имеется входных портов или выходных выражений, сколько выходных портов. В таком случае шаблоны или выражения сопоставляются по положению с объявлениями портов.
Один из способов думать об актере - это как оператор для потоков данных - последовательности токенов входят в него на его входных портах, а последовательности токенов оставляют его на его выходных портах. Обсуждая работу актора, часто полезно рассматривать его как оператор потоков. Актеры могут иметь параметры. Они действуют как константы во время выполнения актора, и им присваивается конкретное значение, когда актор создается как часть сети акторов. Основная цель параметров акторов - позволить программистам указать семейства связанных акторов без необходимости дублировать большой объем кода.
A недетерминированный субъект - это субъект, который для одних и тех же входных последовательностей допускает более одного запуска и более одного возможного вывода. Недетерминизм может быть очень мощным при правильном использовании, но он также может быть очень неприятным источником ошибок. Особое беспокойство вызывает то, что недетерминированный субъект может быть непреднамеренно введен в действие актора, т. Е. Автор думает, что субъект детерминирован, хотя это не так. Одна из ключевых целей разработки языка CAL состояла в том, чтобы позволить описание недетерминированных субъектов, в то же время позволяя инструментам идентифицировать возможные источники недетерминизма, чтобы они могли предупреждать пользователя о них.
Ключевым следствием недетерминированного субъекта, такого как NDMerge, является то, что во время фактического выполнения его вывод может зависеть от времени его ввода. Если обе его входные очереди пусты и NDMerge ожидает ввода, то любой вход, на который приходит следующий токен, может быть тем, который копируется рядом с выходом. Следовательно, планирование действий в сети акторов или относительные скорости акторов, подключенных к актору, подобному NDMerge, могут повлиять на вывод системы. Иногда это может быть желательно, а иногда - нет. В любом случае это свойство, о котором нужно знать.
Один из способов взглянуть на недетерминизм, который делает актора зависимым от точного времени поступления токенов, состоит в том, что такой субъект кажется недетерминированным только в том случае, если мы смотрим на него как на оператор на streams, потому что это представление абстрагируется от временных свойств выполнения и, таким образом, целенаправленно удаляет информацию, которая используется для определения последовательности, в которой запускаются действия. С точки зрения языка CAL это не совсем точно, но даже в этом случае легко написать недетерминированные акторы, которые не были бы детерминированными, даже если бы мы знали все о времени токенов и реализации актора, например следующие:
Предложение guard для действия содержит ряд выражений, которые все должны быть истинными, чтобы действие могло быть запущено. Чтобы первое действие было активным, входящий токен должен быть больше или равен нулю, и в этом случае он будет отправлен на выход P. В противном случае это действие не может сработать. И наоборот, чтобы второе действие можно было запустить, токен должен быть меньше нуля, и в этом случае он отправляется на выход N. Запуск этого актора может выглядеть следующим образом: у актера могут возникнуть проблемы, если он когда-либо столкнется с нулевой токен, потому что ни одно из его действий не сможет запустить его.
Нет ничего незаконного в написании акторов, которые завершаются на некотором вводе, и на самом деле может быть важно иметь несколько из них в некоторых системах. Но это ловушка, о которой нужно знать. Во-вторых, защитные условия также не пересекаются, а не являются исчерпывающими.
Наконец, обратите внимание, что условия защиты могут «заглядывать» во входящие жетоны, фактически не потребляя их - если сторожевые устройства оказываются ложными или действие не запускается по какой-либо другой причине, и если токен не потребляется другим действием, он остается на месте и будет доступен для следующего выстрела. (Или он останется там навсегда, как в случае с нулевым токеном перед SplitDead, который никогда не удаляется, потому что актер мертв.)
Актер Select ниже - еще один пример использования охраняемых действий. Он похож на актера NDMerge в том смысле, что он объединяет два потока (те, которые поступают на его входные порты A и B). Однако это происходит в соответствии с (логическими) значениями токенов, поступающих на его входной порт S.
Пока что для всех акторов ничего не было выполнено срабатыванием действия, которое никак не повлияет на последующие срабатывания действий того же самого актера. Используя переменные состояния, запуски действия могут оставлять информацию для последующих запусков одного и того же или другого действия того же актера. Как написан этот актер, выбор следующего входного токена и фактическое копирование токена на выход - это один атомарный шаг.
Обратите внимание, что Select и IterSelect почти, но не полностью, эквивалентны. Прежде всего, IterSelect делает вдвое больше шагов, чтобы обработать то же количество токенов. Во-вторых, он фактически считывает и, следовательно, потребляет входной токен S, независимо от того, доступен ли соответствующий токен данных на A или B.
The IterSelect В предыдущем разделе актер проиллюстрировал использование состояния для управления выбором действий. На практике это чрезвычайно распространено, и язык CAL предоставляет для этой цели специальный синтаксис в виде расписаний. Концептуально расписания можно рассматривать как кодирование определенного паттерна использования переменной состояния - они ничего не добавляют к языку с точки зрения выразительности. Обоснование использования расписаний двоякое:
Каждый переход состояния состоит из трех частей: исходного состояния, списка тегов действий и следующее состояние. Стоит отметить, что количество действий увеличилось - вместо исходных трех в новой версии с расписанием теперь есть четыре действия. Причина в том, что действие больше не может напрямую назначать состояние преемника, как это было в оригинале, где в зависимости от значения состояния чтения токена будет присвоено либо значение 1, либо 2. В версии с расписанием это модификация состояния неявно присутствует в структуре конечного автомата и происходит в зависимости от того, какое действие запускается. Соответственно, условие, которое проверяет значение токена, переместилось из тела действия в защиту двух действий с тегами readT и readF.
Пока он имеет вход только на одном из своих входных портов, все однозначно. Но, как и NDMerge, как только входные данные доступны на обоих входных портах, он может запускать любое из двух своих действий, и в спецификации этого актора нет ничего, что могло бы предрасполагать его к выбору одного из них.
Ни одна из языковых конструкций до сих пор не позволяла нам это делать. В отличие от этого случая расписаний, которые можно рассматривать синтаксическим сахаром, потому что они могут быть сведены к существующим элементам языка (переменным состояния, средствам защиты и присваиваниям), эта ситуация на самом деле требует истинного расширения - приоритеты действий. Основная идея состоит в том, чтобы добавить ряд неравенств, которые соотносят действия с их приоритетом срабатывания.
Как и в случае с расписаниями, мы используем теги действий для идентификации действий, к которым мы хотим обратиться позже - на этот раз в рамках неравенства приоритетов. Блок приоритета содержит только одно такое неравенство, связывающее конфигурацию с тегами действия с одним тегированным процессом, давая первому приоритет над вторым. Конечно, даже эта версия очень сильно зависит от времени. В этом случае это не должно быть проблемой, и на самом деле это, вероятно, требование, чтобы этот субъект выполнял свою функцию. Но в целом важно понимать, что приоритеты, особенно когда они используются, как в предыдущем примере, должны быть хорошо поняты для получения правильных результатов. Особенно, когда информация о времени обмена данными внутри сети расплывчата, вероятно, лучше думать о них как о строгих директивах реализации.
В предыдущей главе основное внимание уделялось тем конструкциям в клиентской лицензии, которые связаны с концепциями, зависящими от актора - вводом и выводом токенов, действиями, управлением выбором действий и т. Д. В этом разделе обсуждаются более «прозаические» части клиентской лицензии, операторы и выражения, используемые для управления объектами данных и выражают (последовательные) алгоритмы. Эта часть языка похожа на то, что можно найти во многих языках процедурного программирования (таких как C, Pascal, Java, Ada ), поэтому мы сосредоточимся на области, которые могут немного отличаться в CAL.
В отличие от таких языков, как C, CAL проводит четкое различие между операторами и выражениями. У них очень разные роли, очень разные значения, и они никогда не могут быть взаимозаменяемыми. Выражение в CAL - это фрагмент кода, единственная цель которого - вычислить значение. Мы также говорим, что выражение имеет значение или что оно оценивается как значение. Для большинства выражений значение, которое они оценивают, будет зависеть от значений одной или нескольких переменных в то время, когда выражение оценивается. Поскольку значения переменных могут изменяться со временем, одно и то же выражение может иметь разные значения при оценке в разные моменты времени.
Вероятно, самые фундаментальные выражения - это константы. Другая группа основных выражений - это ссылки на переменные. Синтаксически переменная - это любая последовательность букв и цифр. Одним из важных свойств выражений является то, что они гарантированно не изменяют переменные (мы также говорим, что они не имеют побочных эффектов) - следовательно, внутри выражения множественные ссылки на одну и ту же переменную всегда будут давать один и тот же результат.
CAL предоставляет операторы двух видов для построения выражений: унарные и [[двоичные операции} двоичные]]. Унарный оператор в CAL всегда является префиксным, т. Е. Стоит перед своим единственным операндом. Бинарный оператор находится между двумя его операндами.
В некотором смысле CAL прямо противоположны выражениям: они не имеют «возвращаемого значения», но могут изменять значения переменных. Действительно, изменение значений переменных - это весь смысл утверждений. Операторы выполняются в строгом последовательном порядке, и, если не указано иное, выполнение операторов продолжается в том порядке, в котором они появляются в тексте программы, что означает, что любые изменения переменных, произведенные оператором, могут повлиять на выполнение последующих операторов.
Как и в большинстве других языков программирования, существуют конструкции для управления порядком, в котором выполняются операторы в программе. Часть этого цикла, которая непосредственно следует за ключевым словом foreach, является генератором, очень похожим на те, что используются в списках.
