Parallel Programming 4

Performance Optimization : Locality, Communication, and Contention

Total communication time : overhead + occupancy + network delay

Pipelined communication에서 memory bandwidth-bound execution!

 

Arithmetic intensity = amount of computation(e.g., instructions)/amount of communication(e.g., bytes)

-> 높을수록 좋다

Inherent communication

오른쪽의 grid가 communication cost가 더 크다

 

• Inherent communication : information that fundamentally must be moved between processors to carry out the algorithm given the specified assignment
• Artifactual communication : all other communication

4개의 elements를 계산할 때마다 loads three lines을 해야한다.

다음과 같이 grid를 계산한다면 6개의 elements를 계산할 때마다 load two cache lines

즉, spatial locality 를 잘 활용하자!

 

Contention

• Flat communication
• Tree structured communication

 

Reducing communication costs

• Reduce overhead of communication to sender/receiver
• Reduce latency of communication
• Reduce contention
• Increase communication/computation overlap
  • asynchronous communication, pipelining, multi-threading, pre-fetching, out-of-order execution