2110793 Advanced topic in digital systems   2009

Prabhas Chongstitvatana
email me
office:  Engineering building 4, floor 18, room 13,  phone 02-218-6982
lecture:    Tues  16:00-17:30am   Eng. Bld. 4,  floor 20
               Thurs  10:30-12am  Eng. Bld. 3, room 319.

Previous lecture 2007  2004    2002     2001  1999

What's new

5 Nov  2009    the eval.nut  is now working correctly
10 Nov 2009   update to Nut4 (tools)  and nut-compiler-in-nut
2 Dec 2009    complete code generator gen4.txt   sx-chip simulator  sx0.zip   

Syllabus

Announcement

1)  Midterm project (Read and Analyse):  Choose a topic in language and architecture, read the state-of-the-art articles about the topic and write a 4-5 pages report.  Due date to submit and present the project  Tue 12 Jan 2010
2)  Schedule for the second half of the course:
19 Jan : discuss, commit projects
21 Jan lecture : VM, low power
26 Jan lecture : VM, low power
28 Jan lecture : VM, low power
2 Feb : discuss projects
4 Feb : discuss projects
9 Feb : discuss projects
11 Feb : submit projects, take home exam
16 Feb : no class   final exam
18 Feb : no class   final exam
23 Feb : no class   final exam
25 Feb : submit final paper.

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.  An executable abstract language is used to as a mean to explore all levels. 

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, a real-time operating system includes task switcher and message passing.  Real-time concurrent application programs such as multiple clocks will be run on this operating system.
 
The students will learn:

Topic by Week

  1. Overview of building a computer system
  2. Nut language and semantic, its internal structure, n-code       example of internal form
  3. Semantic of n-code     the evaluator   eval.nut  (use with nut4)  how to use eval
  4. Nut compiler   pseudo code   Nut-compiler completion kit     Nut-completion kit source
  5. Code generator     How to do Code-gen completion kit     (gen2.txt) the source
  6. Computer Architecture      Microprogramming
  7. Processor  Sx-chip    Sx-microprogram     How to microprogram Sx chip    mspec.txt
  8. Nut Operating System (NOS)   nos0.txt  (source code of NOS version 0)  
  9. Supervisor program (NOSS)    package     the update code generator to handle (run (fn...))
  10. Performance measurement
  11. Code optimisation
  12. Running an OS on a processor simulator
  13. Real-time OS

Assignments

Week 1

Write Nut program
1.1  To find maximum of three numbers.
1.2  To sum the odd numbers from 1..m.
1.3  To do multiplication from addition.
1.4  Use 1.3  to do x power to n.

Week 2

Modify the eval.nut to add other operators:  sub, put, stx

Week  3

Working with compiler   For how-to discussion
3.1  Extend the nut-in-nut compiler to include "let" and "enum"
3.2  Write a function in nut compiler to output "linearise" vesion of object code, so that the object code will be locatable.

Week 4

Complete the code generator

Week 5

Language extension
Implement a new language feature in Nut. Modify the compiler for it and create a new n-code to achieve the desired operation.  The evaluator must be modified to execute this new n-code. Implement "switch" statement using a table look-up scheme. Here is the suggested syntax:

(case ex (label1 action1) (label2 action2) ...)

where label1 ..  are numeric.  The meaning is as follows.  Evaluate "ex" which result is numeric, then take "action" that "label" matches the result. All labels must be unique.  If no match then no action is taken.

The easiest internal form (n-code) is the one that has its structure matches the source.  But it will take a linear search to find a match with all labels.  There are two alternatives to reduce the search time.  The first one is "binary-search" among labels.  The internal form separates labels and actions and sort the label list, order the action list accordingly: 

  (label1 label2 ...) (action1 action2...)

Now that the list of labels is sorted.  One can perform binary-search for a match.  Using that index to select the corresponding action.

The second alternative is "hash".  A full range table, contains the pointer to an appropriate action, is created.  The range of label is lo..hi, there will be some empty "hole" in this table.  To choose the appropriate action, perform the following index calculation, assuming the case number is n:
   if (n >= lo) and (n <= hi)
      perform action[n-lo]

Week 6

6.1 Write and implement and run the simulator for a microprogram for a new instruction :   2*x
6.2  Write a microprogram for a function  string copy and compare the number of cycle used with nut program (both running on Sx-chip):
(def strcopy (s1 s2) ()
   (do
   (while (vec s1 0)
      (do
      (setv s2 0 (vec s1 0))
      (set s1 (+ s1 1))
      (set s2 (+ s2 1))))
   (setv s2 0 0)))

Week 7

Run the example in the book chapter OS

Documents

Tools

Text

Computer languages
Computer architecture
Operating systems
last update 20 Jan 2010