cancel
Showing results for 
Search instead for 
Did you mean: 

Archives Discussions

shreedhar_pawar
Adept II

Parallel Manipulation of a Source and destination Array of a Graph

Jump to solution

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..?

Tags (1)
0 Likes
1 Solution

Accepted Solutions
himanshu_gautam
Grandmaster

Re: Parallel Manipulation of a Source and destination Array of a Graph

Jump to solution

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

View solution in original post

0 Likes
10 Replies
LeeHowes
Staff
Staff

Re: Parallel Manipulation of a Source and destination Array of a Graph

Jump to solution

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
Adept II

Re: Parallel Manipulation of a Source and destination Array of a Graph

Jump to solution

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...!

0 Likes
shreedhar_pawar
Adept II

Re: Parallel Manipulation of a Source and destination Array of a Graph

Jump to solution

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...?

0 Likes
LeeHowes
Staff
Staff

Re: Parallel Manipulation of a Source and destination Array of a Graph

Jump to solution

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.

0 Likes
LeeHowes
Staff
Staff

Re: Parallel Manipulation of a Source and destination Array of a Graph

Jump to solution

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.

0 Likes
himanshu_gautam
Grandmaster

Re: Parallel Manipulation of a Source and destination Array of a Graph

Jump to solution

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

View solution in original post

0 Likes
shreedhar_pawar
Adept II

Re: Parallel Manipulation of a Source and destination Array of a Graph

Jump to solution

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

0 Likes
himanshu_gautam
Grandmaster

Re: Parallel Manipulation of a Source and destination Array of a Graph

Jump to solution

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.

0 Likes
himanshu_gautam
Grandmaster

Re: Parallel Manipulation of a Source and destination Array of a Graph

Jump to solution

Hi Shreedhar,

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

Thanks,

0 Likes