How to use Mulitcore Processors with GNAT ?

How to use Mulitcore Processors with GNAT ?

[Vincent DIEMUNSCH]

Hello,
I'm wondering how we could use the incoming power of multicore
processors in Ada with GNAT.

Ada allows us to express parallelism in an abstract and portable
manier through the use of tasks. But the fact is that a single, local
Ada task is often implemented by a thread (a "light" process), and
creating a bunch of threads each time we find computations that can be
parallized is not efficient !

I heard that the language Erlang, and others, have integrated into the
  Run-Time the ability to create very small "processes" that are
dynamically dispatched (multiplexed) on a fixed number of threads,
corresponding to the number of processing cores of the machine.

So I had the following ideas :
1) to express parallelism in Ada, we can rewrite a sequential program
with the use of local tasks that are TRIVIAL ie that have simply no
entry and do not call any entry. We simply have to be sure that there
 is no data conflict during the parallel execution. Here is an exemple:

procedure Multicore is

   function Big_Work (Number : natural) return Segmentation
   is
      Result : Segmentation;
   begin
      ...
      return Result;
   end Big_Work;

   Final_Segmentation : array (1 .. 4) of Segmentation;

begin

   -- Sequential case :
   for i in 1 .. 4 loop
      Final_Segmentation(i) := Big_Work (i);
   end loop;

   -- Parallel case :
   declare
      task type Work (i : natural);
      task body Work is
      begin
         Final_Segmentation(i) := Big_Work (i);
      end Work;

      type Work_Access is access Work;
      Agent : array (1..4) of Work_Access;
   begin
      for i in 1 .. 4 loop
         Agent (i) := new Work (i);
      end loop;
   end;
   -- when the "end" is completed, all the "Agent" tasks have
   -- terminated. An the Final_Segmentation Array is filled.

end Multicore;

