Review for Midterm: Crosscutting Issues

CS 441/641 Lecture, Dr. Lawlor

Many of the same issues come up again and again at different levels of the system.

Data Dependencies limit the available parallelism in the application. Some big dense applications have very simple data flow, and almost no dependencies; while compiler-type or database-type applications can have very complex data flows. Often as applications get smarter, their data dependencies get more complex.
Branching is a problem because the machine doesn't know what will come next. Again, branch complexity varies dramatically between applications: a rendering application might have only a few unpredictable branches per millisecond, while a database might have thousands.
Old code often needs to be run on new machines. A recent survey of supercomputing showed the useful life of their hardware (from procurement to retirement) was about three years; while the useful life of the software (from the start of the project to obsolescence) was about thirty!
Load imbalance is when the majority of the hardware is idle, waiting for one small part to finish. It's a classic problem in any group project, where everybody's waiting for 'that guy' to finish. Hardware doesn't procrastinate, but it's still easy to end up imbalanced due to a poor division of labor.

Here's how these issues are solved at various levels of the machine.

	Data Dependencies	Branching	Old Code	Load Imbalance
Pipelining	Solve with operand forwarding (register file bypass)	Predict or flush	May have poor branch behavior	Breaking up the pipeline stages so they take approximately equal time.
Superscalar	Solve WAW/WAR with register renaming; Tolerate RAW with out-of-order execution.	Predict or die!	May not have enough instruction-level parallelism	Keeping all execution units busy (e.g., big instruction window)
SIMD	Between instructions: see above. Within a register: need data shuffling.	Take both branches, mux into one answer. Branch locality is important.	Needs to be rewritten to use weird SIMD datatypes and branches. See Intel's ArBB (or NVIDIA CUDA) for automatic translation.	Not a problem, since data-parallel is automatically balanced
Multicore	Solve WAW/WAR with privatization; Tolerate RAW with locks or atomics.	Not a problem, since cores can branch independently.	May have multithread shared data problems, making it difficult to run correctly in multicore.	Keeping all the threads busy (e.g., dynamic scheduling)

Other things to know:

Circuit design, from the fine level of electrons and transistors up to the coarse level of ALUs and registers.
Memory hierarchy, from RAM latency versus bandwidth, to multicore cache coherence.

641 students should be familiar with the broad outlines of the topics in each of the research papers I've been sending out.