Conference rusure::math

986.0. "Combining Mechanism" by CLT::GILBERT (Multiple inheritence happens) Mon Dec 05 1988 20:43

A recent ACM article (1) describes a "combining mechanism" that can be used
to reduce interlock contention on shared computer variables in multiprocessors.

Suppose fetch-and-theta is a primitive atomic operation:

	function fetch-and-theta (X,b)
	    begin
	    temp := X;
	    X := X theta b;
	    return (temp);
	    end;

For example, fetch-and-add is such an atomic operation on several computers.

Suppose requests have the form: <id, addr, f>, where id identifies the request,
addr is the memory address of the shared variable, and f is a suitable encoding
of the operation to be performed.  Let @addr be the contents of location addr.
The memory unit fetches @addr, and sets the value to f(@addr); it replies with
<id, @addr>, where @addr is the original value.

The following "combining mechanism" reduces contention for shared variables.
Suppose we have requests <id1,addr,f> and <id2,addr,g>.  The combining mechanism
saves these requests, and forwards <id1,addr,f o g> to the memory unit, where
f o g denotes functional composition, f o g (x) = g(f(x)).  When the combining
mechanism receives the reply <id1,val>, it returns it as the result for id1,
and sends <id2,g(val)> as the result for the id2 request.

For example, with fetch-and-add, f and g could simply be the addends; the
combining mechanism combines <id1,addr,f> and <id2,addr,g> into <id1,addr,f+g>,
and when it gets the reply <id1,val>, at also sends <id2,val+g> back for id2.
Bitwise test-and-set operations can be similarly combined.

The following has been proposed as an atomic interlocked operation:

	function fetch-and-rma (X,b,c)
	    begin
	    temp := X;
	    X := (X and not b) + c;
	    return (temp);
	    end;

Here, X is a binary number of w bits, (X and not b) is a bitwise logical
operation, and the addition is performed modulo 2^w.

The combining mechanism requires a suitable encoding of 'f o g', where (roughly)
f = <b1,c1> and g = <b2,c2>.  Indeed, we'd like an encoding such that we have
closure over 'f o g'.  The problem is to find such an encoding, and/or to
determine a (near-)minimum number of bits needed for such an encoding.

As a second problem, suppose the combining mechanism is allowed some freedom:
when it receives two requests <id1,addr,f> and <id2,addr,g>, the combining
mechanism may choose to forward either <id1,addr,f o g> or <id2,addr,g o f>;
that is, it may combine the requests in either order.  Does this significantly
reduce the number of bits needed for the fetch-and-rma encoding?

					- Gilbert

(1) "Efficient Synchronization on Multiprocessors with Shared Memory";
Kruskal, Rudolph, and Smir; ACM Transactions on Programming Languages and
Systems, Vol.10, No.4, Oct.1988, pgs.579-601.

>> ...it returns it as the result for id1,
>> and sends <id2,g(val)> as the result for the id2 request.

This seems to be a typo - did you mean <id2,f(val)> (which is the
value "before" g is applied)?

>> ... also sends <id2,val+g> back for id2.

In the same vein, shouldn't this be <id2,val+f>?

Right, right.  Sorry about those typos.

If we have 1-bit numbers, all 4 functions can be produced from fetch-and-rma.

	f(0) f(1)
	 0    0		((x and not 3) + 0)
	 0    1		(x)
	 1    0		(x + 1)
	 1    1		((x and not 3) + 1)

If we have 2-bit numbers, 28 functions on 2-bit numbers can be produced, ...

	f(0) f(1) f(2) f(3)

	 0    0    0    0
	 0    0    2    2
	 0    1    2    3
	 0    1    0    1
	 0    2    2    0
	 0    2    0    2
	 0    3    0    3

... the above 7, and 21 more that result from adding 1, 2, or 3 to each
of the above functions.