Re: Teaching Concurrency

[griest@ajpo.sei.cmu.edu (Tom Griest)]

Regarding the postings on teaching Ada tasking:

The important thing to consider is that tasks should be used
for operations which are really likely to be physically concurrent.
(Or in some cases to serialize concurrent access to devices.)
For example, embedded applications frequently have interactions
with real-world events which can happen concurrently.  An
automotive processor which must monitor oxygen content of fuel
combustion while monitoring velocity is a case where two activities
are occurring concurrently and it fits more naturally into a tasking
model than a subprogram that polls to achieve the same effect.

Another case where tasking can be used is to achieve higher performance
by allowing additional processors to work on a single program's problem.
This is only meaningful when you have a system which has more than one
CPU and software that supports the distribution of the load.  In these
cases, the Ada task provides a convenient method for designers to 
specify where it is "reasonable" to divide the work load.  The "reasonable"
decision must be made based on the overhead associated with communication
and scheduling among the cooperating processors.  This is similar to
any project where decisions must be made how divide up tasks among
workers.   LabTek Corp. uses this approach to divide up work to do rocket
trajectory calculations.  Since the calculations are independent between
different rockets, we can divide up the work to get the job done sooner.
Our technique involves using a dynamic array of tasks which is dimensioned
during elaboration based on information provided by an underlying
distributed runtime.  (The system has some fault tolerance and can 
reconfigure itself based on how many processors are available.)

The interesting part is being able to reduce the overhead when only a
few (or one) processor is available.  Obviously having a separate task per
rocket would consume considerable overhead in a case where there was
only 1 available processor and 20 rockets.  Therefore Each "guidance" task has
the ability to accept a work list which is dynamically constrained.
Therefore only one rendezvous is needed if only one processor is
available.  When additional processors are available the work list is
effectively "sliced" up to divide the work among additional "guidance"
tasks.  The tricky part is keeping track of persistent information
and maintaining a consistent work list when multiple CPUs are involved.
What I mean by this is that as rockets are launched and destroyed, the
"guidance" tasks must get the same rockets each time.  This is because
there is a substantial amount of "track history" related to each rocket
used in the calculations to implement the trajectory planner.  Since
the application is distributed across a network, transferring the data
would be additional overhead which would probably be intolerable.
We implemented a rather simple allocation routine to make sure that
once a rocket was assigned to a processor, it remained there.

Unless you want to teach your students to be rocket scientists, this
is probably overkill for a teaching application (although "Missile Command"
used to be a popular video game).  What I recommend is building a
simple game using a graphics display and a mouse (or joystick).  One
task moves a symbol on the screen while another accepts data from the
mouse and plots the cursor on the screen.  A third task might determine
if the symbol is "hit" by the cursor and does something in response to
this event.  You will probably need a forth task to insure mutual exclusion
to the graphics interface.

One problem you might have is getting a low cost Ada system that is capable 
of true tasking (interrupts, etc) and suitable for this application.
Typical DOS-based compilers have problems with concurrency because of
the lack of reentrancy in the BIOS.

If you're interested and need help with the graphics/mouse interface
send me a message.

    Tom Griest
    LabTek Corporation