spmd/split/SplitMap2D.java

package appl.parallel.spmd.split;

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

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