Waterloo Programming Languages Seminars

Also of interest:

Gerald Jay Sussman, May 25 and 26, 2010

Date Title Location
Tue. May 25, 2010 at 5:00 pm Why Programming is a Good Medium for Expressing Poorly Understood and Sloppily Formulated Ideas MC 2066
Wed. May 26, 2010 at 5:00 pm The Art of the Propagator MC 5158

Computer Science Club talks

Date Speaker Title Location
Tue. June 22, 2010 at 4:30 pm Prabhakar Ragde Compiling To Combinators MC 2066
Tue. July 6, 2010 at 4:30 pm Nomair Naeem Dataflow Analysis MC 2054

Previous terms: F08 S08 W08 F07 W07 F06 S06 W06

Current term:

Date Speaker Title (click for abstract) Location
Tue. May 18, 2010 at 1:30 pm Mirza Omer Beg A Graph Theoretic Approach to Cache-Conscious Placement of Data for Direct Mapped Caches DC 1331
Fri. May 21, 2010 at 1:30 pm Jonathan Rodriguez A Concurrent IFDS Dataflow Analysis Algorithm Using Actors DC 2314
Tue. May 25, 2010 at 1:30 pm Roy Krischer Safe Asynchronous Exception Propagation DC 2314
Thu. May 27, 2010 at 1:30 pm Pavel Parízek Verification of Java programs and components using Java Pathfinder DC 1331
Thu. June 3, 2010 at 10:00 am Peter F. Sweeney The Poor State of Experimental Evaluation of Software and Systems in Computer Science DC 1304
Thu. June 17, 2010 at 1:30 pm Pavel Parízek Java Pathfinder: General Overview and Current State of Affairs DC 1331

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.

Abstracts

A Graph Theoretic Approach to Cache-Conscious Placement of Data for Direct Mapped Caches

 Mirza Omer Beg
May 18, 2010
Caches were designed to amortize the cost of memory accesses by moving copies of frequently accessed data closer to the processor. Over the years increasing gap between processor speed and memory access latency has made the cache a bottleneck for program performance. Enhancing cache performance has been instrumental in speeding up programs. For this reason several hardware and software techniques have been proposed by researchers to optimize the cache for minimizing the number of misses. Among these are compile-time data placement techniques in memory which improve cache performance. For the purpose of this work, we concern ourselves with the problem of laying out data in memory given the sequence of accesses on a finite set of data objects such that cache-misses are minimized. The problem has been shown to be very hard to solve optimally even if the sequence of data accesses is known at compile time. In this paper we show that given a direct-mapped cache, its size, and the data access sequence, it is possible to identify the instances where there are no conflict misses. We describe an algorithm which can assign the data to cache for minimal number of misses if there exists a way in which conflict misses can be avoided altogether. We also describe the implementation of a heuristic for assigning data to cache for instances where the size of the cache forces conflict misses. Experiments show that our technique results in a 30% reduction in the number of cache misses compared to the original assignment.

A Concurrent IFDS Dataflow Analysis Algorithm Using Actors

 Jonathan Rodriguez
May 21, 2010
There has recently been a resurgence in interest in techniques for effective programming of multi-core computers. General-purpose concurrent programming is considered by many to be very difficult, which severely limits the number of applications that currently benefit from multi-core computers. There already exist many concurrent solutions for regular applications, which include many forms of simulation and numeric code. For irregular applications, which operate on dynamic and pointer- and graph-based structures, efficient concurrent solutions have so far remained elusive. Dataflow analysis applications, which are often found in compilers and program analysis tools, have received particularly little attention with regard to execution on multi-core machines. Operating on the theory that the Actor model, which structures computations as systems of asynchronously-communicating entities, is a more appropriate method for representing irregular algorithms than the shared-memory model, this work presents a concurrent Actor-based formulation of the IFDS dataflow analysis algorithm. The implementation of this algorithm is done using the Scala language and its Actors library. Significant speedup on multi-core machines is demonstrated without using any optimistic execution. This work assists Actor research by showing how the Actor model can be practically applied to a problem that is considered difficult using other approaches. This work assists static analysis research by showing how a dataflow analysis algorithm can effectively make use of multi-core machines, allowing the possibility of faster and more precise analyses.

