Tasking in Ada

Tasking in Ada

[Kang Su Gatlin]

Hello, I am currently working on a senior project in parallel algorithms but
I am also going to implement some of them.  One of the langueages that I'm
using is Ada.

I have hit a snag with Ada.  I need to create dynamic tasks that know which
task they are.

For example I create n tasks.  Task 1 knows it is task 1 and that there are
n total tasks.  Task 2 knows it is task 2 and that are n total tasks.  Task
n knows it is task n and that there are n total tasks.

I can't seem to find a way to pass information to tasks efficiently.  I want
all the tasks to run simultaneously so that the creation and execution of
the tasks can be done in t(1) time.  

The only way I can think of how to do it is to loop through and create the 
tasks but that is O(n) time.  Or I can create an array of tasks (if that is
possible) but then how do I get information to the tasks with using the
rendezvous mechanism (again O(n)).

All help is greatly appreciated, and methods used will be fully cited, so
include all information you would like printed.

Kang Su Gatlin

Re: Tasking in Ada

[howland.reston.ans.net!wupost!cs.utexas.edu!utnut!utcsri!csri.toronto.edu]

kgatlin@galaxy.csc.calpoly.edu (Kang Su Gatlin) writes:

>I have hit a snag with Ada.  I need to create dynamic tasks that know which
>task they are.
...
>I can't seem to find a way to pass information to tasks efficiently.  I want
>all the tasks to run simultaneously so that the creation and execution of
>the tasks can be done in t(1) time.  

>The only way I can think of how to do it is to loop through and create the 
>tasks but that is O(n) time.  Or I can create an array of tasks (if that is
>possible) but then how do I get information to the tasks with using the
>rendezvous mechanism (again O(n)).

If n is small, then looping through is probably the best way. If n is large
then consider the array of tasks as a tree (i.e. the children of task i are
tasks 2i and 2i+1) and have each task communicate the identities to its
children. This would give you O(log n) time. To start things off you would
need only to tell task 1 its identity.

At any rate, if your code is running on a serial machine, then simply looping
through is faster anyway, for there would be less parallelism being simulated
to assign the identities.

Cheers,
Ray
blaak@csri.toronto.edu

Re: Tasking in Ada

[cis.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!howland.]

In article 17841@rat.csc.calpoly.edu, kgatlin@galaxy.csc.calpoly.edu (Kang Su G
atlin) writes:
>Hello, I am currently working on a senior project in parallel algorithms but
>I am also going to implement some of them.  One of the langueages that I'm
>using is Ada.
>
>I have hit a snag with Ada.  I need to create dynamic tasks that know which
>task they are.
>
>For example I create n tasks.  Task 1 knows it is task 1 and that there are
>n total tasks.  Task 2 knows it is task 2 and that are n total tasks.  Task
>n knows it is task n and that there are n total tasks.
>
>I can't seem to find a way to pass information to tasks efficiently.  I want
>all the tasks to run simultaneously so that the creation and execution of
>the tasks can be done in t(1) time.  
>
>The only way I can think of how to do it is to loop through and create the 
>tasks but that is O(n) time.  Or I can create an array of tasks (if that is
>possible) but then how do I get information to the tasks with using the
>rendezvous mechanism (again O(n)).
>
>All help is greatly appreciated, and methods used will be fully cited, so
>include all information you would like printed.
>
>Kang Su Gatlin
>

The following will create an array of n tasks:

      task type Sample_Task;
      task body Sample_Task is
      begin
        ...
      end Sample_Task;

      type TASK_ARRAY is array (1 .. n) of Sample_Task;

      Task_List : TASK_ARRAY;

Unfortunately each task, Task_List(i), does not know which task it is.  You
can modify the task type to have an entry call to start the task and provide
a parameter such as a task ID.  But this might not fit in with your desire to
have tasks elaborate simultaniously (assuming a true parallel environment exist
s
to accomplish this).

