Parallelism Concepts

A crash into Parallelism, some terms are listed and very basic concepts are introduced.

All the pics and contents are not original. The contents of the whole series are mainly collected from:

NVIDIA CUDA初级教程视频

CIS 565 2019

CMU 15-418/618 (2018)

Terms

Flynn’s taxonomy

some terms

• Task
• Parallel Task
• serial execution
• parallel execution
• shared memory
• distributed memory
• communications
• synchronization
• granularity
• observed speedup
• parallel overhead
• scalability

Introduction

Memory

• shared memory
• distributed memory
• hybrid distributed-shared memory

parallel coding models

• shared memory model
• threads model (OpenMP)
• message passing model (MPI)
• data parallel model (Hybrid)

Design a parallel system

• choose manually or auto parallel
• understand the problem and algorithm
• division of data and problem
  • based on specific problem
  • lots of methods
• communication and synchronization design
  • methods
    • broadcast, scatter, gather, reduction
  • barrier
  • lock/semaphore
  • synchronous communication
• data reliance
• overhead balance
• granularity
• IO
• cost
• performance analysis and optimisation

Amdahl's Law

The observed speedup is depend on the part of program that can be paralleled. \[ Speedup_n = \frac{1}{1-P} \] with N processors, set S as the serial proportion, \[ Speedup = \frac{1}{\frac{P}{N}+s} \] The scalability is limited by P: