Synchronous Parallel Process in C# / C++

Question

I have an array x[] containing data. Also there is an array of "system states" c[]. The process:

for(i = 1; i < N; i++)
{   
  a = f1(x[i] + c[i-1]);
  b = f2(x[i] + c[i-1]);
  c[i] = a + b;
}

Is there any efficient way to find the values of f1 and f2 on 2-core system using 2 parallel threads? I mean the following (in pseudo-code):

thread_1
{
    for(i = 1; i < N; i++)
      a = f1(x[i] + c[i-1]);    
}
thread_2
{
    for(i = 1; i < N; i++)
    {
      b = f2(x[i] + c[i-1]);
      c[i] = a + b;  //here we somehow get a{i} from thread_1
    }
}

f1 and f2 are not time consumptive, but have to be calculated many times, so desired speedup is about x2. See the diagram for graphical representation:

Looking for code examples for Windows.

Answer 1

If I understand you right,

• a[i] can only be calculated when c[i-1] is available
• b[i] can only be calculated when c[i-1] is available
• c[i] is only available when a[i] and b[i] are calculated

It means that the only process which you can do separately is calculating a[i] and b[i].

That's how I see it in C#:

for (int i = 1; i < N; i++)
{
    Task<double> calcA = Task.Factory.StartNew(() => { return f1(x[i] + c[i-1]); });
    Task<double> calcB = Task.Factory.StartNew(() => { return f2(x[i] + c[i-1]); });

    // .Result will block the execution and wait for both calculations to complete
    c[i] = calcA.Result + calcB.Result; 
}

This will run two separate threads, which will calculate f1 and f2 respectively. After both f1 and f2 are calculated, it will set c[i] value, and run the next iteration.

Note that:

• I use double, assuming that your f1 and f2 return double
• The loop starts from 1, assuming that you have some initial a[0] and b[0] values. Otherwise, c[i-1] would throw an exception
• This will only bring improvement if calculation of f1 and f2 is really resource-consuming and long, compared to other calculations
• Task.Factory.StartNew (unlike using Thread) uses ThreadPool which means that it doesn't create a new thread every time, but reuses the existing from the pool. It noticably reduces the overhead.

Answer 2

The only parallel part in this algorithm is calculation of f1 and f2, but you say that f1 and f2 are not time consumptive, so it might be much better to use SIMD vectorization (e.g. System.Numerics.Vectors in C#) and run it on one core (that also reduce cache misses). Or probably you could modify your algorithm to be parallelizeable (but it might require hard work).