System Architecture: An Ordinary Engineering Discipline

Book Preface

This text contains the lecture notes of a class we teach in Saarbr¨ucken to first-yearstudents within a single semester. The purpose of the class is simple: to exhibit constructions of

• a simple MIPS processor
• a simple compiler for a C dialect
• a small operating system kernel and to give detailed explanations for why they work.

We are able to cover all this material within a single lecture course, because we treat computer science as an engineering discipline like any other: for any topic there is appropriate math which is intuitive and adequate to deal with it, both for specifications and for explanations for why constructions work. High school mathematics happens to suffice to deal with all subjects in this text.

As a warm-up exercise we study in Chap. 2 how to prove some very basic properties of decimal addition. Chapter 3 contains reference material about basic mathematical concepts which are used throughout the book. Elementary properties of binary numbers, two’s complement numbers, and Boolean algebra are treated in Chap. 4. In particular the correctness of algorithms for binary addition and subtraction is shown. Of course we also include a proof of the fact that every switching function can be computed by a Boolean formula.

A digital hardware model consisting of circuits and registers is introduced in Chap. 5 and some simple circuits are constructed. Chapter 6 contains various constructions of random access memory (RAM) that are needed later in the text. Several adder constructions (including conditional-sum adders and carry-look-ahead adders), an arithmetic logic unit (ALU), and a simple shifter are covered in Chap. 7. In Chap. 8 a subset of the MIPS instruction set architecture (ISA) is introduced and a simple sequential (i.e., not pipelined) MIPS processor is constructed. Although the correctness proof of the basic processor is straightforward, it exhibits an important concept: processor hardware usually does not interpret all ISA programs; only programs which satisfy certain software conditions are correctly executed. In our case we require so-called ‘alignment’ and the absence of writes into the ROM (read-only memory) region. Because we have a correctness proof we know that this list of conditions is exhaustive for our simple processor. In the text we contrast this with the situation for commercial multi-core processors and arrive at slightly worrisome conclusions.