Design and Evaluation of a Compiler Algorithm for Prefetching

By Todd C. Mowry, Monica S. Lam and Anoop Gupta

Software-controlled data prefetching is a promising technique for improving the performance of the memory subsystem to match today's high-performance processors. While prefetching is useful in hiding the latency, issuing prefetches incurs an instruction overhead and can increase the load on the memory subsystem. As a result, care must be taken to ensure that such overheads do not exceed the bene ts.

This paper proposes a compiler algorithm to insert prefetch instructions into code that operates on dense matrices. Our algorithm identi es those references that are likely to be cache misses, and issues prefetches only for them. We have implemented our algorithm in the SUIF (Stanford University Intermediate Form) optimizing compiler. By generating fully functional code, we have been able to measure not only the improvements in cache miss rates, but also the overall performance of a simulated system. We show that our algorithm signi cantly improves the execution speed of our benchmark programssome of the programs improve by as much as a factor of two. When compared to an algorithm that indiscriminately prefetches all array accesses, our algorithm can eliminate many of the unnecessary prefetches without any signi cant decrease in the coverage of the cache misses.

Click to Download

Learning compiler design as a research activity

By Francisco Moreno-Seco, Mikel L. Forcada

This paper describes the application of a pedagogical model called "learning as a research activity" [D. Gil-P'erez and J. Carrascosa-Alis, Science Education 78 (1994) 301{315] to teach a two-semester course on compiler design for Computer Engineering students. In the new model, the classical pattern of classroom activity based mainly on one-way knowledge transmission/reception of pre-elaborated concepts is replaced by an active working environment that resembles that of a group of novel researchers under the supervision of an expert. The new model, rooted in the now commonly-accepted constructivist postulates, strives for meaningful acquisition of fundamental concepts through problem solving in close parallelism to their construction through history.

Introduction

This paper describes the implementation of an adapted version of the learning as a research activity model ([1, 2, 3, 4, 5]) to the subject of compiler design at the University of Alacant. The need for trying a new teaching model arose two years ago when we con rmed our realization that the combination of classical lecturing of theory and solved problems in the classroom and open laboratory assignments was insufficient for most students to learn the basic skills needed to successfully tackle new problems in the eld. The learning as a research activity model, which has been successfully applied to the teaching of science in secondary school, was adopted, adapted, and applied to our subject. We have found the new model to be more adequate, more successful, and more consistent with an engineering education style.

The classical model used in most universities in Spain to teach computer engineering subjects such as compiler design could be simpli ed (in its extreme form) as follows. In the classroom, the teacher tries his or her best to explain carefully the theoretical and conceptual aspects of the subject, usually assuming but seldom carefully checking that the students are familiar with a set of basic concepts on which the new material is based.

After that, some more lecturing time is devoted to showing, with as much detail as possible, the teacher's or a book's solution to a handful of selected (intendedly representative) problems or exercises. Laboratory work may be organized either around an open or closed structure, but usually consists either in building one or more programs that implement the algorithms and techniques taught in the classroom to solve a set of selected problems or in writing applications according to some speci ed requirements. In addition, the teacher is available during some scheduled office hours to assist students with their personal work.

Of course, signi cant deviations from this simpli ed model are observed: a few students may interact with the teacher during an explanation, usually to ask him to repeat something, or explain some passage better, or to point out a minor blunder; teachers may ask questions to the students to try to make sure that they are following the explanation; the teacher's solution to a given problem may only be explained after students have had some time to think about it, etc.

Click to Download

Principles of Compiler Design

By Clifford Wolf

In this presentation I will discuss:

• A little introduction to Brainf*ck
• Components of a compiler, overview
• Designing and implementing lexers
• Designing and implementing parsers
• Designing and implementing code generators
• Tools (Lex, bison, iburg, etc.)
• Overview of more complex code generators
• Abstract syntax trees
• Intermediate representations
• Basic block analysis
• Backpatching
• Dynamic programming
• Optimizations
• Design and implementation of the Brainf*ck Compiler
• Implementation of and code generation for stack machines
• Design and implementation of the SPL Project
• Design and implementation of LL(regex) parsers

After this presentation, the auditors ..

• should have a rough idea of how compilers are working.
• should be able to implement parsers for complex conguration files.
• should be able to implement code-generators for stack machines.
• should have a rough idea of code-generation for register machines.

Click to Download