spmd/split/SplitMap2D.java

package appl.parallel.spmd.split;

import java.awt.Point;
import java.awt.Rectangle;
import java.awt.geom.Rectangle2D;
import java.util.Vector;

import appl.parallel.client.RemoteExecutionController;
import appl.parallel.spmd.split.AbstractSplitMap.NeighborhoodBoxingMode;
import appl.parallel.util.Helper;
import appl.util.RasterMetaData;
import schmitzm.data.WritableGrid;

/**
 * Responsible for splitting a 2D Area (e.g a {@link WritableGrid}) in a 2D
 * fashion. The splitting is irregular, meaning that the rectangles are not
 * equally sized, but partitioned according to the given weights. 
 * Splitting is as follows: <br><br>
 * 1 to 4 Partitions: 1 row <br>
 * 4 to 8 Partitions: 2 rows <br>
 * 9 to 15 Partitions: 3 rows <br>
 * and so on (depending on the square root of the partititons)<br>
 * <br>
 * For partitioning the this class strongly depends on {@link SplitMap1DHorizontal}
 * and {@link SplitMap1DVertical}. First the squareroot of the number of
 * participating resources is taken to determine how many rows should be
 * created. After this the height of the rows is weighted by adding the weight
 * of the resources in that horizontal partition. The Grid is then splitted
 * horizontal. Finally the horizontal partitions are splitted vertical according
 * to the relative weight to each other. This is only a a virtual split (a map
 * of a split). <br>
 * A neighborhood range can be specified to create partitions that overlap each
 * other. This overlapping can be done in two different ways: <br>
 * <br>
 * <b>Inboxing</b>(default):<br>
 * <br>
 * Inboxing means, that the neighborhood area is not part of the calculation
 * area. <br>
 * <br>
 * <b>Outboxing:</b><br>
 * Outboxing means that the neighborhood area is part of the calculation area.
 * <br>
 * <br>
 * Note that this may also be applied to three dimensional data structures (a 2D
 * splitting of a 3D datatype).
 * 
 * @author Dominik Appl
 */

public class SplitMap2D extends AbstractSplitMap implements SplitMap {

        private SplitMap1DHorizontal horizontalMap;

        private SplitMap1DVertical[] verticalMaps;

        public SplitMap2D(int width, int height, int neighborhoodRange,
                        int noOfPartitions, NeighborhoodBoxingMode boxingMode) {
                super(width, height, neighborhoodRange, noOfPartitions, boxingMode);
        }

        /**
         * needed for serialization
         */
        public SplitMap2D() {
        }

