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	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	import de.schmitzm.geotools.data.WritableGrid;
9
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	}