Distributed computing

EXAMPLE: MATRIX MULTIPLICATION

• There are two matrices A and B. We store A’s rows and B’s columns as tuples.
• (“A”, 1, A’s first row), (“A”, 2, A’s second row) ….
• (“B”, 1, B’s first column), (“B”, 2, B’s second column) ….
• (“Next”, 15)
• There is a global counter called Next in the range 1 .. number of rows of A x number of columns of B.
• A process performs an “in” on Next, records the value, and performs an “out” on Next+1, provided Next is still in its range.
• Convert Next into the row number I and column number j such that Next = i x total number of columns + j.

ACTUAL MULTIPLICATION

• First find i and j.
• in (“Next”, ?temp);
• out (“Next”, temp +1);
• convert (temp, i, j);
• Given i and j, a process just reads the values and outputs the result.
• read (“A”, i, ?row_values)
• read (“B”, j, ?col_values)
• out (“result”, i, j, Dotproduct(row, col)).

LINDA IMPLEMENTATION OF SHARED TUPLE SPACE

• The implementers assert that the work represented by the tuples is large enough so that there is no need for shared memory hardware.
• The question is how to implement out, in, and read (as well as inp and readp).

BROADCAST IMPLEMENTATION 1

• Implement out by broadcasting the argument of out to all sites. (Use a negative acknowledgement protocol for the broadcast.)
• To implement read, perform the read from the local memory.
• To implement in, perform a local read and then attempt to delete the tuple from all other sites.
• If several sites perform an in, only one site should succeed.
• One approach is to have the site originating the tuple decide which site deletes.
• Summary: good for reads and outs, not so good for ins.

• out

BROADCAST IMPLEMENTATION 2

• Implement out by writing locally.
• Implement in and read by a global query. (This may have to be repeated if the data is not present.)
• Summary: better for out. Worse for read. Same for in.

• in, read