Parallel Programming 2

Parallel Programming Basics

Problem Decomposition -> Assignment -> Orchestration -> Mapping

Problem Decomposition

Break up problem into tasks that can be carried out in parallel

Create at least enough tasks to keep all execution units on a machine busy

Identifying Dependencies!!

Amdahl’s Law : dependencies limit maximum speedup due to parallelism

순차적으로 실행되어야 할 필요가 있는 부분이 있다면 병렬적으로 처리가 불가능하다.

따라서 maximum speedup due to parallel execution <= 1/s

S = the fraction of total work that is inherently sequential

Sequential한 부분이 클수록 Speedup이 제한된다.

In most cases , the programmer is responsible for decomposing a program into independent tasks

Assignment

Assigning tasks to threads

Goals : achieve good workload balance, reduce communication costs

Can be performed statically (before application is run) or dynamically

Orchestration

• Structuring communication
• Scheduling tasks
• Organizing data structures in memory

Goals : reduce costs of communication/sync, preserve locality of data reference, reduce overhead, etc.

Mapping

Mapping “threads” to hardware execution units

• Mapping by the operating system
  • map a thread to HW execution context on a CPU code
• Mapping by the compiler
  • map ISPC program instances to vector instruction lanes
• Mapping by the hardware
  • map CUDA thread blocks to GPU cores