        /*
         * (non-Javadoc)
         * 
         * @see appl.parallel.spmd.split.AbstractSplitMap#makeMap()
         */
        public void makeMap() {
                // take the squareroot of the number of participating resources to
                // determine the number of rows:
                int noOfRows = (int) Math.sqrt(noOfPartitions);
                // calculate weights for the rows (sum of the weights of the partitions
                // inside that row)
                double rowWeights[] = new double[noOfRows];
                int noOfCols[] = new int[noOfRows]; // noOfCols per row
                for (int row = 0; row < noOfRows; row++) {
                        // calculate no. of cols in the row:
                        noOfCols[row] = (noOfPartitions / noOfRows);
                        // the last row may contain a greater number of cols
                        if (row == noOfRows - 1)
                                noOfCols[row] = noOfPartitions
                                                - ((noOfRows - 1) * noOfCols[row]);
                        for (int col = 0; col < noOfCols[row]; col++)
                                rowWeights[row] += weights[row * col + col];
                }

                // create the horizontal Splitmap
                horizontalMap = new SplitMap1DHorizontal(globalWidth, globalHeight,
                                neighborhoodRange, noOfRows, boxingMode);
                horizontalMap.setWeights(rowWeights);
                horizontalMap.makeMap();

                // for each horizontal partition create a vertical split
                verticalMaps = new SplitMap1DVertical[noOfRows];
                for (int row = 0; row < noOfRows; row++) {
                        //notice: all splitmaps start at (0,0), later a conversion must be made
                        verticalMaps[row] = new SplitMap1DVertical((int) horizontalMap
                                        .getGlobalBounds().getWidth(), (int) horizontalMap
                                        .getPartitionCalculationBounds(row).getHeight(), neighborhoodRange,
                                        noOfCols[row], boxingMode);
                        int ratings[] = new int[noOfCols[row]];
                        for (int col = 0; col < noOfCols[row]; col++) {
                                {
                                        // the rating of the col is the weight of the col * 100000
                                        // (ratings must be positive integers)
                                        ratings[col] = (int) (weights[row * col + col] * 1000000);

                                }

                                verticalMaps[row].setWeights(Helper.calculateWeights(ratings));
                                verticalMaps[row].makeMap();
                        }
                }
                // now we have partitioned the grid. Lets assign the calculation and
                // neighborhoodareas:
                for (int i = 0; i < noOfPartitions; i++) {
                        int row = getRowForIdx(i);
                        int col = getColForIdx(i);
                        partitionCalculationBounds[i] = verticalMaps[row]
                                        .getPartitionCalculationBounds(col);
                        //because all splitmaps start with (0,0) we must move 
                        //the rectangles to the right position
                        int x = (int) partitionCalculationBounds[i].getX(); //the x value remains unchanged
                        partitionCalculationBounds[i].setLocation(
                                        new Point(x,(int) horizontalMap.getPartitionCalculationBounds(row).getY()));
                        // if there is only one partition there are no explicit neighborhood
                        // bounds
                        if (noOfPartitions == 1)
                                partitionNeighborhoodBounds[i] = partitionCalculationBounds[i];
                        // else simply extend the Rectangle with the Neighborhoodbounds
                        // created calculation Area (@see AbstractSplitMap)
                        else
                                partitionNeighborhoodBounds[i] = new Rectangle(
                                                (int) partitionCalculationBounds[i].getX()
                                                                - neighborhoodRange,
                                                (int) partitionCalculationBounds[i].getY()
                                                                - neighborhoodRange,
                                                (int) (partitionCalculationBounds[i].getWidth() + 2 * neighborhoodRange),
                                                (int) (partitionCalculationBounds[i].getHeight() + 2 * neighborhoodRange));

                        // cut of the obverlapping sections which are out of the grid:
                        partitionNeighborhoodBounds[i] = partitionNeighborhoodBounds[i]
                                        .intersection(globalBounds);

                        // the partitionCalculation bounds were created for inboxing:
                        if (boxingMode == NeighborhoodBoxingMode.outBoxing)
                                partitionCalculationBounds[i] = partitionNeighborhoodBounds[i];
                }
        }

        /**
         * @param i
         * @return
         */
        private int getColForIdx(int index) {
                int noOfRows = (int) Math.sqrt(noOfPartitions);
                int avgNoOfCols = noOfPartitions / noOfRows;
                int currentRow = getRowForIdx(index);
                int returnValue = (index - currentRow*avgNoOfCols);
                return returnValue;
        }

        private int getRowForIdx(int index) {
                int noOfRows = (int) Math.sqrt(noOfPartitions);
                int avgNoOfCols = noOfPartitions / noOfRows;
                int returnValue = index / avgNoOfCols;
                //special handling for the last row (contains more partitions)
                if(noOfRows==returnValue)
                        return noOfRows-1;
                else return returnValue;
        }

        /*
         * (non-Javadoc)
         * 
         * @see appl.parallel.spmd.split.SplitMap#getNeighborsForPosition(int)
         */
        public int[] getNeighborsForPosition(int pos) {
                Vector neighbors = new Vector();
                // simply intersect with all partitions to find the neighbors:
                for (int i = 0; i < noOfPartitions; i++) {
                        if (i == pos)
                                continue;
                        if (partitionNeighborhoodBounds[i]
                                        .intersects(partitionNeighborhoodBounds[pos]))
                                neighbors.add(pos);
                }
                int results[] = new int[neighbors.size()];
                // copy into array
                for (int i = 0; i < results.length; i++) {
                        results[i] = (Integer) neighbors.get(i);
                }
                return results;
        }

