Wanna design a computer?

The next installment in the courseware section — computer design — is now available.

This course shows how to design a computer starting with an abstract specification of the instruction set architecture (ISA) and ending with a gate-level implementation. The course teaches a method which successively translates a higher-level representation for the machine into a lower-level representation. For example, the ISA is translated to a datapath consisting of large-grain building blocks and a control graph annotated with register transfer statements. Then, the datapath and control graph are mapped into gate-level building blocks and control store. Different datapath and control styles (clocking, pipelining and microprogramming) are discussed. Computer science students should be comfortable with the representations — no scary electronics.

I taught this course for several years at Case Western Reserve University. It’s an undergraduate level course that assumes a prerequisite course in basic logic design. So, if you already know about gates, flip/flops and simple sequential logic, you’re ready to dive right in! Course material includes draft chapters for a book on computer design and slides.

I hope that you will be able to use this course for background knowledge once I begin to experiment with and write up Papillio projects. I would probably base class projects on Xilinx FPGAs (Papillio) if I were teaching this course today. Papillio makes hardware design personal and affordable. I would love to see more computer science students take up hardware design, especially in high school. Perhaps this course will help you out.

Courseware is here

Finally, the courseware section of the site is open for business!

The first course is undergraduate data structures. I taught this course twice at Tufts University. Topics include the most important elements of the old ACM 2001 “CS2” curriculum along with a basic introduction to software engineering. The course is compatible with the “new” ACM 2013 curriculum which distributes computer science topics across one or more courses. Most of the hours are devoted to data structures with software engineering and algorithms/complexity playing secondary roles.

The main web page provides a rationale for the course design. It lays out the syllabus for a one semester course (15 to 16 weeks). The syllabus links to a full set of lecture notes. These notes should be a gold-mine for any instructor — high school or college — who needs to develop and deliver a course on data structures. I tried to meld and blend the best information I could find on each topic, usually from multiple textbooks. Of course, if you are a student, please dive in and browse, too!

The main course page also has links to the projects. I drew inspiration from my background as a system programmer, so the projects are not your usual “search tree this, search tree that.” The projects include lexical analysis, expression evaluation and discrete event simulation among other subjects. For the more advanced projects, I provided a source code framework/infrastructure to the students to help get them started. They were required to design to an interface specification and then integrate their implementation into the framework. This approach allowed my students to attack larger problems with more substance and purpose.

The course uses C++. Quite often, however, the code examples were translated from Java. So, it shouldn’t be too hard to translate back to Java. The examples do not use STL, Boost or templates that would hinder translation to Java or reuse.

Please take a look! For your convenience, here are links to a sampling of topics: stacks,
linked lists, trees, debugging, algebraic datatypes (ADT) and testing.

I will be rolling out additional courses during the month of August. These courses will be hardware-oriented: computer design, VLSI systems and computer architecture. If you ever prep’ed a course, you know how time consuming it can be to simply organize course material. Blog posts will be a little less frequent until I complete the courseware section.