|
S.No.
|
Topics
|
Lectures
|
Instructor
|
References/Notes
|
|
1
|
Introduction:
Parallel Computations and Architectures
|
01-03
|
SDR
|
[A. Grama, A. Gupta, G. Karypis, V. Kumar]
Chap 2, 4 (the relevant portions, related to what was covered in class)
|
|
|
Microprocessors, Microcontrollers, Models of Computers: the von
Neumann and Harvard models, multi-tasking, time-sharing,
multiprogramming. Processes and threads (a bare-bones introduction)
|
24 Jul (Mon) {lecture#01}
|
SDR
|
|
|
|
Store-and-forward routing, linear rings, wrap-around meshes,
hypercubes. (Cut-through routing is not in course). Ideal time
complexity, and pseudo-code for the non-ideal case (processors
not equally powerful, links not with the same bandwidth).
Basic Communication operations: One-to-all broadcast on a linear
ring, and wrap-around mesh.
|
27 Jul (Thu) {lecture#02}
|
SDR
|
|
|
|
One-to-all broadcast on a hypercube.
Introduction to linear pipelines (data, instruction). Difference
between static and dynamic pipelines. (Only static pipelines will
be in the course). Linear pipeline metrics. The basic pipeline
scheduling problem.
Greedy and non-greedy approaches to pipeline scheduling.
Examples with reservation tables A and B (as in the book).
The depressing worst-case bound: exponential.
|
31 Jul (Mon) {lecture#03}
|
SDR
|
|
|
2
|
Theory of Pipelining
|
03-05
|
SDR
|
[P. Kogge]
|
|
|
The MAL Lemma (Lemma 3-1), and its (easy) proof.
The need for a better (more compact) representation, than a reservation table:
Collision Vectors. State diagrams (modified state diagrams, actually).
FSM modelling of the pipeline scheduling problem.
|
03 Aug (Thu) {lecture#04}
|
SDR
|
|
|
|
Simple cycles and compound cycles. Lemma 3-2, and its proof, and
physical significance. Finding all greedy cycles. Lemma 3-3 and
its proof. Summary of all the lemmas, and the overall practical
significance of the above exercise.
|
10 Aug (Thu) {lecture#05}
|
SDR
|
|
|
|
|
14 Aug (Mon)
|
---
|
(No class: make-up class on 19 Aug (Sat))
|
|
3
|
RISC Pipelining
|
06-07
|
SDR
|
[Patterson's paper]
|
|
|
RISC Pipelining: history. The trend towards CISC. Factors leading
to RISC.
|
17 Aug (Thu) {lecture#06}
|
SDR
|
|
|
|
RISC pipeline hazards: structural, data and control.
The Delayed Branch and Optimal Delayed Branch.
Introduction to software issues for RISC pipelines.
|
19 Aug (Sat) {lecture#07}
|
SDR
|
Make-up class (in lieu of missed 14 Aug (Mon) class): 09:00am-10:30am.
Venue: II-241 (EE Committee Room)
|
|
4
|
RISC Pipelining: Deeper Issues
|
07-11
|
SDR
|
[Hennessy-Patterson]
|
|
|
Software issues for RISC pipelines. Compiler stages. Compiler
optimisations.
|
21 Aug (Mon) {lecture#08}
|
SDR
|
|
|
|
Software issues: Data dependences, Name dependences
(Anti-dependences, Output dependences), Control dependences.
Pipeline scheduling and loop unrolling: an introduction.
|
24 Aug (Thu) {lecture#09}
|
SDR
|
|
|
|
Loop unrolling and pipeline scheduling: in isolation, and in
combination. Example, issues.
|
28 Aug (Mon) {lecture#10}
|
SDR
|
Early class 07:30am-09:00am
|
|
---
|
Minor 1
|
01 Sep (Fri)
|
---
|
---
|
|
5
|
Caches
|
11-17
|
SDR
|
[Hennessy-Patterson]
Cache Basics: Appendix B: Review of Memory Hierarchy.
Sections B.1 and B.2
Multiprocessor Cache Coherence: Chapter 5: Thread-Level
Parallelism.
Sections 5.1 and 5.2
Some lecture notes [Internal links]:
[a],
[b],
[c],
[d],
[e],
[f]
(IITD only)
|
|
|
Concluding RISC Pipelining: A mere mention of branch
predictors.
Caches: reiteration of the von Neumann and Harvard Architectures.
Caches for general purpose processors and DSPs. Cache blocks and
memory blocks, and address spaces. The four basic cache
questions. Cache organisation: direct mapped, fully associative
and set associative. Cache block replacement.
|
04 Sep (Mon) {lecture#11}
|
SDR
|
|
|
|
Cache block replacement strategies. Write strategies: Write-Back
and Write-Through.
|
07 Sep (Thu) {lecture#12}
|
SDR
|
|
|
|
Write-Allocate and No-Write-Allocate.
Two basic Cache formulae, and their physical significance.
|
11 Sep (Mon) {lecture#13}
|
SDR
|
|
|
|
Split Caches and Unified Caches: the complete loaded example!
|
14 Sep (Thu) {lecture#14}
|
SDR
|
|
|
|
Multiprocessor Cache Coherence: SMP architecture and its
significance, the issue of cache coherence for Write-Back
caches, and the popular Write Invalidate Protocol.
|
18 Sep (Mon) {lecture#15}
|
SDR
|
|
|
|
The Write Invalidate Protocol (contd)
|
21 Sep (Thu) {lecture#16}
|
SDR
|
|
|
|
The Write Invalidate Protocol (contd)
|
25 Sep (Mon) {lecture#17}
|
SDR
|
|
|
6
|
Vector Processors, SIMD Multimedia Extensions, GPU Architectures
|
18-26
|
SDR
|
[Hennessy-Patterson] Chapter 4
|
|
|
Vector Processors, SIMD Multimedia Extensions, GPU Architectures:
an introduction. History.
I. Vector Architectures.
VMIPS
|
28 Sep (Thu) {lecture#18}
|
SDR
|
|
|
---
|
Minor 2
|
06 Oct (Fri)
|
---
|
---
|
|
|
DAXPY as an important operation. Chaining, Lanes, Convoys.
Clarifications on the Write Invalidate Protocol for Multiprocessor
Cache Coherence.
|
09 Oct (Mon) {lecture#19}
|
SDR
|
|
|
|
Important Questions for Vector Architectures.
1. Lanes for > 1 element per cycle
2. Vector Length Registers: Handling loops not equal to 64
3.`IF' (conditional) inside code to be vectorised
|
12 Oct (Thu) {lecture#20}
|
SDR
|
|
|
|
4. Memory Banks: for Bandwidth to Vector Load/Store Units
|
23 Oct (Mon) {lecture#21}
|
SDR
|
|
|
|
5. Multiple Dimensional Matrices
6. Gather-Scatter
7. Compilers and Vector Computers
|
26 Oct (Thu) {lecture#22}
|
SDR
|
|
|
|
II. SIMD Instruction Set Extensions.
Historical Perspective. Why have they been successful?
|
30 Oct (Mon) {lecture#23}
|
SDR
|
|
|
|
Discussion on threads (and processes), and virtual memory:
instructions can be paused
|
02 Nov (Thu) {lecture#24}
|
SDR
|
|
|
|
III. Graphics Processing Units (GPUs).
__host__ and
__device__/__global__
|
06 Nov (Tue) {lecture#25}
|
SDR
|
|
|
|
GPUs: an example of grids, thread blocks and SIMD parallelism
with a vector multiplication example.
|
09 Nov (Thu) {lecture#26}
|
SDR
|
|
|
7
|
Warehouse-Scale Computers
|
27-27
|
SDR
|
[Hennessy-Patterson] Chapter 5
|
|
|
Warehouse-Scale Computers
|
13 Nov (Mon) {lecture#27}
|
SDR
|
|
|
|
---
|
16 Nov (Thu) {lecture#28}
|
SDR
|
|
|
---
|
Major
|
21 Nov (Tue)
|
---
|
---
|