Неопределенность в параллельных вычислениях

Неопределенность в параллельных вычислениях связана с эффектами неопределенности в параллельных вычислениях . Вычисления — это область, в которой неопределенность становится все более важной из-за массового увеличения параллелизма из-за сетей и появления многоядерных компьютерных архитектур. Эти компьютерные системы используют арбитров , что приводит к неопределенности .

ограничение

Патрик Хейс [1973] утверждал, что «обычное резкое различие, проводимое между процессами вычислений и дедукции, вводит в заблуждение». Роберт Ковальски разработал тезис о том, что вычисления можно отнести к дедукции , и с одобрением процитировал: «Вычисления — это контролируемая дедукция». который он приписал Хейсу в своей статье 1988 года о ранней истории Пролога. В отличие от Ковальского и Хейса, Карл Хьюитт утверждал, что логический вывод не способен выполнять параллельные вычисления в открытых системах. .

Хьюитт [1985] и Ага [1991] и другие опубликованные работы утверждали, что математические модели параллелизма не определяют конкретные параллельные вычисления следующим образом: Модель актера использует арбитраж (часто в форме условных арбитров ) для определения того, какое сообщение является следующий в порядке прибытия Актера, которому одновременно отправляется несколько сообщений. Это вносит неопределенность в порядок прибытия. Поскольку порядок прибытия не определен, его нельзя вывести из априорной информации только с помощью математической логики. Следовательно, математическая логика не может реализовать параллельные вычисления в открытых системах.

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

прибытия

По словам Хьюитта, в конкретных терминах для акторных систем мы обычно не можем наблюдать детали, с помощью которых определяется порядок прибытия сообщений для актора. Попытка сделать это влияет на результаты и может даже увеличить неопределенность в другом месте. например, см. метастабильность в электронике и арбитрах . Вместо того, чтобы наблюдать за внутренностями арбитражных процессов вычислений Actor, мы ждем результатов. Неопределенность арбитров порождает неопределенность актеров. Причина, по которой мы ждем результатов, заключается в том, что у нас нет альтернативы из-за неопределенности.

Важно четко понимать, на чем основано опубликованное утверждение об ограничении математической логики. Дело не только в том, что Актеры вообще не могли быть реализованы в математической логике. Опубликованное утверждение заключалось в том, что из-за неопределенности физической основы модели Актера ни одна дедуктивная математическая логика не может избежать этого ограничения. Это стало важным позже, когда исследователи попытались расширить Пролог (который имел некоторую основу в логическом программировании ) для параллельных вычислений с использованием передачи сообщений. (См. раздел ниже).

Что говорит по этому поводу математическая теория Актеров? система Закрытая определяется как система, которая не сообщается с внешней средой. Теория модели акторов предоставляет средства для характеристики всех возможных вычислений замкнутой системы акторов с использованием теоремы о представлении [Hewitt 2007] следующим образом:

Математическое обозначение, обозначаемое замкнутой системой S находится путем построения все более лучших приближений на основе начального поведения, называемого ⊥ _S с использованием функции, аппроксимирующей поведение прогрессия _S для построения обозначения (значения) для С следующим образом:

$\mathbf {Denote} _{\mathtt {S}}\equiv \lim _{i\to \infty }\mathbf {progression} _{{\mathtt {S}}^{i}}(\bot _{\mathtt {S}})$

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

Таким образом, математическая логика может характеризовать (а не реализовывать) все возможные вычисления закрытой системы Актеров.

Ограничение логики из-за недостатка информации

Открытая система актеров S — это тот, в котором адреса внешних Актеров могут быть переданы в S в середине вычислений, так что S может общаться с этими внешними актерами. Эти внешние Актеры затем могут, в свою очередь, взаимодействовать с Внутренними Актерами. S используя адреса, предоставленные им С. ​Из-за ограничения невозможности определить порядок прибытия знание того, какие сообщения отправляются извне, не позволит ответить S, подлежащий выводу. другие модели параллельных систем (например, исчисление процессов Когда для реализации открытых систем используются ), эти системы также могут иметь поведение, которое зависит от порядка времени прибытия и поэтому не может быть реализовано путем логического вывода.

что параллельные системы, подобные Прологу, основаны на математической

Кит Кларк , Эрве Галлер, Стив Грегори, Виджай Сарасват, Уди Шапиро, Казунори Уэда и др. разработали семейство Пролог -подобных систем параллельной передачи сообщений, используя унификацию общих переменных и потоков структуры данных для сообщений. Утверждалось, что эти системы основаны на математической логике. Такая система легла в основу японского проекта пятого поколения (ICOT) .