        /*
         * (non-Javadoc)
         * 
         * @see appl.parallel.spmd.split.AbstractSplitMap#getDescription()
         */
        @Override
        public String getDescription() {
                return "2D-irregular Splitmap";
        }

}
1	mojays	2	package appl.parallel.spmd.split;
2
3			import java.awt.Point;
4			import java.awt.Rectangle;
5			import java.awt.geom.Rectangle2D;
6			import java.util.Vector;
7
8			import appl.parallel.client.RemoteExecutionController;
9			import appl.parallel.spmd.split.AbstractSplitMap.NeighborhoodBoxingMode;
10			import appl.parallel.util.Helper;
11			import appl.util.RasterMetaData;
12			import schmitzm.data.WritableGrid;
13
14			/**
15			* Responsible for splitting a 2D Area (e.g a {@link WritableGrid}) in a 2D
16			* fashion. The splitting is irregular, meaning that the rectangles are not
17			* equally sized, but partitioned according to the given weights.
18			* Splitting is as follows: <br><br>
19			* 1 to 4 Partitions: 1 row <br>
20			* 4 to 8 Partitions: 2 rows <br>
21			* 9 to 15 Partitions: 3 rows <br>
22			* and so on (depending on the square root of the partititons)<br>
23			* <br>
24			* For partitioning the this class strongly depends on {@link SplitMap1DHorizontal}
25			* and {@link SplitMap1DVertical}. First the squareroot of the number of
26			* participating resources is taken to determine how many rows should be
27			* created. After this the height of the rows is weighted by adding the weight
28			* of the resources in that horizontal partition. The Grid is then splitted
29			* horizontal. Finally the horizontal partitions are splitted vertical according
30			* to the relative weight to each other. This is only a a virtual split (a map
31			* of a split). <br>
32			* A neighborhood range can be specified to create partitions that overlap each
33			* other. This overlapping can be done in two different ways: <br>
34			* <br>
35			* <b>Inboxing</b>(default):<br>
36			* <br>
37			* Inboxing means, that the neighborhood area is not part of the calculation
38			* area. <br>
39			* <br>
40			* <b>Outboxing:</b><br>
41			* Outboxing means that the neighborhood area is part of the calculation area.
42			* <br>
43			* <br>
44			* Note that this may also be applied to three dimensional data structures (a 2D
45			* splitting of a 3D datatype).
46			*
47			* @author Dominik Appl
48			*/
49
50			public class SplitMap2D extends AbstractSplitMap implements SplitMap {
51
52			private SplitMap1DHorizontal horizontalMap;
53
54			private SplitMap1DVertical[] verticalMaps;
55
56			public SplitMap2D(int width, int height, int neighborhoodRange,
57			int noOfPartitions, NeighborhoodBoxingMode boxingMode) {
58			super(width, height, neighborhoodRange, noOfPartitions, boxingMode);
59			}
60
61			/**
62			* needed for serialization
63			*/
64			public SplitMap2D() {
65			}
66
67			/*
68			* (non-Javadoc)
69			*
70			* @see appl.parallel.spmd.split.AbstractSplitMap#makeMap()
71			*/
72			public void makeMap() {
73			// take the squareroot of the number of participating resources to
74			// determine the number of rows:
75			int noOfRows = (int) Math.sqrt(noOfPartitions);
76			// calculate weights for the rows (sum of the weights of the partitions
77			// inside that row)
78			double rowWeights[] = new double[noOfRows];
79			int noOfCols[] = new int[noOfRows]; // noOfCols per row
80			for (int row = 0; row < noOfRows; row++) {
81			// calculate no. of cols in the row:
82			noOfCols[row] = (noOfPartitions / noOfRows);
83			// the last row may contain a greater number of cols
84			if (row == noOfRows - 1)
85			noOfCols[row] = noOfPartitions
86			- ((noOfRows - 1) * noOfCols[row]);
87			for (int col = 0; col < noOfCols[row]; col++)
88			rowWeights[row] += weights[row * col + col];
89			}
90
91			// create the horizontal Splitmap
92			horizontalMap = new SplitMap1DHorizontal(globalWidth, globalHeight,
93			neighborhoodRange, noOfRows, boxingMode);
94			horizontalMap.setWeights(rowWeights);
95			horizontalMap.makeMap();
96
97			// for each horizontal partition create a vertical split
98			verticalMaps = new SplitMap1DVertical[noOfRows];
99			for (int row = 0; row < noOfRows; row++) {
100			//notice: all splitmaps start at (0,0), later a conversion must be made
101			verticalMaps[row] = new SplitMap1DVertical((int) horizontalMap
102			.getGlobalBounds().getWidth(), (int) horizontalMap
103			.getPartitionCalculationBounds(row).getHeight(), neighborhoodRange,
104			noOfCols[row], boxingMode);
105			int ratings[] = new int[noOfCols[row]];
106			for (int col = 0; col < noOfCols[row]; col++) {
107			{
108			// the rating of the col is the weight of the col * 100000
109			// (ratings must be positive integers)
110			ratings[col] = (int) (weights[row * col + col] * 1000000);
111
112			}
113
114			verticalMaps[row].setWeights(Helper.calculateWeights(ratings));
115			verticalMaps[row].makeMap();
116			}
117			}
118			// now we have partitioned the grid. Lets assign the calculation and
119			// neighborhoodareas:
120			for (int i = 0; i < noOfPartitions; i++) {
121			int row = getRowForIdx(i);
122			int col = getColForIdx(i);
123			partitionCalculationBounds[i] = verticalMaps[row]
124			.getPartitionCalculationBounds(col);
125			//because all splitmaps start with (0,0) we must move
126			//the rectangles to the right position
127			int x = (int) partitionCalculationBounds[i].getX(); //the x value remains unchanged
128			partitionCalculationBounds[i].setLocation(
129			new Point(x,(int) horizontalMap.getPartitionCalculationBounds(row).getY()));
130			// if there is only one partition there are no explicit neighborhood
131			// bounds
132			if (noOfPartitions == 1)
133			partitionNeighborhoodBounds[i] = partitionCalculationBounds[i];
134			// else simply extend the Rectangle with the Neighborhoodbounds
135			// created calculation Area (@see AbstractSplitMap)
136			else
137			partitionNeighborhoodBounds[i] = new Rectangle(
138			(int) partitionCalculationBounds[i].getX()
139			- neighborhoodRange,
140			(int) partitionCalculationBounds[i].getY()
141			- neighborhoodRange,
142			(int) (partitionCalculationBounds[i].getWidth() + 2 * neighborhoodRange),
143			(int) (partitionCalculationBounds[i].getHeight() + 2 * neighborhoodRange));
144
145			// cut of the obverlapping sections which are out of the grid:
146			partitionNeighborhoodBounds[i] = partitionNeighborhoodBounds[i]
147			.intersection(globalBounds);
148
149			// the partitionCalculation bounds were created for inboxing:
150			if (boxingMode == NeighborhoodBoxingMode.outBoxing)
151			partitionCalculationBounds[i] = partitionNeighborhoodBounds[i];
152			}
153			}
154
155			/**
156			* @param i
157			* @return
158			*/
159			private int getColForIdx(int index) {
160			int noOfRows = (int) Math.sqrt(noOfPartitions);
161			int avgNoOfCols = noOfPartitions / noOfRows;
162			int currentRow = getRowForIdx(index);
163			int returnValue = (index - currentRow*avgNoOfCols);
164			return returnValue;
165			}
166
167			private int getRowForIdx(int index) {
168			int noOfRows = (int) Math.sqrt(noOfPartitions);
169			int avgNoOfCols = noOfPartitions / noOfRows;
170			int returnValue = index / avgNoOfCols;
171			//special handling for the last row (contains more partitions)
172			if(noOfRows==returnValue)
173			return noOfRows-1;
174			else return returnValue;
175			}
176
177			/*
178			* (non-Javadoc)
179			*
180			* @see appl.parallel.spmd.split.SplitMap#getNeighborsForPosition(int)
181			*/
182			public int[] getNeighborsForPosition(int pos) {
183			Vector neighbors = new Vector();
184			// simply intersect with all partitions to find the neighbors:
185			for (int i = 0; i < noOfPartitions; i++) {
186			if (i == pos)
187			continue;
188			if (partitionNeighborhoodBounds[i]
189			.intersects(partitionNeighborhoodBounds[pos]))
190			neighbors.add(pos);
191			}
192			int results[] = new int[neighbors.size()];
193			// copy into array
194			for (int i = 0; i < results.length; i++) {
195			results[i] = (Integer) neighbors.get(i);
196			}
197			return results;
198			}
199
200			/*
201			* (non-Javadoc)
202			*
203			* @see appl.parallel.spmd.split.AbstractSplitMap#getDescription()
204			*/
205			@Override
206			public String getDescription() {
207			return "2D-irregular Splitmap";
208			}
209
210			}