Linda (koordinationsspråk)

Linda

Paradigm	Multiparadigm
Familj	Koordinationsspråk
Designad av	David Gelernter
Utvecklare	Scientific Computing Associates
Dök först upp	1986 ( 1986 )
Hemsida	lindaspaces .com
Influerade
Java

Inom datavetenskap är Linda en koordinationsmodell som underlättar kommunikation i parallella datormiljöer . Utvecklat av David Gelernter , är det tänkt att användas tillsammans med ett fullfjädrat beräkningsspråk som Fortran eller C där Lindas roll är att " skapa beräkningsaktiviteter och att stödja kommunikationen mellan dem".

Historia

David Gelernter skrev den första versionen av Linda som Ph.D. kandidat 1979 och döpte den efter Linda Lovelace , som medverkade i den pornografiska filmen Deep Throat . På den tiden var huvudspråket för parallell bearbetning Ada , utvecklat av det amerikanska försvarsdepartementet och en hyllning till Ada Lovelace , som Gelernter ansåg vara ett "olegant och skrymmande" språk.

Den släpptes flitigt 1986, när Gelernter, tillsammans med sin Yale-kollega Nicholas Carriero och Sudhir Ahuja vid AT&T Bell Laboratories , publicerade "Linda and Friends" i en IEEE- tidskrift.

I början av 1990-talet användes Linda i stor utsträckning av företag för att mer effektivt genomföra big data- analyser, inklusive Wall Street -mäklare såväl som AT&T , Boeing och United Technologies . Det fanns till och med företag som specialiserade sig på att skapa specialiserade parallella datorapplikationer baserade på Linda, varav den största var Scientific Computing Associates, ett New Haven -baserat företag grundat av flera Yale-datavetare (Gelernter konsulterade ibland för dem men arbetade inte där). Intresset för Linda sjönk i mitten av 1990-talet, för att sedan göra comeback i slutet av 1990-talet med flera företag som implementerade Linda i Java , inklusive Sun Microsystems och IBM .

Översikt

Modell

Linda-modellen tillhandahåller ett distribuerat delat minne , känt som ett tuppelutrymme eftersom dess grundläggande adresserbara enhet är en tupel , en ordnad sekvens av maskinskrivna dataobjekt; specifikt i Linda är en tuppel en sekvens av upp till 16 skrivna fält omgivna inom parentes". Tuppelutrymmet "delas logiskt av processer" som kallas arbetare som lagrar och hämtar tuplar.

Operationer

En av Lindas främsta fördelar är att det är enkelt, med endast sex operationer som arbetare utför på tuplarna för att komma åt tuplespace:

• ut : Lägger en tuppel i tuppelutrymmet
• in : Tar ut en tuppel som matchar ett givet mönster från tupelutrymmet (om det inte finns någon matchning blockeras operationen)
• rd : Kopierar en tuppel som matchar ett givet mönster från tupelutrymmet (om det inte finns någon matchning blockeras operationen)
• eval : Skapar en ny process för att utvärdera tupler
• inp : En icke-blockerande version av in (om det inte finns någon matchning returneras ett felmeddelande)
• rdp : En icke-blockerande version av rd (om det inte finns någon matchning returneras ett felmeddelande)

Jämförelse

Jämfört med andra parallellbearbetningsmodeller är Linda mer ortogonal när det gäller att behandla processkoordination som en separat aktivitet från beräkning, och det är mer generellt när det gäller att kunna subsumera olika nivåer av samtidighet – enprocessor, flertrådig multiprocessor eller nätverksansluten – under en enda modell. Dess ortogonalitet gör att processer som använder olika språk och plattformar kan samverka med samma primitiver. Dess generalitet gör att ett flertrådigt Linda-system kan distribueras över flera datorer utan förändring.

Medan meddelandeöverförande modeller kräver tätt kopplade processer som skickar meddelanden till varandra i någon sekvens eller protokoll, är Linda-processer frikopplade från andra processer och kommunicerar endast genom tupelutrymmet; en process behöver inte ha någon aning om andra processer förutom de typer av tuplar som konsumeras eller produceras. Kritik mot Linda från multiprocessing-gemenskapen tenderar att fokusera på den minskade hastigheten för operationer i Linda-system jämfört med Message Passing Interface (MPI)-system. , motbevisades dessa påståenden till stor del för en viktig klass av problem Detaljerad kritik mot Linda-modellen finns också i Steven Ericsson-Zeniths bok Process Interaction Models .

