{"id":120,"date":"2008-04-30T16:20:01","date_gmt":"2008-04-30T21:20:01","guid":{"rendered":"http:\/\/mariusbancila.ro\/blog\/?p=120"},"modified":"2008-04-30T16:20:01","modified_gmt":"2008-04-30T21:20:01","slug":"parallelization-in-f","status":"publish","type":"post","link":"https:\/\/mariusbancila.ro\/blog\/2008\/04\/30\/parallelization-in-f\/","title":{"rendered":"Parallelization in F#"},"content":{"rendered":"

In my last post I was writing about parallelizing loops with Parallel.For in C#. Today I though it would be nice to try that in F#. So, here is the benchmarking of the matrix multiplication and the bubblesort algorithm in F4.<\/p>\n

Matrices Multiplication<\/h3>\n

I started with a create_matrix function that creates and randomly initializes a matrix of doubles.<\/p>\n

\r\nlet create_matrix rows columns =\r\n   let rnd = System.Random()\r\n   Array2.init rows columns (fun i j -> rnd.NextDouble())\r\n<\/pre>\n
Sequential multiplication could look like this:<\/p>\n
\r\nlet multiply_sequential (m1:float[,]) (m2:float[,]) =\r\n   let rows1 = Array2.length1 m1\r\n   let cols1 = Array2.length2 m1\r\n   let rows2 = Array2.length1 m2\r\n   let cols2 = Array2.length2 m2\r\n   let result = Array2.create rows1 cols2 0.0\r\n   \r\n   if(cols1 <> rows2) then \r\n      failwith \"Matrices size incorrect for multiplication!\"\r\n      \r\n   for i = 0 to rows1-1 do\r\n      for j = 0 to cols2-1 do\r\n         for k = 0 to cols1-1 do\r\n            result.[i,j] <- result.[i,j] + m1.[i,k] * m2.[k,j]\r\n         done\r\n      done\r\n   done\r\n   result\r\n<\/pre>\n
Parallelizing it only implies replacing the outer loop with Parallel.For.<\/p>\n
\r\nlet multiply_parallel (m1:float[,]) (m2:float[,]) =\r\n   let rows1 = Array2.length1 m1\r\n   let cols1 = Array2.length2 m1\r\n   let rows2 = Array2.length1 m2\r\n   let cols2 = Array2.length2 m2\r\n   let result = Array2.create rows1 cols2 0.0\r\n   \r\n   if(cols1 <> rows2) then \r\n      failwith \"Matrices size incorrect for multiplication!\"\r\n      \r\n   Parallel.For(0, rows1, (fun i->\r\n      for j = 0 to cols2-1 do\r\n         for k = 0 to cols1-1 do\r\n            result.[i,j] <- result.[i,j] + m1.[i,k] * m2.[k,j]))\r\n   result\r\n<\/pre>\n
We can test those function and get the same output as I had in my previous post with this:<\/p>\n
\r\nlet main() = \r\n   let step = 100\r\n   let size = ref step\r\n   while (!size <= step*10) do\r\n      let m1 = create_matrix !size !size\r\n      let m2 = create_matrix !size !size\r\n      printfn \"Matrices size: %dx%d\" !size !size\r\n      \r\n      printf \"Sequential...\\t\"\r\n      let starts = DateTime.Now\r\n      let ms = multiply_sequential m1 m2\r\n      printfn \"%a\" output_any (DateTime.Now - starts)\r\n      \r\n      printf \"Parallel...\\t\"\r\n      let startp = DateTime.Now\r\n      let ms = multiply_parallel m1 m2\r\n      printfn \"%a\" output_any (DateTime.Now - startp)\r\n\r\n      size := !size + step    \r\n   done   \r\n   \r\nmain()\r\n<\/pre>\n
Before running, you have to make sure you add System.Threading.dll to the referred assemblies. And since this one depends on System.Core.dll, you also have to add this one. In you are using Visual Studio and a F# project, you can add the two references from the project properties.<\/p>\n
-r c:\\Windows\\assembly\\GAC_MSIL\\System.Core\\3.5.0.0__b77a5c561934e089\\System.Core.dll -r “C:\\Program Files\\Microsoft Parallel Extensions Dec07 CTP\\System.Threading.dll”<\/p><\/blockquote>\n
The results are shown below:<\/p>\n
\r\nMatrices size: 100x100\r\nSequential...   00:00:00.1250000\r\nParallel...     00:00:00.1250000\r\nMatrices size: 200x200\r\nSequential...   00:00:00.9218750\r\nParallel...     00:00:00.6093750\r\nMatrices size: 300x300\r\nSequential...   00:00:03.1093750\r\nParallel...     00:00:01.9375000\r\nMatrices size: 400x400\r\nSequential...   00:00:07.5000000\r\nParallel...     00:00:04.7343750\r\nMatrices size: 500x500\r\nSequential...   00:00:15.1562500\r\nParallel...     00:00:09.3125000\r\nMatrices size: 600x600\r\nSequential...   00:00:25.7031250\r\nParallel...     00:00:16.5312500\r\nMatrices size: 700x700\r\nSequential...   00:00:41.9843750\r\nParallel...     00:00:26.4375000\r\nMatrices size: 800x800\r\nSequential...   00:01:03.5781250\r\nParallel...     00:00:39.8281250\r\nMatrices size: 900x900\r\nSequential...   00:01:32.1093750\r\nParallel...     00:00:57.3125000\r\nMatrices size: 1000x1000\r\nSequential...   00:02:07.0468750\r\nParallel...     00:01:18.9687500\r\n<\/pre>\n
Array Sorting<\/h3>\n
First, I created a function, create_array, that creates and randomly initializes an array of doubles.<\/p>\n
\r\nlet create_array size = \r\n    let rnd = new Random()\r\n    let arr = Array.create size 0.0\r\n    for i = 0 to arr.Length-1 do\r\n        arr.(i) <- rnd.NextDouble()\r\n    arr\r\n<\/pre>\n
The sequential bubblesort implementation is quite straight forward, of course.<\/p>\n
\r\nlet bubblesort_seq (arr : double array) = \r\n    for i = 0 to arr.Length-1 do\r\n        for j = 0 to arr.Length-1 do\r\n            if (arr.(i).CompareTo(arr.(j)) < 0) then\r\n                let temp = arr.(j)\r\n                arr.(j) <- arr.(i)\r\n                arr.(i) <- temp\r\n    arr\r\n<\/pre>\n
Parallelizing it, again, only means replacing the outer for loop with Parallel.For.<\/p>\n
\r\nlet bubblesort_parallel (arr : double array) = \r\n    Parallel.For(0, arr.Length, (fun i -> \r\n            for j = 0 to arr.Length-1 do\r\n                if (arr.(i).CompareTo(arr.(j)) < 0) then\r\n                    let temp = arr.(j)\r\n                    arr.(j) <- arr.(i)\r\n                    arr.(i) <- temp))\r\n\r\n    arr\r\n<\/pre>\n
And this is how the two functions were used:<\/p>\n
\r\nlet main()=\r\n    let step = 5000\r\n    let size = ref step\r\n    while (!size <= step*10) do\r\n        let arr = create_array !size\r\n        printfn \"Array size: %d\" arr.Length\r\n        \r\n        printf \"Sequential...\\t\"\r\n        let starts = DateTime.Now\r\n        let arrs = bubblesort_seq arr\r\n        printfn \"%a\" output_any (DateTime.Now - starts)\r\n        \r\n        printf \"Parallel...\\t\"\r\n        let startp = DateTime.Now\r\n        let arrp = bubblesort_parallel arr\r\n        printfn \"%a\" output_any (DateTime.Now - startp)\r\n\r\n        size := !size + step\r\n    done\r\n    \r\nmain()\r\n<\/pre>\n
The output for the program is:<\/p>\n
\r\nArray size: 5000\r\nSequential...   00:00:00.2343750\r\nParallel...     00:00:00.1562500\r\nArray size: 10000\r\nSequential...   00:00:00.8593750\r\nParallel...     00:00:00.5156250\r\nArray size: 15000\r\nSequential...   00:00:01.9531250\r\nParallel...     00:00:01.1718750\r\nArray size: 20000\r\nSequential...   00:00:03.3125000\r\nParallel...     00:00:02.1562500\r\nArray size: 25000\r\nSequential...   00:00:05.4062500\r\nParallel...     00:00:03.5312500\r\nArray size: 30000\r\nSequential...   00:00:07.4062500\r\nParallel...     00:00:05.0312500\r\nArray size: 35000\r\nSequential...   00:00:10.6562500\r\nParallel...     00:00:06.8906250\r\nArray size: 40000\r\nSequential...   00:00:13.2343750\r\nParallel...     00:00:08.9375000\r\nArray size: 45000\r\nSequential...   00:00:17.6406250\r\nParallel...     00:00:11.4687500\r\nArray size: 50000\r\nSequential...   00:00:20.8281250\r\nParallel...     00:00:14.2187500\r\n<\/pre>\n
If you compare the output with the one from C#, you’ll notice that the times are smaller. It looks like F# is faster than C#. Of course it can get faster if I replace the call to CompareTo() with operator <.<\/p>\n
\r\nif (arr.(i).CompareTo(arr.(j)) < 0) then\r\n<\/pre>\n
\r\nif (arr.(i) < arr.(j)) then\r\n<\/pre>\n
In this case the results look like this:<\/p>\n
\r\nArray size: 5000\r\nSequential...   00:00:00.1093750\r\nParallel...     00:00:00.1093750\r\nArray size: 10000\r\nSequential...   00:00:00.4843750\r\nParallel...     00:00:00.2343750\r\nArray size: 15000\r\nSequential...   00:00:01.1093750\r\nParallel...     00:00:00.4687500\r\nArray size: 20000\r\nSequential...   00:00:01.9062500\r\nParallel...     00:00:00.8437500\r\nArray size: 25000\r\nSequential...   00:00:03.0156250\r\nParallel...     00:00:01.2500000\r\nArray size: 30000\r\nSequential...   00:00:04.3437500\r\nParallel...     00:00:01.8906250\r\nArray size: 35000\r\nSequential...   00:00:05.9062500\r\nParallel...     00:00:02.4375000\r\nArray size: 40000\r\nSequential...   00:00:07.7656250\r\nParallel...     00:00:03.3593750\r\nArray size: 45000\r\nSequential...   00:00:09.8281250\r\nParallel...     00:00:04.0312500\r\nArray size: 50000\r\nSequential...   00:00:12.2031250\r\nParallel...     00:00:05.2343750\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
In my last post I was writing about parallelizing loops with Parallel.For in C#. Today I though it would be nice to try that in F#. So, here is the benchmarking of the matrix multiplication and the bubblesort algorithm in F4. Matrices Multiplication I started with a create_matrix function that creates and randomly initializes a … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_uag_custom_page_level_css":"","advgb_blocks_editor_width":"","advgb_blocks_columns_visual_guide":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[37,42],"tags":[],"class_list":["post-120","post","type-post","status-publish","format-standard","hentry","category-fsharp","category-parallel-programming"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t