|
Home
Chasqui
Seminar
meets Fridays, 3:30pm board room SENSQ 6329 (Spring 2005)
Group meeting spring 2005: Tuesdays 2:30 - 3:30pm (tentative)
TBD
|
|
The Chasqui Research Agenda
In the Chasqui project we investigate novel approaches to program
optimization for modern computer architectures that are based on a
combination of traditional static program analysis and dynamic
information obtained via run-time profiling.
Examples of such optimization systems include just-in-time compilers
for
Java, run-time partial-evaluation based dynamic compilers
such as
DyC .
The latter systems, for example, combine information about run-time
semi-invariance of values to derive profitable run-time
specializations of code that executes more rapidly than the original
un-specialized codes.
In the Chasqui project, we attempt to push this idea to
another level
by exploring program properties beyond value-invariance that can be
exploited for optimization. Since memory-hierarchy based optimizations
(e.g., redundant load removal) are going to be increasingly important
based on the widening gap between processor and memory performance,
one of our curren projects focuses on optimizations based on
non-aliasing. Initial
results indicate that this requires sophisticated compiler support
since approaches based on programmer assistance fall short. A technical
report with this result is available
here
(Pitt CS internal).
Acknowledgments: Special thanks to Satoko Iizuka , a
marvelous Japanese artist who graciously supplied us with the
beautiful logo. Check out the wonderful art on his web site and, when
in Tokyo, in person.
Specific Research Projects and Opportunities to Get Involved
in Research
(e.g., via CS2002 or independent study)
In all of these projects, there are many interesting research questions
and projects of various sizes and difficulty. Please talk to us to find
out more and get involved!
H-SPOT: Hardware-assisted Speculative Program Optimization
(Joint with Professor Babak Falsafi, CMU)
A major problem
facing optimizing compilers today is the increasing ineffectiveness of
traditional program optimization techniques.
Programs are increasingly constructed from components, which are
dynamically selected to adapt systems to changes in their
environments,
for instance, by using software that is distributed on demand in portable
formats such as Java bytecode. To support this dynamism
programming languages used to build such systems use mechanisms like
dynamic dispatch and dynamic linking of
libraries.
This dynamism poses numerous challenges to traditional optimizing
compilers. In particular, it forces the compiler to make
progressively
more conservative assumptions about possible
program
behavior. Unfortunately, such assumptions will frequently
prevent
program optimizations even though they would be safe vis-a-vis actual program behavior.
To
overcome these limitations, this project develops a framework for hardware-assisted speculative program
optimization (H-SPOT). H-SPOT
optimizes programs aggressively based on actually observed
program properties by speculatively performing optimizations that
are profitable but cannot be guaranteed to be safe at static compile
time. The project develops a transactional processor model that provides
architectural support to ensure the correctness of optimizations at run
time.
Collaborators in this project
Scout Compilation
In this research,
we develop a novel approach to program optimization based on dynamic
analysis at its core. To achieve
this goal, we are designing and implementing a compilation framework
that combines dynamic analysis with traditional
static program analysis to enable optimizations that are frequently
suppressed because of the imprecision of traditional static analysis.
We call this novel program optimizationapproach scout compilation because simple code fragments
(called scouts) are
embedded in compiled code to perform a dynamic program analysis. The
information collected by these scouts then enables program optimization
in situations where traditional static program analysis would be
ineffective. By developing the scout compilation framework, we strive
to work out the following significant research questions:
- what are the crucial program transformations that are
necessary for high performance in novel computing paradigms, such as
grid computing;
- how can classical program optimizations be augmented with
dynamic analysis to enable aggressive optimization even in contexts
where it woul normally be suppressed;
- what mechanisms are required to efficiently detect the
run-time properties used in dynamic analysis based optimization and how
can they be verified quickly during optimized program execution;
- what is the impact of specific computer architecture
features on the run-time cost of program optimization based on dynamic
analysis and what possible features would be useful to decrease the
run-time costs;
- what are the possible synergies arising from performing
both dynamic program analysis and dynamic compilation and what are the
application characteristics that favor one over the other.
Achieving these objectives will change the way compilers are structured
and enable the aggressive optimization of programs that are currently
difficult to optimize because of unpredictable run-time behavior.
By developing techniques for the efficient collection and
exploitation of dynamic information, this research will also have an
impact beyond compilers and program optimization: the whole emerging
field of dynamic analysis for software tools and software error
detection and testing will benefit from the techniques developed in
this research. By developing an extensible and well-documented scout
compilation infrastructure that will be distributed to the research
community, other researchers will be able to develop their own dynamic
analyses and study the interaction with other parts of the
computational infrastructure, including, but not limited to, novel
computer architectures.
Collaborators in this project
Evaluation of Data and Control Speculation in Itanium 2
Compilation
Intel's Itanium
processor already provides some rudimentary hardware support for
speculative program optimization in the form of control and data
speculation. For instance, it provides a hardware structure named ALAT
(Advanced Load Address Table), a fully-associative table that stores
the addresses of special advanced load instructions. When a store
operation to an address in the table occurs, the entry for the load is
cleared. By adidtionally providing a checked load instruction, the
compiler can speculatively promote values from memory to registers
despite possible memolry aliasing. The use of the register is then
preceded by a special checked load instruction, which will only reload
the value to the register if the contents of the data at the load
address has ben modified since the advanced load (in this case the
address will no longer be in the ALAT table), otherweise the check load
insturctions turns into a NOP. Since the ALAT is relatively
small, we are interested to find out how much benefit it can provide in
practice. Is oversubscription of the table frequence (capacity misses)?
How much speculation do actual compilers perform with the ALAT
currently?
How important is control speculation (hositing loads across control
dependences, eg., conditional branches) and what are its interactions
with data speculation?
Collaborators in this project
Transactional Computer Architecture (Joint with professors
Falsafi and Hoe from CMU)
In this project we
develop the Transactional Computer Architecture (TCA) where fine and
coarse-grain transactions i.e., atomic code sequences whose effects are
reversible are supported as first-class objects in at the ISA
level. Modern superscalar out-of-order processors already
internalize many key elements of fine-grain transactions for the
purpose of precise exception and branch misprediction rollback. In
these instances and in general in TCA fine-grain transactions enable
large performance gains by making it possible to speculate on
profitable optimizations that has a small but non-zero risk of failing
dynamically. Further elaboration of microarchitectural-level
fine-grain transactions to automatically extract parallelism has
reached a point of diminishing returns in terms of performance gain vs.
complexity. In this project, we explore the possibility of exposing the
general notion of transactions at the ISA level such that
application-level software is able to leverage domain-specific
speculation opportunities in the developed transactional
computation
paradigm.
In particular, we are working on the following areas:
- Low-overhead
Checkpointing: TCA provides low-overhead hardware checkpointing
mechanisms to support transactions for a spectrum of sizes ranging from
hundreds to tens of thousands instructions. The efficiency of
existing fine-grain checkpointing mechanisms in superscalar
out-of-order processors is limited to transactions of no more than a
few hundred instructions. The large overhead of existing coarse-grain
checkpointing solutions limits their range applicability in TCA.
- Mechanisms to Trigger Rollback: We design mechanisms to
automatically abort a transaction when the monitoring hardware detects
an application-specific transaction assumption has been violated. These
user-definable trigger conditions depend on the application for which
TCA is used. For instance, pointer aliasing requires that addresses
referenced by a processor to be compared against each other, whereas
race detection in a multiprocessor/multithreaded program requires
addresses to be compared across processors.
- TCA Instruction Set Architecture: To allow software to
exploit the transactional execution semantics supported by the
hardware, a TCA ISA exports an interface to: (1) start and end a
transaction driving the hardware to checkpoint and commit machine
state, and (2) to specify conditions that abort a transaction and
trigger a rollback.
Collaborators in this project
|
