{"id":209,"date":"2011-02-27T18:28:18","date_gmt":"2011-02-27T17:28:18","guid":{"rendered":"http:\/\/trigonakis.com\/blog\/?p=209"},"modified":"2011-05-02T10:59:37","modified_gmt":"2011-05-02T09:59:37","slug":"parallelizing-simple-algorithms-fibonacci","status":"publish","type":"post","link":"http:\/\/trigonakis.com\/blog\/2011\/02\/27\/parallelizing-simple-algorithms-fibonacci\/","title":{"rendered":"Parallelizing simple algorithms : Fibonacci"},"content":{"rendered":"
This entry is part 2 of 2 in the series Parallelizing simple algorithms<\/a><\/div>
\"Fibonacci<\/a>

Fibonacci Blocks<\/p><\/div>\n

It took me a little more than I expected, but finally I managed to write the first post for the Parallelizing simple algorithms series<\/a>.<\/p>\n

As I “promised”, I will start these series by parallelizing the Fibonacci Number<\/strong> sequence generation. As you probably already know, Fibonacci numbers are the integer sequence produced by the following relationship:<\/p>\n

   F0<\/sub><\/code> = 0\r\n   F1<\/sub><\/code> = 1\r\n   Fn<\/sub><\/code> = Fn-2<\/sub><\/code> + Fn-1<\/sub><\/code><\/pre>\n
The resulting sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . .<\/p>\n
Lets start with programming!<\/h4>\n
<\/p>\n
Erlang is a functional language, so programming with Erlang is based on functions<\/strong> and recursion<\/strong>.<\/p>\n
 For these two reasons, implementing the above recursive definition of Fibonacci sequence is straightforward.<\/p>\n
Single process solution<\/h5>\n
\r\nfib0(0) ->\r\n    0;\r\nfib0(1) ->\r\n    1;\r\nfib0(N) ->\r\n    fib0(N-1) + fib0(N-2).\r\n<\/pre>\n
I believe that this implementation is self-documented, right? This is the plain, single threaded (or single process<\/strong> in Erlang terminology) solution.<\/p>\n
Lets parallelize<\/strong> it a little :-).<\/p>\n
Two processes solution<\/h5>\n
First, lets break the computation into two processes:<\/p>\n
\r\nfib1(0) ->\r\n    0;\r\nfib1(1) ->\r\n    1;\r\nfib1(N) ->\r\n    Self = self(),\r\n    spawn(fun() ->\r\n\t\t  Self ! fib0(N-1)\r\n\t  end),\r\n    spawn(fun() ->\r\n\t\t  Self ! fib0(N-2)\r\n\t  end),\r\n    receive\r\n\tF1 ->\r\n\t    receive\r\n\t\tF2 ->\r\n\t\t    F1 + F2\r\n\t    end\r\n    end.\r\n<\/pre>\n
Two process are spawned, each of them running the sequential code of fib0<\/code>. After the two processes complete, they send back the results to the process that spawned them. This process acts as a coordinator<\/em>.<\/p>\n
In the introductory post<\/a> of the series, I presented the necessary theory behind parallelization. As you can easily udnerstand, the solution fib1<\/code> uses Data parallelism<\/strong>, since it repeats the same computation on different data in parallel.<\/p>\n
Unlimited parallelism<\/h5>\n
Lets write the solution that uses Unlimited parallelism<\/strong>:<\/p>\n
\r\nfib2(0) ->\r\n    0;\r\nfib2(1) ->\r\n    1;\r\nfib2(N) ->\r\n    Self = self(),\r\n    spawn(fun() ->\r\n\t\t  Self ! fib2(N-1)\r\n\t  end),\r\n    spawn(fun() ->\r\n\t\t  Self ! fib2(N-2)\r\n\t  end),\r\n    receive\r\n\tF1 ->\r\n\t    receive\r\n\t\tF2 ->\r\n\t\t    F1 + F2\r\n\t    end\r\n    end.\r\n<\/pre>\n
In this case, every call to fib2<\/code> creates 2 new worker<\/em> processes. So, in order to calculate fib2(2)<\/code>, 2 extra processes are spawned, fib2(3)<\/code>, 4 extra, fib2(4)<\/code>, 8 extra, …, fib2(N)<\/code>, 2N<\/sup> extra processes. It should be obvious that this exponential process growth cannot work.. As usual, unlimited parallelism is not an appropriate solution.<\/p>\n
So, 1-process, 2-processes, 2N<\/sup>-processes.. what else? Well, in the introductory post I omitted to write about something rather important.<\/p>\n
Amdahl’s law<\/h5>\n
Amdahl’s law “sets” a limitation on the performance improvement that can be achieved in case that only one part of the system is improved. In parallel programming the meaning of the law can be simplified in the following example: if a piece of code cannot be parallelized, it immediately sets a limit to the speedup that can be achieved by parallelizing. For example, if a sequential application runs in 10 seconds and the bigger non-parallelizable part executes in 3 seconds, parallelizing the system is impossible to achieve better performance than these 3 seconds! Read more about Amdahl’s law on Wikipedia<\/a>.<\/p>\n
Why did I mention Amdahl’s law? Well, right now the best solution is the 2-threaded one. But, why not trying with more processes?<\/p>\n
Four processes solution<\/h5>\n
Just to mention that by saying 4 process, I mean only the worker ones, excluding the coordinators. For example, in this case, the four worker processes are complemented with 3 coordinator ones (imagine it as a binary tree, where the leaves are the workers, and the others the coordinators).<\/p>\n
\r\nfib3(0) ->\r\n    0;\r\nfib3(1) ->\r\n    1;\r\nfib3(N) ->\r\n    Self = self(),\r\n    spawn(fun() ->\r\n\t\t  Self ! fib1(N-1)\r\n\t  end),\r\n    spawn(fun() ->\r\n\t\t  Self ! fib1(N-2)\r\n\t  end),\r\n    receive\r\n\tF1 ->\r\n\t    receive\r\n\t\tF2 ->\r\n\t\t    F1 + F2\r\n\t    end\r\n    end.\r\n<\/pre>\n
fib3<\/code> follows fib1<\/code>‘s logic. It spawns 2 fib1<\/code> processes, which in turn become coordinators and spawn 2 more processes each, so 4 workers in total.<\/p>\n
Lets make a more generic solution.<\/p>\n
Generic solution<\/h5>\n
\r\nfib4(0, _) ->\r\n    0;\r\nfib4(1, _) ->\r\n    1;\r\nfib4(N, M) when N >= M ->\r\n    Self = self(),\r\n    spawn(fun() ->\r\n\t\t  Self ! fib4(N-1, M)\r\n\t  end),\r\n    spawn(fun() ->\r\n\t\t  Self ! fib4(N-2, M)\r\n\t  end),\r\n    receive\r\n\tF1 ->\r\n\t    receive\r\n\t\tF2 ->\r\n\t\t    F1 + F2\r\n\t    end\r\n    end;\r\nfib4(N, M) when N < M ->\r\n    Self = self(),\r\n    spawn(fun() ->\r\n\t\t  Self ! fib0(N-1)\r\n\t  end),\r\n    spawn(fun() ->\r\n\t\t  Self ! fib0(N-2)\r\n\t  end),\r\n    receive\r\n\tF1 ->\r\n\t    receive\r\n\t\tF2 ->\r\n\t\t    F1 + F2\r\n\t    end\r\n    end.\r\n\r\nfib4_5(N) ->\r\n    fib4(N, N-4).\r\nfib4_6(N) ->\r\n    fib4(N, N-5).\r\nfib4_7(N) ->\r\n    fib4(N, N-6).\r\nfib4_8(N) ->\r\n    fib4(N, N-7).\r\nfib4_9(N) ->\r\n    fib4(N, N-8).\r\nfib4_10(N) ->\r\n    fib4(N, N-9).\r\n<\/pre>\n
fib4(N, M)<\/code> spawns 2 new processes while N >= M. That means that if we call fib4(20, 18)<\/code>, we will have 10 fib0<\/code> worker processes. To check it, draw the “spawning” binary tree..<\/p>\n
Disappointment<\/h5>\n
I never understood why people use Fibonacci as a parallelization example.. The sequential implementation below should explain why!<\/p>\n
\r\nfib5(0) ->\r\n    0;\r\nfib5(1) ->\r\n    1;\r\nfib5(N) ->\r\n    fib_bottom(0, 1, 2, N).\r\n\r\nfib_bottom(L, H, C, N) when C >= N ->\r\n    L+H;\r\nfib_bottom(L, H, C, N) ->\r\n    fib_bottom(H, L+H, C+1, N).\r\n<\/pre>\n
It is not complicated and, as you will see in the benchmarking section, it is fast.<\/p>\n
Benchmarking<\/h4>\n
In order to make the measuring process easier, I created some testing functions in this module<\/a>. Rename it from “test.txt” to “test.erl” to use it. The interface is:<\/p>\n
\r\nrun(Module, Functions, Parameters, Repeats)\r\n<\/pre>\n
Which runs, times, and generates the average time to Repeats<\/i> runs of Functions<\/i> in the Module<\/i>, with Parameters<\/i>. Parameters<\/i> is a list of parameters. One item of the list is used as a parameter at a time.<\/p>\n
In order to run my tests, I booted my Ubuntu and used a virtual console<\/a>, so that I manage a somehow unobstructed execution.<\/p>\n
Measurements<\/h5>\n
So, first:<\/p>\n
\r\ntest:run(fib, [fib0, fib1, fib2, fib3, fib4_6, fib4_8, fib5], [10, 15, 20, 25], 3).\r\n<\/pre>\n
I will present the output parameter by parameter:<\/p>\n
\r\nParameter: 10 -- Start ----------\r\n>>fib0:   AVG: 44.7 micros   | [40,38,56]\r\n>>fib1:   AVG: 106.7 micros  | [128,97,95]\r\n>>fib2:   AVG: 2202.0 micros | [2341,2274,1991]\r\n>>fib3:   AVG: 99.7 micros   | [93,131,75]\r\n>>fib4_6: AVG: 1584.0 micros | [1481,1570,1701]\r\n>>fib4_8: AVG: 2207.7 micros | [2332,2145,2146]\r\n>>fib5:   AVG: 8.3 micros    | [21,2,2]\r\n<\/pre>\n
The results are not very “stable”, but we can draw some conclusions. The computation (data) is very short in this case, so the overhead of parallelizing is more than the benefit gained. This overhead is due to the process creation<\/strong> and the communication<\/strong> (small, because the processes run locally).<\/p>\n
As expected, the non-recursive execution is the fastest and the performance is decreasing as the concurrency increases. From now on, I will simply not take into consideration the fib5<\/code> solution. It will be the fastest, so it is not interesting..<\/p>\n
Then,<\/p>\n
\r\nParameter: 15 -- Start ----------\r\n>>fib0:   AVG: 200.7 micros   | [190,218,194]\r\n>>fib1:   AVG: 215.3 micros   | [225,200,221]\r\n>>fib2:   AVG: 28233.3 micros | [29247,28091,27362]\r\n>>fib3:   AVG: 243.3 micros   | [261,278,191]\r\n>>fib4_6: AVG: 1822.0 micros  | [1887,1758,1821]\r\n>>fib4_8: AVG: 4603.7 micros  | [4906,4408,4497]\r\n>>fib5:   AVG: 2.7 micros     | [3,3,2]\r\n<\/pre>\n
We can already see that parallelizing is close to take effect. Both with the Fibonacci of 10 and of 15, it is obvious that the unlimited parallelism (fib2<\/code>) is not working<\/strong>!<\/p>\n
\r\nParameter: 20 -- Start ----------\r\n>>fib0:   AVG: 2332.0 micros   | [2403,2294,2299]\r\n>>fib1:   AVG: 1391.3 micros   | [1528,1335,1311]\r\n>>fib2:   AVG: 349473.3 micros | [340365,331448,376607]\r\n>>fib3:   AVG: 2222.7 micros   | [2146,2377,2145]\r\n>>fib4_6: AVG: 3894.0 micros   | [4029,3909,3744]\r\n>>fib4_8: AVG: 6970.3 micros   | [7371,6468,7072]\r\n>>fib5:   AVG: 3.3 micros      | [4,3,3]\r\n<\/pre>\n
Parallelism “won”<\/strong>!! We can also notice that the measurements are stabilizing as the computation grows bigger. The two workers version (fib1<\/code>) is the fastest. My processor has 2 cores, right? <\/p>\n
Lets continue<\/p>\n
\r\nParameter: 25 -- Start ----------\r\n>>fib0:   AVG: 23961.0 micros   | [24605,23901,23377]\r\n>>fib1:   AVG: 23197.3 micros   | [23195,23126,23271]\r\n>>fib2:   AVG: 3915766.3 micros | [3833718,4018613,3894968]\r\n>>fib3:   AVG: 12501.0 micros   | [13569,11962,11972]\r\n>>fib4_6: AVG: 13220.3 micros   | [13163,13159,13339]\r\n>>fib4_8: AVG: 15519.0 micros   | [15137,15212,16208]\r\n>>fib5:   AVG: 3.0 micros       | [4,3,2]\r\n<\/pre>\n
The winner is fib3<\/code><\/strong> (4 worker processes)! So, why isn’t the best solution the one with #threds == #cores<\/strong>? Do you remember Amdahl’s law<\/i>?<\/p>\n
What happens is that the longer execution (of the two workers), as explained by the Amdahl’s law, sets the lower limit that can be achieved with parallelizing. fib1(25)<\/code> spawns fib0(24)<\/code> and fib0(23)<\/code>. If we independently measure them:<\/p>\n
\r\n2> timer:tc(fib, fib0, [24]).\r\n{21558,75025}\r\n3> timer:tc(fib, fib0, [23]).\r\n{13324,46368}\r\n<\/pre>\n
We can understand that the fib0(24)<\/code> call set the performance limit (~21500 microseconds). On the other hand, fib3(25)<\/code> uses the fib0(23)<\/code>, fib0(22)<\/code>, fib0(22)<\/code>, and fib0(21)<\/code> workers:<\/p>\n
\r\n4> timer:tc(fib, fib0, [23]).\r\n{13106,46368}\r\n5> timer:tc(fib, fib0, [22]).\r\n{8297,28657}\r\n6> timer:tc(fib, fib0, [21]).\r\n{5036,17711}\r\n<\/pre>\n
We can see that fib0(23) sets the time limit. Just to mention that the numbers appearing in these last measurements tend to be higher because I am taking them with the full OS loaded.<\/p>\n
We can notice this effect in the CPU utilization also (taken from a call to fib1(40)<\/code>):
\n
\"\"<\/a>
The Cores Utilization while computing fib1(40)<\/p><\/div>
\nAfter the faster of the two workers finishes (fib0(38)<\/code>), the processing power is not fully utilized!<\/p>\n
No more Unlimited Parallelism<\/h5>\n
As the fib2 is out of the contest (in the opposite way than fib5<\/code>), I decided not to use it for tests with parameter higher than 25 (I was bored to wait :-P). With this in mind, I continued with the following tests:<\/p>\n
\r\ntest:run(fib, [fib0, fib1, fib3, fib4_6, fib4_8, fib5], [30, 40, 41, 42], 3).\r\n<\/pre>\n
\r\nParameter: 30 -- Start ----------\r\n>>fib0:   AVG: 152250.0 micros | [159005,151430,146315]\r\n>>fib1:   AVG: 103349.7 micros | [99814,105109,105126]\r\n>>fib3:   AVG: 88625.7 micros  | [87651,94793,83433]\r\n>>fib4_6: AVG: 88146.3 micros  | [89569,91849,83021]\r\n>>fib4_8: AVG: 84386.3 micros  | [84099,84560,84500]\r\n>>fib5:   AVG: 3.3 micros      | [4,3,3]\r\n\r\nParameter: 40 -- Start ----------\r\n>>fib0:   AVG: 26544721.7 micros | [23168055,28247057,28219053]\r\n>>fib1:   AVG: 21077023.7 micros | [21047387,21032536,21151148]\r\n>>fib3:   AVG: 17733562.3 micros | [16394906,17871455,18934326]\r\n>>fib4_6: AVG: 16344892.0 micros | [16330718,16220437,16483521]\r\n>>fib4_8: AVG: 16306948.3 micros | [16206762,16446090,16267993]\r\n>>fib5:   AVG: 10.0 micros       | [5,22,3]\r\n\r\nParameter: 41 -- Start ----------\r\n>>fib0:   AVG: 47261960.3 micros | [47514272,47015432,47256177]\r\n>>fib1:   AVG: 34266284.3 micros | [32578166,34148118,36072569]\r\n>>fib3:   AVG: 33014777.7 micros | [30061008,36471809,32511516]\r\n>>fib4_6: AVG: 29779055.7 micros | [29715648,30000853,29620666]\r\n>>fib4_8: AVG: 29979546.3 micros | [30140758,29720501,30077380]\r\n>>fib5:   AVG: 4.0 micros        | [5,4,3]\r\n\r\nParameter: 42 -- Start ----------\r\n>>fib0:   AVG: 78229815.0 micros | [77388307,79200132,78101006]\r\n>>fib1:   AVG: 55877460.3 micros | [54076288,56712128,56843965]\r\n>>fib3:   AVG: 52787426.3 micros | [50520162,52976514,54865603]\r\n>>fib4_6: AVG: 50517868.7 micros | [52275541,50447961,48830104]\r\n>>fib4_8: AVG: 49112005.0 micros | [49638298,50027250,47670467]\r\n>>fib5:   AVG: 4.7 micros        | [5,5,4]\r\n<\/pre>\n
As we can see, the fib4_8 was generally the fastest. In case of parameter 30, there was a time decrease of ((152250-84386.3)\/152250) = 44.6%<\/strong>!<\/p>\n
More processes<\/h5>\n
Now, lets compare the fib4_* solutions, since they “look” more competitive with higher parameters.<\/p>\n
\r\ntest:run(fib, [fib4_6, fib4_7, fib4_8, fib4_9, fib4_10], [30, 40, 41, 42], 3).\r\n<\/pre>\n
\r\nParameter: 30 -- Start ----------\r\n>>fib4_6:  AVG: 138976.0 micros | [132737,154900,129291]\r\n>>fib4_7:  AVG: 129955.3 micros | [130810,129461,129595]\r\n>>fib4_8:  AVG: 131024.3 micros | [130824,130597,131652]\r\n>>fib4_9:  AVG: 131907.3 micros | [131885,132068,131769]\r\n>>fib4_10: AVG: 141973.3 micros | [133670,158155,134095]\r\n\r\nParameter: 40 -- Start ----------\r\n>>fib4_6:  AVG: 16494758.3 micros | [16551363,16241427,16691485]\r\n>>fib4_7:  AVG: 16330959.0 micros | [16080028,16451705,16461144]\r\n>>fib4_8:  AVG: 16324207.7 micros | [16235259,16569521,16167843]\r\n>>fib4_9:  AVG: 16436575.7 micros | [16565366,16617853,16126508]\r\n>>fib4_10: AVG: 16563677.0 micros | [16627788,16308796,16754447]\r\n\r\nParameter: 41 -- Start ----------\r\n>>fib4_6:  AVG: 32710283.7 micros | [32047340,30147917,35935594]\r\n>>fib4_7:  AVG: 38032535.3 micros | [35256794,41837955,37002857]\r\n>>fib4_8:  AVG: 36848240.7 micros | [36764344,38615563,35164815]\r\n>>fib4_9:  AVG: 36471677.7 micros | [38606656,36677249,34131128]\r\n>>fib4_10: AVG: 35954456.0 micros | [34594636,37284090,35984642]\r\n\r\nParameter: 42 -- Start ----------\r\n>>fib4_6:  AVG: 58263948.0 micros | [59179553,58509795,57102496]\r\n>>fib4_7:  AVG: 62005141.7 micros | [58846929,57270566,69897930]\r\n>>fib4_8:  AVG: 59224815.0 micros | [65590241,56918707,55165497]\r\n>>fib4_9:  AVG: 56413852.3 micros | [57657222,57665314,53919021]\r\n>>fib4_10: AVG: 54196771.0 micros | [54126552,54178425,54285336]\r\n<\/pre>\n
As you can see, the results are very close to each other. Though, it looks like that as the computation increases, the more processes created help. Of course, we saw that unlimited parallelism does not help, so there is a cap after which instead of gaining performance, we decrease it.<\/p>\n
One last thing<\/h5>\n
I kept the best for the end ;-). The tests of fib0<\/code> were done with SMP enabled. So, although the code is single-threaded, Erlang runtime did its best to utilize the 2 cores. That’s why I turned of SMP in Erlang and run the fib0<\/code> tests again:<\/p>\n
\r\ntest:run(fib, [fib0], [10, 20, 30, 40], 3).\r\n<\/pre>\n
\r\nParameter: 10 -- Start ----------\r\n>>fib0: AVG: 327.0 micros      | [958,12,11]\r\n\r\nParameter: 20 -- Start ----------\r\n>>fib0: AVG: 2510.0 micros      | [2553,2514,2463]\r\n\r\nParameter: 30 -- Start ----------\r\n>>fib0: AVG: 301458.7 micros    | [301585,301662,301129]\r\n\r\nParameter: 40 -- Start ----------\r\n>>fib0: AVG: 37499354.0 micros  | [37525814,37473104,37499144]\r\n\r\nParameter: 41 -- Start ----------\r\n>>fib0: AVG: 63639971.0 micros  | [63708948,63542924,63668041]\r\n\r\nParameter: 42 -- Start ----------\r\n>>fib0: AVG: 104382637.3 micros | [105213567,104180367,103753978\r\n<\/pre>\n
Comparing the fastest solution for each parameter with the fib0<\/code> gives:<\/p>\n\n\n\n\n\n\n\n\n
Parameter<\/th>\nfib0 (\u03bcs)<\/th>\nBest (\u03bcs)<\/th>\nDecrease<\/th>\n<\/tr>\n
10<\/td>\n327.0<\/td>\n99.7<\/td>\n69.5%<\/td>\n<\/tr>\n
20<\/td>\n2510.0<\/td>\n1391.3<\/td>\n44.5%<\/td>\n<\/tr>\n
30<\/td>\n301458.7<\/td>\n84386.3<\/td>\n72.0%<\/td>\n<\/tr>\n
40<\/td>\n37499354.0<\/td>\n16324207.7<\/td>\n56.4%<\/td>\n<\/tr>\n
41<\/td>\n63639971.0<\/td>\n32710283.7<\/td>\n48.6%<\/td>\n<\/tr>\n
42<\/td>\n104382637.3<\/td>\n54196771.0<\/td>\n48.0%<\/td>\n<\/tr>\n<\/table>\n
Wow! 72% less time..<\/strong> Not bad for a Core2Duo processor!<\/p>\n
Conlusions<\/h5>\n
So, what conclusions can we draw from what we saw?<\/p>\n