University:
Boston University
Course:
MET CS 201 | Introduction to Programming
Academic year:

2022
Views:

468

Pages:

14
Author:

nyuga4l68

DATA ACCESS CONFLICTS Conflicting Data Accesses Cause Serialization and Delays • Massively parallel execution cannot afford serialization • Contentions in accessing critical data causes serialization A Simple Example • A naïve inner product algorithm of two vectors of one million elements each – All multiplications can be done in time unit (parallel) – Additions to a single accumulator in one million time units (serial) * Time * * * * + + + …… + * How much can conflicts hurt? • Amdahl’s Law – If fraction X of a computation is serialized, the speedup can not be more than 1/(1-X) • In the previous example, X = 50% – Half the calculations are serialized – No more than 2X speedup, no matter how many computing cores are used GLOBAL MEMORY BANDWIDTH Global Memory Bandwidth Ideal Reality Global Memory Bandwidth • Many-core processors have limited off-chip memory access bandwidth compared to peak compute throughput • Fermi – 1 TFLOPS SPFP peak throughput – 0.5 TFLOPS DPFP peak throughput – 144 GB/s peak off-chip memory access bandwidth • 36 G SPFP operands per second • 18 G DPFP operands per second – To achieve peak throughput, a program must perform 1,000/36 = ~28 SPFP (14 DPFP) arithmetic operations for each operand value fetched from off-chip memory LOAD BALANCE Load Balance • The total amount of time to complete a parallel job is limited by the thread that takes the longest to finish good bad How bad can it be? • Assume that a job takes 100 units of time for one person to finish – If we break up the job into 10 parts of 10 units each and have fo10 people to do it in parallel, we can get a 10X speedup – If we break up the job into 50, 10, 5, 5, 5, 5, 5, 5, 5, 5 units, the same 10 people will take 50 units to finish, with 9 of them idling for most of the time. We will get no more than 2X speedup. How does imbalance come about? • Non-uniform data distributions – Highly concentrated spatial data areas – Astronomy, medical imaging, computer vision, rendering, … • If each thread processes the input data of a given spatial volume unit, some will do a lot more work than others Eight Algorithmic Techniques (so far) You can do it. • Computational thinking is not as hard as you may think it is. – Most techniques have been explained, if at all, at the level of computer experts. – The purpose of the course is to make them accessible to domain scientists and engineers. ANY MORE QUESTIONS?