Another way to get each task assigned an unique ID would be to create a task to
assign IDs.  As each of your tasks in the array begin execution, they could eac
h
rendezvous with this server task to get an unique ID.  Example:

      task ID_Manager is
        entry Get_ID(ID : out INTEGER);
      end ID_Manager;

      task body ID_Manager is
        Current_ID : INTEGER := 0;
      begin
        loop
          accept Get_ID(ID : out INTEGER) do
            ID := Current_ID;
            Current_ID := Current_ID + 1;
          end Get_ID;
        end loop;
      end ID_Manager;


      task type Sample_Task;
      task body Sample_Task is
        ID : INTEGER;
      begin
        ID_Manager.Get_ID(ID);
        ...
      end Sample_Task;

      type TASK_ARRAY is array (1 .. n) of Sample_Task;

      Task_List : TASK_ARRAY;


Now the above does not guarantee that the index of the task array will match th
e
ID each task receives, but it will guarantee unique IDs for each task.

If you need to create the tasks dynamically, you then create an access type of 
the
task type.  You could then create an array of these access objects if desired.
Example:

     task type Sample_Task is ...

     type SAMPLE_TASK_ACCESS is access Sample_Task;
     type SAMPLE_TASK_ACCESS_LIST is array (1 .. n) of SAMPLE_TASK_ACCESS;

     My_Task : SAMPLE_TASK_ACCESS_LIST;


     begin
       My_Task(i) := new Sample_Task;       -- task object is created here.

       if My_Task(i)'callable then          -- make sure task is available befo
re
         ...                                -- any attempt to rendezvous.
         

Hope the above examples help or give you some ideas.  Good luck.

                   Bob

Re: Tasking in Ada

[Mark A Biggar]

In article <1993Sep15.094745.16963@jarvis.csri.toronto.edu> blaak@csri.toronto.
edu (Raymond Blaak) writes:
>kgatlin@galaxy.csc.calpoly.edu (Kang Su Gatlin) writes:
>>I have hit a snag with Ada.  I need to create dynamic tasks that know which
>>task they are.
>...
>>I can't seem to find a way to pass information to tasks efficiently.  I want
>>all the tasks to run simultaneously so that the creation and execution of
>>the tasks can be done in t(1) time.  
>>The only way I can think of how to do it is to loop through and create the 
>>tasks but that is O(n) time.  Or I can create an array of tasks (if that is
>>possible) but then how do I get information to the tasks with using the
>>rendezvous mechanism (again O(n)).
>If n is small, then looping through is probably the best way. If n is large
>then consider the array of tasks as a tree (i.e. the children of task i are
>tasks 2i and 2i+1) and have each task communicate the identities to its
>children. This would give you O(log n) time. To start things off you would
>need only to tell task 1 its identity.
>At any rate, if your code is running on a serial machine, then simply looping
>through is faster anyway, for there would be less parallelism being simulated
>to assign the identities.

The above is all you can do in Ada83, but there will be relief in Ada9x.
Ada9x allows for discriminants ob task types, which can be used in the obvious
way to parameterize tasks at creation time.

--
Mark Biggar
mab@wdl.loral.com

Re: Tasking in Ada

[Robert Kitzberger]

kgatlin@galaxy.csc.calpoly.edu (Kang Su Gatlin) writes:

>I have hit a snag with Ada.  I need to create dynamic tasks that know which
>task they are.

If your compiler implements CIFO (the Catalog of Interface Features and
Options for the Ada Runtime Environment) or ExTRA then you can call these
libraries to obtain the task control block for the current task.  Even
if CIFO/ExTRA isn't supported, then your compiler vendor may provide some
implementation-dependent way of getting the current task's TCB. 

>I can't seem to find a way to pass information to tasks efficiently.  I want
>all the tasks to run simultaneously so that the creation and execution of
>the tasks can be done in t(1) time.  

Creation of the tasks will take time linear to n on SISD machines.  On
MISD or MIMD machines, the runtime can activate the tasks in parallel
on multiple processors, achieving activation of n tasks in o(c).  But
on a uniprocessor, even in the case of creating an array of tasks (see
below) the underlying runtime system will activate the tasks
sequentially.  Execution-time complexity of the tasks is another
matter entirely, and outside of the realm of the Ada run-time
environment.  So you see, even if your Ada code appears to
have O(c) complexity, you are a slave to the underlying Ada runtime's
time and space complexity.

