Einführung in Linda

Was ist Linda?

Linda ist ein Konzept im Bereich der konkurrenten Programmierung. Linda verwendet zur Kommunikation
und unterscheidet sich daher grundlegend von Ada (synchron, Sender kennt Empfänger).

Linda ist also unabhängig von
Linda ist jedoch keine Programmiersprache, sondern besteht aus einigen Funktionen [primitives] die in andere Programmiersprachen eingebettet werden können. Dazu später mehr.

Der Tupelraum [tupel space]

Ein Prozeß, der eine neue Aufgabe erzeugt, die er nicht sofort selbst erledigt, stellt diese auf ein Blackboard. Das ist eine Stelle, auf die auch alle anderen Prozesse zugreifen können, ist also "shared memory".

Dieses Blackboard heißt in Linda "tuple space" (Tupelraum) und ist folgendermaßen aufgebaut:

Wie eine Tabelle ohne festgelegter Spaltenanzahl und Spaltentyp. Das heißt jeder Eintrag, genannt Tupel, in diesem Tupelraum hat eine gewisse Anzahl von Parametern.

Die Stärke (das Geniale) von Linda liegt darin, daß ein Tupel auch formale Elemente [formal elements] enthalten kann. Die Parameter können nicht nur aktuell, sondern auch formell sein. Als Elemente eines Tupels wird also auch eine Typangabe akzeptiert.

Parameter ::= Wert | Typ
Tupel ::= Parameter {, Parameter}
Tupelraum ::= Tupel {, Tupel}

Ein Tupel soll so etwas wie eine Aufgabe beschreiben, wobei man den gewünschten ausführenden Prozeß (Prozeßnummer), eine Aufgabenkennung oder den aufrufenden Prozeß mit in das Tupel eintragen kann oder nicht. Es muß nur die Eindeutigkeit gewährleistet sein.


Manipulationen im Tupelraum

Zum Eintragen eines Tupels in den Tupelraum bzw. zum Auslesen eines Tupels aus den Tupelraum gibt es folgende Aufrufe [primitives]:

Output(T)Trägt das Tupel T in den Tupelraum ein.
Input(T) Entfernt ein passendes Tupel aus dem Tupelraum und bindet die formalen Parameter. Falls kein passenden Tupel gefunden wird, wartet es auf ein passendes.
Read(T)Wie Input, entfernt aber das Tupel nicht.
Try_Input(T)Wie Input, wartet aber nicht, wenn kein passendes Tupel vorhanden ist.
Try_Read(T)Wie Read, wartet aber nicht, wenn kein passendes Tupel vorhanden ist.

Zwei Tupel passen aufeinander [are matching], wenn die aktuellen Parameter übereinstimmen und die formalen Parameter des einen dem Typ des aktuellen Parameters des anderen Tupels entsprechen.

Beispiel:

Output(1, 'A')
Input(I: integer; C: character)

Output stellt das Tupel (1, 'A') in den Tupelraum. Input liest den Tupelraum und findet (1, 'A') als passendes Tupel, denn 1 ist vom Typ integer und 'A' ist vom Typ character. Die formalen Parameter werden gebunden (i:= 1, c:='A'). Das Tupel wird aus dem Tupelraum entfernt.

Anstelle von Input(I: integer, C: character) wäre zB auch folgendes möglich:

Input(I: integer; 'A')

Auch hier würde das Tupel (1, 'A') passen. I: integer würde mit 1 gebunden.


Einfaches Beispiel

Es soll folgende einfache Aufgabe gelöst werden:
Berechne das Produkt aus 2 und 3, bzw. 4 und 5 und drucke die Ergebnisse aus.

Eine "Ada"-ähnliche Lösung könnte etwa so aussehen:

Task 1
...
	prod1, prod2: natural;
begin
	output ('multipliziere', 2, 3);
	output ('multipliziere', 4, 5);
	input ('Produkt', prod1: natural);
	input ('Produkt', prod2: natural);
	print ("Ergebnisse: " & prod1 & "  " & prod2);
end;
Task 2 und 3
...
	input ('multipliziere', a: natural, b: natural);
	output ('Produkt', a*b);
end;


Dies führt zu folgendem Ergebnis:

Ergebnisse: 6 20

bzw.

Ergebnisse: 20 6

Je nachdem, ob Task 2 oder Task 3 als erster auf den Tupelraum zugreift.


Matrix Multiplikation in Linda


Geben seien folgende Matrizen A und B:

	1   2   3			1   1   1
   A =	4   5   6      und     B =	0   2   1
	7   8   9			2   1   1

Gesucht ist C = A * B.

Durch folgende Anweisungen werden die Daten der Matrizen in den Tupelraum geschrieben.

Output('A', 1, (1, 2, 3)); -- rows of first matrix
Output('A', 2, (4, 5, 6));
Output('A', 3, (7, 8, 9));
Output('B', 1, (1, 0, 2)); -- columns of second matrix
Output('B', 2, (1, 2, 1));
Output('B', 3, (1, 1, 1));

Output("Next", 1); -- next job counter

Zum Auslesen und zur Anzeige der Daten könnte ein Ada-Programm etwa so aussehen: Das Programm kann parallel zur eigentlichen Multiplikation ausgeführt werden:

for i in 1..3 loop
	for j in 1..3 loop
		INPUT('C', i: integer, j: integer, C: integer);
		print C(i, j);
	end loop;
end loop;


Die Arbeit der Matrixmultiplikation wird durch "worker"-Prozesse erledigt. Dabei ist es egal, ob es mehrere oder nur einen "worker"-Prozeß gibt.

Ein "Worker"-Prozeß könnte wie folgt aussehen:

task body workers is
	...					-- local data
	...					-- declarations
begin
	loop
		INPUT("Next", element);		-- get job number
		OUTPUT("Next", element + 1);	-- put next job number
		exit when element > 3 * 3;	-- check for termination
		i := (element - 1) / 3 + 1;	-- compute row number
		j := (element - 1) mod 3 + 1;	-- compute column number
		row_tuple := READ('A', i, v1);	-- get row
		col_tuple := READ('B', j, v2);	-- get coloumn
		x := inner_product(v1, v2);	-- compute result
		OUTPUT('C', i, j, x);		-- put result
	end loop;
end workers;