Линда (координационный язык)

Линда
Парадигма	Мультипарадигмальность
Семья	Язык координации
Разработано	Дэвид Гелернтер
Разработчик	Ассоциация научных вычислений
Впервые появился	1986 год ; 38 лет назад
Веб-сайт	Линдаспасс .с
Под влиянием
	Ява

В информатике параллельных Линда — это координационная модель, которая помогает общению в вычислительных средах. Разработанный Дэвидом Гелернтером , он предназначен для использования вместе с полноценным языком вычислений, таким как Фортран или C, где роль Линды состоит в том, чтобы « создавать вычислительные действия и поддерживать связь между ними». ^[3]^[4]^[5]

История [ править ]

Дэвид Гелернтер написал первую версию Линды как доктор философии. кандидатом в 1979 году, назвав его в честь Линды Лавлейс , снявшейся в порнографическом фильме « Глубокая глотка» . В то время основным языком для параллельной обработки был Ada , разработанный Министерством обороны США и дань уважения Аде Лавлейс , которую Гелернтер считал «неэлегантным и громоздким» языком. ^[6]

Он получил широкое распространение в 1986 году, когда Гелернтер вместе со своим коллегой из Йельского университета Николасом Карьеро и Судхиром Ахуджей из AT&T Bell Laboratories опубликовал статью «Линда и друзья» в журнале IEEE . ^[7]

К началу 1990-х годов Linda широко использовалась корпорациями для более эффективного проведения анализа больших данных , в том числе на Уолл-стрит, брокерскими компаниями а также AT&T , Boeing и United Technologies . Существовали даже компании, специализировавшиеся на создании специализированных приложений для параллельных вычислений на базе Linda, крупнейшей из которых была Scientific Computing Associates, компания из Нью-Хейвена , основанная несколькими учеными-компьютерщиками из Йельского университета (Гелернтер иногда консультировал их, но не работал там). ^[6] Интерес к Linda упал в середине 1990-х годов, но вернулся в конце 1990-х, когда несколько корпораций внедрили Linda на Java , включая Sun Microsystems и IBM . ^[3]

Обзор [ править ]

Модель [ править ]

Модель Линды предоставляет распределенную разделяемую память , известную как пространство кортежей, поскольку ее основной адресуемой единицей является кортеж , упорядоченная последовательность типизированных объектов данных; в частности, в Linda кортеж представляет собой последовательность из 16 типизированных полей, заключенных в круглые скобки». Пространство кортежа «логически разделяется процессами», которые называются рабочими, которые хранят и извлекают кортежи. ^[8]

Операции [ править ]

Одним из основных преимуществ Linda является ее простота: для доступа к кортежному пространству рабочие выполняют над кортежами всего шесть операций: ^[9]

out: Помещает кортеж в пространство кортежей.
in: извлекает кортеж, соответствующий заданному шаблону, из пространства кортежей (если совпадений нет, операция блокируется).
rd: копирует кортеж, соответствующий заданному шаблону, из пространства кортежей (если совпадений нет, операция блокируется).
eval: Создает новый процесс для оценки кортежей.
inp: неблокирующая версия in (если совпадений нет, возвращается сообщение об ошибке)
rdp: неблокирующая версия rd (если совпадений нет, возвращается сообщение об ошибке)

Сравнение [ править ]

По сравнению с другими моделями параллельной обработки, Linda более ортогональна , рассматривая координацию процессов как отдельную от вычислений деятельность, и является более общей, поскольку позволяет объединить различные уровни параллельной обработки — однопроцессорный, многопоточный, многопроцессорный или сетевой — в одну модель. одиночная модель. Его ортогональность позволяет процессам, вычисляющим на разных языках и платформах, взаимодействовать, используя одни и те же примитивы. Его универсальность позволяет без изменений распределять многопоточную систему Linda на несколько компьютеров.

