Current term:
Date | Speaker | Title (click for abstract) | Location |
May 25, 2006 | Adam Richard | C*: An Improved C++ | DC 3314 |
June 08, 2006 | Michal Antkiewicz | Framework-Specific Modeling Languages | DC 3314 |
June 22, 2006 | Jun Chen | Uncovering Race Conditions in Concurrent Programs | DC 3314 |
Aug. 10, 2006 at 10:30 am | Abid Malik | Optimal Superblock Instruction Scheduling for Multiple-Issue Processors using Constraint Programming | DC 3314 at 10:30 am |
Seminars are Thursdays at 2:30 pm, unless otherwise indicated.
All are welcome.
Talk announcements are also posted to a public mailing list.
To volunteer to give a talk, contact Ondřej Lhoták. Talks can range from informal to formal, and they can be about any of the following:
The purpose is for us all to see what people are interested in, and motivate discussions.
C* began with the name CFlat which I designed and partially implemented
for my Undergraduate Honours Thesis. Since then, it has become
something of a hobby of mine. The talk consists of describing both the
features that I described in that thesis as well as further directions
the language has taken since then. There is also brief discussion of
the design of the language and its partial implementation, which has
been done both in and to C++. I assume that listeners have a good
understanding of C++.
Framework-Specific Modeling Languages
Michal Antkiewicz
June 08, 2006
In this paper, we propose the concept of Framework-Specific Modeling
Languages (FSMLs). FSMLs are a special category of Domain-Specific
Modeling Languages that are defined on top of an object-oriented
application framework. They are used to express models showing how
framework-provided abstractions are used in framework-based application
code. Such models may be connected with the application code through a
forward and a reverse mapping enabling automated round-trip engineering.
The forward mapping automates the creation of framework-completion code
from a model. The reverse mapping creates a model as an architectural
overview of the application code and helps verifying that the code
respects the rules of the framework. After, positioning FSMLs within
the broader landscape of Domain-Specific Modeling Languages, we present
a proof-of-concept FSML for modeling the interaction of workbench
parts within Eclipse. Finally, we identify a number of challenges,
opportunities, and directions for future research on FSMLs.
Uncovering Race Conditions in Concurrent Programs
Jun Chen
June 22, 2006
Concurrent programs have two or more threads that cooperate in
parallel to carry out a task. Concurrent applications achieve better
speed and reliability than their sequential counterparts. However,
concurrent programs are notoriously hard to debug since they execute
non-deterministically. The interleaving between threads, which affects
the order of reads and writes to shared variables, is controlled
at run-time by the scheduler. If the program does not contain
proper synchronization, some of these orders may generate incorrect
results because of timing-dependent errors called race conditions.
Moreover, given a particular set of input, a race condition may not
appear consistently across multiple runs due to the non-deterministic
interleaving. Consequently, some traditional debugging strategies for
sequential programs, such as inserting print statements, will not be
helpful in debugging concurrent programs containing race conditions.
In this presentation, I will give a survey of existing techniques for
uncovering potential race conditions in concurrent programs. For each
type of approach, I will use some concrete examples to illustrate its
design concepts as well as its strengths and weaknesses.
Optimal Superblock Instruction Scheduling for Multiple-Issue Processors using Constraint Programming
Abid Malik
Aug. 10, 2006
Modern processors have multiple-issue pipelined functional unit, which
can issue more than one instruction per clock cycle. This put great
pressure on the instruction scheduling phase in a compiler to expose
maximum instruction level parallelism. Instruction level parallelism
(ILP) at local level using basic blocks is limited. Compilers increase
ILP by doing instruction scheduling at global level using larger
regions, which are created by combining basic blocks. Commonly used
region is superblock. The global instruction scheduling is NP-complete,
and is done sub-optimally in all compilers using heuristic approaches.
In this work, we present a constraint programming approach to the
global instruction scheduling problem using superblock, that is both
optimal and fast enough to be incorporated into production compilers. We
experimentally evaluated our optimal scheduler on the SPEC2000 integer
and floating point benchmarks. On this benchmark suite, the optimal
scheduler was very robust and scaled to the largest superblocks. Atmost
16 superblocks in the benchmark suite could not be solved optimally
within a reasonable time limit. The scheduler was able to routinely
solve the largest superblocks, including superblocks with up to 2600
instructions. This compares favorably to the recent best work by Shobaki
and Wilken on optimal superblock scheduling using dynamic programming
and enumeration.
Joint Work with Peter Van Beek, Tyrel Russell and Michael Chase