Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Неопределенность в параллельных вычислениях изучает влияние недетерминизма на результаты таких вычислений. Вычисления – это область, где недетерминизм приобретает все большее значение в связи с резким ростом параллелизма, обусловленным развитием сетей и многоядерных компьютерных архитектур. В этих компьютерных системах используются арбитры, что и является источником недетерминизма.
Indeterminacy in concurrent computation is concerned with the effects of indeterminacy in concurrent computation. Computation is an area in which indeterminacy is becoming increasingly important because of the massive increase in concurrency due to networking and the advent of many core computer architectures. These computer systems make use of arbiters which gives rise to indeterminacy.
Патрик Хейс [1973] утверждал, что "обычное чёткое различие, проводимое между процессами вычисления и дедукции, вводит в заблуждение". Роберт Ковальски развил тезис о том, что вычисления можно подчинить дедукции, и с одобрением процитировал: "Вычисление – это управляемая дедукция", которую он приписал Хейсу в своей работе 1988 года о ранней истории Пролога. В отличие от Ковальски и Хейса, Карл Хьюитт утверждал, что логическая дедукция не способна осуществлять параллельные вычисления в открытых системах. Хьюит [1985] и Ага [1991], а также другие опубликованные работы, доказывали, что математические модели параллелизма не определяют конкретные параллельные вычисления следующим образом: модель акторов использует арбитраж (часто в форме гипотетических арбитров) для определения следующего сообщения в порядке поступления для актора, которому одновременно отправляется несколько сообщений. Это вносит недетерминированность в порядок поступления. Поскольку порядок поступления недетерминирован, его нельзя вывести из предшествующей информации исключительно математической логикой. Следовательно, математическая логика не может реализовать параллельные вычисления в открытых системах. Авторы утверждают, что, хотя математическая логика, по их мнению, не может реализовать общий параллелизм, она способна реализовать некоторые частные случаи параллельных вычислений, например, последовательные вычисления и некоторые виды параллельных вычислений, включая лямбда-исчисление.
Patrick Hayes [1973] argued that the "usual sharp distinction that is made between the processes of computation and deduction, is misleading". Robert Kowalski developed the thesis that computation could be subsumed by deduction and quoted with approval "Computation is controlled deduction." which he attributed to Hayes in his 1988 paper on the early history of Prolog. Contrary to Kowalski and Hayes, Carl Hewitt claimed that logical deduction was incapable of carrying out concurrent computation in open systems. Hewitt [1985] and Agha [1991], and other published work argued that mathematical models of concurrency did not determine particular concurrent computations as follows: The Actor model makes use of arbitration (often in the form of notional arbiters) for determining which message is next in the arrival ordering of an Actor who is sent multiple messages concurrently. This introduces indeterminacy in the arrival order. Since the arrival orderings are indeterminate, they cannot be deduced from prior information by mathematical logic alone. Therefore, mathematical logic cannot implement concurrent computation in open systems. The authors claim that although mathematical logic cannot, in their view, implement general concurrency it can implement some special cases of concurrent computation, e. g., sequential computation and some kinds of parallel computing including the lambda calculus.
Ограничение логики из-за отсутствия информации
Открытая система акторов – это система, в которой адреса внешних акторов могут быть переданы в процессе вычислений, чтобы обеспечить возможность взаимодействия с этими внешними акторами. Эти внешние акторы, в свою очередь, могут взаимодействовать с внутренними акторами, используя адреса, полученные от них. Из-за ограничения, связанного с невозможностью определения порядка поступления сообщений, знание о том, какие сообщения отправляются извне, не позволит определить ответ системы. Когда другие модели параллельных систем (например, исчисление процессов) используются для реализации открытых систем, эти системы также могут демонстрировать поведение, зависящее от порядка поступления сообщений, и, следовательно, не могут быть реализованы исключительно логическим выводом.
An open Actor system is one in which the addresses of outside Actors can be passed into in the middle of computations so that can communicate with these outside Actors. These outside Actors can then in turn communicate with Actors internal to using addresses supplied to them by Due to the limitation of the inability to deduce arrival orderings, knowledge of what messages are sent from outside would not enable the response of to be deduced. When other models of concurrent systems (e. g., process calculi) are used to implement open systems, these systems also can have behavior that depends on arrival time orderings and so cannot be implemented by logical deduction.
Утверждалось, что одновременные системы, подобные Prolog, основаны на математической логике
Кит Кларк, Герве Галлер, Стив Грегори, Виджай Сарасват, Уди Шапиро, Кадзунори Уэда и другие разработали семейство систем конкурентной передачи сообщений, подобных Prolog, использующих унификацию общих переменных и потоки структур данных для сообщений. Заявлялось, что эти системы основаны на математической логике. Этот тип систем был использован в качестве основы японского проекта пятого поколения (ICOT). Карл Хьюитт и Гул Ага [1991] утверждали, что эти системы конкурентной работы, подобные Prolog, не являлись ни дедуктивными, ни логическими: как и модель Actor, системы конкурентной работы, подобные Prolog, основывались на передаче сообщений и, следовательно, подвержены той же недетерминированности.
Keith Clark, Hervé Gallaire, Steve Gregory, Vijay Saraswat, Udi Shapiro, Kazunori Ueda, etc. developed a family of Prolog like concurrent message passing systems using unification of shared variables and data structure streams for messages. Claims were made that these systems were based on mathematical logic. This kind of system was used as the basis of the Japanese Fifth Generation Project (ICOT). Carl Hewitt and Gul Agha [1991] argued that these Prolog like concurrent systems were neither deductive nor logical: like the Actor model, the Prolog like concurrent systems were based on message passing and consequently were subject to the same indeterminacy.
Логические операции и эффективность системы
Хьюитт утверждал, что из Prolog и систем, подобных Prolog, можно извлечь важный урок: универсальная модель параллельных вычислений ограничена любыми обязательными накладными расходами в базовых механизмах коммуникации. Это аргумент против включения вызова, управляемого образцом, с использованием унификации и извлечения сообщений из потоков структур данных в качестве фундаментальных примитивов. Однако, для контраргументов, обратитесь к обзору Шапиро, посвященному языкам программирования, подобным Prolog, для параллельного программирования.
Hewitt maintained that a basic lesson can be learned from Prolog and the Prolog like concurrent systems: a universal model of concurrent computation is limited by having any mandatory overhead in the basic communication mechanisms. This is an argument against including pattern directed invocation using unification and extraction of messages from data structure streams as fundamental primitives. But compare Shapiro's survey of Prolog like concurrent programming languages for arguments for inclusion.
Неопределенность в других моделях вычислений
Арбитраж лежит в основе недетерминированности в акторной модели параллельных вычислений (см. История акторной модели и теория акторной модели). Он также может играть роль в других моделях параллельных систем, таких как исчисления процессов.
Arbitration is the basis of the indeterminacy in the Actor model of concurrent computation (see History of the Actor model and Actor model theory). It may also play a role in other models of concurrent systems, such as process calculi.