В то время как модели передачи сообщений требуют тесно связанных процессов, отправляющих сообщения друг другу в некоторой последовательности или протоколе, процессы Linda отделены от других процессов и взаимодействуют только через пространство кортежей; процессу не обязательно иметь представление о других процессах, за исключением типов потребляемых или производимых кортежей. Критика Linda со стороны сообщества многопроцессорных систем, как правило, сосредоточена на сниженной скорости операций в системах Linda по сравнению с системами интерфейса передачи сообщений (MPI). ^{[ нужна ссылка ]} Хотя и не без оснований, эти утверждения были в значительной степени опровергнуты в отношении важного класса проблем. ^[10] Подробную критику модели Линды можно также найти в книге Стивена Эрикссона-Зенита « Модели взаимодействия процессов» . ^[11]

Исследователи предложили больше примитивов для поддержки различных типов связи и координации между (открытыми распределенными) компьютерными системами, а также для решения конкретных проблем, возникающих в результате различного использования модели. ^{[ нужна ссылка ]} Исследователи также экспериментировали с различными способами реализации виртуальной общей памяти для этой модели. ^{[ нужна ссылка ]} Многие из этих исследователей предложили более крупные модификации исходной модели Линды, разработав семейство систем, известных как Линда-подобные системы и реализованных как ортогональная технология (в отличие от исходной версии). Примером этого является язык Ease, разработанный Стивеном Эрикссоном-Зенитом.

Подход Линды также сравнивают с программированием на основе потоков . ^[12]

Линда-Исчисление [ править ]

Линда-исчисление представляет собой формализацию приведенной выше модели с той разницей, что в следующих $\mathrm {outeval}$ включает в себя операции out и eval . ^[13]

Синтаксис [ править ]

Мы абстрагируем конкретное представление кортежей.Мы просто предполагаем, что у нас есть набор кортежей $t\in {\mathcal {T}}$ инам разрешено формировать и применять функцию замены $\sigma$ о кортежах, заменяющих переменные терминами, что дает кортеж.Например, у нас есть кортеж $t=({\mathit {hello}},x)$ , затемприменение замены $\sigma =\{{\mathit {world}}/x\}$ на $t$ урожайность $({\mathit {hello}},{\mathit {world}})$

Процессы Линда-исчисления определяются следующей грамматикой.

$P,Q::=t\;|\;\mathrm {outeval} (P).Q\;|\;\mathrm {rd} (t).P\;|\;\mathrm {in} (t).P\;|\;P+Q\;|\;\mathbf {rec} X.P\;|\;X$

Синтаксис включает в себя упомянутые выше операции Линды, недетерминированный выбор и рекурсию . Функция подстановки рекурсивно распространяется на процессы.

Семантика [ править ]

Пространство кортежей представляется как мультимножество процессов. Мы пишем $M\,|\,P$ для $M\uplus \{P\}$ где $M$ это мультимножество, $\{P\}$ одноэлементный мультимножество и $\uplus$ — операция объединения мультимножеств. Семантика затем определяется как отношение редукции на мультимножестве. $M\rightarrow M'$ следующее.

