Midterm Topic Outline

Because midterm is a take-home quiz, nothing to prepare really. You can use this document as a guide to the reviewing of the book content. You may also use use this outline as a quick reference to find where to locate the book sections when working with on the midterm.

Types of Questions

• Terminology - Show your knowledge of common terminology Example: network topologies, SIMD, etc.
• Understanding and application Example: Computing performance metrics
• Design Example: design a cache aware algorithm
• Parallel software * Compiling with OpenMP * Write a complete OpenMP program * Running parallel program

Performance Model

Calculations of key performance metrics. Know some terms.

• Communication cost model
• Parallel time complexity
• Speedup
• Efficiency
• Strong scaling vs Weak scaling
• Amdahl’s law

Parallel Hardware

• SISD, SIMD, and MIMD
• Interconnection networks: ring, toroidal mesh, hypercube, fat tree
• Shared memory vs distributed memory vs distributed shared memory
• Non-uniform memory access
• Cache coherence and false sharing
• Race conditions

Parallel Algorithms

• Integration – trapezoid example
• Matrix operations * Matrix multiplication * Matrix addition * Matrix-vector multiplication
• Broadcast

Optimizing for Cache

• Ideal cache model and cache complexity
• Improving cache complexity through loop reordering
• Row major vs column major ordering

Single Core Optimization

• Using -O3 as an optimization flag
• Using memcpy and memset

OpenMP Programming

• Directives: parallel, for, critical
• Clauses: private, reduction, schedule
• Library functions: omp_get_max_threads, omp_get_thread_num, omp_get_num_procs, omp_set_num_threads
• Header file: omp.h
• Compilation command: -fopenomp
• Running parallel code