Computing: The Australasian Theory Symposium

Computing: The Australasian Theory Symposium (CATS) in 2007 will be held in Ballarat from 30th January to 2nd February 2007. CATS is the premier theoretical computer science conference in Australasia. It is held annually as part of Australasian Computer Science Week (ACSW) which comprises many other conferences and is overseen by the Computer Research and Education Association (CORE - previously CSA).

CATS 2007 will be the thirteenth time that CATS has been held. The symposium will consist of invited talks and formal paper presentations. All papers will be fully refereed with proceedings published by CRPIT .

Accepted papers

are now listed on the Programme page.

Our invited speaker is
Professor Jens Palsberg , UCLA

on the topic

Register Allocation via Coloring of Chordal Graphs

Abstract

A revolution in register allocation is going on right now: compared to the state of the art, the new register allocators are much simpler and generate code of equivalent quality. In 2005, Bouchez, Brisk et al., and Hack independently discovered that if a program is in static-single assignment (SSA) form, then a core register allocation problem can be solved in polynomial time. Many compilers and virtual machines represent programs in SSA form internally, including gcc version 4.0, Sun Microsystem's Java HotSpot Virtual Machine, and IBM's Java virtual machine Jikes RVM. A compiler can translate any program to SSA form in polynomial time, and amazingly thereby change the register allocation problem from NP-complete to polynomial time; the reason is that the transformation may change the need for registers. Luckily, the program in SSA form needs a number of registers which is the same or smaller than that of the original program. We have a win-win situation here: translating to SSA form changes an NP-complete problem to a simple polynomial-time problem and it decreases the need for registers.

The key insight is that a program in SSA form has a chordal interference graph. A greedy algorithm can optimally color a chordal graph in linear time in the number of edges. Completing the picture, Hack et al. have presented a new SSA-elimination algorithm that does not demand extra registers. The combined result is a simple, optimal, polynomial-time algorithm for a core register allocation problem. The new SSA-elimination algorithm of Hack et al. is essential because classical SSA elimination leads to an NP-complete core register allocation problem, as shown by Palsberg and Pereira. Register allocation with spilling for SSA form remains NP-complete.

We can get most of the advantages of SSA form without actually transforming to SSA form: a vast majority of realistic benchmark programs have chordal interference graphs. For example, 95% of the methods in the Java 1.5 library have chordal interference graphs when compiled with the JoeQ compiler. Pereira and Palsberg have shown how to add simple heuristics for spilling and coalescing to the greedy coloring algorithm. The result is a simple and efficient register allocation algorithm which compares well with the iterated register coalescing algorithm of George and Appel.

Jens Palsberg is a Professor and Vice Chair of Computer Science at UCLA. His research interests span the areas of compilers, embedded systems, programming languages, software engineering, and information security. He has authored over 80 technical papers, co-authored the book Object-Oriented Type Systems, and co-authored the 2002 revision of Appel's textbook on Modern Compiler Implementation in Java. He is the recipient of National Science Foundation CAREER and ITR awards, a Purdue University Faculty Scholar award, an IBM Faculty Award, and an Okawa Foundation research award. Dr. Palsberg's research has also been supported by DARPA, Intel, and British Telecom. Dr. Palsberg is an associate editor of ACM Transactions of Programming Languages and Systems, a member of the editorial board of Information and Computation, and a former member of the editorial board of IEEE Transactions on Software Engineering. He is serving as the secretary/treasurer of ACM SIGBED, Special Interest Group on Embedded Systems, and he has served as the general chair of the ACM Symposium on Principles of Programming Languages.

Call for papers

Papers are invited on all aspects of Theoretical Computer Science. Some representative, but not exclusive, topics include the following:

logic and type systems
semantics of programming languages
formal program specification and transformation
concurrent, parallel and distributed systems
algorithms and data structures
automata theory and formal languages
computational complexity
applications of discrete mathematics and optimisation

Full papers for CATS 2007 should be submitted electronically no later than Friday August 11 2006. Submissions must be original work, not published or submitted elsewhere. All submissions will be refereed. Accepted papers will appear in the published proceedings.

Important Dates

Submission of abstracts Thursday July 27 2006
Submission of full papers Friday August 11 2006
Notification of authors Tuesday September 26 2006
Final version due Friday October 20 2006
Author registration Friday October 20 2006
ACSW begins 30th January 2007
ACSW ends ends 2nd February 2007

Program Chairs

Barry Jay
University of Technology, Sydney
Email: cbj@it.uts.edu.au

Joachim Gudmundsson
National ICT Australia
Email: Joachim.Gudmundsson@nicta.com.au