Safe Asynchronous Exception Propagation

 Roy Krischer
May 25, 2010
Asynchronous exception handling introduces non-determinism into a program's control flow. Restricting asynchrony to certain well-defined points in combination with asynchronous propagation control can re-establish the determinism required to verify a program's correctness. Unfortunately, this approach introduces a delay between delivery of an asynchronous exception and its propagation. It also disturbs a programmer's intuition about asynchronous propagation in the program and requires the use of programming idioms to avoid errors.

This talk examines general concepts related to asynchrony and how asynchronous exception handling affects control flow. It demonstrates how unrestricted asynchrony can be safely employed under certain circumstances in order to reduce the delay between delivery and propagation, and to allow for a more intuitive use of asynchronous propagation control. The necessary extension to the semantics of the language uC++ are documented, as well the efforts required and obstacles encountered when implementing this feature.

Verification of Java programs and components using Java Pathfinder

Pavel Parízek
May 27, 2010
Pavel Parizek is a new post-doctoral fellow at the School of Computer Science, University of Waterloo. He is working with professor Ondrej Lhotak. Pavel received his PhD degree at the Charles University in Prague, Czech Republic, in 2008.

This talk presents an overview of his previous research. Topics will include: 1) modular verification of software systems built from Java components using Java Pathfinder (JPF) and behavior protocols, 2) techniques for efficient detection of concurrency errors in Java programs with JPF, and 3) model checking real-time Java programs with thread scheduling and a model of time based on thread periods.

The Poor State of Experimental Evaluation of Software and Systems in Computer Science

Peter F. Sweeney
June 3, 2010
As hardware and software continues to evolve into increasingly complex systems, our ability to understand their behavior and measure their performance is increasingly difficult. Nevertheless, many areas of computer science use experiments to identify performance bottlenecks and to evaluate innovations. In the last few years, researchers have identified some disturbing flaws in the way that experiments are performed in computer science.

This talk presents two of these flaws. First, changing a seemingly innocuous aspect of an experimental setup can result in a systems researcher drawing wrong conclusions from an experiment. What appears to be an innocuous aspect in the experimental setup may in fact introduce a significant bias in an evaluation of native (C and C++) applications.

Second, performance analysts profile their programs to find methods that are worth optimizing: the "hot" methods; however, four commonly used Java profilers (xprof , hprof , jprofile, and yourkit) often disagree on the identity of the hot methods. This talk demonstrates that these profilers all violate a fundamental requirement for sampling based profilers: to be correct, a sampling-based profiler must collect samples randomly.

Unfortunately, the flaws discussed above are not the full extent of the problem. If computer science is to be taken seriously as a scientific discipline, we as a community need to do a better job designing experiments and evaluating their results.

Peter F. Sweeney is a Research Staff Member in the Program Technology Department at the IBM T.J. Watson Research Center in Hawthorne, New York. His research interests are performance analysis and tuning of computer systems with a focus on automation. Peter received a Master degree in Computer Science from Columbia University SEAS and he joined IBM research in 1985. Peter is a senior member of ACM.

Java Pathfinder: General Overview and Current State of Affairs

Pavel Parízek
June 17, 2010
This talk will introduce Java Pathfinder, a platform for analysis and verification of Java programs. It will describe the tool both from the user and developer perspective, covering especially the following topics:

1) Supported properties, algorithms, and optimizations of state space traversal;

2) Modular architecture of JPF core and basic principles of internal functioning;

3) Extension points and JPF API, configuration options;

4) Publicly available extensions (symbolic execution, GUI framework, RTSJ programs, and many others);

5) Development model, current projects, and selected applications.

Presentation slides