How do I parallelize this?

Question

0.00/5 (No votes)

See more:

I would want to parallelize this on the top loop, but I don't think that there's an analytic formula for c so that c can be computed instead of iterated. Can anyone solve it?

C#

<pre>int nPSEtriangles = PSE_PTS.Length * (PSE_PTS.Length - 1) * (PSE_PTS.Length - 2) / 6;
PSEtriangles = new JPMath.Triangle[nPSEtriangles];
int c = 0;
for (int i = 0; i < PSE_PTS.Length - 2; i++)
	for (int j = i + 1; j < PSE_PTS.Length - 1; j++)
		for (int k = j + 1; k < PSE_PTS.Length; k++)
		{
			PSEtriangles[c] = new JPMath.Triangle(PSE_PTS[i], PSE_PTS[j], PSE_PTS[k]);
			c++;
		}

What I have tried:

staring at it for very long times, concluding always that c cannot be computed in this scenario, only iterated

Posted 22-Aug-24 18:52pm

CommentFree

Updated 22-Aug-24 18:54pm

v2

Add a Solution

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Luc Pattyn · Accepted Answer · 2024-08-23T06:34:00

FIRST APPROACH

With an extra array cstart[] and assuming n=PSE_PTS.Length you could calculate the behavior of c in advance:

int c=0;
for (int i = 0; i < n - 2; i++) {
    cstart[i] = c;
	for (int j = i + 1; j < n - 1; j++)
		for (int k = j + 1; k < n; k++)
		{
			c++;
		}
}

and then use cstart[] to parallelize your outer loop:

for (int i = 0; i < n - 2; i++) {
    c = cstart[i];
    ...
}

SECOND APPROACH

But then you could notice cstart actually holds a predictable sequence of values from a polynomial of the third degree. I won't reproduce all the math involved here, however you can forgo the extra array and simply write:

for (int i = 0; i < n - 2; i++) {
    int y=n-i;
    c = nPSEtriangles - y*(y-1)*(y-2)/6;
    ...
}

assuming int nPSEtriangles = n*(n-1)*(n-2)/6 as you already have.
:)

OriginalGriff · Accepted Answer · 2024-08-22T19:44:00

Unless the JPMath.Triangle constructor takes a significant amount of time, then it's likely that parallelisation will slow down processing rather than accelerate it. As I said yesterday to a different user (or a sock puppet account) Improve the speed of for loops[^] parallelisation is not a magic bullet and it needs to be carefully thought about, or it can slow you down rather than speed you up.

When you parallelise code, you add threads - and there is a processing cost associated with each thread you create because each thread needs it's own stack space and "control block" so the system knows what state it is in, what priority it has, who owns it, and so forth. There is also a shutdown cost, though that is smaller - releasing memory and other resources back to the system. Those costs aren't trivial and if the setup / shutdown time exceeds the processing time each thread uses then your app will run slower.
Additionally, thread execution is restricted by the hardware it runs in: if you have 4 cores then the whole system can only execute 4 threads simultaneously - all the others are "frozen" waiting for core time. And there is a cost associated with freezing and unfreezing a thread as well: nothing is for free! If you have 8 cores, then it's 8 threads and so on.
So if you add many threads by parallelising indiscriminately, you very quickly run into the law of diminishing returns: your app slows down because you tried to speed it up!

I'd start by first measuring the current speed really carefully over a range of data sizes so you have a benchmark to work from, then looking at how you could parallelize the outer loop only, so that each iteration of i is on a separate thread but j and k remain very much the same: you will need to pass each thread a different value of c instead of using a simple increment in the innermost loop. That might speed things up, it might not. I suspect that if your triangle constructor is trivial you aren't going to get a major speed increase in any way.

Parallelism isn't a magic bullet - I know I said that above but it bears repeating - you need to think about it very carefully and it will change and complicate your code so it'll be a lot harder to test, debug, and maintain.

How do I parallelize this?

2 solutions

Solution 2

Solution 1

Add your solution here

Preview 0