Неопределенность в параллельных вычислениях - Indeterminacy in concurrent computation

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

Предполагаемое ограничение логического программирования

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

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

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

Неопределенность порядка прибытия

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

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

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

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

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

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

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

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

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

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

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

Логические операции и эффективность системы

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

Неопределенность в других моделях вычислений

Арбитраж - это основа неопределенности в модели параллельных вычислений акторов (см. Историю модели акторов и теорию модели акторов ). Он также может играть роль в других моделях параллельных систем, таких как вычисления процессов .

Смотрите также

Ссылки

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

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