Computer Science 430 Hardware Organization Winter 2010–11

Equivalent web page:
Catalog description: Viewable at
James S. Evans
Science Hall 131
Extension 6571
Home: 734-6304 (not after 10:00 PM, please)
Office hours: You may either make a specific appointment, or just stop by the office any time that the door is open (more of the time than for the majority of faculty members?).
Class meetings: 8:30–9:40 M W F, Briggs Hall 419
Text: Computer Organization and Design: the Hardware/Software Interface, 4th ed., by David A. Patterson (University of California, Berkeley) and John L. Hennessy (Stanford University), published by Morgan Kaufmann, a part of Elsevier, (2009). ISBN 978-0-12-374493-7.
(Supporting web page for 4th ed.: click here; errata click here)
Coverage: The course may include some material selected from other sources. Topics may be introduced in class in a somewhat different order and style than the treatment in the text. The intent is complementation and supplementation, not conflict. Assignments may require that you combine knowledge and skills gained from the text, class presentations, and other reference sources.
Rationale for this course: Some awareness of the underlying hardware upon which computer software systems are built may contribute to maturity of understanding among students pursuing a computer science emphasis in their undergraduate years. This particular course experience is most suited to industrious self-starters who can learn independently, not just from lectures, and who can sustain energy for a difficult undertaking. Procrastination will be fatal.
Class meeting format: Class periods should be used to focus on highlights and difficult concepts, not on exhaustive coverage of the material from the book. Every member of the class is expected to keep up with the reading assignments in the text in order to participate actively at every class meeting. We are neither equipped nor staffed to offer formal laboratory work for this course.
Student requests brought this course into Lawrence’s computer science offerings. Usually students have some personal reasons for wanting to study under this big umbrella rubric. Make the experience personally meaningful to yourself through customization!
Assessments: Frequent problem assignments, two in-class exams, the final examination, and an optional individual project will form the basis for evaluation.
     Assignments 45%
