In this project, we are investigating adaptive scheduling and resource
allocation in the domain of dynamic multithreading. Most
existing parallel programming systems are nonadaptive,
where each job is assigned a fixed number of processors.
This strategy may lead to a poor use of available
resources. For example, if the job's parallelism changes
while the job is executing, or if the resources available
in the system change, the job is still forced to run with
the same number of processors as it was allotted when it
started executing. A more attractive model would be an
adaptive model, where processors allotted to a job change
according to the job's parallelism and the system
environment.
Towards this end, we developed two adaptive thread schedulers that provide
provably history-based feedback about the job's
parallelism, without knowing the future of the job. These
thread schedulers complete the job in near-optimal time
while guaranteeing low waste. We analyze these thread
schedulers under stringent adversarial conditions, making
the thread schedulers robust to various system environments
and allocation policies. To analyze the thread schedulers
under this adversarial model, we have developed a new
technique called trim-analysis, which allows the thread
scheduler to perform poorly on a small number of time steps
while guaranteeing good behavior on a vast majority.
Currently, our adaptive multithreading model does not support full
multithreaded programming features --- such as i/o, pipelines,
master-slaves --- and the full environment for adaptive multithreading has
not been developed. We plan to tackle these problems and explore feedback
driven policies for making scheduling and resource allocation decisions in
the adaptive environment. We believe that history-based feedback
mechanisms can be developed and can provide theoretically good and
practically efficient performance.
Moreover, we plan to build an adaptive multithreaded environment called
Fabric to embody these mechanisms and policies. Fabric will be based on
our existing JCilk multithreaded runtime system. JCilk is a portable,
strongly typed, object-oriented, garbage-collected language which
implements a provably good, but nonadaptive, thread scheduler. Fabric will
be used to evaluate various policies and mechanisms emprically and gauge
their practical application.
|