Archives Discussions

[shreedhar_pawar]

I have a source array and a destination array of an MST graph created by placing their ids of the MSTs in place of the actual vertices as follows:

src : 16 16 16 16 16   9   9  9   9   9  9  9   9   9   9 19 19 19 19 19 19 10 10 10 10 10 10 16 16 16 16 16 16   9  9   9   9   9 19 19 19 19 19 19 19 19 

dest 9   9 10 9  22 10 10 16 16 16 10 10 10 16 19 10 10 13   9 10  9  13 14 19 19 19 19  9  22 29  9   9  9  19 16 19 16 16  9  10  9 10   9 16   9 34

These sources are arranged correspondingly with its destination in the arrays. I want to bring similar pairs at one place. For eg my o/p should look like..

src   16 16 16 16 16 16   9    9   9  9   9

dest   9   9   9   9  9  9  10  10  10 10 10   .... and so on...!

can this be done in parallel, if not in parallel how can this be done sequentially in a performance efficient way..?

[LeeHowes]

By sorting? Construct an array of source value/index pairs. Sort that array. Then use the indices in the sorted list of pairs to rearrange the source and destination arrays accordingly. A radix sort of small key/value pairs should be pretty fast if you implement it right.

[shreedhar_pawar]

Suppose I sort the src array, src array and the indices array  will look like...

src      9  9  9  9  9    9  9   9   9   9....  16 16 16 16 16  16  16  16  16  16  16...

index   5  6  7  8  9  10 11 12 13 14...    0   1  2   3  4    27   28  29 30  31 32...

then according to index array the dest array will be

          10 10 16 16 16 10 10 10 16 19... 9  9  10  9  22   9   22  29   9    9   9...

by which it is clear that the pairs are not in one place. Even if  the destination array is sorted and the positions are stored it gives the same problem...!

[shreedhar_pawar]

Oh but if the dest array is sorted for each source then we get them all in one place, din't observe this firstly... Did I get you right LeeHowes...?

[LeeHowes]

Yes, I didn't actually say that, but indeed you could do that. It would probably be cleaner (single pass) to make your sort keys bigger and based off the two values. So you have a key that is 16, 9; a key that is 16,10 and so on. It depends on how big your source and dest are of course but, for example, if they are 16 bit values you could sort: (source << 16 + dest, index) as your key/value pairs.

[LeeHowes]

Right, but bringing similar sources together is a start isn't it? It depends on how you define a similar pair. You could sort based on the source and destination being the key if you want to treat "similar" as being based on the lexicographic definition of the pairs.

if you want some other definition of similar you could generate the sorting array instead of just taking the source value across, you could compute something from the pair. Maybe it's the sum of the two values you want, in which case you generate a sums + indices array:

16 + 9, 0; 16 + 9; 1; 10 + 10; 2....

Sort that and then shuffle the source and destination arrays. It's still O(O of sort) as an algorithm.

[himanshu_gautam · Accepted solution]

Bolt's sort_by_key() API would be very hepful for you. Check out.

[shreedhar_pawar]

Please give the link where I can find the sort_by_key algorithm...! I cant find it in clpp Data Primitive library by Google...!

[himanshu_gautam]

http://developer.amd.com/tools/heterogeneous-computing/amd-accelerated-parallel-processing-app-sdk/b...

Check the link above.

Bolt works only for Windows 64-bit only at the moment....Also, APP SDK 2.8 has some Bolt samples.

I see "Sort" out there... But "sort_by_key" is not there yet -- as on APP SDK 2.8

But check the latest preview in the URL above and look for new features.

Bolt is under active development. So, you can expect lot of goodies down the line.

[himanshu_gautam]

Hi Shreedhar,

Did you check bolt? Do you need any further help on this issue?

Thanks,

[shreedhar_pawar]

Hey Himanshu,

   No i din't check until now... but I will surely check n i do need help on this.. Its just that I am  doing some other parts of my code...! will surely tell u of my doubts...!