Hour exams 30%
Final exam 25%
Optional project    5–15% by displacement
There is room for individual expression of emphasis among problems, exams, and personal efforts. Persons differ in styles of learning, and you may arrange an individual conference very early in the term to determine how you want these various components to be weighted.
The cumulative distribution of grades for this course in previous years from this instructor has been as follows: A, 38%; B, 48%; C, 10%; D, 2%; F, 2%. These percentages are merely history, however, and in no way represent quotas or promises for this year.
Assignments: There will be about eight assignments, coming along after every few class meetings.
Assignments are due at 1:00 PM on the stated day. Late work will be handled as follows: Each student will begin the term with a “contingency” account containing 10 “contingency points.” When an assignment is late, this account reduces at the rate of 2 points per calendar day (or fraction thereof). If an assignment can be completed nicely and handed in earlier than 5:00 PM preceding the stated due date, then additional contingency points can be accrued at a rate of 1 per calendar day. The contingency account uses signed integer arithmetic. At the end of the term, the balance may be used to resolve ultimate grading decisions, but there is no predetermined relationship of contingency points to the standard grading scale.
The text contains many problems. Some seem to be relatively short. Others seem rather challenging. Development of proficiency with such problems is important, through both oral expression (in class, or outside of class when studying with others) and written exposition.
Optional independent reading or individual or group project: The text identifies many sources of additional information and alternative points of view. You are encouraged to develop curiosity and to gain recognition for satisfying that curiosity by selecting topics from those references for independent study during the term. Or perhaps you are intrigued by futuristic topics such as molecular electronics and quantum computing. If you wish to do so, you may submit a brief report in which you indicate the scope of your reading, summarize the chief points, and reveal your understanding of the new material for each topic that you have explored.
Individuals or groups may submit proposals by the end of Week 3 for term projects that could displace 5–15% of the weighting of other components making up the course grade. (A project would not produce “bonus points” or the like.)
Honor code: Each piece of work that you submit in this course should bear the Lawrence University honor pledge, your signature, and the date of completion on the final page.
Please seek help from others whenever you can learn effectively in the process, but always acknowledge the source, nature, and extent of assistance or collaboration. The final product should be distinctively your own.
Assistance: CMSC 430 is an intermediate-level opportunity intended for diligent students who can seek out assistance well in advance of the fabled “point of desperation.” Please bring any ambiguities in the assigned work or any lack of clarity in class presentations to the instructor’s attention immediately.
Tentative Schedule (2010-11): The pace will be brisk. Keep up! The book has only 7 chapters, but some are rather long. We will tentatively allocate time to those chapters as follows.
Note that the book has a somewhat unusual structure, in that certain segments of chapters and all of the appendices appear only on the CD.
Week Day Date Readings, assignments, and events
1 Mon  03 Jan  Chapter 1, plus our only physics
Wed  05 Jan  Chapter 1, plus our only physics
Fri  07 Jan  Chapter 2, sections 1–6
Sat  8 Jan  Assignment 1 due at 1:00 PM
2 Mon  10 Jan  Appendix C
Wed  12 Jan  Appendix C
Thu  13 Jan  Assignment 2 due at 1:00 PM
Fri  14 Jan  Appendix C
3 Mon  17 Jan No class (MLK Day)
Wed  19 Jan  Chapter 2
Fri  21 Jan  Chapter 2
Sat  22 Jan  Assignment 3 due at 1:00 PM
4 Mon  24 Jan  Chapter 3
Wed  26 Jan  Hour exam (Ch 1–2 and Appendix C)
Fri  28 Jan  Chapter 3
5 Mon  31 Jan  Chapter 4
Wed  02 Feb  Chapter 4
Fri  04 Feb  Chapter 4
Sat  05 Feb  Assignment 4 due at 1:00 PM
6 Mon  07 Feb  Chapter 4
Wed  09 Feb  Chapter 4
Fri  11 Feb  No class (reading period)
7 Mon  14 Feb  Chapter 5
Wed  16 Feb  Preview and Hour exam (Ch 3–4)
Fri  18 Feb  Chapter 5
8 Mon  21 Feb  Chapter 5
Tue  22 Feb  Assignment 5 due at 1:00 PM
Wed  23 Feb  Chapter 5
Fri  25 Feb  Chapter 6
9 Mon  28 Feb  Chapter 6
Wed  02 Mar  Chapter 7
Thu  03 Mar  Assignment 6 due at 1:00 PM
Fri  04 Mar  Chapter 7
10 Mon  07 Mar  Chapter 7
Tue  08 Mar  Assignment 7 due at 1:00 PM
Wed  09 Mar  Additional topic(s) or project report(s)
Thu  10 Mar  Final deadline for all written work is 1:00 PM
Fri  11 Mar  Preview and Final examination 11:30 AM–2:00 PM
Simulation software: Previous students have helped to collect references to assorted simulation software that is related to topics that are, or could be, studied in this course.
Some of these applications may assist with comprehension of the material in the text, perhaps in conjunction with the assigned problems. Others may be useful for background. Still others may provoke ideas for projects or deeper study.
Digital logic  xLogicCircuits Java Virtual Machine applet: This tool by David Eck allows building simple circuits using only AND, OR, and NOT gates. Accessible here.
Logisim Java 1.4: This tool by Carl Burch allows building simple circuits using a wider palette of elements than xLogicCircuits. Circuits can be printed. Accessible here.
DigitalSimulator Windows: This design and simulation program by Andreas Herz is a SourceForge project that is available here. Note: the author’s German site has apparently lapsed.
Chipmunk UNIX: This set of tools developed at Caltech is now available in versions for numerous environments, including Linux.
Web links Carl Burch’s list of graphical circuit tools.
Bruce McKibben’s list of electronic design automation links.
Boolean algebra and Karnaugh maps Michael Keppler’s applet An interactive web applet for 4-variable Karnaugh maps (English, German). Accessible here. The parent site (in German) contains applets on other topics.
KarnaughMap A freeware program by Russell Sasamori for Windows 95/NT. Accessible here.
Microarchitecture mic1 The freeware simulator prepared by Ray Ontko and Dan Stone to accompany Chapter 4 in the 4th edition of Tanenbaum’s Structured Computer Organization. Downloadable for Unix and Windows systems here. You will also need Sun’s Java developer’s kit (see the Web page for mic1).
CPU Sim A freeware Java program by Dale Skrien that allows you to design your own microarchitecture. Available here.
Printed references: Professional opinions vary, as to whether this subject matter is best approached “top down,” connecting conceptually with the emphasis on abstraction in foundation courses in computer science, or “bottom up,” building concretely from basic concepts in math and physics toward the complexity and abstraction of full computer systems. The book by Stallings exemplifies the first approach, while Tanenbaum’s text pursues the latter path.
Texts and monographs on hardware organization are written from several different perspectives for different audiences. Here is a sampling that is biased toward suitability for the undergraduate level.
Some of the printed references are available in the Lawrence University library. Others are available in the instructor’s office. Note that some of the items may be rather dated, but may still be useful for background.
Books  Books in print (2010) Computer Architecture: Concepts and Evolution by Gerrit A. Blaauw and Frederick P. Brooks, Jr. Reading MA: Addison-Wesley, 1997. ISBN 0-201-61353-4. QA76.9 .A73 B57 1997. A guide and reference for the practicing architect.
Computer Systems: Organization & Architecture by John D. Carpinelli. Boston: Addison-Wesley, 2001. ISBN 0-201-61253-4. A bottom-up computer engineering book.
A History of Modern Computing by Paul E. Ceruzzi, 2nd ed. Cambridge, MA: MIT Press, 2003. ISBN 0-262-53203-4. QA76.17 .C47 2003.
The Principles of Computer Hardware, by Alan Clements, 4th ed. Oxford, UK: Oxford University Press, 2006. ISBN 0-19-927313-8. Computer engineering.
Computer Organization by Carl Hamacher, Zvonko Vranesic and Safwat Zaky, 5th ed. Boston MA: McGraw-Hill, 2002. ISBN 0-07-232086-9. Computer science or computer engineering. ARM, Motorola 680x0, and IA-32 Pentium as the main examples.
Computer Architecture and Organization by John P. Hayes, 3rd ed. New York: McGraw-Hill, 2002. ISBN 0-07-286198-3. QA76.9.A73 H39 1998. Graduate level. Computer engineering.
Computer Architecture: A Quantitative Approach by John L. Hennessy and David A. Patterson, 3rd ed. San Francisco: Morgan Kaufmann Publishers, 2003. ISBN 1-55860-596-7. Older edition: QA76.9 .C643 H46 1998. Graduate level.
Computer Systems: Design and Architecture by Vincent P. Heuring and Harry F. Jordan, 2nd ed. Upper Saddle River, NJ: Pearson Prentice Hall, 2004. ISBN 0-13-048440-7. Uses the viewpoints of an assembly language programmer, a logic designer, and a system architect.
Essentials of Computer Organization and Architecture by Linda Null and Julia Lobur, 2nd ed. Sudbury, MA: Jones and Bartlett, 2006. ISBN 0-7637-3769-0. Undergraduate computer science.
Computer Organization and Design: The Hardware/Software Interface by David A. Patterson and John L. Hennessy, 4th ed. Amsterdam: Morgan Kaufmann Publishers, 2009. ISBN 978-0-12-374493-7. Older edition: QA76.9 .C643 H46 1998. Written with a focus on the MIPS series of RISC processors.
Computer Design and Architecture by Sajjan G. Shiva, 4th ed. CRC Press, 2007. ISBN 9780849304163. Computer engineering.
Computer Organization and Architecture by William Stallings, 5th ed. Upper Saddle River, NJ: Prentice Hall, 2000. ISBN 0-13-081294-3. QA76.9.C643 S73 2000. Newest: 8th ed., 2009. Approaches the material from top down, instead of bottom up.
How to Build a Beowulf: A Guide to the Implementation and Application of PC Clusters by Thomas Sterling, John Salmon, Donald J. Becker, and Daniel F. Savarese. Cambridge, MA: MIT Press, 1999. ISBN 0-262-69218-X. QA76.58 .H69 1999. Linux clustering
Structured Computer Organization and Architecture by Andrew S. Tanenbaum, 5th ed. Upper Saddle River, NJ: Prentice Hall, 2006. ISBN 0-13-148521-0. Older edition: QA76.6 .T38 1999. Approaches the material from bottom up, instead of top down.
Computer Architecture: Design and Performance by Barry Wilkinson, 2nd ed. New York: Prentice Hall, 1996. ISBN 0-13-518200-X. QA76.9 .A73 W54 1996. Computer science and engineering.
Older works Computer Architecture by Robert J. Baron and Lee Higbie. Reading, MA: Addison-Wesley, 1992. ISBN 0-201-50923-7. Contains an unusual glossary/index that makes glaringly obvious how much jargon there is.
Computer Architecture and Logic Design by Thomas C. Bartee. New York: McGraw-Hill, 1991. ISBN 0-07-003909-7. Computer engineering.
Computer Architecture by Mario De Blasi. Wokingham, England: Addison-Wesley, 1990 (translated from Italian). ISBN 0-201-41603-4.
Microcomputer Architectures: RISC, CISC and DSP by Steve Heath, 2nd ed. Oxford: Newnes (Butterworth-Heinemann), 1995. ISBN 0-7506-2303-9. A focus on Motorola designs, with some other comparative information.
Design and Organization of Computing Structures by James H. Herzog. Wilsonville, OR: Franklin, Beedle & Associates, 1996. ISBN 0-938661-97-3. Computer engineering.
Advanced Computer Architecture: Parallelism, Scalability, Programmability by Kai Hwang. New York: McGraw-Hill, 1993. ISBN 0-07-031622-8. QA76.9 .A73 H87 1993. Graduate level computer engineering.
Introduction to Computer Organization and Architecture by Harold Lorin, 2nd ed. New York: John Wiley, 1989. ISBN 0-471-61404-1. Easier to read than some others.
Principles of Computer Architecture by Miles J. Murdocca and Vincent P. Heuring. Upper Saddle River, NJ: Prentice Hall, 2000. ISBN 0-201-43664-7. Based on a subset of SPARC architecture.
Processor Architecture: From Dataflow to Superscalar and Beyond by Jurij Silc, Borut Robic, and Theo Ungerer. New York: Springer, 1999. ISBN 3-540-64798-8. Explores parallelism.
Computer Architecture edited by Harold S. Stone, 2nd ed. Chicago: Science Research Associates, 1980. Older material by distinguished contributing authors.
High-Performance Computer Architecture by Harold S. Stone, 2nd ed. Reading, MA: Addison-Wesley, 1990. ISBN 0-201-51377-3. Computer science.
Foundations of Computer Architecture and Organization by Ivan Tomek. San Francisco: W. H. Freeman, 1990. ISBN 0-7167-8161-1. More suitable for a course with some kind of build-it-yourself laboratory.
Computer Architecture and Design by A. J. van de Goor. Wokingham, England: Addison-Wesley, 1989. ISBN 0-201-18241-6. Computer engineering.
Journals  Peer reviewed Like other scholarly disciplines, computer science has peer-reviewed journals sponsored both by professional societies and by commercial publishers.
Conference proceedings To a greater extent than in many other scientific fields, computer science and especially computer engineering use the “published” proceedings of technical conferences as a major supplement to journals. Unfortunately, only very large research libraries have collected these systematically, but sometimes the conference sponsors provide online versions.
Trade press Computer science and computer engineering also have periodicals supported principally by advertisers to which professionals can subscribe at little or no cost. Be careful not to misinterpret “vaporware” as fact when reading such publications.
Popular press Like other subject areas of relatively broad impact, computer science and computer engineering have numerous subscriber- and advertising-supported periodicals. For academic purposes, these can be useful for orientation, but they are not deemed to be authoritative sources. One should use them as a lead-in to more solid sources such as conference proceedings or technical vendor data.
House organs Certain giants of industry that had historically sustained major research and development laboratories had also published journals principally to showcase the work of their own scientists and engineers. Although these “house organs” vary in quality, intended audience, and independence from the marketing or public relations department, the best of them rise to be on a par with conference proceedings, or even peer reviewed journals.
Unfortunately, many of these have fallen by the wayside because of corporate cutbacks or mergers, and, like conference proceedings, can be difficult to locate except in major research libraries. Fortunately, some current ones, as well as certain historical archives, can be found on the Web (see Electronic resources below).
Electronic references: To an ever-increasing extent, the effort to master a new subject requires the use of electronic as well as print resources.
Some of these electronic references may assist with comprehension of the material in the text, perhaps in conjunction with the assigned problems. Others may be useful for background. Still others may provoke ideas for projects or deeper study.
Architecture manuals For each major computer architecture, the manufacturer will publish a specification that includes thorough, detailed information about the effect of every machine instruction. This may take the form of a published technical book, a printed handbook, and/or some electronic equivalent. See the Itanium architecture book support site for pointers to numerous examples.
Processor manuals Typically, a manufacturer will also publish rather detailed information about each substantially different processor implementation. This is where you should look for information about cache structures, instruction latencies, memory management, and other non-architectural aspects of processor design.
Corporate house organs Alcatel-Lucent (formerly the ‘old’ AT&T) Bell Labs Technical Journal, one of the oldest corporate technical publications, was formerly distributed to libraries gratis, but is now available only on a paid basis from Wiley InterScience.
Digital Digital Technical Journal has ceased publication, but has been archived here except for its first two volumes.
HP Hewlett-Packard Journal has ceased publication without having been archived fully. Issues from the years 1994 through 1998 can be accessed here. The table of contents for issues from July 1968 to November 1998 can be accessed here.
IBM IBM publishes two technical journals, IBM Journal of Research and Development and IBM Systems Journal. On-line versions can be accessed here.
Intel Intel Technology Journal can be accessed here.
Technical reports Scientists and engineers in industry write numerous technical reports, variously intended for internal use, formal publication, and/or customer use. Corporations also make certain reports openly accessible. See, for example, Sun’s SML Technical Reports (preserved by new owner Oracle) and the series of HP Labs Technical Reports.
White papers Corporations also prepare technical briefings or application outlines aimed more toward influencing purchasing decisions than presenting straight factual information of academic interest. Nevertheless, these can serve a learner as an entry point, much as a general encyclopedia article can help frame a more thorough search for information for an academic exploration.
Bibliographies  and finding aids General  The Collection of Computer Science Bibliographies, brought to you by Alf-Christian Achilles and Paul Ortyl, offers one way to search the technical literature. (The site is in English.)
Search engines While regular Google is quick and usually productive, be sure to try Google Scholar also.
More electronic resources: The World Wide Web is a rich source of information from corporate, academic, and individual contributors. The following may be helpful to you at some point during this course.
Online tutorials Digital System Tutorial An online multimedia course in four parts by Peter Lau, School of Electrical and Information Engineering, University of Sydney.
Karnaugh maps Minimization of Boolean expressions using Karnaugh maps, a tutorial by Charles Welty.
Computer science or engineering instructors at other institutions have developed teaching materials such as slide shows, tutorials, and simulations that you may find helpful. You should be able to find reference and tutorial materials used at other colleges and universities for numerous additional topics pertinent to this course. Be sure to cite them appropriately on your own work that you hand in for credit. Bring to the instructor’s attention additional items that you feel should be incorporated into this course outline at Lawrence.
History lessons CPU Info Center This site prepared by Tom Burd is still up, but has not been updated since 2001 and has a note suggesting that it may go away.
Great Microprocessors of the Past and Present This site is a good place to find an overview of various CPU designs, although it has not been updated since 2005.
History of Computers (Have you found anything useful?)
Reference sites Prefixes for Binary Multiples The National Institute of Standards and Technology clarifies why a file of X megabytes from memory might not fit onto an X-megabyte disk. Available here.
William Stallings This author of books on several computer science topics provides a Computer Science Student Resource Page.