Акторная модель: математическая модель конкурентных вычислений, разработанная в 1973 году. Исследование мощности, композиции, архитектур и открытых систем.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В информатике модель акторов, впервые опубликованная в 1973 году, представляет собой математическую модель параллельных вычислений. В данной статье рассматривается более поздняя история модели акторов, в которой основными направлениями исследований были изучение фундаментальных возможностей модели, анализ вопросов композиционности, разработка архитектур и применение к открытым системам. Она является продолжением статьи о ранней истории модели акторов, в которой освещались первые реализации, начальные применения и разработка первой теории доказательств и денотационной семантики.
In computer science, the Actor model, first published in 1973 , is a mathematical model of concurrent computation. This article reports on the later history of the Actor model in which major themes were investigation of the basic power of the model, study of issues of compositionality, development of architectures, and application to Open systems. It is the follow on article to Actor model middle history which reports on the initial implementations, initial applications, and development of the first proof theory and denotational model.
Сила модели актера
Начались исследования базовой вычислительной мощности модели акторов. Карл Хьюитт [1985] утверждал, что благодаря использованию арбитров модель акторов была более мощной, чем логическое программирование (см. недетерминированность в параллельных вычислениях). Семья систем, подобных Prolog, осуществляющих параллельный обмен сообщениями с использованием унификации общих переменных и потоков структур данных для сообщений, была разработана Китом Кларком, Эрве Галлером, Стивом Грегори, Виджаем Сарасватом, Уди Шапиро, Казунори Уэдой и др. Некоторые из этих авторов заявляли, что эти системы основаны на математической логике. Однако, как и модель акторов, системы, подобные Prolog, основывались на передаче сообщений и, следовательно, подвергались недетерминированности в порядке следования сообщений в потоках, аналогичной недетерминированности в порядке поступления сообщений, отправленных акторам. В результате Карл Хьюитт и Гул Ага [1991] заключили, что системы, подобные Prolog, не были ни дедуктивными, ни логическими. Они не были дедуктивными, поскольку вычислительные шаги не выводились дедуктивно из предшествующих, и не были логическими, поскольку ни одна система математической логики не могла вывести факты последующих вычислительных состояний из предшествующих.
Investigations began into the basic power of the Actor model. Carl Hewitt [1985] argued that because of the use of Arbiters that the Actor model was more powerful than logic programming (see indeterminacy in concurrent computation). A family of Prolog like concurrent message passing systems using unification of shared variables and data structure streams for messages were developed by Keith Clark, Hervé Gallaire, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, etc. Some of these authors made claims that these systems were based on mathematical logic. However, like the Actor model, the Prolog like concurrent systems were based on message passing and consequently were subject to indeterminacy in the ordering of messages in streams that was similar to the indeterminacy in arrival ordering of messages sent to Actors. Consequently Carl Hewitt and Gul Agha [1991] concluded that the Prolog like concurrent systems were neither deductive nor logical. They were not deductive because computational steps did not follow deductively from their predecessors and they were not logical because no system of mathematical logic was capable of deriving the facts of subsequent computational situations from their predecessors
Композиционность
Композиционность связана с построением систем из подсистем. Проблемы композиционности оказались серьезными ограничениями для предыдущих теорий вычислений, включая лямбда-исчисление и сети Петри. Например, два лямбда-выражения не являются лямбда-выражением, а две сети Петри не образуют сеть Петри и не могут взаимодействовать друг с другом. В своей докторской диссертации Гул Ага исследовал вопросы композиционности в модели акторов. Конфигурации акторов имеют приемники, которые могут получать сообщения извне и могут располагать адресами приемников других конфигураций акторов. Таким образом, две конфигурации акторов можно объединить в новую конфигурацию, в которой подконфигурации могут обмениваться сообщениями. Конфигурации акторов обладают преимуществом в том, что они могут иметь несколько акторов (то есть приемников), принимающих сообщения извне, без недостатка необходимости постоянного опроса для получения сообщений из множества источников (см. проблемы, связанные с получением сообщений из нескольких каналов).
Compositionality concerns composing systems from subsystems. Issues of compositionality had proven to be serious limitations for previous theories of computation including the lambda calculus and Petri nets. E. g., two lambda expressions are not a lambda expression and two Petri nets are not a Petri net and cannot influence each other. In his doctoral dissertation Gul Agha addressed issues of compositionality in the Actor model. Actor configurations have receptionists that can receive messages from outside and may have the addresses of the receptionists of other Actor configurations. In this way two Actor configurations can be composed into another configuration whose subconfigurations can communicate with each other. Actor configurations have the advantage that they can have multiple Actors (i. e. the receptionists) which receive messages from outside without the disadvantage of having to poll to get messages from multiple sources (see issues with getting messages from multiple channels).
Компьютерные архитектуры
Исследователи из Калифорнийского технологического института под руководством Чака Зайца разработали Cosmic Cube, одну из первых архитектур, основанных на передаче сообщений и акторах. Впоследствии в MIT исследователи под руководством Билла Далли разработали J Machine.
Researchers at Caltech under the leadership of Chuck Seitz developed the Cosmic Cube which was one of the first message passing Actor architectures. Subsequently at MIT researchers under the leadership of Bill Dally developed the J Machine.
Попытки соотнести семантику актора с алгеброй и линейной логикой
Кохей Хонда и Марио Токоро в 1991 году, Хосе Месэгуер в 1992 году, Уго Монтанари и Кэролин Талкотт в 1998 году, М. Гаспари и Г. Заваттаро в 1999 году пытались соотнести семантику акторов с алгеброй. Кроме того, Джон Дарлингтон и Ю. К. Гуо в 1994 году пытались соотнести линейную логику с семантикой акторов. Однако ни один из вышеперечисленных формализмов не рассматривает ключевое свойство – гарантию качества обслуживания (см. неограниченный недетерминизм).
Kohei Honda and Mario Tokoro 1991, José Meseguer 1992, Ugo Montanari and Carolyn Talcott 1998, M. Gaspari and G. Zavattaro 1999 have attempted to relate Actor semantics to algebra. Also John Darlington and Y. K. Guo 1994 have attempted to relate linear logic to Actor semantics. However, none of the above formalisms addresses the crucial property of guarantee of service (see unbounded nondeterminism).
Последние события
Недавние достижения в области модели Actor обусловлены несколькими источниками. Развитие аппаратного обеспечения способствует увеличению как локальной, так и нелокальной массовой параллельности. Локальная параллельность обеспечивается новым оборудованием, таким как 64-битные многоядерные микропроцессоры, многочиповые модули и высокопроизводительные соединения. Нелокальная параллельность обеспечивается новым оборудованием для проводных и беспроводных широкополосных коммуникаций с пакетной коммутацией. Объемы как локальной, так и нелокальной памяти растут экспоненциально. Эти достижения в области аппаратного обеспечения ставят перед нами огромные задачи моделирования. Хьюитт [Hewitt 2006a, 2006b] пытается использовать модель Actor для решения этих задач.
Recent developments in the Actor model have come from several sources. Hardware development is furthering both local and nonlocal massive concurrency. Local concurrency is being enabled by new hardware for 64 bit many core microprocessors, multi chip modules, and high performance interconnect. Nonlocal concurrency is being enabled by new hardware for wired and wireless broadband packet switched communications. Both local and nonlocal storage capacities are growing exponentially. These hardware developments pose enormous modelling challenges. Hewitt [Hewitt 2006a, 2006b] is attempting to use the Actor model to address these challenges.