Карл Хьюитт и Гул Ага [1991] утверждали, что эти параллельные системы, подобные Прологу, не были ни дедуктивными, ни логическими: как и модель Актера, параллельные системы, подобные Прологу, были основаны на передаче сообщений и, следовательно, подвергались той же неопределенности.

и эффективность

Хьюитт утверждал, что из Пролога и пролог-подобных параллельных систем можно извлечь основной урок: универсальная модель параллельных вычислений ограничена наличием каких-либо обязательных накладных расходов в базовых механизмах связи. Это аргумент против включения вызова по шаблону с использованием унификации и извлечения сообщений из потоков структур данных в качестве фундаментальных примитивов. Однако аргументы в пользу включения можно найти в обзоре Шапиро параллельных языков программирования, подобных Прологу.

вычислений

Арбитраж является основой неопределенности в модели Actor параллельных вычислений (см. «История модели Actor» и «Теория модели Actor» ). Это также может играть роль в других моделях параллельных систем, таких как исчисление процессов .

См. также

• Квантовые вычисления
• Рандомизированный алгоритм
• Недетерминированная машина Тьюринга

Ссылки

• Карл Хьюитт Что такое вычисления? Модель актера и модель Тьюринга в вычислимой вселенной: понимание вычислений и исследование природы как вычислений. Посвящается памяти Алана М. Тьюринга к 100-летию со дня его рождения. Под редакцией Гектора Зенила. Мировое научное издательство. 2012 год
• Карл Хьюитт. ПЛАНИРОВЩИК: язык доказательства теорем на роботах IJCAI 1969.
• Карл Хьюитт. Процедурное внедрение знаний в Planner IJCAI 1971.
• Карл Хьюитт, Питер Бишоп и Ричард Стайгер. Универсальный модульный формализм актеров для искусственного интеллекта IJCAI 1973.
• Роберт Ковальски Логика предикатов как язык программирования. Памятка 70, Факультет искусственного интеллекта, Эдинбургский университет . 1973.
• Пэт Хейс. Математические основы вычислений и дедукции в информатике: материалы симпозиума и летней школы, Штрбске Плесо, Высокие Татры, Чехословакия, 3–8 сентября 1973 г.
• Законы Карла Хьюитта и Генри Бейкера для связи параллельных процессов ИФИП-77, август 1977 г.
• Карл Хьюитт. Рассмотрение структур управления как шаблонов передачи сообщений Журнал искусственного интеллекта . Июнь 1977 года.
• Генри Бейкер. Акторные системы для вычислений в реальном времени. Докторская диссертация MIT EECS. Январь 1978 года.
• Билл Корнфельд и Карл Хьюитт. Метафора научного сообщества Транзакции IEEE по системам, человеку и кибернетике . Январь 1981 года.
• Уилл Клингер. Основы акторной семантики Докторская диссертация по математике Массачусетского технологического института . Июнь 1981 года.
• Карл Хьюитт. Вызов открытых систем Журнал Byte. Апрель 1985 г. Перепечатано в сборнике «Основы искусственного интеллекта» Cambridge University Press. 1990.
• Гуль Ага. Актеры: модель параллельных вычислений в распределенных системах Докторская диссертация. МТИ Пресс. 1986.
• Роберт Ковальски. Ограничение логики. Материалы 14-й ежегодной конференции ACM по информатике 1986 года.
• Эхуд Шапиро (редактор). Параллельный Пролог MIT Press . 1987.
• Роберт Ковальски. Первые годы логического программирования в ACM . Январь 1988 года.
• Эхуд Шапиро. Семейство языков программирования параллельной логики ACM Computing Surveys . Сентябрь 1989 года.
• Карл Хьюитт и Гуль Ага. Языки предложений защищенного Хорна: являются ли они дедуктивными и логическими? Международная конференция по компьютерным системам пятого поколения, Омша, 1988. Токио. Также в «Искусственном интеллекте» Массачусетского технологического института , Vol. 2. Массачусетский технологический институт Пресс, 1991.
• Карл Хьюитт. *Карл Хьюитт. Повторяющийся упадок логического программирования и почему оно будет перевоплощено Что пошло не так и почему: уроки исследований и приложений ИИ. Технический отчет SS-06-08. АААИ Пресс. Март 2006 года.

Внешние ссылки

• Хьюитт, Мейер и Шиперски: модель актера (все, что вы хотели знать, но боялись спросить) Microsoft Channel 9. 9 апреля 2012 г.