Assignment VI

Due date Monday November 27.


Assignment VI: concurrency and tasking.
The following describes a solution to the problem outlined in section 7.5 of Sethi's book: a pipeline to compute prime numbers with some degree of parallelism.

a) Read the code below and make sure you understand how each part works.

b) Compile it and find all the primes smaller than 200.

c) As written this is quite inefficient, because the early tasks do much more work than the later ones: the first one discards one third of the numbers, while the 4th one only sees 1/11th, and so on. To make this more efficient, each successive task should really keep track of more primes, for example twice as many as the previous one. This way each task does some more signifi- cant computation between communication steps.

Modify the program accordingly. Each task now has an array My_Primes, that it fills up. When the array is full, the task creates the next tester in the chain, as before. The size of the array is given by a global variable, which is updated by each tester before creating its successor. This is an example of tasks communicating in unsafe manner through a shared location. This is ok in this case, because we know that only one new task will be created at a time, but in general may lead to race conditions so it is to be avoided. Communication through an entry call is semantically safer, but of course more expensive.

When a tester gets a number, it divides it successively by all the primes it stores, so you need to keep track of how many are already in this tester. >
------------------------------------------------------------------------------
-- A concurrent sieve to find prime numbers: each task holds one prime and
-- communicates with the task that holds the Next prime. The candidate number is
-- tested by each task in  succession; if it is not divisible in the current task,
-- it is sent to its successor. If it reaches the end of the chain, it is a new
-- prime, in which case a new task is created to hold it. Concurrency is achieved
-- because several candidates may be propagating simultaneously down the chain.
-- We can visualize the system as follows (assume that we generate only odd
-- numbers, to save some effort:
-- 
-- -----     -------------     -------------      ---------------------    ----
-- |main| -> |divisor by 3| -> |divisor by 5| ... |divisor by nth prime| ->... 
-- -----     -------------     -------------      ---------------------    ----

package Primes is 
    task type Tester is
       entry my_Prime(X: Integer);         --  each task has one prime to check
       entry Check(X: Integer);           --  neighbor passes number to check.
    end Tester;

    subtype Prime is Tester;               -- to simplify code below
    type Ptr_Prime is access Prime;        -- to create tasks dynamically.
end Primes;

with Text_Io; use Text_Io;
package body Primes is
    task body Tester is
       Mine: Integer;                    --  store it locally.
       Next_Prime: Ptr_Prime;            --  next task in chain.
    begin
       accept my_Prime(x : Integer) do 
          Mine := X;                     --  now we know what to divide by.
          Put_Line("new Prime:" & Integer'image(X));
       end;

       loop                                             -- indefinitely
          select
              accept Check(X: Integer) do
                 if X mod Mine /= 0 then		-- pass it on.
                     if Next_Prime = null then		-- a new prime.
                         Next_Prime := new Prime;	-- clone,
                         Next_Prime.my_Prime(X);	-- and initialize.
                     else
                         Next_Prime.Check(X);		-- just pass it on.
                     end if;
                 else
                    null;                               --  discard multiple.
                 end if;
              end;
          or
	      terminate;
          end select;
       end loop;
    end Tester;
end Primes;

with Primes; use Primes;
procedure main is
  First: Ptr_Prime := new Prime;                      -- to hold first divisor

begin
  First.my_Prime(3);                                   --  which is three.

  --  generate odd numbers only

  for i in 2 .. 50 loop
      First.Check (2 * i + 1);
   end loop;

  abort First.all; 				-- the others will also go.
end main;