Go backward to Long Integer Multiplication Go up to Tutorial |
// ---------------------------------------------------------------------------- // Long Integer Multiplications (Bag Version) // ---------------------------------------------------------------------------- #include <rt++.h> typedef char Digit; typedef Array<Digit> Number; ... // ---------------------------------------------------------------------------- // sum of two numbers // ---------------------------------------------------------------------------- Number sum(Number a, Number b) { ... return(s); } // ---------------------------------------------------------------------------- // product of number and digit // ---------------------------------------------------------------------------- Number prod(Number a, Digit b) { ... return(p); } // ---------------------------------------------------------------------------- // multiplication of two numbers // ---------------------------------------------------------------------------- Number mult(Number a, Number b) { int lb = Length(b); int n = 2*lb-1; ThreadBag<Number> bag(n); for (int i = 0; i < lb; i++) { ThreadBag2<Number, Number, Digit>(bag, prod, a, b[i]); } for (int j = 0; j < n-2 ; j += 2) { Number a = Wait(bag, j); Number b = Wait(bag, j+1); ThreadBag2<Number, Number, Number>(bag, sum, a, b); } return(Wait(bag, n-1)); } ...
The program is based on the concept of thread bags that collect thread results and provide them in the order in which they have been computed (i.e. in the order in which the threads have terminated):
declares a bag that can hold up to n threads of result typeThreadBag<Number> bag(n);
Number
. It is also possible to declare bags without an explicit
size specification but this is less efficient.
creates a new thread computingThreadBag2<Number, Number, Digit>(bag, prod, a, b[i]);
prod(a, b[i])
. The thread itself is
anonymous but its result can be retrieved via bag.
returns the j-th thread result in bag where it is undefined by which thread this result was computed (but two calls ofWait(bag, j)
Wait
with the same index in the same program run always return the same result).
The first two declarations are required because digits and numbers are used as thread arguments and results, respectively. The third sort of declaration is required for any type of thread bags used by the program (the individual kinds of anonymous threads need not be declared).Atom(Digit); Ref(Number); ThreadBagRes(Number);
Above solution has one disadvantage compared to the approach presented in the previous section. The main program waits for the first phase thread results in the bag before it starts the second phase threads. We can overcome this over-synchronization by passing the thread bag directly to the second phase threads and let these threads themselves synchronize with their required arguments. This idea is sketched below (the full program can be found here).
// ---------------------------------------------------------------------------- // Long Integer Multiplications (Bag Version) // ---------------------------------------------------------------------------- #include <rt++.h> typedef char Digit; typedef Array<Digit> Number; ... // ---------------------------------------------------------------------------- // sum of two thread bag results // ---------------------------------------------------------------------------- Number sum(ThreadBag<Number> a, int j) { Number a = Wait(bag, j); Number b = Wait(bag, j+1); ... return(s); } // ---------------------------------------------------------------------------- // product of number and digit // ---------------------------------------------------------------------------- Number prod(Number a, Digit b) { ... return(p); } // ---------------------------------------------------------------------------- // multiplication of two numbers // ---------------------------------------------------------------------------- Number mult(Number a, Number b) { int lb = Length(b); int n = 2*lb-1; ThreadBag<Number> bag(n); for (int i = 0; i < lb; i++) { ThreadBag2<Number, Number, Digit>(bag, prod, a, b[i]); } for (int j = 0; j < n-2 ; j += 2) { ThreadBag2<Number, ThreadBag<Number>, int>(bag, sum, bag, j); } return(Wait(bag, n-1)); } ...
In order to get an executable program, the following top-level declarations have to be provided to the garbage collector
The examples presented in this and the previous section outline the sort of programming style suggested by RT++: threads are entities that can be used and passed around as any other sort of runtime values. Consequently it is not necessary for the creator of a thread to resolve synchronization dependencies; this task can be as well performed by the threads themselves (self-synchronization). Furthermore, the program need not explicitly allocate or free resources; this task is performed by the underlying memory management system (garbage collection). The resulting programming style closely resembles the dataflow style of parallel computation.Atom(Digit); Ref(Number); Atom(int); Ref(ThreadBag<Number>); ThreadBagRes(Number);