What is Parallel Computing?
A form of computation: 1) Large problems divided into smaller ones; 2)Smaller ones are carried out and solved simultaneously
Why parallel computing?
- Save time (execution time) and money!Parallel program can run faster if running concurrently instead of sequentially.
- Solve larger and more complex problems!
Utilize more computational resources
Why parallel computing is the only way, so far, to achieve high performance computing
- Applications that require HPC are naturally parallelizable, and Data cannot fit in memory of one machine Computer systems
- Physics limitation: has to build it parallel. and Parallel systems are widely accessible
Three pillars of science: theory, experiment and computer simulation.
What is Flop/s (FLOPS)? What is Top500?
So far the performance of the fastest supercomputing in the Top500 is around 93 a) Petaflops, b) Teraflops, c) Gigaflops, d) exaflops
How to compute CPU and machine peak performance?
How to measure and calculate application performance?
How Top500 machines are being ranked?
How to calcualte HPC performance and power efficiency
The difference of HPL (Top500), HPCG, Green500, and Graph500 Ranking
What is Moore's Law and why we cannot enjoy the performance improvement over the years as before with regards to the Moore's Law (Problems of traditional ILP scaling)
Since 2002-2005, what is the hardware solution for overcoming the performance and scaling challenges from traditional ILP? (multicore)
- OpenMP multithreading execution model: fork-join
OpenMP multithreading memory model: shared memory. Threads each has its own private memory and all threads have direct load/store access to the shared memory region.
Given the following OpenMP parallel program
#pragma omp parallel private(i) num_threads(4) schedule(static, 10)
for (int i = 0; i < 100; i++ {
a[i] = i;
}
Which thread would execute iteration 76? Which chunks of iterations would thread 2 execute? Fill in the following table?
| Thread |
Chunks |
| 0 |
[0-9], [40-49], [80-89] |
| 1 |
|
| 2 |
|
| 3 |
|
Optimizing the following code by removing redundant barriers:
#pragma omp parallel private(i)
{
#pragma omp for
for(i=0;i<n;i++)
a[i] +=b[i];
#pragma omp for
for(i=0;i<n;i++)
c[i] +=d[i];
#pragma omp barrier
#pragma omp for reduction(+:sum)
for(i=0;i<n;i++)
sum += a[i] + c[i];
}
Solution:
#pragma omp parallel private(i)
{
#pragma omp for nowait
for(i=0;i<n;i++)
a[i] +=b[i];
#pragma omp for nowait
for(i=0;i<n;i++)
c[i] +=d[i];
#pragma omp barrier
#pragma omp for nowait reduction(+:sum)
for(i=0;i<n;i++)
sum += a[i] + c[i];
}
What is the final results of IS: (2+8+9+10). For LASTPRIVATE(IS), it means the last thread who executes the last iteration will return the IS value to the master thread after the parallel region. So the value of IS depends on which thread executes the last iteration (10). One, the most common one, way of chunking the loop is to have [1-4] for thread 0, [5-7] for thread 1 and [8-10] for thread 3. Thus the thread that executes the last iteration 10 finishes iterations 8,9,10, and the IS value is 2 (coming from LASTPRIVATE(IS)) + 8 + 9 + 10. It is also possible that thread 3 execute [7-10] or thread 0 execute [1-3,10], which will yield different results for IS.
IS = 2
C$OMP PARALLEL DO FIRSTPRIVATE(IS)
C$OMP& LASTPRIVATE(IS) NUM_THREADS(3)
DO J=1,10
IS = IS + J
CONTINUE
C$OMP END PARALLEL DO
print *, IS
Understand false-sharing and first-touch policy
In Assignment #3, the 2-dimension array is decomposed using row-wise distribution among all the MPI processes. E.g. For array u[256][256] and 4 processes, and each MPI process will computate 256/4=64 rows of data. Check MPI Exercise slide
Explain why parallel execution time also depends on the platform and communication parameters. (Explain why analyzing parallel program execution time is more complicated than analyzing sequential program).
Give examples of parallel overheads
Explain each of the five metrics of parallel program analysis: Execution Time, Overhead, Speedup, Efficiency, and Cost
Fill in the following tables, assuming serial execution time is 100
| Num of Processors |
Parallel Execution Time |
Speedup |
Efficiency |
Cost |
Parallel Overhead |
| 2 |
60 |
|
|
|
|
| 4 |
40 |
|
|
|
|
| 8 |
20 |
|
|
|
|
Explain what is linear speedup.
Why superlinear speedup is posibble? Using examples to explain.
What is Amdahl’s Law? A program has three portions, sequential portion, 30% that can be optimized 4 times and 50% can be accelerated by 2 times, what is the overall speedup using Amdahl's Law.
The sequential portion is 1 - 30% - 50% = 20%
Speedup = 1 / (0.2 + 0.3/4 + 0.5/2) ~= 1.9
