001: /*
002: * This file or a portion of this file is licensed under the terms of
003: * the Globus Toolkit Public License, found in file GTPL, or at
004: * http://www.globus.org/toolkit/download/license.html. This notice must
005: * appear in redistributions of this file, with or without modification.
006: *
007: * Redistributions of this Software, with or without modification, must
008: * reproduce the GTPL in: (1) the Software, or (2) the Documentation or
009: * some other similar material which is provided with the Software (if
010: * any).
011: *
012: * Copyright 1999-2004 University of Chicago and The University of
013: * Southern California. All rights reserved.
014: */
015: package org.griphyn.cPlanner.partitioner;
016:
017: import org.griphyn.cPlanner.common.PegasusProperties;
018: import org.griphyn.cPlanner.common.LogManager;
019:
020: import org.griphyn.cPlanner.partitioner.graph.GraphNode;
021: import org.griphyn.cPlanner.partitioner.graph.Bag;
022: import org.griphyn.cPlanner.partitioner.graph.LabelBag;
023:
024: import java.util.Map;
025: import java.util.HashMap;
026: import java.util.List;
027: import java.util.ArrayList;
028: import java.util.LinkedList;
029: import java.util.Iterator;
030: import java.util.Set;
031: import java.util.HashSet;
032:
033: /**
034: * This partitioner partitions the DAX into smaller partitions as specified by
035: * the labels associated with the jobs. If no label is specified, then the
036: * partitioner puts the job into a unique partition corresponding to the job
037: * ID.
038: *
039: * @author Karan Vahi
040: * @version $Revision: 50 $
041: *
042: *
043: */
044: public class Label extends Partitioner {
045:
046: /**
047: * The default label that is associated with the job in case of no label
048: * being specified.
049: */
050: // public static final String DEFAULT_LABEL = "default";
051: /**
052: * A short description about the partitioner.
053: */
054: public static final String DESCRIPTION = "Label Based Partitioning";
055:
056: /**
057: * A map indexed by the label. Each value is a partition object
058: * consisting of jobs with that label.
059: */
060: private Map mPartitionMap;
061:
062: /**
063: * The first in first out queue, that manages the set of gray vertices in a
064: * breadth first search.
065: */
066: private LinkedList mQueue;
067:
068: /**
069: * The handle to the Logging object.
070: */
071: private LogManager mLogger;
072:
073: /**
074: * The overloaded constructor.
075: *
076: * @param root the dummy root node of the graph.
077: * @param graph the map containing all the nodes of the graph keyed by
078: * the logical id of the nodes.
079: * @param properties the properties passed to the planner.
080: */
081: public Label(GraphNode root, Map graph, PegasusProperties properties) {
082: super (root, graph, properties);
083: mPartitionMap = new HashMap(10);
084: mQueue = new LinkedList();
085: mLogger = LogManager.getInstance();
086: }
087:
088: /**
089: * Partitions the graph passed in the constructor, on the basis of the labels
090: * associated with the nodes in the graph. All the nodes, with the same label
091: * are deemed to be in the same partition.
092: *
093: * @param c the callback for the partitioner.
094: */
095: public void determinePartitions(Callback c) {
096: int currentDepth = 0;
097: GraphNode node;
098: GraphNode parent;
099: GraphNode child;
100: int depth = 0;
101: List levelList = new java.util.LinkedList();
102: String currentLabel = null;
103: int i = 0, partitionNum = 0;
104:
105: mLogger.log("Starting Graph Traversal",
106: LogManager.INFO_MESSAGE_LEVEL);
107: //set the depth of the dummy root as 0
108: mRoot.setDepth(currentDepth);
109:
110: mQueue.addLast(mRoot);
111:
112: while (!mQueue.isEmpty()) {
113: node = (GraphNode) mQueue.getFirst();
114: depth = node.getDepth();
115: currentLabel = getLabel(node);
116: if (currentDepth < depth) {
117: //a new level starts
118: currentDepth++;
119: levelList.clear();
120: }
121:
122: //get the partition for the label
123: Partition p = null;
124: if (mPartitionMap.containsKey(currentLabel)) {
125: p = (Partition) mPartitionMap.get(currentLabel);
126: } else {
127: p = new Partition();
128: if (currentDepth > 0) {
129: partitionNum++;
130: p.setIndex(partitionNum);
131: p.setID(getPartitionID(partitionNum));
132: mPartitionMap.put(currentLabel, p);
133: }
134: }
135:
136: if (p.lastAddedNode() != null
137: && depth > p.lastAddedNode().getDepth() + 1) {
138: throw new RuntimeException("Invalid labelled graph");
139: /*
140: //partition with current label has been fully
141: //constructed. write out the existing partition
142:
143: //create a new partition
144: Partition newp = new Partition();
145: newp.addNode(node);
146: mPartitionMap.put(currentLabel,newp);
147: */
148: } else if (currentDepth > 0) {
149: //add to the existing partition for the current label
150: p.addNode(node);
151: //also associate the partition id with the node
152: node.getBag().add(LabelBag.PARTITION_KEY, p.getID());
153: }
154:
155: mLogger.log("Adding to level " + currentDepth + " "
156: + node.getID(), LogManager.DEBUG_MESSAGE_LEVEL);
157: levelList.add(node);
158:
159: node.setColor(GraphNode.BLACK_COLOR);
160: for (Iterator it = node.getChildren().iterator(); it
161: .hasNext();) {
162: child = (GraphNode) it.next();
163: if (!child.isColor(GraphNode.GRAY_COLOR)
164: && child.parentsColored(GraphNode.BLACK_COLOR)) {
165: mLogger.log("Adding to queue " + child.getID(),
166: LogManager.DEBUG_MESSAGE_LEVEL);
167: child.setDepth(depth + 1);
168: child.setColor(GraphNode.GRAY_COLOR);
169: mQueue.addLast(child);
170: }
171:
172: }
173: node = (GraphNode) mQueue.removeFirst();
174: mLogger.log("Removed " + node.getID(),
175: LogManager.DEBUG_MESSAGE_LEVEL);
176: }
177: mLogger.logCompletion("Starting Graph Traversal",
178: LogManager.INFO_MESSAGE_LEVEL);
179:
180: for (Iterator it = mPartitionMap.entrySet().iterator(); it
181: .hasNext();) {
182: Map.Entry entry = (Map.Entry) it.next();
183: Partition p = (Partition) entry.getValue();
184: p.constructPartition();
185: mLogger.log("Partition is " + p.getNodeIDs()
186: + " corresponding to label " + entry.getKey(),
187: LogManager.DEBUG_MESSAGE_LEVEL);
188: c.cbPartition(p);
189: }
190:
191: mLogger.log("Determining relations between partitions",
192: LogManager.INFO_MESSAGE_LEVEL);
193: //construct the relations
194: for (Iterator it = mPartitionMap.entrySet().iterator(); it
195: .hasNext();) {
196: Map.Entry entry = (Map.Entry) it.next();
197: Partition p = (Partition) entry.getValue();
198: List roots = p.getRootNodes();
199: Set parentPartitions = new HashSet(roots.size());
200:
201: //get the Root nodes for each partition and
202: //for each root, determine the partitions of it's parents
203: for (Iterator rootIt = roots.iterator(); rootIt.hasNext();) {
204: node = (GraphNode) rootIt.next();
205: for (Iterator parentsIt = node.getParents().iterator(); parentsIt
206: .hasNext();) {
207: parent = (GraphNode) parentsIt.next();
208: //the parents partition id is parent for the
209: //partition containing the root
210: parentPartitions.add(parent.getBag().get(
211: LabelBag.PARTITION_KEY));
212: }
213: }
214: //write out all the parents of the partition
215: if (!parentPartitions.isEmpty()) {
216: c.cbParents(p.getID(), new ArrayList(parentPartitions));
217: }
218: }
219: mLogger.logCompletion(
220: "Determining relations between partitions",
221: LogManager.INFO_MESSAGE_LEVEL);
222:
223: //done with the partitioning
224: c.cbDone();
225: }
226:
227: /**
228: * Returns a textual description of the transfer implementation.
229: *
230: * @return a short textual description
231: */
232: public String description() {
233: return this .DESCRIPTION;
234: }
235:
236: /**
237: * Returns the label for the node. If no label is associated with the node,
238: * then the ID of the node is assumed as the label.
239: *
240: * @param node the node for which the label is required.
241: *
242: * @return the label associated with the job, else the id of the node.
243: */
244: private String getLabel(GraphNode node) {
245: Bag b = (LabelBag) node.getBag();
246: Object obj = b.get(LabelBag.LABEL_KEY);
247: return (obj == null) ? node.getID() /*this.DEFAULT_LABEL*/
248: : (String) obj;
249: }
250:
251: /**
252: * Constructs the id for the partition.
253: *
254: * @param id the integer id.
255: *
256: * @return the ID of the partition.
257: */
258: private String getPartitionID(int id) {
259: StringBuffer sb = new StringBuffer(5);
260: sb.append("ID").append(id);
261: return sb.toString();
262: }
263:
264: }
|