Click here to Skip to main content
12,817,428 members (37,235 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as


75 bookmarked
Posted 29 Feb 2008

Tricky Programming on Multi-Core Processors

, 29 Feb 2008 CPOL
Rate this:
Please Sign up or sign in to vote.
An article on experiments with multithreading on a multi-core processor


Nowadays, multi-core processing is a growing industry trend as single core processors rapidly reach the physical limits of possible complexity and speed. It's obvious that if such wonderful hardware exists, it should be supported in .NET, shouldn't it? To check this I looked for a well-known easy-parallelizable algorithm. The benchmark should have handled different .NET parallelizing techniques with memory and mathematical operations. In my opinion, the best algorithms that fit these requirements are QuickSort and Matrix multiplication.

Please take into account, that this article doesn't describe any algorithms' optimization techniques. Instead it shows, how to parallelize your C# code and compares the performance of different approaches.

The Idea

Quicksort can be easily parallelized due to its divide-and-conquer nature. If we have p processors, we can divide a list of n elements into p sublists in Θ(n) average time, then sort each of these in average time. Ignoring the Θ(n) preprocessing, this a is linear speedup. Given n processors, only Θ(n) time is required overall. One advantage of parallel quicksort over other parallel sort algorithms is that no synchronization is required. A new thread could be started as soon as a sublist is available for it to work on and it does not communicate with other threads. When all threads are complete, the sort is done.

What about matrices? Well, it's quite the same — easy to paralellize (lots of ways to do it) and no synchronization required. Also, it's much easier to divide a multiplication process into two equal sub-processes (what is not done in Quicksort). In general, an algorithms complexity is . The speedup depends on an approach that programmer chooses. In case of proposed tests the speedup was up to 50%.


If you are not familiar with Quicksort or Matrix multiplication, please check the reference section. You should also know a little about multithreading. Some of the tests use Parallel FX library. It is free to download and is included in source files.

Inside the code::Quicksort

The QuickSort<T> where T : IComparable class contains all tests and three basic methods that implement Quicksort. The standard Quicksort function looks like this:

private void QSort(int left, int right)
   if (right > left)
      int pivotIndex = GetPivotIndex(left, right); // median-of-three approach
      int pivotNewIndex = Partition(left, right, pivotIndex); 
      QSort(left, pivotNewIndex - 1);
      QSort(pivotNewIndex + 1, right);

The first test uses managed threads to parallelize quicksort. It's advantages are:

  • No extra-libraries are needed.
  • Best performance results in benchmark
public void SortParallelThreads(T[] array)
   this.array = array;
   int pivotIndex = GetPivotIndexParallel(array); // get pivot index after partitioning
   Thread sort1 = new Thread(new ThreadStart(delegate()
      QSort(0, pivotIndex); // sort the first part of the array
      ((AutoResetEvent)(waitHandles[0])).Set(); // signal, that sorting is completed

   Thread sort2 = new Thread(new ThreadStart(delegate()
      QSort(pivotIndex + 1, array.Length - 1); // sort the second part of the array

   sort1.Start(); // start threads one by one
   WaitHandle.WaitAll(waitHandles); // wait until both sorting threads finish their work

This test uses Microsoft Parallel Extensions to .NET Framework 3.5. The advantages of using Parallel FX are:

  • No need in thread synchronization (meaning main thread and both sorting threads)
  • The smallest code
public void SortParallelFX(T[] array)
   this.array = array;
   int pivotIndex = GetPivotIndexParallel(array); 

      QSort(0, pivotIndex);
      QSort(pivotIndex + 1, array.Length - 1); 

The last test uses the ThreadPool class to queue and run sorting threads.

public void SortParallelThreadPool(T[] array)
   this.array = array;
   int pivotIndex = GetPivotIndexParallel(array);

   ThreadPool.QueueUserWorkItem(new WaitCallback(delegate(object x)
      QSort(0, pivotIndex);

   ThreadPool.QueueUserWorkItem(new WaitCallback(delegate(object x)
      QSort(pivotIndex + 1, array.Length - 1);


Inside the code::Matrix multiplication

The Matrix class is a wrapper for double[,] array. Its Multiply(..) method is shared by all tests except MultiplyFXFor() (see below).

The MultiplyThreads(), MultiplyThreadPool(), MultiplyFXDo() methods share the same concept: divide a multiplication operation in two sub-operations and process them side by side (using both processor's cores). The code for these methods is slightly different from the code of Quicksort methods. (Multiply(..) is called instead of QSort(..)).

The m1 and m2 parameters are matrix multipliers, the resMatrix is the product. beg and end parameters are used to parallelize the process.

For example: linear sort calls Multiply(.., 0, m1.rows), while most of tests use Multiply(.., 0, m1.rows/2) and Multiply(.., m1.rows/2 + 1, m1.rows).

private static void Multiply(Matrix m1, Matrix m2, Matrix resMatrix, int beg, int end)
   for (int i = beg; i < end; i++)
      for (int j = 0; j < m2.columns; j++)
         double tValue = 0.0;
         for (int k = 0; k <= m1.columns - 1; k++)
            tValue += m1[i, k] * m2[k, j];
         tMatrix[i, j] = tValue;

MultiplyFXFor() has no analogues in sorting tests. It takes the advantage of ParallelFX library in loops parallelizing.

Parallel.For(0, m1.rows,delegate (int i) // Parallel.For is used
   for (int j = 0; j < m2.columns; j++)
      double tValue = 0.0;
      for (int k = 0; k <= m1.columns - 1; k++)
         tValue += m1[i, k] * m2[k, j];
      tMatrix[i, j] = tValue;

The Results

Each quicksort method passed 10 tests with random integer arrays of 10^7 elements. Quicksort terrifically depends on an array structure and on pivot elements. This explains results diversity and answers the question "why parallel tests are not twice as fast as the linear one?" As I expected, the "pure .NET" sort should beat all tests. Very nice results for Array.Sort

Parallel FX3.855.763.853.734.15.914.593.574.245.044.47

Each matrix multiplication method passed 5 tests with random 1000x1000 matrices. Because each parallel operation works with the same amount of data, the results do not diverse much, and the speedup is close to 50%.



The Task Parallel Library (TPL) is designed to make it much easier to write managed code that can automatically use multiple processors. Using the library, you can conveniently express potential parallelism in existing sequential code, where the exposed parallel tasks will be run concurrently on all available processors.

The same could be done with "traditional" approaches like Managed threads or ThreadPool. But ParallelFX library has one significant advantage: it uses all available processor to parallelize the operation. Programmers should not worry about the end-users CPU type, it could be single-core, multi-core, or event multiprocessor system. Although Parallel.For is slower than Parallel.Do (speaking about multiplication tests) on a processor with two cores, it should work much faster on a processor with three or four cores, and no code changes are needed!
At last, this is CPU's usage during the parallel multiplication tests. 100% usage of both cores.


What is multi-core processor?
Quicksort - Wikipedia, the free encyclopedia
Matrix multiplication - Wikipedia, the free encyclopedia
Optimize Managed Code For Multi-Core Machines
Download Microsoft Parallel Extensions to .NET Framework 3.5


  • 24.02.2008 - Release
  • Smallest code


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Zaur Nasibov
Software Developer
Finland Finland
I'm a Master degree student, studying at the University of Joensuu, Finland.

You may also be interested in...

Comments and Discussions

GeneralMy vote of 5 Pin
thatraja21-Jan-11 18:12
mvpthatraja21-Jan-11 18:12 
Generalinteresting - have 5 Pin
Pranay Rana3-Jan-11 19:39
memberPranay Rana3-Jan-11 19:39 
GeneralMy vote of 1 Pin
Andreas04920-Feb-10 7:38
memberAndreas04920-Feb-10 7:38 
GeneralExcellent Pin
RugbyLeague2-Oct-08 3:40
memberRugbyLeague2-Oct-08 3:40 
GeneralRe: Excellent Pin
Zaur Nasibov2-Oct-08 4:22
memberZaur Nasibov2-Oct-08 4:22 
GeneralGreat Introduction, Thanks! Pin
NiteBeast22-May-08 17:42
memberNiteBeast22-May-08 17:42 
GeneralVery Interesting Pin
merlin9815-Mar-08 4:50
membermerlin9815-Mar-08 4:50 
GeneralRe: Very Interesting Pin
Zaur Nasibov5-Mar-08 10:34
memberZaur Nasibov5-Mar-08 10:34 
GeneralVery interesting. Pin
Muaddubby4-Mar-08 3:22
memberMuaddubby4-Mar-08 3:22 
GeneralRe: Very interesting. Pin
Zaur Nasibov4-Mar-08 5:09
memberZaur Nasibov4-Mar-08 5:09 
GeneralRe: Very interesting. Pin
Muaddubby4-Mar-08 5:33
memberMuaddubby4-Mar-08 5:33 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170308.1 | Last Updated 29 Feb 2008
Article Copyright 2008 by Zaur Nasibov
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid