Analyzing Space Bounds

6.895 Theory of Parallel Systems Lecture 6 Analyzing Space Bounds Lecture Summary 1. Bounds on space requirements We look at upper and lower bounds on the space requirements of parallel Cilk programs. 2. Memory Allocators We compare different types of heap storage memory allocators, and we examine the Hoard memory allocator in detail. 3. Project Ideas We present several project ideas based on the topics in these notes. 1 Bounds on space requirements In this section, we look at upper and lower bounds on space requirements for Cilk programs. We begin with a general upper bound and then consider a tighter bound for a specific matrix multiplication algorithm. Next, we look at a lower bound on general multithreaded computations. Finally, we mention the Blelloch-Narlikar algorithm, which provides a better upper bound on space for Cilk-like dags. General upper bound The Cilk scheduler is a busy-leaves scheduler. As a result, we can show an upper bound on space which is linear to P, the number of processors in the system. We can view the execution of a parallel program as a cactus stack. Let S₁ be the amount of space required to execute the program on a single processor. Figure 1 shows that S₁ can never exceed the maximum height of the stack. When run on a P-processor system, the Cilk scheduler ensures that there are at most P leaves allocated. From Figure 1, we see that there are at most P stacks that have been allocated by the system, where each stack has a maximum height of S₁. Thus, we derive the general upper bound of SpP-S1. Applying the general upper bound on space We apply the general upper bound for space requirements to the divide-and-conquer matrix multiplication algorithm. Each iteration of this algorithm on an nxn matrix spawns & multiplications of submatrices of size n/2 x n/2. For each of these multiplications, we need a temporary matrix to store the result. For serial execution, we can describe the total space used with the following recurrence, illustrated by the recursion tree in Figure 2: S₁(n) = S₁()+² = Θ(π²). Therefore, a P-processor execution uses O(PS1) O(Pn²) space. (1) Figure 1: A cactus stack. Cilk uses a busy-leaves scheduler, which means that at most P leaves are scheduled at any given time. The shaded stack frames represent allocated memory, and the darker frames represent leaves currently being executed by the processors. In this example, P = 3. Figure 2: The recursion tree for the divide-and-conquer matrix multiplication algorithm on a single processor. The values shown indicate the space used at each level. Stronger bound for divide-and-conquer matrix multiplication We can derive a better bound on space for the divide-and-conquer algorithm. The general upper bound we derived earlier counts the maximum height (S₁) of the stack P times. As a result, many of the frames in the shallower levels are counted more than once; the top level frame, for example, is counted P times, but its space is only allocated once. Since shallower levels require more space than deeper ones, the problem of double-counting is worse towards the top of the tree. This poor accounting results in a much weaker bound than we can achieve. Consider the worst case for the divide-and-conquer algorithm. Given that space requirements drop drastically at lower levels of the tree, the worst case is fully parallel at the top until there are P leaves, then serial thereafter. The recursion tree in /figrefmmult worstcasespace illustrates this transition. We can solve the recursion tree by considering the space used at each level. The top level requires n ^ 2 space. The next level requires 8 * (n / 2) ^ 2 space. If we continue this patten, the level with P leaves requires 8 ^ log_6(P) * (n / (2 ^ log_8(P))) ^ 2 = P * (n / (P ^ (1/3))) ^ 2 since the depth of this level is log_s(P) The serial execution following total space. only a constant times (n / (P ^ (1/3))) ^ 2 spaceSumming the space for all the levels yields O(n ^ 2 * P ^ (1/3)) Space per level a ^ 2 = n ^ 2 8 * (n/2) ^ 2 = 2n ^ 2 64 * (n/4) ^ 7 = 4n ^ 2 log_i(P) lgn 00 Pleaves Figure 3: The worst case for the divide-and-conquer matrix multiplication algorithm running on P processors. The execution is fully parallel until we reach P leaves, after which the execution continues serially on cach processor (since Cilk uses a busy-leaves scheduler). Lower bound We now consider a lower bound on space for computation dags. We know that Cilk produces series-parallel execution dags. Earlier, we showed that a busy-leaves scheduler results in an expansion of space that is linear to the number of processors that is, S_{P} <= P*S_{1} Both of these properties are necessary to get good space bounds; without these properties, we can find a multithreaded computation such that T_{P} <= T_{1} / 2 implies S_{P} \approx sqrt(T_{1}) In other words, space grows with work. Definition 1 (Depth-first computation dag) In a depth-first computation dag, a left to right depth-first traversal visits all threads on which a given thread depends before that thread. In other words, there exists a serial execution for the dag. The dag does not have to be series-parallel. Figure 4 shows an example of a depth-first computation dag. The edge from node A to D cannot exist in the graph because it violates the dependency condition above; namely, that a thread (node D) is only visited after all threads on which it depends (nodes K and C) are visited first. Clearly, a left to right depth-first traversal cannot visit both C and K before visiting D.