i wait so much because of loops

Luc Pattyn

Hi Harold, in

for (int k = 0; k < 2000; k++) {
for (int i = 0; i < 2000; i++) {
for (int j = 0; j < 2000; j++) {
G[i, j] = Math.Min(G[i, j], G[i, k] + G[k, j]);
}
}
}

each element G[i,j] depends on the elements from the row and column it sits in, so you can execute the iterations of the inner loop in parallel as they all modify a different matrix element, and all read elements that are not going to be written, unless k==i or k==j. You can deal with the former right away (outside the inner loop), and the latter can be handled separately. So it becomes:

for (int k = 0; k < 2000; k++) {
for (int i = 0; i < 2000; i++) {
if (i==k) {
for (int j = 0; j < 2000; j++) {
G[i, j] = Math.Min(G[i, j], G[i, k] + G[k, j]);
}
} else {
//G[i, j] = Math.Min(G[i, j], G[i, j] + G[j, j]); // special case k==j
G[i, k] = Math.Min(G[i, k], G[i, k] + G[k, k]); // special case k==j
for (int j = 0; j < 2000; j++) {
if (j!=k) G[i, j] = Math.Min(G[i, j], G[i, k] + G[k, j]);
}
}
}
}

And now the highlighted loop has no data dependencies any more. Furthermore, the diagonal elements start at value zero; assuming no negative cycles in the graph, their MIN operation won't affect them, and the special cases do not need to be set aside, so we are back at the original code. If negative cycles are allowed, proper handling still allows parallellization with negative cycle detection (which turns diagonal elements into negative values), and even then the special cases are not really necessary as the presence of negative cycles makes the results not optimal as the optimum would be minus infinity anyway. [EDIT] fixed a mistake, signaled by Pete [\EDIT] :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]

Prolific encyclopedia fixture proof-reader browser patron addict?
We all depend on the beast below.

modified on Monday, May 3, 2010 5:27 PM

Lost User · modified on Monday, May 3, 2010 5:27 PM

Nice thanks :)

Luc Pattyn

you're welcome. Now go install .NET 4.0 and write that article! :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]

Prolific encyclopedia fixture proof-reader browser patron addict?
We all depend on the beast below.

Lost User

I'm not sure.. that's actually quite advanced.. and I'm still only halfway understanding linear time suffix array construction (bit slow I know..)

Luc Pattyn

If things are getting slow, you should start doing some of them in parallel... :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]

Prolific encyclopedia fixture proof-reader browser patron addict?
We all depend on the beast below.

Lost User

:laugh: Win :) Anyway, how's your prime number thing going?

Pete OHanlon

I've just knocked up a blog post[^] to show how this code could be accomplished using .NET 4. Here's the same code rewritten to use the Task Parallel Library.

"WPF has many lovers. It's a veritable porn star!" - Josh Smith

As Braveheart once said, "You can take our freedom but you'll never take our Hobnobs!" - Martin Hughes.

My blog | My articles | MoXAML PowerToys | Onyx

Luc Pattyn

very good, thanks, it currently uses 1.1 threads. There isn't enough work to keep a dual-core busy :laugh: :laugh: I'll publish it later this year.

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]

Prolific encyclopedia fixture proof-reader browser patron addict?
We all depend on the beast below.

Luc Pattyn

Hi Pete, I'm afraid I disagree with your parallel sample in this particular case; it seems to violate the Floyd-Warshall_algorithm[^], which theoretically uses a three-dimensional array, but then maps the k-iterations (the outer loop) onto a single two-dimensional array, provided it gets executed in the correct sequence. In another part of this thread I have shown Harold how parts of the calculation could be executed in parallel, but your and my approach are quite different. FWIW: I have no clue what the speed up would be for say a 2000 node graph and a 4-way core; I'm not overly optimistic as there is a lot of data involved, so using multiple cores is likely to seriously reduce cache efficiency. :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]

Prolific encyclopedia fixture proof-reader browser patron addict?
We all depend on the beast below.

Pete OHanlon

Luc - I wasn't trying to demonstrate the algorithm. I was demonstrating purely and simply how to convert his code into a Parallel.For.

"WPF has many lovers. It's a veritable porn star!" - Josh Smith

As Braveheart once said, "You can take our freedom but you'll never take our Hobnobs!" - Martin Hughes.

My blog | My articles | MoXAML PowerToys | Onyx

Pete OHanlon

BTW - your code sample won't compile. The following line is the problem because of an uninitialized variable:

G[i, j] = Math.Min(G[i, j], G[i, j] + G[j, j]); // special case k==j

"WPF has many lovers. It's a veritable porn star!" - Josh Smith

As Braveheart once said, "You can take our freedom but you'll never take our Hobnobs!" - Martin Hughes.

My blog | My articles | MoXAML PowerToys | Onyx

Luc Pattyn

I appreciate that, Pete. However I'm afraid you wrecked the algorithm, which isn't a very nice thing to do. When the results aren't the same, there isn't much point in measuring the speed difference, is there? :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]

Prolific encyclopedia fixture proof-reader browser patron addict?
We all depend on the beast below.

Luc Pattyn

you're right, I replaced k's by j's, it should have been the other way around. Sorry for that. :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]

Prolific encyclopedia fixture proof-reader browser patron addict?
We all depend on the beast below.

karayel_kara

hi ,i modified my code folowing that, but i get some error folowing code running ! double[,] a, b, c; a = new double[2000, 2000]; b=new double[2000,2000]; c=new double[2000,2000]; int s = 2000; Parallel.For(0, s, delegate(int i) { for (int j = 0; j < s; j++) { double v = 0; for (int k = 0; k < s; k++) { v += a[i, k] * b[k, j]; } c[i, j] = v; } }); bu my code isn't run :( Parallel.For(0, nrons, delegate(int k) { for (i = 0; i < nrons; i++) for (j = 0; j < nrons; j++) //G[i, j] = Math.Min(G[i, j], G[i, k] + G[k, j]); if (G[i, j]> (G[i, k] + G[k, j]) ) G[i, j] =(G[i, k] + G[k, j]) ; } ); why did i get error ?

Luc Pattyn

karayel_kara wrote:

my code isn't run

is not informative. does it compile? if not, what is the first error? does it run? if not, what is the first exception, with all the details? and at what line is it pointing? anyway, your code looks all wrong. You now have three arrays. Why? You don't initialize the arrays. I see six for loops, you only need three. And the way I understand the algorithm you can not possibly run the outer loop in parallel (that was the essence of my comment to Pete too). And please, please, please, please, please, please, show code in PRE tags, not in CODE tags. Final remark: when all you do to the algorithm is run it in parallel, the best you can hope for is to get it N times faster, with N the number of cores, say 4. That is something, but not much. And there are no guarantees. My first experiment did run 5 times slower, because it trashed the caches all the time! (and I'm afraid that will be true for your app too). :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]

Prolific encyclopedia fixture proof-reader browser patron addict?
We all depend on the beast below.