Ce.scu.ac.ir

CS 554/CSE 512 Homework Assignment 1 — Solutions 1. (a) If one worker can dig a post hole in one hour, can sixty workers dig the post Answer : No, because so many workers cannot effectively share such a confinedspace. In effect, there is insufficient “bandwidth” to support this level of con-currency, resulting in excessive contention for a shared resource, namely accessto the hole. Moreover, the hole must be dug sequentially, in that upper portionsof the hole must be dug before lower portions.
(b) If one worker can drive a railroad spike with a sledgehammer in two minutes,can two workers with sledgehammers drive the spike in one minute? Why? Answer : Yes, by alternating blows, with one worker striking the spike whilethe other is on his backswing. In effect, each swing is a two-stage pipeline(backswing and forward swing), so that both workers can perform at full speedwithout interfering with each other, and hence the job is done in half the time.
(c) What accounts for the difference between the answers to parts (a) and (b)? Answer : The degree of concurrency required. In part (a), two workers mightwell be able to halve the time by alternating access to the post hole, while in(b), sixty workers obviously could not work effectively to drive the same spikeconcurrently.
2. Suppose an automobile assembly line has 15 stations, each of which requires six minutes to perform its portion of the assembly of a given car. How long doesit take to build a single car? How long does it take to build 10 cars? 100 cars?1000 cars? Explain your answers.
Answer : It takes 90 minutes to build one car. In general, it takes 90+6(n−1) =84 + 6n minutes to build n cars. Thus, it takes 144 minutes to build 10 cars,684 minutes for 100 cars, and 6084 minutes for 1000 cars. As the number ofcars becomes very large, the time per car approaches six minutes.
3. A conventional oven can bake one potato in one hour or six potatoes in one hour. A microwave oven can bake one potato in ten minutes or six potatoes inone hour. Explain these different behaviors in terms of the physical processesinvolved. What analogies can you draw with serial and parallel computers? Answer : A conventional oven maintains a constant temperature but may ex-pend a variable amount of energy to do so, depending on the contents of theoven. It heats a potato by a relatively slow process, diffusion of heat from thesurface into the interior of the potato. Because the temperature is held constant,the potatoes cook at the same rate regardless of the number of potatoes.
A microwave oven heats a potato by a much faster process (radiation), but uses afixed amount of energy, which is shared by however many potatoes may be in the oven. Thus, a single potato will cook rapidly, but a larger number of potatoeswill cook more slowly (indeed, they may as well be cooked sequentially).
A microwave oven is somewhat like a fast uniprocessor, whereas a conventionaloven is somewhat like a multiprocessor with relatively slow processors. Andtrue to the analogy, much of the capacity of a conventional oven is wasted muchof the time.
4. Suppose that a classroom of p students, each sitting at a desk, is to compute the sum of n numbers, each of which is written on an index card. In one unit oftime a given student can either add two numbers and write the sum on a card,or pass a card to another student at an adjacent desk (i.e., at most an arm’slength away). Assuming that n ≥ p, derive an expression for the minimum timeto compute the overall sum. Specify the initial distribution of cards and thearrangement of desks assumed in your answer.
Answer : Despite its relatively simple statment, this question has a surprisinglycomplicated answer, and it depends on various assumptions one may make. Forexample, it seems reasonable to assume that the arrangement of desks is planar(i.e., we do not permit desks to be stacked vertically!). The usual arrangementof desks in a classroom is a two-dimensional array, but other arrangements arepossible, including a one-dimensional array, a ring, or a tree. We have alreadyassumed that a single student cannot compute and communicate simultaneously,so it seems reasonable to assume that a single student can neither send norreceive more than one card in one time step. Finally, the initial distribution ofcards was left unspecified. Let us assume that the cards are distributed amongthe students as unformly as possible, with each student having either n/p or n/p , so that all students participate (which may not actually yield the best possible solution unless n is sufficiently larger than p). Further remarks on thisassumption are given below.
Under the assumptions just made, the first step in summing the numbers is forall students to compute the sums of their share of the numbers, which takestime n/p − 1. Now the problem is reduced to that of combining these localresults to arrive at the overall sum, and this process depends on the particulararrangement of desks.
First, consider a one-dimensional array of p desks. The students on both endsof the array pass cards containing their totals to the next students toward thecenter, who receive the cards, add the new figures to their initial sums, and passthe resulting cards along to the next students, etc. The final answer ends upat the center desk if p is odd, or one of the two middle desks if p is even. Thetotal time required for this phase is 2 (p + 1)/2 . A ring arrangement of thep desks gives the same answer, since the added connection offers no advantagefor this particular problem.
A two-dimensional arrangement of the desks works similarly, except that partialsums are first collected along rows, say, using the one-dimensional algorithm,and then the final sum is collected along the resulting column, again using theone-dimensional algorithm. If the array of desks is pr × pc, where p ≤ pr · pc,then the total time required for this phase is 2( (pr + 1)/2 + (pc + 1)/2 ),assuming that a “center” desk is occupied in each row and column and thestudents are seated contiguously. The final answer ends up at the “center” ofthe two-dimensional array.
Finally, consider a binary tree arrangement of the desks. Let k be the number oflevels in a (possibly incomplete) binary tree with p nodes, i.e., k is the smallestinteger such that p ≤ 2k − 1. Each leaf node sends its local sum to its parent,which adds them to its own total and then passes the new partial sum to itsparent, and so on up to the root of the tree, where the final total ends up. Thetotal time required for this phase is 4(k − 1) if p is not a power of two, and4(k − 1) − 2 otherwise.
If we relax the assumption that the cards are uniformly distributed initially,then minor additional optimizations are possible. For example, a small gaincan be achieved by giving fewer cards to the students near the ends of the 1-Darray, and correspondingly more cards to the students toward the center, sothat the former can complete their initial sums and communicate their resultsearlier, while the middle students compute their extra additions when theywould otherwise be idle awaiting the sums propagating from the ends. Similaroptimizations can be done for the 2-D array or binary tree; in the latter case,for example, the students near the leaves would have fewer cards than thosenear the root. In some situations, it may even be best if some students have nocards at all.
Roughly speaking, the times required for the 1-D, 2-D, and binary tree arrange- p), and O((n/p) + log p), respectively.
Note, however, that the binary tree arrangement is not scalable, in that an in-creasing distance between adjacent desks is required as p increases, which wouldeventually exceed “arm’s length” for large enough p. Alternatively, a binary treecould be embedded within another arrangement, such as a 2-D array, but thenadditional communication time would be required due to the resulting dilation(i.e., some desks that are logically adjacent in the tree arrangement would notbe physically adjacent in the grid arrangement, so cards passed between themwould have to be routed through intermediate desks).
5. Suppose that four composers who live in four different cities agree to collaborate in composing a string quartet having four movements. Discuss the relative mer-its of the following possible divisions of labor among the composers, particularlywith reference to their load balance and their communication requirements.
(a) Composer 1 writes the first movement, allegro.
Composer 2 writes the second movement, andante.
Composer 3 writes the third movement, scherzo.
Composer 4 writes the fourth movement, presto.
(b) Composer 1 writes the 1st violin part for all four movements.
Composer 2 writes the 2nd violin part for all four movements.
Composer 3 writes the viola part for all four movements.
Composer 4 writes the cello part for all four movements.
(c) Composer 1 writes all notes played on the first string for each of the four Composer 2 writes all notes played on the second string for each of thefour instruments.
Composer 3 writes all notes played on the third string for each of the fourinstruments.
Composer 4 writes all notes played on the fourth string for each of the fourinstruments.
Answer : Method (a) will likely require the least communication. The com-posers will need to communicate at the beginning to plan the composition, andperhaps again at the end to tidy up at bit, but in between each composer canwrite his assigned movement independently. Method 1 may have a poor loadbalance, however, as the four movements are likely to differ in tempo, duration,and complexity, so some composers may need much more time than others tocomplete their movements.
Method (b) will require much more communication in order for the music to haveany melodic, rhythmic, or harmonic coherence. In particular, the composers arelikely to need to communicate measure by measure. On the other hand, theload balance is likely to be better, since each composer participates in eachmovement, although there may still be some differences in complexity of thefour instrumental parts.
Method (c) will require extremely frequent communication in order to ensurethat the composition is even physically playable on the instruments, much lessmusically sensible. It is hard to imagine that this method could produce anaesthetically attractive result. Again, the load balance might be reasonablygood, since each composer participates in each movement, although there maystill be some differences in the relative use of the different strings.
6. Derive an expression — a reasonably simple function of the number of nodes p — for the average distance (in hops) between any two nodes (i.e., the averageover all pairs of distinct nodes) in each of the following networks.
Answer : The sum of the distances from node j to each other node is Summing this value over all p nodes, we obtain the overall total distance Dividing by the total number of node pairs, p (p − 1), we obtain the averagedistance between nodes, (p + 1)/3.
Answer : The answer depends on whether p is odd or even. If p is odd, then thesum of the distances from any given node to each other node is Dividing by the number of other nodes, p − 1, we obtain the average distance,(p + 1)/4. If p is even, then the sum of the distances from any given node toeach other node is Dividing by the number of other nodes, p − 1, we obtain the average distance,p2/(4(p − 1)). Thus, in either case, the average distance in a ring is about p/4for large p.
to conclude that the average distance in each dimension is ( p + 1)/3, for an overall average total distance of 2( p + 1)/3 for all pairs of nodes whose rowand column indices are both distinct. The average distance between pairs with only one distinct row or column index is ( p + 1)/3. The weighted average over all distinct pairs of nodes is therefore 2 p/3.
Answer : The distances for any node vary from 1 to log(p), but each distancemust be weighted by the number of nodes at that distance. If k = log(p), thenthere are nodes at distance j (i.e., the number of ways of choosing j bits out of k thatdiffer from those of the given node). Thus, the average distance is This result is intuitively obvious, since the number of nodes whose distance isgreater than log(p)/2 is the same as the number of nodes whose distance is lessthan log(p)/2, and they are all symmetrically placed about this middle distance.
7. For a 3-cube, draw pictures of three edge-disjoint spanning trees (i.e., for broad- casting, no edge is used at the same stage in more than one tree). All threetrees should have the same root and minimum height.
Figure 1: Three edge disjoint spanning trees for 3-cube.

Source: http://ce.scu.ac.ir:8083/choobin/Algorithm/P%20algorithm-hw01_key.pdf