Implementation Mechanism
In this lecture, we first consider the final step of patterns of parallel programming — implementation mechanism, which is tied closely to particular microarchitectures. Generally, we have three major types of parallelisms, and we can explore them in both hardware and software perspectives.
- ILP
- HW: OoO, dataflow, VLIW
- SW: within in the code
- DLP
- HW: SIMD, Vector
- SW: loops, independent tasks on disjoint data
- TLP:
- HW: multi-core with multiple sequences
- SW: DLP + producer-consumer chains
Hardware has the final say on how to extract parallelism from the software. Furthermore, it can convert one form of parallelism into another one: Easy path: DLP → TLP → ILP Hard & inefficient path: ILP → TLP → DLP (Reason: Requires analysis and speculation. Predication is a tool used for this type of conversion at the expense of losing efficiency.) There are many examples of conversion in software and hardware:
- Software:
- Loop unrolling (DLP → ILP)
- Software pipelining (DLP/TLP → ILP)
- Creating threads (DLP → TLP)
- Hardware:
- SMT - Simultaneous Multi-Threading (DLP/TLP → ILP)
- TLP - Thread-Level Speculation (ILP → TLP)
How easily are the 6 supporting structures and 4 implementation patterns we talked about in previous lectures mapped to the three hardware implementation mechanisms? Refer to the slides!
Molecular Dynamics Simulation
Problem Characterization
As a wrap up for the entire topic of parallelism in software , we consider a real world application, molecular dynamics, to understand how we can apply the patterns for parallel programming to actually parallelize it.
Molecular Dynamics is a form of computer simulation used in Biology and Chemistry. It models atoms and molecules and allows them to interact for a period of time under known laws of physics, giving a view of the motion of the atoms.
The goal of molecule simulation is to calculate the force affecting each atom in the system. Ideally, we want to calculate the interactions of every pair of atoms, which would lead to a computation complexity of O(n2). Therefore, as an approximation, we only count forces between atoms located closer than a certain distance ( r ) and assume those more than r do not interact with each other. This would lead to a computation complexity of O(nr3).
The first job is to find concurrency. Across atoms, computation of forces for them are completely independent. With in each atom computation, the computation is additive as follows:
F = 0; for(all neighbor atoms i) F += f(i);
This is a reduction operation, and could be implemented in parallel.
In order to characterize our algorithm, we use speedup, parallel efficiency and work efficiency. The latter two are defined as follows.
- Parallel efficiency = total resources used / total resources available
- Work efficiency = total computation to be performed originally / total computation to be performed in new algorithm
Note that the work efficiency of a parallel algorithm is compared with an optimal sequential algorithm. Typically,
Since the parallelism across atoms is straightforward, we here consider how to parallelize reduction operation.
Suppose we have N processor elements (PE) as many as the number of elements to be reduced. The total parallel computation time would be logn. Therefore, speedup = (n / logN).
Since at step i, the number of actually used PE is N/i, we can calculate the parallel efficiency = 2n / n*logN. Also, regardless of which algorithm we use, the total units computation is always n + (n - 1), assuming all kinds of operations take the same amount of time. Therefore, the working efficiency in this case is 1.
Now let’s consider the case with P processing elements where P < N. In this case, speedup would be n / ((n / p) + (n / 2*p) + (n / 4*p) + 1 + epsilon) = p / 2. Also, intuitively, with #PEs fewer than N, PEs are more “busier” with their work (since there are fewer workers now!). Accordingly, parallel efficiency is better than with N PEs. Work efficiency is still 1.
Implementation Details
Now let’s consider more details of our algorithm, especially how to construct the data structure. The most space efficient data structure would be a global array, which is split up into multiple sections with each section holding the neighbor atoms of one atom to be computed. Naively, three steps involved to build this data structure are 1) creating local arrays for all atoms be to processed; 2) finding boundary points of different setions; 3) copying local arrays into a global memory.
For simplicity, let’s assume we are able to parallelize step 1, and the output of step 1 is an array, where each element is the length of corresponding local array. Step 2 takes this intermediate array (we call it I1) as the input and outputs another intermediate array (we call it i2) with each element indicating the boundary point. For example, if I1 = {3, 1, 7, 1, 4, 1, 6, 3}, then I2 should be {0, 3, 4, 11, 12, 16, 17, 23, 26}. We now study how to parallelize step 2.
The key operation involved in step 2 is known scan, or prefix sum. The first attempt to parallelize scan operation we discussed in class is as follows. Note that the ith element in I2 is the sum of all elements form 1st to (i-1)th in I1. We explore this fact by adding pairs of elements with S elements apart, starting from S = 1 and doubling S at each iteration. After logN (N is the number of elements in I1) steps, we can get I2.
This algorithm is simple, but very work inefficient. A quantitative analysis is provided in the lecture slide, but intuitively it could be understood by thinking about the number of redundant computations performed. For example, the 4th and 5th elements in I2 both require the sum of the 1st and 2nd elements in I1. In the original sequential algorithm, this addition only needs to be performed once; whereas in our parallel algorithm, it has to be performed twice for 4th and 5th elements respectively, resulting in redundant operations and thus low work efficiency.
Then we briefly went through a more common parallel algorithm based balanced tree. Please refer to the slides!
