Preface

The computer system engineering requires a unified view of hardware and software, from the level of data path to application software. Understanding the relationship throughout all levels is an essential knowledge to deal with complex computer systems today.

Most students in computer science or computer engineering department must face a rapid change in technologies. It is no wonder they usually feel bewildered from menageries of subjects that are driven by the most up-to-date technologies. Teachers also face the same dilemma, if we teach only the fundamentals students will not be able to practice. The tools change too fast. There are too many subjects to teach and there is not enough time to learn. Throughout my years of teaching, there is a swing from giving too much practical projects to not giving any practical projects. Parnas, a famous professor in computer science who invented the term “module”, once lamented that we were giving out too many useless projects to our students. I am also a victim of these “fashions”. I am afraid that my students will not know the latest software tools. I am also afraid that my students do not know enough fundamentals. The fact is both the number of tools and fundamentals always increase. Both our students and us, teachers, are facing the impossible task.

Computer science is a young science. The first electronic computer was invented in the 1950 era. Computer engineering is not yet a mature engineering discipline. The microelectronics era has just begun in 1965. I do believe that the present state of the art in computing, the technologies that are in used nowadays, have just scratched the surface of possibilities. There are so many wonderful inventions lying in the future. Let us be patient.

What has been taught in computer science and computer engineering today is adequate. Many new subjects find their way into the curriculum. Most old fundamentals have been through revision and condensation. However, helping students to navigate through these subjects is not always a success as it should be. The most striking feeling in my teaching career is that students in the senior year, who have been through the whole curriculum, are unable to “put all the pieces together” to form a coherent view of the field they studied. There are too many subjects that they become unrelated, inconsistent, or sometimes irrelevant.

It is my attempt in this book to put a whole picture to students, to ask them to build a whole system by themselves. The essences of computer system engineering are the ability to understand components and compose them into a system. To tackle a project of this size is not possible without critical assessment of the system we intend to build. My selections are: language, compiler, code generator, processor and operating system. All these components are implemented under one language which itself is also a subject to be studied. Each component is carefully designed so that it is as simple as possible and yet is able to demonstrate the principle of its operation.

Building a whole computer system always gives a good insight to understand the current technologies. The ability to ask “what if” questions throughout all levels of a computer system is a great benefit. Students can discover many principles by themselves. They can also gain a large factor of confidence in handling a complex system. They will understand how components interact, how to make tradeoff between various constraints and how to choose among alternatives.

The book is divided into nine chapters. They present a sequence of system building, from the language to processor, and then the operating system is implemented to complete the whole system. The outline of each chapter is as follows.

Chapter 1 An overview of computer system engineering

The chapter introduces a computer system structure, the relationships between hardware and software, the nature of computation, the performance issue and a brief history of computer.

Chapter 2 High level language Nut

the chapter lays down the first tool for building our computer system, the language, Nut; the design principle is discussed; the syntax and semantic of the language are given; the internal forms and the instruction set are studied.

Chapter 3 Nut compiler

the compiler for Nut language is studied; the parser, the symbol table, the run-time support and finally the evaluator.

Chapter 4 Code generation

the N-code to machine code translation is studied; the target machine code, S-code, is elaborated; a three-address instruction set is also illustrated.

Chapter 5 Microprogramming

in order to study a processor, the control unit is implemented in microprogram; the chapter discusses the basic and variations of microprogramming and illustrates a systematic design of microprogram.

Chapter 6 Processor Sx

the main processor, its data path and its instruction set are studied; the execution cycle is explained; the microprogram is developed; the performance on benchmark programs is measured.

Chapter 7 Performance enhancement

to address the issue of performance of a processor, this chapter studied stack frame caching; the data path is modified; the effect of the mechanism is analysed.

Chapter 8 Operating System Nos

the Nut operating system is studied in this chapter; its service includes interprocess communication, message passing and timer; the supervisor that provides an interface to the processor simulator is discussed.

Chapter 9 Optimisation

the last chapter takes a look at the performance improvement at every level of the system; macro expansion, introduction of new primitives, improve code generation, and new instructions.

