Integrating Tasking and Active Message Style Communication in Gardens

  Clemens Szyperski and Paul Roe         {c.szyperski,p.roe}@qut.edu.au
  Programming Languages and Systems Group
  Queensland University of Technology, Brisbane, Australia


The Gardens Project aim at supporting Adaptive Parallel Computing on NOWs
where we utilize a workstation either for "normal" use or to execute part of
a single parallel application. We intend to efficiently support and
experiment with a variety of paradigms, such as data, master/worker (cf
Piranha) and general task parallelism. We avoid general language bindings and
instead concentrate on a single new language and library support for the
various paradigms. For the obviously very different needs in terms of
policies, we are working on an extensible object-oriented architecture to
support pluggable policy modules. These should allow programmed control over
issues such as task locality and distribution, task coalescing, or other
preferences, eg, kill-and-restart instead of migration. 

Our current emphasis is on providing a general but efficient base layer
supporting message passing, lightweight tasking, and task migration. In
particular, we chose to use an AM style semantics of split phase
communication and direct addressing of receiving handlers. The tasks are
lightweight in that it is non-preemptive and that no protection or isolation
is enforced at run-time - we simultaneously work on language-level support
for this. Task migration is primarily targeted to support release of
workstations; it may also be used for some coarse-grained load balancing. 
Newly created tasks remain in an embryonic state until either the local or a
remote processor until they are required - until then they may be killed of
again at little cost. Tasks are used to combine the latency masking
properties of split-phase computing with support for recursive programming. 

In our non-preemptive tasking model, each processor holds at most one active
task at a time. All others sit in a blocking call or are embryonic. In
particular, calls to request (send) messages or to poll for incoming messages
can be used to switch tasks. With AM's credit scheme, we replace waiting for
credits by setting a task to an "out of credits" state known to the
scheduler. The invariant of at most one active task per processor ensures
that on every call to the communication layer an incoming message could be
delivered to the destination task by calling its handler without introducing
preemptive semantics for the receiving task. 

In principle, preemptive task migration is desirable to swiftly release
workstations. However, to maintain our invariant of at most one active task
per processor at a time, we can either only migrate passive tasks (ie,
blocked or embryonic ones), or migrate an active task to a workstation that
is currently entirely passive. We therefore only support non-preemptive
migration in the base layer; migration takes place at the next invocation of
a potentially blocking call. A higher layer may actually restrict
communication semantics such that it is known that asynchronous activities
are strictly bounded. Under such conditions, preemptive migration outside of
these bounded regions could be supported. 

There is a set of related open problems that could be discussed at the
workshop. In particular, there is a need to control the number of produced
tasks and it may be necessary to ensure sufficiently frequent polls. Also, it
is not necessary to switch tasks on every send or poll and switches may be
directed by most recent message exchange (eg, hand-off scheduling); the
resulting scheduling problem seems difficult. To get some handle on the
number of tasks, we consider feedback to the program to switch between
sequential and parallel mode. Polls could be inserted by a compiler given a
sufficiently precise language.