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	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	}