The prerequisite is basic knowledge of digital design, computer architecture, and some knowledge in computer language and compiler. No extensive knowledge of operating systems is required. Some programming skill is required as students will run and modify various given simulators.

The book is suitable for senior undergraduate students and the first year graduate students. I do not cover the basic of all topics discussed in this book. I assume that they can be learnt from other textbooks or students already acquired them before tackling the project in this book. However, this book also serves many practitioners who want to reinforce or refresh some of their skills. I have used various chapters of this book to teach graduate students for a number of years. Graduate students usually have diverse background; teachers must supplement the necessary materials. I also offer this course for senior undergraduate students who have a uniform background. The material must be condensed to fit the available learning load.

We will be using one high level language to describe and to model an executable system in all levels of details throughout. This will force us to be consistent and to be complete in the sense that every concept can be implemented and measured in a system. We have three kinds of languages used in this text. The first one is a normal English text. It will be printed in Times-Roman font. The second one is the pseudo code, used to describe the algorithm or the specification. It is printed in Italics. The third language is the implementation language, it is the executable code, and is printed in Arial font.

For example, a quicksort algorithm can be described as follows.

An English prose

A quicksort algorithm does the sorting in place using the partition function to divided elements into two sub-arrays according to the pivot. Then it is applied recursively to sort both sub-arrays.

The input is an array ax[p..r]. q is the pivot, it divides ax into two sub-arrays ax[p..q] and ax[q+1..r].

An algorithm

quicksort(ax,p,r)
if(p < r)
    q = partition(ax, p, r)
    quicksort(ax, p, q)
    quicksort(ax, q+1, r)

A concrete program

(def quicksort (ax p r) (q)
    (if (< p r)
        (do
        (set q (partition ax p r))
        (quicksort ax p q)
        (quicksort ax (+ q 1) r))))

All programs discussed in this text will be presented as many individual functions that will be composed together, similar to constructing a shape from building blocks.

This is not a read-only text. It is a construction kit for a whole computer system. Students will be given a number of pieces of software (a set of functions) that can be put together to perform a task. Some piece will be left out so that students have to write it by themselves. However, with the given pieces, the system can be built to demonstrate its working condition and will process the input and will give the correct output. Students are asked to extend this working prototype, to implement some piece in a different way. Students can measure all the effect from their changes. They can decide after analysing the execution profile, whether any change is good or whether the change is cost effective.

Because of the highly vertical integration of this system, the effect of any level can be observed, from the top level of applications down to the lowest level of data path and machine cycle. This can bring insight and appreciation of seeing a computer system as a whole, completely transparent.

The appendices provide all the code referred to in the text. However, the initial tools such as an executable Nut-compiler and the most up-to-date version of program (including updates and bug-fixes) are available from the website supporting this course. They should be used to build the system.

http://www.cp.eng.chula.ac.th/faculty/pjw/ecse/

Acknowledgements

First and foremost I thank my parents who gave me spirit, knowledge and compassion. I thank all my teachers; Susak Thongthammachart is my mentor, Yuen Pooworawan is my true advisor, Boonklee Plunksiri taught me the wonderful world of switching and finite state automata, Paisan Saguanmoo gave me the first glimpse of computer architecture, Robin Popplestone is my research inspiration, Tim Smithers carefully shaped my idea, Chris Malcolm carried me through my doctoral program, and all teachers who taught me. My existence in the past fifteen years owed so much to my students as much as to my colleagues. Somchai Prasitjutrakul is my best friend from the first question he asked me “why do you want to be a teacher?”. I think now I can answer that question with confidence. I thank all my colleagues in my department and in other universities. I thank all my students, without them, there would not be this book. They are my source of motivation. Several times indeed, they suffered from my effort in teaching! However, looking back, I think all my students taught me so well how to be a good teacher. I thank the department of computer engineering, Chulalongkorn university that provides me with the best environment to teach and to be taught. It is also the place where I spent most of my time wondering about the meaning of education. Lastly, I thank my family, my wife who did all the figures in this book, and my two daughters who suffered negligence during my time focusing on this book. They gave me the energy!

Prabhas Chongstitvatana