|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
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
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
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