Han,
It should be fairly simple to estimate the amount of data transmitted
by the two algorithms. Since the reduction on the HashMap is cumulative
(i.e., all of the entries are retained, rather than combined), you will
send some entries more than once in the butterfly reduction pattern.
So, the butterfly reduction pattern does not offer the same benefit for
HashMaps as it does for integer reduction.
Also, since you're posting from a generic email address, it would help
if you stated your affiliation...
Igor
Han Han <saviola7...@gmail.com> wrote on 05/09/2010 05:30:08 PM:
> Hi,
>
> I have 8 HashMaps distributed over 8 places with the PlaceLocalHandle
> functionality. I am trying to merge the contents together into place 0.
I
> have two implementations. The first is the brute forced way where I
insert
> all the entries from HashMaps at other places into the HashMap at place
0:
>
> finish for(i = 1; i < places; i++)
> {
> async(Place.places(i))
> {
> for(e in hashmap.entries())
> {
> val key = e.getKey();
> val value = e.getValue();
> async(Place.places(0))
> {
> hashmap.insert(key, value);
> }
> }
> }
> }
>
> The second way, I am attempting to implement a global reduction of
merging
> the HashMaps, it would look something like this:
>
> initial HashMaps at Places: 0 1 2 3 4 5 6 7
>
> I have a function similar to the one above that merges 4 to 0, 5
> to 1, 6 to 2 and 7 to
3.
>
> I will be left with HashMaps at Places: 0 1 2 3 since 4,5,6,7 have
> been merged into them.
>
> Thereafter, I do the same with 2 to 0 and 3 to 1. And finally
> merging 1 to 0. I do this recursively until place 0.
>
> When I was testing the performance of these two implementations, I
initially
> thought that the global reduction method would outperform the brute
forced
> way. However, the results showed that the brute force way was usually 2x
~
> 3x times faster than the global reduction method. Would anyone have any
idea
> as to why the results are like this? The code for the global reduction
is
> similar to the brute forced in the way it gets the entries and inserts
them
> into the HashMaps.
--
Igor Peshansky (note the spelling change!)
IBM T.J. Watson Research Center
X10: Parallel Productivity and Performance (http://x10-lang.org/)
XJ: No More Pain for XML's Gain (http://www.research.ibm.com/xj/)
"I hear and I forget. I see and I remember. I do and I understand" --
Confucius
------------------------------------------------------------------------------
_______________________________________________
X10-users mailing list
X10-users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/x10-users