2) Once we have these "Trivial Tasks" that in fact are simply "job
items", we could give the ability to the GNAT Compiler to treat them
in  a special Run-Time Queue that will provide dispatching on as many
thread as we have available cores at the present time on the machine.
To do that we have to add a pragma ("MULTICORE" ? or
"LIGHT_PARALLEL_PROCESSING" ??) just like the Restricted_Runtime or
"Ravenscar" pragmas. The Run-Time could then be something like the
following (it's just ideas... !) : 

-- This package could be a part of the GNU Ada Run Time, called
-- System.Tasking.Trivial_Tasks or something like !

-- Trivial tasks are tasks with :
--   No entry declaration
--   No specific priority
--   No child task
--   No entry call
--   No accept statement
--   The call of protected functions or procedures is tolerated, provided
--   that the suspension time be bounded and short.

-- It aims at multiplexing the trivial tasks on a fixed number of threads,
-- precisely one per processing core, so that parallelism on multicore
processor
-- can be realized easely.

with Ada.Exceptions; use Ada.Exceptions;
package System_Tasking_Trivial_Tasks is

   -- first the main task creates a computation, with a given priority.
   type Conputation_Id is limited private;
   function Create_Computation return Conputation_Id;

   -- then, the main task register the small local tasks that can be
executed
   -- in parallel to make the Computation. All tasks have the same
priority,
   -- equal to the main task. They are executed only once and
terminate after
   -- they have done their job.
   type Trivial_Task_Id is limited private;
   procedure Register_Trivial_Task (Where         : Conputation_Id;
                                    State         : Task_Procedure_Access;
                                    Discriminants : System.Address;
                                    Task_Image    : String;
                                    Created_Task  : out Trivial_Task_Id);

   -- Finally, the main task will wait until the computation is done
(until all
   -- tasks of this computation have returned) and contribute to the
work by
   -- executing some tasks (enventually all if the system is very busy !).
   procedure Complete_Computation (Computation        : Conputation_Id;
                                   Exception_Occurred : out Boolean;
                                   Error              : out
Exception_Occurrence);


private
   -- ... to do !


end System_Tasking_Trivial_Tasks;

And the corresponding BODY :

package body System_Tasking_Trivial_Tasks is

   -- To register the trivial tasks we use a FIFO queue, where trivial
tasks are
   -- grouped according to their computation. When all tasks of the
computation
   -- have terminated, the Computation is Done. (cf. Tasking.Stages).

   type Computation_State is
     (Idle,       -- NO unterminated trivial tasks in the FIFO queue
      busy,       -- THERE IS unterminated tasks in the FIFO queue
      aborted);   -- an exception or an abort signal occured

   -- To do the jobs, we create as many SYSTEM THREADS as we have
processor
   -- cores, minus 1 (since the Main task is already a thread). We
call these
   -- "contributing tasks".
   task type Contributor;

   -- We put this queue in a protected object, with the following
specifications
   protected Job_Queue is

      -- The main task can create trivial tasks (jobs) inside a given
computation
      -- All these trivial tasks have the priority of their main task.
      procedure New_Computation  (NC_Id : out Conputation_Id);
      function  Computation_Done (C_Id  : Conputation_Id) return Boolean;

      procedure Add_Job          (Where         : Conputation_Id;
                                  State         : Task_Procedure_Access;
                                  Discriminants : System.Address;
                                  Task_Image    : String;
                                  Created_Task  : out Trivial_Task_Id);

      procedure Abort_Job        (T_Id          : Trivial_Task_Id);
      procedure Abort_Computation(C_Id          : Conputation_Id);

      -- Each Contribtuing task waits for a job. When it gets a job, it's
      -- priority is raised to the priority of the main task who
created the job.
      entry     Wait_for_a_Job   (Job_Procedure : out
Task_Procedure_Access;
                                  Task_Id       : out Trivial_Task_Id);
      procedure Notify_Exception (Task_Id       : Trivial_Task_Id;
                                  Occurrence    : Exception_Occurrence);

      -- the main task contribute for it's own computation only, until the
      -- computation is done. If the computation is busy, it will
return a job
      -- to do. If the computation is aborting it will return an
exception.
      procedure Contribute       (To            : Conputation_Id;
                                  State         : out Computation_State;
                                  Job_Procedure : out
Task_Procedure_Access;
                                  Task_Id       : out Trivial_Task_Id;
                                  Comp_Exception: out
Exception_Occurrence);

      procedure Clear_Computation(C_Id  : Conputation_Id);
      -- Computation is cleared only if not busy (ie idle or aborted).

   private
      Empty_Queue : Boolean := True; -- If the Queue is empty.

   end Job_Queue;


   -- contributing tasks, simply wait for jobs to do !
   task body Contributor is
      Job_Procedure : Task_Procedure_Access;
      Task_Id       : Trivial_Task_Id;
   begin
      loop
         Job_Queue.Wait_for_a_Job (Job_Procedure, Task_Id);
         begin
            null; -- call the given "Task_Procedure_Access"
         exception
            when E : others =>
               Job_Queue.Notify_Exception (Task_Id, E);
         end;
      end loop;
   end Contributor;



   procedure Complete_Computation (Computation        : Conputation_Id;
                                   Exception_Occurred : out Boolean;
                                   Error              : out
Exception_Occurrence)
   is
      State          : Computation_State;
      Job_Procedure  : Task_Procedure_Access;
      Task_Id        : Trivial_Task_Id;
      Comp_Exception : Exception_Occurrence;
   begin
      loop
         Job_Queue.Contribute(Computation, State, Job_Procedure, Task_Id,
                              Comp_Exception);
         exit when State /= Busy;
         begin
            null; -- call the given "Task_Procedure_Access"
         exception
            when E : others =>
               Job_Queue.Notify_Exception (Task_Id, E);
         end;
      end loop;

      case State is
         when Idle =>
            Exception_Occurred := False;
            Save_Occurrence (Error, Null_Occurrence);
            return;
         when Busy =>
            raise Assertion_Fault;
         when Aborted =>
            Exception_Occurred := True;
            Save_Occurrence (Error, Comp_Exception);
            return;
      end case;
   end Complete_Computation;

 -- !!! NOT FINISHED


end System_Tasking_Trivial_Tasks;


I would be very pleased to hear any comment about that.
Thanks in advance.

Vincent 



 

Re: How to use Mulitcore Processors with GNAT ?

[tmoran]

> dispatching on as many thread as we have available cores at the present
> time on the machine.
    Suppose you write a somewhat interactive, but highly computational
program - video rendering, say - to use all the cores.  Then I come along
and want to control it with speech recognition, which needs a lot of CPU.
Your program will do the rendering slightly faster by trying to monopolize
all the CPUs, but the interactive control will be very poor.