Regardless... the classic, portable way to assign task ids and
maintain task counts is to have a 'task manager' assigning ids (pardon
any syntax errors -- I'm just typing this in as I go...)

  type task_id is new natural;

  task id_manager is
     entry new_id( id : out task_id);
     entry number_of_tasks( count : out natural );
     -- to make this an accurate count, you'll want to add 'recycle_id'
     -- or some other such entry to notify the manager of task death
  end id_manager;

  task body id_manager is
     current : task_id := task_id'first;
  begin
     loop
         select
            accept new_id( id : out task_id ) do
                current := current + 1;
                id := current;
            end new_id;
         or
            accept number_of_tasks( count : out natural ) do
                count := natural(current);
            end number_of_tasks;
         or
            terminate;
         end select;
     end loop;
  end id_manager;

Each new task would need to call id_manager.new_id upon startup in
order to determine its identity.  For example:

  task type t is
  end t;

  task body t is
    my_id : task_id;
  begin
    id_manager.new_id( my_id );
    ...
  end t;

  Task_Array : array(1..n) of t;

Note that this will still take time linear to n on uniprocessor
architectures, even if the compiler is smart enough to perform some of
the task initialization at compile-time (e.g. the runtime will loop
through the n task control blocks, allocating stack space, heap space,
register save areas, etc. -- a certain amount can be done in O(c),
but the rest is O(n)).

On a multiprocessor (MISD) architecture, the compiler/runtime could
allocate the tasks to multiple processors and activate in O(c) (minus
some noise for contention on shared memory).

Too bad that tasks can't be generic units -- otherwise you could
parameterize a task with a unique id (as well as address clauses
for interrupt entries, etc...)

Good luck,

	.Bob.

--
Bob Kitzberger                          Internet:   rlk@rational.com
Rational, Grass Valley, CA              CompuServe: 70743,1550

Re: Tasking in Ada

[Raymond Blaak]

mab@dst17.wdl.loral.com (Mark A Biggar) writes:

>The above is all you can do in Ada83, but there will be relief in Ada9x.
>Ada9x allows for discriminants ob task types, which can be used in the obvious
>way to parameterize tasks at creation time.

>--
>Mark Biggar
>mab@wdl.loral.com


How could one use this to tell the task its position in an array? If this can
be done, I would love to know how.

Cheers,
Ray
blaak@csri.toronto.edu

Re: Tasking in Ada

[Wes Groleau x1240 C73-8]

In article <1993Sep15.041622.17841@rat.csc.calpoly.edu> kgatlin@galaxy.csc.calp
oly.edu (Kang Su Gatlin) writes:
>I have hit a snag with Ada.  I need to create dynamic tasks that know which
>task they are.
>
>I can't seem to find a way to pass information to tasks efficiently.  I want
>all the tasks to run simultaneously so that the creation and execution of
>the tasks can be done in t(1) time.  

Someone will undoubtedly post a better way, but here's one.  I have left out
a lot of the trivial stuff that most programmers can figure out in 20 minutes
with a reference manual and an error message.  (If you've ever written an Ada
program you'll do it in one minute with no manual.)  If you decide to use this,
you can use my name if you wish, but I'd prefer nothing else (no e-mail address
,
company name, street address, phone number, etc., please)

Wes Groleau

task body SAMPLE is

   My_ID : ID_TYPE := No_ID;

begin

   accept IDENTIFICATION ( ID : ID_TYPE ) do
      My_ID := ID;
   end IDENTIFICATION;

   -- the following loop is only necessary if you need them all
   -- to start at approximately the same time.  There is no way
   -- to start all at EXACTLY the same time.  I have a way to
   -- get a more accurate start time than this, but it's kludgey.
   while Global_Start_Flag /= Go loop
      delay Some_Small_Amount;
   end loop;

   -- do the task

end SAMPLE;

begin -- main program

  for I in Array_Of_Tasks'RANGE loop
    Array_Of_Tasks ( I ) . IDENTIFICATION ( I );
  end loop;

  Global_Start_Flag := Go;

end;  -- main program

-----------

Re: Tasking in Ada

[Wes Groleau x1240 C73-8]

In article <rlk.748114486@bonnie> rlk@bonnie.Rational.COM (Robert Kitzberger) w
rites:
>Too bad that tasks can't be generic units -- otherwise you could
>parameterize a task with a unique id (as well as address clauses
>for interrupt entries, etc...)

But a generic package CAN contain a task, which could then know what its 
generic parameters are.  The disadvantage (which would also apply if the
task itself was generic) is that you can't have an array of instantiations;
you'd have to call each by its instantiated name.