Forskare har föreslagit mer primitiver för att stödja olika typer av kommunikation och samordning mellan (öppna distribuerade) datorsystem, och för att lösa särskilda problem som uppstår vid olika användningar av modellen. Forskare har också experimenterat med olika sätt att implementera det virtuella delade minnet för denna modell. Många av dessa forskare föreslog större modifieringar av den ursprungliga Linda-modellen och utvecklade en av system som kallas Linda-liknande system skillnad från originalversionen). Ett exempel på detta är språket Ease designat av Steven Ericsson-Zenith.

Lindas tillvägagångssätt har också jämförts med flödesbaserad programmering . Koordinationsspråk - En liten diskussion om skillnaderna mellan Lindas tillvägagångssätt och Flow-baserad programmering

Linda-kalkyl

Linda-kalkylen är en formalisering av ovanstående modell med den skillnaden att i det följande o u t e $mathrm {outeval} }$ subsumerar både ut- och evaloperationer .

Syntax

Vi abstraherar den konkreta representationen av tuplar. Vi antar bara att vi har en uppsättning tuplar $t\in {\mathcal {T}}$ och vi får bilda och tillämpa en substitutionsfunktion $\sigma$ på tupler som ersätter variabler för termer som ger en tupel. Till exempel, givet att vi har en tuppel $t=({\mathit {hej}},x)$ , och sedan tillämpa en substitution $\sigma =\{{\mathit {world}}/x\}$ på $t$ ger $({\mathit {hej}},{\mathit {världen}})$

Linda-kalkylprocesserna definieras av följande grammatik.

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

Syntaxen inkluderar de efternämnda Linda-operationerna, icke-deterministiskt val och rekursion . Substitutionsfunktionen utvidgas till processer rekursivt.

Semantik

Ett tupelutrymme representeras som en multiuppsättning av processerna. Vi skriver $M\,|\,P$ för $M\uplus \{P\}$ där $M$ är en multiset, $\{P \}$ en singleton multiset, och $\uplus$ är multiset-unionsoperationen. Semantiken definieras sedan som en reduktionsrelation på en multiset $M\rightarrow M'$ enligt följande.

${\begin{array}{lrcll}{\text{(outeval)}}&M\,|\,\mathrm {outeval} (P).Q&\rightarrow &M\,|\,P \,|\,Q&\\{\text{(läs)}}&M\,|\,\mathrm {rd} (t).P\,|\,t'&\högerpil &M\,|\,P \sigma \,|\,t'&{\text{om det finns }}\sigma {\text{ så att }}t\sigma =t'\\{\text{(ingång)}}&M\,|\ ,\mathrm {i} (t).P\,|\,t'&\högerpil &M\,|\,P\sigma &{\text{om det finns }}\sigma {\text{ så att }}t \sigma =t'\\{\text{(vänster val)}}&M\,|\,P+Q&\högerpil &M\,|\,P&\\{\text{(höger val)}}&M\, |\,P+Q&\högerpil &M\,|\,Q&\\{\text{(rekursion)}}&M\,|\,\mathbf {rec} XP&\högerpil &M\,|\,P\{\ mathbf {rec} XP/X\}&\\\end{array}}$

Observera att (inmatning) förbrukar tupeln $t'$ från tupelutrymmet medan (läs) bara läser den. Den resulterande operativa semantiken är synkron.

Genomföranden

Linda implementerades ursprungligen i C och Fortran , men har sedan dess implementerats i många programmeringsspråk, inklusive:

• C : C-Linda, TCP-Linda , LinuxTuples
• C++ : CppLinda , Boreas
• C# : pSpaces
• Erlang : Erlinda
• Gå : pSpaces
• Java : JavaSpaces , jRESP , TSpaces , LightTS , LIME , pSpaces
• JavaScript : pSpaces
• Läspa
• Lua : LuaTS Lua Lanes
• Prolog : SICStus Prolog Linda
• Python : PyLinda
• Ruby : Rinda
• Swift : pSpaces

Några av de mer anmärkningsvärda Linda-implementeringarna inkluderar:

• C-Linda eller TCP-Linda - den tidigaste kommersiella och en utbredd implementering av virtuellt delat minne för superdatorer och klustrade system från Scientific Computing Associates, grundat av Martin Schultz.
• JavaSpaces - en Java-baserad tuplespace-implementering som hjälpte till att popularisera distribuerad datoranvändning.
• TSpaces - en Java-baserad tuplespace-plattform från IBM.

Se även

• Data flöde
• Dataflödesdiagram
• Dataflödesprogrammering
• Flödesbaserad programmering
• Parallell beräkning