CS/EE 5515
Fall 1995
Index numbers Meeting time Meeting location
CS: 5487, EE: 6027 MWF 1-1:50 Randolph 207
Course Description:
This course covers advanced computer architecture. Most of the course material discusses methods of increasing the throughput and decreasing the execution time of numeric computations.
Computer architects have traditionally depended on intuition and experiences from past architectures to guide design of new architectures. A more recent trend in architecture is to use quantitative design, based on extensive measurement of existing programs. However, very little "theory" underlies architecture. Consequently the course is a survey of techniques for achieving high performance: pipelining, vector processing, and multiprocessing. Each topic will be presented through a discussion of basic principles, augmented with case studies of commercial architectures.
Instructor:
Dr. M. Abrams
641 (later 508) McBryde Hall
231-8457; abrams@cs.vt.edu
Office hours: MWF 2-3 p.m., and by appointment
If you wish to pop in and ask a question outside of office hours without an appointment, I can give you more time if you visit in the afternoon. However, the day before and the morning before an exam, I am always willing to answer questions by phone or in person without making an appointment.
GTA:
Mr. Xiangdong Liu
liu@csgrad.cs.vt.edu
Office hours: 11:00-12:00 Tues, 9:00-10:00 Thurs, McB 116
Texts (required):
[HP] J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. San Mateo: Morgan Kaufmann Publishers. 1990.
[H] K. Hwang, Advanced Computer Architecture, McGraw Hill, 1993
Additional readings will be placed on reserve in the library, and in some cases, distributed in class.
Strategies for Success
Students are encouraged to meet in study groups to understand the material, review before exams, and to discuss approaches to solving the homeworks. However, each student must work out homework solutions and exam problems independently from classmates.
One challenge that arises in teaching an architecture course cross listed in EE and CS is that EE and CS students have different backgrounds. EE students will do some problems better than CS students, and vice versa. I will try to balance the homework and exam problems to make the course "fair" for both groups of students, based on my undergraduate EE and graduate CS background.
As explained below, homeworks are collected at the start of class, after which we will go over the homework solution. You may wish to make a copy of your homework to refer to as we go over the solution.
Prerequisites:
The equivalent of CS 4504 is a prerequisite. Therefore you should be familiar with virtual memory; multiprogramming; assembly language; microprogramming; basic memory, processor, and I/O subsystem organizations; RISC and CISC architectures; and basic knowledge of digital logic and bus organizations. You are responsible for determining if you have satisfied the prerequisite. When I've taught the course in the past, some students have had a deficiency (i.e., CS students with no knowledge of microprogramming, or EE's with little exposure to virtual memory), which has hurt their performance in the class.
Honor System:
All work is to be done under the provisions of the Virginia Tech Honor System. Students can discuss the interpretation of an assignment, however solutions must be independent.
Never copy more than 3 words from any reference material onto any written work in this class without enclosing the passage with quotes and listing a citation for the source.
Whenever I learn that a student has violated the honor code, I am obligated to report the violation. If you fall behind, have too many deadlines, can't find time for a job along with classes, please let me know -- but don't cheat.
Grading:
Homework (lowest HW dropped) 25%
Mid-term Exam (27 September, to be returned on last drop day, 29 September) 35%
Comprehensive final exam (Friday, 8 December , 1:05-3:05) 40%
There will be an opportunity to do an extra credit project worth a maximum of 3% involving use of a simulator for the DLX instruction set.
If you have an excused absence from the mid-term exam, the weight of the exam will be added to the final exam weight. Examples of excused absences include religious holidays, participation in university sports, attending CS or EE-related conferences, death in the family, or illness verifiable with a doctor's note.
Homework assignments are due at the start of class. I will go over the solution after collecting the assignment; therefore one cannot turn in a homework late. If you have an excused absence from a class, turn in the homework assignment prior to the class session. Generally you have one week to work on each homework.
Reference Materials
The following texts and papers will be put on reserve in the Newman library whenever they are referred to in class.
[BT] D. P. Bertsetkas and J. N. Tsitsiklis, Parallel and Distributed Computation, Prentice-Hall, 1989, pp. 10-11.
[HB] K. Hwang and F. Briggs., Computer Architecture and Parallel Processing, McGraw-Hill, 1984.
[HS] W. D. Hillis and G. L. Steele, "Data Parallel Algorithms," CACM 29 (12), Dec. 1986, pp. 1170-1183.
[K] L. Kohn. "Architecture of the Intel i860 64-bit Microprocessor," Proc. COMPCON Spring 89, March 1989.
[K1] L. Kohn and N. Margulis, "Introducing the Intel i860 64-bit Microprocessor," IEEE Micro, Aug. 1989, pp. 15-30.
[Q] M. J. Quinn, Parallel Computing: Theory and Practice, 2nd ed., McGraw-Hill, 1994.
[S] H. S. Stone, High-Performance Computer Architecture, 3nd edition, Addison-Wesley, 1993.
Course Outline:
Note: I will be out of town on 18 September and 6-8 November.
Mandatory Additional
Week Topic Reading References[1]
Part 1: Introduction
1-2 Introduction; taxonomy; PRAM [H] Ch1 (skip 1.4.2) [Q] Ch1, 2.1 (PRAM),
[BT] pp. 10-11 (complexity)
Embedding programs; [Q] Ch. 2
SIMD programs [HS]
Part 2: Pipelining
3 Basic concept of pipelining [HP] 6.1 [S] 3.1
Big and little Endian representations
DLX instruction set [HP] 4.5, 5.2
Basic steps of DLX execution [HP] 5.3
4 DLX pipe [HP] 6.2
Avoiding structural hazards in DLX[HP] 6.3
Pipeline hazards [HP] 6.4 to p. 269
Interrupts [HP] 5.6, 6.5 to pp. 280
Control of pipelines [H] 6 to 6.2.2 [S] 3.4.1-3.4.3, [HB] 3.3.5
[HP] 6.7-6.8[2]
Go over Homework Set #1
5 Continue control of pipelines
Inserting delays to improve [H] 6.2.3 [S] 3.4.4 to pp. 165 pipeline performance [HB] 3.3.6
6 Go over Homework Set #2
Exam #1 review
Exam #1
Go over Exam #1
7 Brief discussion of miscellanea:[3]
Dynamic pipe scheduling [HP] 6.7 to pp.307
Loop unrolling [HP] 6.8 (pp. 315-318)
Superscalar [HP] 6.8 (pp. 318-322)
Very Long Instruction Word (VLIW) [HP] 6.8 (pp. 322-328)
8 Control hazards [HP] 6.4 pp. 270-278, [S] 3.5.1
[HP] 6.7 pp. 307-314
Case study: [K]
DEC alpha or Intel i860
Part 3: Parallel Processing Overview
9-10 System Interconnect Architectures [H] 2.4
Performance Measures [H] 3.1
Speedup Performance Laws [H] 3.3
Part 4: MIMD: Multiprocessors and Multicomputers
11 Multiprocessor interconnects [H] 7.1
Go over Homework #3
12 Cache coherence [H] 7.2 to page 353
Case study: [H] 7.3
Three multicomputer generations
Part 5: Vector and SIMD Computers
13-14 Introduction to vector processors [H] 8.1
Case study of vector processor:
DLX-V [HP] 7.1 to 7.3, pp. 379-380
Case study: [H] 8.4
SIMD computer organizations
15 Go over Homework Set #4
Review for final exam