Since you are all poor students, you wave them in and offer to split the pizza between the four of you. You go to the shop with a friend, order a personal pizza to split between the two of you, and as you are waiting, two other friends walk by and see you through the window. When you stop the timer, it reads 1 minute + 4 minutes = 5 minutes, which is faster than the 9 minutes it took you to eat the pizza by yourself. Since the two of you can eat your slices in parallel (i.e., simultaneously) and eating a slice takes 2 minutes, step 8 takes the two of you 2 slices × 2 minutes/slice = 4 minutes to actually eat the pizza. Since there are N = 4 slices to consume and there are P = 2 PEs, each person gets 2 slices. To make this clear, Figure 0-6 color-codes the slices: red for the pizza slices PE 0 eats and yellow for the slices PE 1 eats.Īs before, suppose that it takes both you and your friend 1 minute to work through steps 1-7. In the world of computing, this is a parallel solution to the problem with P = 2. The key is to see that you and your friend each follow the same algorithm independently, performing all 8 of its steps, so while you each compute the same values for N, P, and slicesPP, you each get different values for id, start, stop, and s. 1:įigure 0-6: The Simple Parallel Pizza-Eating Algorithm, N=4, P=2 ¶ You and your friend each work through the algorithm, computing the values shown in Figure 0-6, flipping a coin for who gets id 0 vs. After the pizza arrives, you start the timer. In this situation, there are two PEs (P = 2, you and your friend). You go to the shop with a friend and being poor students, you order a personal pizza to split between the two of you. Figure 0-5 color-codes each pizza slice red, to indicate that a single PE ( you) ate all of the slices. ![]() ![]() In the world of computing, this is the equivalent of a sequential solution to the problem, since you as the single PE 2 eat each of the slices of pizza, one after another. Since (i) it takes you 2 minutes to eat each slice, (ii) you are the only PE solving the problem (i.e., P = 1), and (iii) there are N = 4 slices, it takes you 1 minute + 4 slices × 2 minutes/slice = 1 minute + 8 minutes = 9 minutes to eat all of the pizza slices. Suppose that it took you one minute to write down the values in steps 1-7. Since we are studying computer science, suppose that we search the Internet for “parallel pizza eating algorithm” and find the algorithm shown in Figure 0-4, that each PE can followįigure 0-5: The Simple Parallel Pizza-Eating Algorithm, N=4, P=1 ¶Īfter computing steps 1-7, you eat the pizza as specified in step 8, and stop the timer when you have finished the final slice. Suppose also that it takes a hungry person 2 minutes to eat a slice of pizza. Then N, the size of the problem, is the number of slices in the pizza we must consume to finish the pizza, and P is the number of PEs (pizza-eaters) we have to help us solve the problem. Suppose also that our “problem” is to completely consume a pizza as quickly as possible. To make all of this less abstract, suppose that our local pizza store Penelope’s Parallel Pizzeria sells the following different sizes of pizza 1: P: How many PEs are we using to solve the problem? For the parallel program, there are two relevant parameters to this timing: ![]() To determine how much faster a parallel program is than its sequential counterpart, we must time the two programs, measuring how long it takes to solve the same instance of the problem. The acronym PE is used as a shorthand for processing element. Within the parallel computing community, the term processing element was adopted as a generic way to describe the number of parallel entities a parallel program is using to solve a problem on a given multiprocessor. As we saw in Section 0.1, multiprocessors have existed since the 1960s, and different manufacturers used different terminologies to describe their hardware.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |