Waterloo Programming Languages Seminars

Previous terms: W06

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*: An Improved C++

Adam Richard
May 25, 2006
In this seminar, I present C*, a language in progress which makes various improvements to C++. C* is not backwards compatible with C++ (or C for that matter), but otherwise is quite similar in philosophy and style. The goal is to make the best language possible, removing redundant and/or unnecessary features, and to eventually write a source transformation to convert C++ to C* so that old code can still be used. The result is a language that is more powerful, easier to program in, and more type-safe than C++.

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