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