Введение

В информатике Линда — это модель координации, облегчающая взаимодействие в средах параллельных вычислений. Разработанная Дэвидом Гелернтером, она предназначена для использования совместно с полноценным языком программирования, таким как Fortran или C, где роль Линды заключается в создании вычислительных процессов и обеспечении связи между ними.

История

Дэвид Гелернтер написал первую версию Linda в 1979 году, будучи аспирантом, и назвал её в честь Линды Лавлейс, известной по порнографическому фильму «Глубокое горло». В то время основным языком для параллельных вычислений был Ada, разработанный Министерством обороны США как дань уважения Аде Лавлейс, который Гелернтер считал «неэлегантным и громоздким». Linda получила широкое распространение в 1986 году, когда Гелернтер вместе со своим коллегой из Йельского университета Николасом Каррьеро и Судиром Ахуджей из AT&T Bell Laboratories опубликовали статью «Linda и друзья» в журнале IEEE. К началу 1990-х годов Linda широко использовалась корпорациями для более эффективного анализа больших данных, включая брокерские фирмы на Уолл-стрит, а также компании AT&T, Boeing и United Technologies. Существовали даже компании, специализирующиеся на создании специализированных приложений для параллельных вычислений на основе Linda, крупнейшей из которых была Scientific Computing Associates, компания из Нью-Хейвена, основанная несколькими учеными-компьютерщиками из Йеля (Гелернтер время от времени консультировал их, но не работал в ней).

Сравнение

По сравнению с другими моделями параллельной обработки, Linda более ортогональна в том, что рассматривает координацию процессов как отдельную деятельность от вычислений, и более универсальна, поскольку способна охватывать различные уровни параллелизма – однопроцессорный, многопоточный многопроцессорный или сетевой – в рамках единой модели. Эта ортогональность позволяет процессам, выполняющим вычисления на разных языках и платформах, взаимодействовать, используя одни и те же примитивы. Универсальность Linda позволяет многопоточной системе распространяться на несколько компьютеров без изменений. В то время как модели передачи сообщений требуют тесно связанных процессов, обменивающихся сообщениями в определенной последовательности или по протоколу, процессы Linda отсоединены друг от друга и взаимодействуют только через пространство кортежей (tuplespace); процессу не требуется знать о существовании других процессов, кроме типов потребляемых или производимых кортежей. Критика Linda со стороны сообщества многопроцессорных систем часто фокусируется на снижении скорости операций в системах Linda по сравнению с системами интерфейса передачи сообщений (MPI). Хотя эти утверждения не лишены оснований, они были в значительной степени опровергнуты для важного класса задач. Подробную критику модели Linda можно найти в книге Стивена Эрикссона Зенита «Модели взаимодействия процессов». Исследователи предлагали дополнительные примитивы для поддержки различных типов связи и координации между (открытыми распределенными) компьютерными системами, а также для решения конкретных проблем, возникающих при различных применениях модели. Исследователи также экспериментировали с различными способами реализации виртуальной разделяемой памяти для этой модели. Многие из этих исследователей предлагали существенные модификации оригинальной модели Linda, разработав семейство систем, известных как Linda-подобные системы (Linda-like systems) и реализованных как ортогональная технология (в отличие от оригинальной версии). Примером этого является язык Ease, разработанный Стивеном Эрикссоном Зенитом. Подход Linda также сравнивался с потоковым программированием.

Линда-калькулус

Расчет Линды является формализацией вышеописанной модели, с той разницей, что операция "следующий" включает в себя как операции out, так и eval.

Семантика

Тупловое пространство представляется как мультимножество процессов. Мы записываем , где – мультимножество, – мультимножество, содержащее единственный элемент, а – операция объединения мультимножеств. Семантика затем определяется как отношение редукции на мультимножестве следующим образом. Обратите внимание, что (ввод) извлекает кортеж из туплового пространства, в то время как (чтение) только считывает его. Получаемая операционная семантика является синхронной.