Virtual Machines for Object Oriented Languages

Q1+Q2 2008, 10 ECTS

This course focuses on how to design and implement virtual machines for object oriented languages. First part of the course discusses techniques and designs behind some of today's high performance virtual machines. Executions model, adaptive code generation, garbage collection, threading, and sand boxing are all subjects that will be covered in this part. The second part of the course is project based; participants are expected to enhance an existing virtual machine or implement a new one. A virtual machine is introduced as a testing platform for the project work. The result is a project report that describes the implementation and any experiences.

Objectives

After this course the participants should be able to:

Describe the challenges of implementing a virtual machine for a language without classes
Explain 'inline caching' and other techniques for dynamic dispatching
Explain techniques for optimization and deoptimization for supporting debugging
Evaluate the pros and cons of the various types of JIT compilation
Evaluate the pros and cons of various garbage collection algorithms
Relate and apply this knowledge to construct solutions to performance problems in virtual machines

Lecturers

Lars Bak, Kasper Lund, and other members of the Google Aarhus team.

(Lars is a leading expert in implementation of virtual machines. He led the development of the Sun Hotspot virtual machine for Java and is now tech lead manager for Google Aarhus.)

Groups

You should form groups of 2-3 persons for doing the handins in Q1 and the project in Q2. When you have formed a group, please send an email to Mathias stating the names and student IDs of the groups members.

DAIMI contact person: Anders Møller <amoeller@cs.au.dk>
Teaching assistant: Mathias Schwarz <schwarz@cs.au.dk>

Preliminary plan for first part of the course

Lectures are Thursdays 11-14 in IT Huset, Lille Aud.

Day	Topic
week 35 28. Aug.	Motivation and presentation of a virtual machine Slides from the lecture: 1 2
week 36 4. Sep.	Byte codes and interpreters Assignment 1 due September 2nd Threaded Code, James R. Bell, Comm. of ACM, 1973 The Structure and Performance of Efficient Interpreters, M. Anton Ertl and David Gregg, 2003 The Smalltalk-80 System, BYTE magazine Slides from the lecture: 1
week 37 11. Sep.	Automatic memory management Assignment 2 due September 9th An Efficient Implementation of SELF, a Dynamically-Typed Object-Oriented Language Based on Prototypes, Craig Chambers, David Ungar, and Elgin Lee, 1991 Uniprocessor Garbage Collection Techniques, Paul R. Wilson Slides from the lecture: 1 2
week 38 18. Sep.	JavaScript Dynamic compilation Assignment 3 due September 16th A Survey of Adaptive Optimization in Virtual Machines, Matthew Arnold, Stephen J. Find, David Grove, Michael Hind, and Peter F. Sweeney, IEEE. Making the Compilation "Pipeline" Explicit: Dynamic Compilation Using Trace Tree Specialization, Andreas Gal, Michael Bebenita, Mason Chong, and Michael Franz. Prototype-based programming on Wikipedia Slides from the lecture: 1 2
week 39 25. Sep.	Type feedback and aggressive function inlining C++ pointer tutorial Slides from the lecture: 1 2
week 40 2. Oct.	Threading and locking Assignment 4 due October 2nd Slides from the lecture: 1
week 41 9. Oct.	Programming tools and conclusion Description of example projects and plan for the second quarter Assignment 5 due October 7th gprof: a Call Graph Execution Profiler, Susan L. Graham Peter B. Kessler Marshall K McKusick Debugging Optimized Code with Dynamic Deoptimization , Urs Hölzle, Craig Chambers, and David Ungar Slides from the lecture: 1 2

Papers marked with are required reading. The others are recommended but not required. Some of the papers may have restricted access; use your DAIMI username/password.

Second part of the course

The second quarter will consist of project work, involving, for example, Google's V8 virtual machine for JavaScript. Each Thursday at 11 AM some people from Google will be available to discuss the project. There will also be some lectures when announced here. Finally near the end of the quarter each group will present their work and conclusions to everybody else. This is the tentive plan:

Day	Topic
week 44 30. Oct.
week 45 6. Nov.	Assignment 6 due November 4th
week 46 13. Nov.	Live Migration of Virtual Machines Guest lecturer: Jacob Gorm Hansen Slides from the lecture: 1
week 47 20. Nov.
week 48 27. Nov.
week 49 4. Dec.
week 50 11. Dec.	Project presentations
Week 51 18. Dec.	December 17th 23:59: Deadline for handing in your code and your report. No projects will be accepted after this deadline. Project presentations

Exam

Exam Schedule

The exam will consist of two parts: 1) the project report (written by each group) and 2) an oral exam (individual). Both parts must be passed.

The oral exam will be January 12, 14, and 16 in Shannon-156 with 20 minutes per person, with a question for each of the five topics mentioned above under 'Objectives' and some discussion about the group project.

The oral exam will include the material marked as 'Required Reading' above and the project report.

VM