Adaptive Scheduling of Parallel Jobs
|
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. 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. We are working on developing theoretically
sound and practically efficient schedulers in this model.
|
| People to Contact:
Kunal Agrawal
Siddhartha Sen |
| Webpage:
More details |
|
Cache-Oblivious Search Trees
|
We are investigating cache-oblivious search trees. On disk-systems they seem to outperform traditional B-Trees.
|
| People to Contact:
Bradley C. Kuszmaul
Jeremy T. Fineman |
| Webpage:
More details |
|
Cilk Implementation
|
Cilk
(pronounced ''silk'') is a C-based, multithreaded language
for parallel programming being developed at the
MIT Computer Science and Artificial
Intelligence Laboratory (CSAIL).
Programming in Cilk is simple because protocols for job
coordination and load balancing are handled automatically
by Cilk's provably efficient runtime system. Cilk is
particuarly effective for asynchronous parallel applications,
such as sparse numerical algorithms, N-body simulations,
or chess programs. The current Cilk release is
Cilk-5.4.5.
|
| People to Contact:
Bradley C. Kuszmaul
Charles E. Leiserson |
Webpage:
To see the new webpage, check
this page.
To see the old archive, check
this page.
|
|
JCilk -- Java based Cilk
|
We are currently developing JCilk,
a Java-based multithreaded programming language. JCilk
extends the Java language to provide call-return semantics
for multithreading, much as Cilk does for C. Java's
built-in thread model does not support the passing of
exceptions or return values from one thread back to the
"parent" thread that created it. JCilk imports Cilk's
fork-join primitives spawn and
sync into Java to provide
procedure-call semantics for concurrent subcomputations.
JCilk integrates exception handling with multithreading by
defining semantics consistent with the existing semantics
of Java's try and catch constructs, but which handle
concurrency in spawned methods.
|
| People to Contact:
I-Ting Angelina Lee |
| Webpage:
More details |
|
LecTix: A Lecture-Multimedia Player
|
We have designed and implemented LecTix, a
lecture-multimedia player that is usable, widely
available, and extensible.
|
| People to Contact:
Tim Olsen |
| Webpage:
More details |
|
Race Detection
|
Multithreaded programs, though intended to be deterministic,
may exhibit nondeterministic behavior due to bugs called
determinacy races. These bugs
are typically difficult to detect using normal debugging
techniques such as breakpoints or print statements, as
these bugs are dependent on a specific scheduling and
timing.
We have a race detection tool for the Cilk programming
language called the Nondeterminator. This tool augments the
source code to maintain series-parallel relationships between
threads and keep access histories to memory locations. We
currently have serial implementations of the
Nondeterminator. We are working on both more efficient
serial implementations and a multiprocessor implementation.
Many of the techniques we use for the Nondeterminator can be
applied to other multithreaded programming languages.
|
| People to Contact:
Jeremy T. Fineman |
| Webpage:
More details |
|
Transactional Cilk
|
We have modified the Cilk language to allow users to
specify and execute transactions atomically. We plan to use
this system to investigate the issues involved when
programming with transactions and when compiling for hardware
transactional memory.
|
| People to Contact:
Jim Sukha |
| Webpage:
More details |
|
Unbounded Transactional Memory
|
Unbounded Transactional Memory
is a hardware transactional memory scheme that ensures
atomicity of a defined group of memory operations.
Compared to lock-based approaches, UTM simplifies the
programming interface and avoids common execution hazards
such as deadlock and convoying. Unlike previous hardware
transactional models, this approach does not limit
transaction size or require a special transactional cache.
|
| People to Contact:
Bradley C. Kuszmaul
Charles E. Leiserson |
| Webpage:
More details |
