Researchers often can access various computing resources through
Computational Grids.  However, to actually use these resources is far
from user-friendly because of different architectures, network
interconnects, memory bandwidths, etc.  Users are also faced with the
systems' schedulers that assign CPUs/nodes to jobs.  Schedulers ask
the user to provide an estimate of what amount of resources their
application will demand at runtime.  It is especially difficult to
estimate wall clock times, as the runtime not only depends on the
algorithms and the degree of parallelism used in the application.
Moreover, it is influenced by environmental issues (e.g. the current
system load or network load) that are often difficult to predict and
change in unforeseen ways.  If a job's runtime is underestimated the
scheduler terminates it.  This causes a loss of computation.

There are two common ways out to deal with the runtime estimation
problem.  First, the application can be decomposed into smaller phases
after each of which the application can resume if it was terminated.
However, this increases both programming effort and code complexity.
Second, the runtime can be overestimated extensively (twice what is
estimated or maximal allowed runtime).  By accepting the penalty of
extra long waiting in the cluster queues users "buy" a likely complete
run of their job.  Besides waiting penalties this also causes
reservation holes in the job schedules and hence reduced overall
cluster throughput.

We propose a solution to this problem that does not suffer from the
above mentioned drawbacks and that also makes Grid computing more
transparent.  If an OpenMP application is about to exceed the reserved
time, it is automatically checkpointed and transparently migrated to
either a new local reservation or to a reservation on a different
accessible (possible remote) system. The target system may have a
different architecture or network interconnect.  If the available CPU
count is changed in this migration, the application is automatically
reparallelized and adapts to the new degree of parallelism by adding
to or removing threads from the parallel region that was being
executed when checkpointing and migration commenced.

Our current research focuses on the migration strategy.  We
investigate a centralized bidding system.  Each accessible cluster
runs a small daemon that continuously monitors its load.  In regular
intervals, the daemon reports a bid that indicates what compute power
the cluster can deliver at what time in its future job schedule.
Based on the incoming bids, the runtime system selects the most
suitable cluster as the target for migration, i.e., the one that
delivers the highest computing power at the earliest time.  This
repeats until the application has finished.