COMPUTER SCIENCE RESEARCH MELISSES: Liquid Services for Scalable Multithreaded and Multicore Execution on Emerging Supercomputers Page: 1 of 6
This report is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to Digital Library by the UNT Libraries Government Documents Department.
The following text was automatically extracted from the image on this page using optical character recognition software:
Final Report for DOE ECPI Grant ER25751
Dimitrios S. Nikolopoulos
Department of Computer Science, Virginia Tech
In the following sections, we summarize the contributions made through support from this DOE ECPI
award to research and training in advanced computing systems.
1 Dynamic scheduling of layered parallelism on emerging multi-core pro-
cessors and many-core clusters
We have developed several schedulers for dynamic multi-grain parallelization on the Cell Broadband En-
gine. The Cell processor presents a new paradigm for parallel computing on multicore platforms, by com-
bining conventional processor cores with customized accelerators and by offering an explicitly managed
memory hierarchy to programmers, for tighter control of locality and performance. Parallel computation on
the Cell is accomplished by off-loading compute-intensive and data-intensive code from the conventional
cores to the vector SIMD accelerators. Heterogeneous multi-core architectures such as the Cell represent
a design point in computer architecture which holds greater promise for sustaining high performance and
power-efficiency than conventional, homogeneous multi-core architectures. Cell is also the processor of
choice for Roadrunner, a Petaflop-capable supercomputer currently in the development phase by IBM. Due
to these reasons, we believe that the research conducted on Cell with support from the DOE ECPI award is
timely, relevant and in line with DOE missions.
The first of the novel schedulers developed in this activity, named MGPS-SLED (for Multi-grain Par-
allelism Scheduling using Slack Minimizing Event-Drive execution), exploits effectively thread-level and
data-level (SIMD) parallelism at runtime, without prior knowledge of the application or input from the pro-
grammer. MGPS-SLED follows an event-driven execution model for scheduling tasks and data parallelism
of varying granularity, on the synergistic processing elements (SPE) of the Cell. MGPS-SLED provides a
novel mechanism for deciding between task-level, loop-level and data-level parallelization on the fly, based
on runtime workload characterization and observable utilization metrics on the SPEs. As part of the MGPS-
SLED effort, we have ported the MELISSES hardware monitor on the Cell PPE and SPE -the conventional
power processing element and the synergistic processing elements of the processor respectively-, to collect
continuous data on SPE and PPE utilization and drive the multi-grain decomposition and scheduling pro-
cesses. More specifically, MELISSES enabled us to collect a historical profile of task execution on the SPE,
which in conjunction with program phase analysis, enabled MGPS-SLED to adaptively select the layers and
degrees of parallelism to activate in any phase of the program. We emphasize the major contribution of
MGPS-SLED, namely phase-aware optimization of the scheduling process, which would have been impos-
sible without leveraging the MELISSES performance monitoring framework. Phase-aware program control
in MELISSES has enabled unprecedented performance and power optimizations in parallel programs. We
view this result as one of the major contributions of this effort.
MGPS-SLED was initially tested with RAxML, a computational phylogeny toolkit that uses algorithms
based on the Maximum Likelihood (ML) method and rapid bootstrapping. The results of this work originally
appeared in a publication in the 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel
Here’s what’s next.
This report can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Report.
Nikolopoulos, Dimitrios S. COMPUTER SCIENCE RESEARCH MELISSES: Liquid Services for Scalable Multithreaded and Multicore Execution on Emerging Supercomputers, report, August 10, 2008; United States. (digital.library.unt.edu/ark:/67531/metadc933258/m1/1/: accessed December 15, 2018), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT Libraries Government Documents Department.