${\begin{array}{lrcll}{\text{(outeval)}}&M\,|\,\mathrm {outeval} (P).Q&\rightarrow &M\,|\,P\,|\,Q&\\{\text{(read)}}&M\,|\,\mathrm {rd} (t).P\,|\,t'&\rightarrow &M\,|\,P\sigma \,|\,t'&{\text{if exists }}\sigma {\text{ such that }}t\sigma =t'\\{\text{(input)}}&M\,|\,\mathrm {in} (t).P\,|\,t'&\rightarrow &M\,|\,P\sigma &{\text{if exists }}\sigma {\text{ such that }}t\sigma =t'\\{\text{(left choice)}}&M\,|\,P+Q&\rightarrow &M\,|\,P&\\{\text{(right choice)}}&M\,|\,P+Q&\rightarrow &M\,|\,Q&\\{\text{(recursion)}}&M\,|\,\mathbf {rec} X.P&\rightarrow &M\,|\,P\{\mathbf {rec} X.P/X\}&\\\end{array}}$

Обратите внимание, что (вход) потребляет кортеж $t'$ из пространства кортежа, тогда как (read) только читает его.Результирующая операционная семантика является синхронной.

Реализации [ править ]

Первоначально Linda была реализована на C и Fortran , но с тех пор была реализована на многих языках программирования, в том числе:

C : C-Linda , TCP-Linda , LinuxTuples
C++ : CppLinda , Борей
С# : pSpace
Эрланг : Эрлинда
Перейти : pSpaces
Java : JavaSpaces , jRESP , TSpaces , LightTS , LIME , pSpaces
JavaScript : pSpaces
Лисп
Lua : LuaTS Lua Lanes
Пролог : SICStus Пролог Линда
Питон : ПиЛинда
Руби : Скучаю по тебе
Свифт : pSpaces

Некоторые из наиболее известных реализаций Linda включают:

C-Linda или TCP-Linda — самая ранняя коммерческая и широко распространенная реализация виртуальной общей памяти для суперкомпьютеров и кластерных систем от компании Scientific Computing Associates, основанной Мартином Шульцем.
JavaSpaces — реализация пространства кортежей на основе Java, которая помогла популяризировать распределенные вычисления.
TSpaces — платформа пространства кортежей на основе Java от IBM. ^{[ чрезмерный вес? - обсуждать ]}

См. также [ править ]

Ссылки [ править ]

^ Чианкарини, Паоло. «Лекция 3: Языки координации» (PDF) . Болонский университет . Проверено 9 января 2022 г.
^ «Дэвид Гелернтер, бакалавр и магистр '76» . Йельский научный институт . 14 февраля 2011 года . Проверено 8 января 2022 г.
^ Jump up to: Перейти обратно: ^а ^б Уэллс, Джордж (июль 2005 г.). «Языки координации: Назад в будущее с Линдой» (PDF) . Конференция: 2-й международный семинар по методам координации и адаптации предприятий-разработчиков программного обеспечения . Университет Родоса. Архивировано из оригинала (PDF) 19 декабря 2009 года.
^ Гелернтер, Дэвид; Каррьеро, Николас (февраль 1992 г.). «Языки координации и их значение» (PDF) . Коммуникации АКМ . 35 (2): 97–107. дои : 10.1145/129630.129635 . S2CID 7748555 .
^ Каррьеро, Николас; Гелернтер, Дэвид (1 января 1985 г.). «Ядро Linda S/Net (расширенное резюме)». Материалы десятого симпозиума ACM по принципам операционных систем - СОСП '85 . СОСП '85. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 160–. дои : 10.1145/323647.323643 . ISBN 978-0897911740 . S2CID 6922183 .
^ Jump up to: Перейти обратно: ^а ^б Маркофф, Джон (19 января 1992 г.). «Роман Дэвида Гелернтера с Линдой» . Нью-Йорк Таймс . Архивировано из оригинала 30 декабря 2019 года . Проверено 8 января 2022 г.
^ Ахуджа, Судхир; Каррьеро, Николас; Гелернтер, Дэвид (август 1986 г.), «Линда и друзья», Компьютер , 19b (8), IEEE: 26–34, doi : 10.1109/mc.1986.1663305 , S2CID 5155678
^ Джон Х. Рейнольдс (декабрь 2002 г.). «Линда будит спящего парикмахера» (PDF) . Материалы зимней симуляционной конференции . Том. 2. Сан-Диего, Калифорния: IEEE. стр. 1804–1808. дои : 10.1109/WSC.2002.1166471 . ISBN 0-7803-7614-5 . S2CID 62584541 . Проверено 8 января 2022 г.
^ Масатоши Секи (февраль 2017 г.). Книга dRuby: Распределенные и параллельные вычисления с Ruby (изд. 0.1). Прагматичные программисты . Проверено 9 января 2022 г.
^ Карьеро; и др. (1 апреля 1994 г.). «Альтернатива Linda системам передачи сообщений» (PDF) . Параллельные вычисления . 2 (4): 633–655. дои : 10.1016/0167-8191(94)90032-9 .
^ Эрикссон-Зенит (1992). Модели взаимодействия процессов . Парижский университет.
^ Дж. Пол Родкер Моррисон (2 июля 2004 г.). «Координационный язык» . Архивировано из оригинала 28 сентября 2023 г. Проверено 9 января 2022 г.
^ Кридлиг, Режис; Губо, Эрик (1993). «Семантика и анализ языков на основе Линды». Конспекты лекций по информатике, том 724 . Шпрингер, Берлин, Гейдельберг. дои : 10.1007/3-540-57264-3_30 . ISBN 978-3-540-57264-0 .

[lecture-1] Чианкарини, Паоло. «Лекция 3: Языки координации» (PDF) . Болонский университет . Проверено 9 января 2022 г.

[scientific-2] «Дэвид Гелернтер, бакалавр и магистр '76» . Йельский научный институт . 14 февраля 2011 года . Проверено 8 января 2022 г.

[wells-3] Jump up to: Перейти обратно: ^а ^б Уэллс, Джордж (июль 2005 г.). «Языки координации: Назад в будущее с Линдой» (PDF) . Конференция: 2-й международный семинар по методам координации и адаптации предприятий-разработчиков программного обеспечения . Университет Родоса. Архивировано из оригинала (PDF) 19 декабря 2009 года.

[coordination-4] Гелернтер, Дэвид; Каррьеро, Николас (февраль 1992 г.). «Языки координации и их значение» (PDF) . Коммуникации АКМ . 35 (2): 97–107. дои : 10.1145/129630.129635 . S2CID 7748555 .

[5] Каррьеро, Николас; Гелернтер, Дэвид (1 января 1985 г.). «Ядро Linda S/Net (расширенное резюме)». Материалы десятого симпозиума ACM по принципам операционных систем - СОСП '85 . СОСП '85. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 160–. дои : 10.1145/323647.323643 . ISBN 978-0897911740 . S2CID 6922183 .

[nyt-6] Jump up to: Перейти обратно: ^а ^б Маркофф, Джон (19 января 1992 г.). «Роман Дэвида Гелернтера с Линдой» . Нью-Йорк Таймс . Архивировано из оригинала 30 декабря 2019 года . Проверено 8 января 2022 г.

[:0-7] Ахуджа, Судхир; Каррьеро, Николас; Гелернтер, Дэвид (август 1986 г.), «Линда и друзья», Компьютер , 19b (8), IEEE: 26–34, doi : 10.1109/mc.1986.1663305 , S2CID 5155678

[barber-8] Джон Х. Рейнольдс (декабрь 2002 г.). «Линда будит спящего парикмахера» (PDF) . Материалы зимней симуляционной конференции . Том. 2. Сан-Диего, Калифорния: IEEE. стр. 1804–1808. дои : 10.1109/WSC.2002.1166471 . ISBN 0-7803-7614-5 . S2CID 62584541 . Проверено 8 января 2022 г.

[9] Масатоши Секи (февраль 2017 г.). Книга dRuby: Распределенные и параллельные вычисления с Ruby (изд. 0.1). Прагматичные программисты . Проверено 9 января 2022 г.

[mpi-10] Карьеро; и др. (1 апреля 1994 г.). «Альтернатива Linda системам передачи сообщений» (PDF) . Параллельные вычисления . 2 (4): 633–655. дои : 10.1016/0167-8191(94)90032-9 .

[process-11] Эрикссон-Зенит (1992). Модели взаимодействия процессов . Парижский университет.

[12] Дж. Пол Родкер Моррисон (2 июля 2004 г.). «Координационный язык» . Архивировано из оригинала 28 сентября 2023 г. Проверено 9 января 2022 г.

[13] Кридлиг, Режис; Губо, Эрик (1993). «Семантика и анализ языков на основе Линды». Конспекты лекций по информатике, том 724 . Шпрингер, Берлин, Гейдельберг. дои : 10.1007/3-540-57264-3_30 . ISBN 978-3-540-57264-0 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]