Digital Systems Construction / Nisan & Schocken / Spring 2002

Digital Systems Construction 

Instructors: Prof. Noam Nisan and Prof. Shimon Schocken
School of Computer Science, Interdisciplinary Center Herzliya, Spring 2002

(also available: course syllabus in PDF and the course plan at-a-glance)

In this course we start with two constants labeled "0" and "1", and, four months later, we end up building a machine – called Hack -- which is roughly as complex and powerful as a GameBoy computer. The hardware and software systems of Hack are based on the same design principles that guide the construction of modern machines. Therefore, the lessons that you will gain from building this computer are directly applicable to real hardware and software engineering tasks.

Following a review of key topics in Boolean Algebra and gate logic, we will design and test about thirty combinational and sequential chips. This will set the stage for the construction of Hack’s ALU, CPU, and memory systems. These hardware elements will be constructed and tested using a simple dialect of HDL (Hardware Description Language). We will then test the entire machine by running some programs on it, written in Hack's machine language. These programs will be executed on a visual software simulator that emulates Hack’s hardware in Java.  We will also define an assembly language and write an assembler for it.

Next, we will build a virtual machine (implemented as a stack machine), and write an interpreter that translates VM code into Hack’s machine language. We will then introduce a Java-like language, called Jack, and write a compiler from Jack to the VM code. This will complete the basic design of the computer. Using Jack, we will then write a simple operating system for the computer, and sample applications like computer games, a text editor, or an HTML browser.

Course Objectives

The purpose of the course is to bring together, in an applied, unified and constructive manner, the following topics:

§      Hardware: Gates, multiplexors, flip-flops, counters, registers, arithmetic circuits, memory, CPU, I/O, chip implementation using a hardware description language;

§      Architecture: Overall processor design (single-cycle, two-cycle), machine code, assembly language programming, memory-mapped I/O;

§      Compilers: Lexical analysis, top-down parsing, symbol tables, virtual stack-based machine, code generation, implementation of object-orientation;

§      Operating Systems: Memory management, I/O drivers, File I/O, language support;

§      Software Engineering: Modularity, structured specifications, design documents, API's, test planning and structured test execution;

§      Data structures and algorithms: Stacks, hash tables, lists, recursion, basic arithmetic algorithms, basic geometric algorithms;

§      Programming Languages: Scope rules, abstract data types, syntax vs. semantics, references, object-based design and programming.

Most of these topics were covered in many different courses that you took at one point or another in the CS program.  In this course you will put them together in the most applied context: building a computer – a machine that we can actually burn in silicon, attach a screen to it, and play Tetris with it.

Requirements

This is a project-oriented course. All the programming will be done in HDL and Java, working with software simulators and API’s that were developed specifically for this course. The homework assignments will be spread evenly during the semester, so there will be no special “crunch” toward the semester’s end.  Each week we will review the work that was done thus far, and give instructions on what has to be done for next week. Students who will miss some work will receive executable versions of the missing modules (for some points penalty), so that they won’t get stuck in the ongoing construction. 

The course grade will be based on 70% homework, 30% final exam.

The course is accompanied by a textbook, whose chapters must be read before each lecture.

Course plan

 

Week of

Topic

Hand in

Read

March 5

Course overview / Boolean algebra / Combinational logic

Read chapters 1 and 2 BEFORE the first class meeting

Ch. 1,2

March 12

Sequential logic

1. Elementary logic gates project

2. Combinational chips project

Ch. 3

March 19

Machine and assembly languages / how to write an assembler

Sequential chips project

Ch. 4

April 9

Machine architecture: CPU design / putting all the hardware together

Assembler project

Ch. 5

April 23

Stack machine processing

Computer architecture project

Ch. 6

May 7

Virtual machines

Virtual machine project part I

Ch. 7

May 14

Object oriented programming in Jack / Building a sample computer game

Virtual machine project part II

Ch. 8

May 21

Compiler design: lexical analysis

Sample application project

Ch. 9

May 28

Compiler design: semantic analysis and code generation

Compiler project part I

 

June 4

Operating systems design I:
I/O drivers, memory management

Compiler project part II

Ch. 10

June 11

Operating systems design II:
math library, abstract data types

Operating systems project