Войти
Неопределенность в параллельных вычислениях связана с эффектами неопределенности в одновременных вычисление. Вычисления - это область, в которой неопределенность становится все более важной из-за значительного увеличения параллелизма из-за сетей и появления многоядерных компьютерных архитектур. Эти компьютерные системы используют арбитров, которые вызывают неопределенность.
Патрик Хейс [1973] утверждал, что «обычное четкое различие между процессами вычисления и дедукции вводит в заблуждение». Роберт Ковальский разработал тезис о том, что вычисления могут быть включены в дедукцию, и с одобрением процитировал: «Вычисления - это контролируемые дедукции». которую он приписал Хейсу в своей статье 1988 года о ранней истории Пролога. В отличие от Ковальски и Хейса, Карл Хьюитт утверждал, что логическая дедукция неспособна выполнять параллельные вычисления в открытых системах.
Хьюитт [1985] и Ага [1991] и другие опубликованные работы утверждали, что математические модели параллелизма не определяют конкретные параллельные вычисления следующим образом: Модель Актора использует арбитраж (часто в форме условного арбитры ) для определения того, какое сообщение будет следующим в порядке поступления субъекта, который одновременно отправляет несколько сообщений. Это вводит неопределенность в порядок прибытия. Поскольку порядок прибытия не определен, его нельзя вывести из априорной информации только с помощью математической логики. Следовательно, математическая логика не может реализовать параллельные вычисления в открытых системах.
Авторы утверждают, что, хотя математическая логика, по их мнению, не может реализовать общий параллелизм, она может реализовать некоторые особые случаи параллельных вычислений, например, последовательные вычисления и некоторые виды параллельных вычислений, включая лямбда-исчисление.
Согласно Хьюитту, в конкретных терминах для систем актеров, обычно мы не можем наблюдать детали, с помощью которых определяется порядок прибытия сообщений для актера. Попытка сделать это влияет на результаты и даже может подтолкнуть неопределенность к чему-то другому. например, см. метастабильность в электронике и арбитры. Вместо того, чтобы наблюдать за внутренними процессами арбитража вычислений Акторов, мы ждем результатов. Неопределенность арбитров порождает неопределенность участников. Причина, по которой мы ждем результатов, заключается в том, что у нас нет альтернативы из-за неопределенности.
Важно четко понимать основу опубликованного заявления об ограничении математической логики. Дело не только в том, что Актеры вообще не могли быть реализованы в математической логике. Опубликованное утверждение заключалось в том, что из-за неопределенности физической основы модели Актера никакая дедуктивная математическая логика не может избежать ограничения. Это стало важным позже, когда исследователи попытались расширить Prolog (который имел некоторую основу в логическом программировании ) для параллельных вычислений с использованием передачи сообщений. (См. Раздел ниже).
Что об этом говорит математическая теория Актеров? Закрытая система определяется как система, которая не взаимодействует с внешним миром. Теория модели акторов предоставляет средства для характеристики всех возможных вычислений замкнутой системы актеров с использованием теоремы представления [Hewitt 2007] следующим образом:
Таким образом, поведение S может быть математически охарактеризовано в терминах всех его возможных поведений (включая те, которые связаны с неограниченным недетерминизмом).
Таким образом, математическая логика может характеризовать (а не реализовывать) все возможные вычисления замкнутой системы Актеров.
Открытая система Актеров S - это система, в которой адреса внешних Актеров могут быть переданы в S в середине вычисления, чтобы S мог общаться с этими внешними Актерами. Эти внешние субъекты, в свою очередь, могут связываться с внутренними субъектами S, используя адреса, предоставленные им S. Из-за ограничения невозможности вывести порядок прибытия, знание того, какие сообщения отправляются извне, не позволит вывести ответ S. Когда другие модели параллельных систем (например, вычисление процессов ) используются для реализации открытых систем, эти системы также могут иметь поведение, которое зависит от порядка времени поступления и поэтому не может быть реализовано с помощью логического вывода.
Кейт Кларк, Эрве Галлер, Стив Грегори, Виджай Сарасват, Уди Шапиро, Кадзунори Уэда и др. Разработали семейство Prolog -подобные системы параллельной передачи сообщений, использующие объединение общих переменных и потоков структуры данных для сообщений. Утверждалось, что эти системы основаны на математической логике. Такая система была использована в качестве основы Японского проекта пятого поколения (ICOT)..
Карл Хьюитт и Гул Ага [1991] утверждали, что эти параллельные системы, подобные Прологу, не были ни дедуктивными, ни логическими: как модель актера параллельные системы, подобные Прологу, основывались на передаче сообщений и, следовательно, были подвержены той же неопределенности.
Хьюитт утверждал, что основной урок можно извлечь из Пролога и параллельных систем, подобных Прологу: универсальная модель параллельных вычислений ограничена обязательными накладными расходами в основные механизмы коммуникации. Это аргумент против включения вызова, управляемого шаблоном, с использованием унификации и извлечения сообщений из потоков структур данных в качестве фундаментальных примитивов. Но сравните обзор параллельных языков программирования, подобных Prolog, на предмет аргументов в пользу включения.
Арбитраж является основой неопределенности в модели акторов параллельных вычислений (см. История модели акторов и Теория модели актера ). Он также может играть роль в других моделях параллельных систем, таких как вычисления процессов.
