Digital Systems  Final 2011

Please choose one question.  I expect a report of 3-4 pages.  Think hard, make some decision and write convincing arguments, backed with good quality quantitative data.  Please organise amongst the group not to have duplicate question.  You can also suggest your own problem related to the class.

1. Language

1.1  Introduce data structure (same as struct in C) to Rz.  Write a grammar for it.  Explain how to compile this and generate a proper machine code (any hypothetical machine code will do). Show some example how this new construct helps to make a program easier to be understood.

1.2  Write eval() that can execute s-code (like somv2x) in Rz. It must be able to run object code of a simple program (like factorial, or sum of an array). (Hint: eval() is in nos-5.zip, "interp.c")

1.3  Design a new language.  Ajarn Somchai suggested to me that we should invent a Miminum Key Stroke programming style.  The goal is to write a program with minimum number of key stroke. This can help students of programming to concentrate on "thinking" rather than rapid "edit-compile-run" cycles. Show the design of a language based on this idea.  Write a grammar for it.  Show several convincing examples and quantitatively compare them to ones written in Rz. (of course by measuring the goodness as the number of key stroke required).

2. Compiler

2.1  Rz3.4 compiler uses sequential search for symbol table (see rz34/comp/symtab.c). Modify the compiler to use "hash" instead.  You must be careful how to handle local variables because they can duplicate the names of global variables. Measure the improvement by counting the average number of times searching for a symbol "compare" the key, (this line)

if( eqs(symtab[i].name, name) ) break;

Use the program in rz3/test/*.txt to benchmark your new routine by compiling them. Concatenate all (eight) programs into one, change main() slightly.  Compare the new search with the old one.

2.2  One way to improve the speed of the compiled program is to use "inline".  This will reduce the overhead of a function call. Most "access" function in Nos such as
getNext(a)
setNext(a,v)
...
getsval(s)
setsval(s,v)

can be "inlined". Modify Rz3.4 compiler to do that. Run some benchmark such as showTwoCount, showSync, showProduce and compare the "inline" and "normal" version by counting the number of instruction executed to do the same job. (you can just run "noss" and notice the report).

2.3  Binary translation.  One way to transfer a binary (executable) file from one machine to a different architecture is to do "binary translation". This means to directly translate one machine code to another (different) one. It is not difficult because most machine codes have analogous codes in different architecture. Only size and format are different. The difficult part lies in calling operating system services and input /output because they are quite different from machines to machines. Write a program (preferably in Rz) to translate s-code object (a stack-based instruction set) to S2 (a register-based instruction set). Testing it with a few simple benchmark programs. Look at S2 and its simulator here.

3. Processor

3.1  Design a new instruction set so that your new processor will be faster than sx-chip in terms of the number of instruction executed. As you are doing this by hand (rather than actually implement the new processor simulator), use one or two simple Rz programs to benchmark your new design.  Compare it to s-code.  You can calculate how many instruction executed by writing the new assembly by hand and count. (for s-code, measuring the number of instruction is simple, run the program under nos, nos-5.zip, the report shows the number of instruction).  Hint: see the evolution of my Som language if you need some idea how to improve an instruction set.

3.2  Micro architecture.  Improve sx-chip by adding pipeline and other necessary units (such as increment/decrement Stack pointer). Show the diagram of the architecture (similar to Fig 6.1 Chapter 6, Sx data path) and write Register Transfer Level sequence of executing each instruction (it is still s-code). Show how many clocks the new data path is faster than the old one.

3.3  Micro program.  Write a microprogram for sx-chip to run bubble sort (see bubble.txt).  You can add some registers to help you to hold values if that is necessary.  Run your new micro program and count how many cycle. Compare it to running the old (sx0) sx-chip on similar data set.

3.4  Modern processors have many functional units, that is, they are superscalar machines.  The instruction stream is reordered such that these functional units can be used as much as possible at the same time.  This is a kind of packing many instructions into one long instruction for concurrent execution. Please modify Sx-chip to have two ALUs and invent instructions that can make use of them. Describe a microprogrammed version of such machine (in executing instructions).

4. Operating System

4.1  Discuss the co-operative process.  How can it be implemented?  Cooperative process can be implemented  at a lower cost than the preemptive OS.  Write co-operative process in Nut and discuss its cost.

4.2  Nos has a single address space.  To protect resources used by a process, a  virtual memory is necessary. Discuss how to implement a virtual  memory under our framework.

5. Applications

5.1  Write some interesting parallel programs.  Run them as thread (multi-task) in Rz+Nos.  Discuss how using a multi-core processor can get the job done faster than a single-core processor.

5.2  Show how to implement a timer. Design a new feature of the OS,
   "at" time_x do function_y

This means at the time_x run the function_y. Time is a global clock of arbitrary unit (integer).  Write Rz program to implement "timer" and "at time".  You don't have to actually make it to work under Nos (becuase it may be too hard) but you must show how it should be done.

5.3  Write a simple line-drawing interactive graphic program with Rz+Nos + some windows GUI.  (a nice demo)  Try to use Rz as much as possible (rather than entirely depends on Godmode).

5.4  Nos has no input, to allow concurrency, the input can be simulated through the console application.  A console accepts input and feed it as a stream to the receiving process.   Write a terminal program in Rz. Show a simple read input from keyboard, print it to console. Use Rz+Nos + something.  You must run multiple terminals. (show two terminals concurrently).  (a nice demo).

5.5  Write a concurrent program (with Rz) showing two clocks (graphical ones) (one for Bangkok, another for London, for example).  This is done using Rz+Nos + some windows function.  (a nice demo)

I may add some more this week.

last update 10 Sept 2011