2110714   Digital Systems 2011

Prabhas Chongstitvatana

email me at prabhas at chula dot ac dot th
office:  Engineering building 4, floor 18, room 13,  phone 02-218-6982

lecture:   Tue,Wed  11:00-12:30am   Eng. Bld. 4,  room 322
for weekend class:    Sat 13:00-16:00  Eng. Bld. 3, room 17-01

Syllabus

Aim

This serie of lectures aims to integrate the knowledge of building a computer system from the most bottom level: functional units, data path, microprogram, to the highest level: operating system, high level language and application programs.  The lectures cover three main areas: processor, compiler and operating system.

This course offers a "hand-on" approach.  Students go through series of building and modifying a "system" simulator.  The system simulation composed of: an instruction-level processor simulator, a compiler, a profiler, an operating system includes task switcher and message passing. Concurrent application programs will be run on this operating system. To ground the processor simulator, a small embed development board will be used to implement an emulator of the processor used in the class.
 
The students will learn:
How the instruction set affects the performance
How to instrument the simulator to measure it
How a compiler generates codes for a processor
Relationship between high level language and machine code
Porting of an operating system to a new processor

Assessment

class work                              10%
small project (may be two)      40%
final exam                               50%

Announcement

9 June 2011   The Monday class is changed to Tuesday the same time.  The room is expected to be the same room.  Next class will meet here.
10 June 2011   One student found that "rz31.zip" and "rz32.zip" contained virus.  I deleted them and zip a new one from fresh files.  If you find any problem please report.
4  July 2011   Microprogramming tool update sx0-2.zip.  New lecture on programming/microprogramming Sx-chip.
7  July 2011   Chapter 7 Sx2-chip, project 1 announced, benchmark program.
2 August 2011   My C compiler has been uploaded.  You will definitely be able to compile Rz package.
20 August 2011  New Rz compiler with executable output (run under somv2 engine) is available (rz33-1.zip) 
23 August 2011  Nos source is available   (nos.zip)  update (nos-1.zip) (correctly terminate)  nos-2.zip (remove bugs)
3 Sept 2011  Nos update  nos-4.zip  (working properly with all examples)  nos-5.zip (with bug-fix compiler)
6 Sept 2011  Take home Final Exam is here.  Please choose one and start working.

Topic by Week

Overview of building a computer system
   Introduction to language and compiler used in this class  Rz language
Computer language and semantic
Computer Architecture      Microprogramming
Processor  Sx-chip    Sx-microprogram     How to microprogram Sx chip    mspec.txt
  Making a new instruction for Sx-chip (microprogram)
  Machine level programming for Sx-chip  
Compiler  intro  scanner  CFG  parser
Evaluator (virtual machine)
Code generator
Operating System  (see additional reading material)
Supervisor program  Nos operating system   example of two processes computing sum of an array
Performance optimisation
Low power design

Previous lecture  2110793 Advanced topic in digital systems   2009,  2004

Homework 

Section Tue,Wed

1.  Familiarize yourself with the language tools.  Use rz31.zip compiler package.  Write a recursive program in Rz language to find the maximum value from an array of integer without using a global variable. The size of the array in known.
2.  Try hand-on with making a new intruction for Sx-chip "djnz".  Use the tool in the package sx0-2.zip
3. 
Project 1)    Design some improvement to Sx-chip so that it runs a benchmark program faster.  Write a 3-4 pages report about your design.  Give an analysis of its performance.  Here are the source of the bubble sort program and its listing.  (bubble-s.txt, bubble-s.lst)  Here is the trace of execution (trace.txt)  and some accompanied explanation (proj1-data-explain.txt). Please hand-in your report (paper)  by 13 July 2011.
4.   Read  the slides "Follow Set".  Try to compiler rz32 package.
5.
Project 2)   Create a Domain Specific Language.  If you want a more formal definition see here  http://en.wikipedia.org/wiki/Domain-specific_language
  Submit the report 2-4 pages of the following:
  a)  design of the language.  explanation of the language
  b)  motivation, why this language, include how to use it, illustrate by some good examples.
  c)  grammar of the language (in BNF or Rail road diagram).   
Please hand-in by 12 Aug 2011  (Mother day :-)
6   1)  The different process has different stack segment.  Then, how to initially pass parameters to each process?  (because the stack of the process "main" is different from the process "count").  Look at the following example:
  count(i){
     while( i < 100) i = i + 1;
  }
  main(){
    p1 = run(count(3));
    p2 = run(count(10));
  }
     2)   Discuss what is the environment (runtime) of "main"?   Is it different from the environment of other process? (such as "switchp", or "count").
     3)   Play with different values of QUANTA in the supervisor.  See the effect when it is very small and very large.
     4)   Write some program that solve one problem using many processes.  Run it on Noss. Usually it requires share variables, but you don't have to worry about it at this moment, if you set QUANTA properly your program should gives the correct answer.

Section Saturday

1.  Familiarize yourself with the language tools.  Use rz31.zip compiler package.  Write a recursive program in Rz language.
2.  In "microprogramming" slide example, explain how the instruction "add" work.
3.  Explain step-by-step of these four instructions of Sx-chip:  lit.n, st.a, jt.a, get.x
4.  Hand-on programming Sx-chip at machine level, using Z-assembler (in sx0-2.zip).  Write a program in Sx native code to find a maximum element in an array of integers.
5.  Design some new instruction for Sx-chip so that it runs faster on some benchmark.  I suggest one benchmark program: bubble sort. Here are the source of the bubble sort program and its listing.  (bubble-s.txt, bubble-s.lst)  Here is the trace of execution (trace.txt)  and some accompanied explanation (proj1-data-explain.txt).
6. Project   Create a Domain Specific Language.  If you want a more formal definition see here  http://en.wikipedia.org/wiki/Domain-specific_language
  Submit the report 2-4 pages of the following:
  a)  design of the language.  explanation of the language
  b)  motivation, why this language, include how to use it, illustrate by some good examples.
  c)  grammar of the language (in BNF or Rail road diagram).   
7.  Try your hands on Nos, vary different QUANTA and see the result (running showTwoCount) Use package nos-4.zip

Tools

Rz language
compiler package  rz31.zip   rz32.zip   rz33-1.zip
Sx-chip simulator  (sx0.zip)
update to sx-chip simulator (sx0-1.zip)  include z-assembler
update sx-chip simulator and its tool set  (sx0-2.zip)    (sx0-3.zip)
C compiler that I used   (lcc-win32  13Mbytes)   how to install    easy start
Nut Operating System  source (nos.zip) update (nos-1.zip) (correctly terminate)  nos-2.zip (remove bugs)   nos-4.zip   nos-5.zip
The package contains new Rz compiler.  The Rz language now (v3.4 and later)  uses indentation instead of { }  and \n  instead of ;
Look at the operating source code to see the new look.

Additional reading material

Programming Recursion   (to familiar yourself with recursive programming)
Chapter 6 Sx-processor   explain in details how Sx chip work at microprogramming level
Chapter 7 Sx2-processor   an example how to improve the performance of Sx-chip
Chapter 8 Operating System    implementing an operating system (code is written in old Nut)
Chapter 9 Optimisation   various methods to improve performance: language, compiler, chip, microprogram, OS.

Text

Chongstitvatana, P.,  The Essence of Computer System Engineering, in preparation, 312 pages, since 2006.  (on the web )

Computer languages

Computer architecture

Operating systems

Additional materials will be hand-out as needed.
Reading: 

last update 13 Sept 2011