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