Menu
▾
▴
[Gridsim-commits] SF.net SVN: gridsim: [164] branches/gridsim-4.1-parallel/source/gridsim/ parallel
|
From: <xu...@us...> - 2008-03-28 11:15:30
|
Revision: 164
http://gridsim.svn.sourceforge.net/gridsim/?rev=164&view=rev
Author: xulio
Date: 2008-03-28 04:14:42 -0700 (Fri, 28 Mar 2008)
Log Message:
-----------
BBModel - Need check the Simply version
Allocs - Extended checks are necesary
Added Paths:
-----------
branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/
branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/BBModel.java
branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/BBParallelGridlet.java
branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/BBParallelTask.java
branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/BBTaskModel.java
branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/MatrixBBModel.java
branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/MatrixBBTaskModel.java
branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/ResBBParallelGridlet.java
branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/ResBBParallelTask.java
branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/SimpleBBModel.java
branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/SimplifyResBBParallelGridlet.java
branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/
branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/BackFillingAlloc.java
branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/BackFillingL1Alloc.java
branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/EASYBackFillingAlloc.java
branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/FIFOAlloc.java
branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/FirstFitAlloc.java
Added: branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/BBModel.java
===================================================================
--- branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/BBModel.java (rev 0)
+++ branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/BBModel.java 2008-03-28 11:14:42 UTC (rev 164)
@@ -0,0 +1,25 @@
+package gridsim.parallel.BBModel;
+
+
+public interface BBModel {
+
+ public double getCommunication();
+
+ public boolean nextState();
+ public State getState();
+ public void reset();
+
+ public enum State{
+ COMMUNICATION,COMPUTATION,FINISHED
+ }
+
+ public double getRemainingData();
+ public int getRemainingCommunications();
+
+ public BBTaskModel[] getTaskModel();
+
+ public double getTotalLength();
+// public boolean isCheckpoint();
+
+ public void backToLastCheckpoint();
+}
Added: branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/BBParallelGridlet.java
===================================================================
--- branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/BBParallelGridlet.java (rev 0)
+++ branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/BBParallelGridlet.java 2008-03-28 11:14:42 UTC (rev 164)
@@ -0,0 +1,239 @@
+package gridsim.parallel.BBModel;
+
+
+import gridsim.Gridlet;
+import gridsim.ParameterException;
+import gridsim.parallel.InternalNetworkModel;
+import gridsim.parallel.ParallelGridlet;
+import gridsim.parallel.PerformanceModeledGridlet;
+import gridsim.parallel.ResParallelGridlet;
+import gridsim.parallel.innacuracy.InaccuracyModel;
+
+/**
+ * This model consider a parallel application as a group of tasks that interact
+ * among them.
+ *
+ * Each task is characterised by a sequence of computations and communications.
+ *
+ *
+ * In this model, communications are supposed to be global, and with
+ * implicit barriers, then all tasks are executed in a synchronised way.
+ *
+ * With this approach, the complexity of the simulation, and the memory
+ * requirements do not increase noticeably the cost of the sequential
+ * simulation itself.
+ *
+ * @author Xulio Lopez
+ *
+ */
+
+public class BBParallelGridlet extends ParallelGridlet implements PerformanceModeledGridlet{
+
+ /**
+ * Stores asociated tasks to this ParallelGridlet
+ */
+ private BBParallelTask[] tasks;
+
+ /**
+ * Transfered data in each communication in bits.
+ */
+ // private double[] gridletCommData;
+ private BBModel model;
+
+ /**
+ * Allocates a new Gridlet object. The Gridlet length, input and output file
+ * sizes should be greater than or equal to 1.
+ *
+ * TODO Explain basic model of flops/coms
+ *
+ * @param gridletID
+ * the unique ID of this Gridlet
+ * @param gridletLength
+ * the length or size (in MI) of this Gridlet to be executed in a
+ * GridResource
+ * @param gridletFileSize
+ * the file size (in byte) of this Gridlet <tt>BEFORE</tt>
+ * submitting to a GridResource
+ * @param gridletOutputSize
+ * the file size (in byte) of this Gridlet <tt>AFTER</tt>
+ * finish executing by a GridResource
+ * @param record
+ * record the history of this object or not
+ * @param numPE
+ * the number of PEs required to run this Gridlet
+ * @param gridletCommunications
+ * the number of communications of this Gridlet to be executed in
+ * a ParallelGridResource.
+ * @param gridletCommData
+ * the data size (in byte) transmited in each communication (same
+ * for all)
+ * @throws ParameterException
+ * Invalid number of communications, data comunicated or PE.
+ * @pre gridletID >= 0
+ * @pre gridletLength >= 0.0
+ * @pre gridletFileSize >= 1
+ * @pre gridletOutputSize >= 1
+ * @pre numPE >= 1
+ * @pre gridletCommunications >= 0
+ * @pre gridletCommData >= 0.0
+ * @post $none
+ */
+ public BBParallelGridlet(int gridletID, double gridletLength,
+ long gridletFileSize, long gridletOutputSize, boolean record,
+ int numPE, int gridletCommunications, double gridletCommData)
+ throws ParameterException {
+ super(gridletID, gridletLength, gridletFileSize, gridletOutputSize,
+ record);
+ if (!this.setNumPE(numPE))
+ throw new ParameterException("Invalid number of PE");
+ SimpleBBModel smodel = new SimpleBBModel(gridletLength,
+ gridletCommunications, gridletCommData, numPE);
+ model = smodel;
+ tasks = new BBParallelTask[numPE];
+ for (int i = 0; i < numPE; i++)
+ tasks[i] = new BBParallelTask(smodel);
+
+ /*
+ * if(numPE>1){ if(gridletCommunications<0) throw new
+ * ParameterException("Invalid number of Communications");
+ * if(gridletCommData<0) throw new ParameterException("Invalid amount
+ * of comData"); //Create only a copy because reduce memory
+ * requirements, due to it is only read array. double[] copy = new
+ * double[gridletCommunications+1]; //TODO Explain the basic model
+ * if(gridletCommunications>1){ double
+ * step=gridletLength/gridletCommunications; if(gridletCommunications>2)
+ * Arrays.fill(copy,1,gridletCommunications,step);
+ * copy[0]=copy[gridletCommunications]=step*0.5; }else
+ * copy[0]=gridletLength; for(int i=0;i<numPE;i++) tasks[i]=new
+ * ComplexBBParallelTask(copy); //All comms with the same amount of
+ * transfered data this.gridletCommData = new
+ * double[gridletCommunications];
+ * Arrays.fill(this.gridletCommData,gridletCommData); }else { //TODO
+ * Search a correct way of notificate this. if(gridletCommunications>0)
+ * System.err.println("Ignore comms in gridlet "+this.getGridletID()+"
+ * because is processed on one processor"); tasks[0]=new
+ * ComplexBBParallelTask(new double[]{gridletLength});
+ * this.gridletCommData = new double[0]; } fixTaskInternalID(tasks);
+ */
+ }
+
+ public BBParallelGridlet(int gridletID, BBModel model,
+ long gridletFileSize, long gridletOutputSize, boolean record)
+ throws ParameterException {
+ super(gridletID, model.getTotalLength(), gridletFileSize, gridletOutputSize, record);
+ this.model = model;
+ BBTaskModel[] tasksModel = model.getTaskModel();
+ if (!this.setNumPE(tasksModel.length))
+ throw new ParameterException("Invalid number of PE");
+ tasks = new BBParallelTask[tasksModel.length];
+ for (int i = 0; i < tasks.length; i++)
+ tasks[i] = new BBParallelTask(tasksModel[i]);
+ }
+
+ /**
+ * Allocates a new Gridlet object. The Gridlet length, input and output file
+ * sizes should be greater than or equal to 1. By default this constructor
+ * sets the history of this object.
+ *
+ * @param gridletID
+ * the unique ID of this Gridlet
+ * @param gridletLength
+ * the length or size (in MI) of this Gridlet to be executed in a
+ * GridResource
+ * @param gridletFileSize
+ * the file size (in byte) of this Gridlet <tt>BEFORE</tt>
+ * submitting to a GridResource
+ * @param gridletOutputSize
+ * the file size (in byte) of this Gridlet <tt>AFTER</tt>
+ * finish executing by a GridResource
+ * @param numPE
+ * the number of PEs required to run this Gridlet
+ * @param gridletCommunications
+ * the number of communications of this Gridlet to be executed in
+ * a ParallelGridResource.
+ * @param gridletCommData
+ * the data size (in byte) transmited in each communication (same
+ * for all)
+ * @throws ParameterException
+ * Invalid number of communications, data comunicated or PE.
+ * @pre gridletID >= 0
+ * @pre gridletLength >= 0.0
+ * @pre gridletFileSize >= 1
+ * @pre gridletOutputSize >= 1
+ * @pre numPE >= 1
+ * @pre gridletCommunications >= 0
+ * @pre gridletCommData >= 0.0
+ * @post $none
+ *
+ * @see BBParallelGridlet (int, double, long, long, boolean, int, int,
+ * double)
+ */
+ public BBParallelGridlet(int gridletID, double gridletLength,
+ long gridletFileSize, long gridletOutputSize, int numPE,
+ int gridletCommunications, double gridletCommData)
+ throws ParameterException {
+ this(gridletID, gridletLength, gridletFileSize, gridletOutputSize,
+ true, numPE, gridletCommunications, gridletCommData);
+ }
+
+ public BBParallelGridlet(int gridletID, BBModel model,
+ long gridletFileSize, long gridletOutputSize)
+ throws ParameterException {
+ this(gridletID, model, gridletFileSize, gridletOutputSize, true);
+ }
+
+ /**
+ * Generates a ParallelGridlet based in a Gridlet. It suposes that comms are
+ * null.
+ *
+ * @param gl
+ * Gridlet to be enveloped
+ * @throws ParameterException
+ * @see ParallelGridlet (int, long, long, int, double[][], double[])
+ */
+ public BBParallelGridlet(Gridlet gl) throws ParameterException {
+ this(gl.getGridletID(), new SimpleBBModel(gl.getGridletLength(), 0,
+ 0, gl.getNumPE()), gl.getGridletFileSize(), gl
+ .getGridletOutputSize());
+ this.setUserID(gl.getUserID());
+ // TODO Auto-generated constructor stub
+ }
+
+ /**
+ * It's necessary to give acceces to this information only to
+ * ResParallelGridlet.
+ *
+ * @return A reference (not a copy) to communication vector.
+ */
+ /*
+ * protected double[] getCommData() { return gridletCommData; }
+ */
+
+ /**
+ * Generates a ResBBParallelGridlet associated to this BBParaleleGridlet
+ *
+ * @param internalNet
+ * internal network model of the GridResource where the
+ * ResGridlet will be processed
+ * @see gridsim.parallel.ParallelGridlet#generateResParallelGridlet(InternalNetworkModel)
+ */
+ @Override
+ public ResParallelGridlet generateResParallelGridlet(
+ InternalNetworkModel internalNet) {
+ // TODO Auto-generated method stub
+ ResBBParallelTask[] resTasks = new ResBBParallelTask[tasks.length];
+ for (int i = 0; i < resTasks.length; i++)
+ resTasks[i] = new ResBBParallelTask(tasks[i]);
+ return new ResBBParallelGridlet(this, resTasks, internalNet,model);
+ }
+
+/* public double calculateEstimatedTime(InternalNetworkModel net, int MIPSrating) {
+ // TODO Auto-generated method stub
+ return model.getTotalLength()/MIPSrating/tasks.length+net.getAssociatedCommunicationTime(model.getRemainingData(),model.getRemainingCommunications(),tasks.length);
+ }*/
+ public double calculateEstimatedTime(InternalNetworkModel net, int MIPSrating,InaccuracyModel inModel) {
+ return inModel.getNextError(
+ model.getTotalLength()/MIPSrating/tasks.length+net.getAssociatedCommunicationTime(model.getRemainingData(),model.getRemainingCommunications(),tasks.length));
+ }
+
+}
Added: branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/BBParallelTask.java
===================================================================
--- branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/BBParallelTask.java (rev 0)
+++ branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/BBParallelTask.java 2008-03-28 11:14:42 UTC (rev 164)
@@ -0,0 +1,45 @@
+package gridsim.parallel.BBModel;
+
+
+import gridsim.parallel.ParallelTask;
+
+
+/**
+ * Each ParallelGridlet is divided in Tasks. Each task is executed only in a PE.
+ * The task has its length, and how much has been processed when a gridlet is migrated.
+ * A task stored the last finished communication point and the finish mips since the last communication.
+ * @author Xulio L�pez
+ */
+public class BBParallelTask extends ParallelTask{
+
+ /** finished mips after the last synchronized point */
+ private double finishedMipsSoFar=0.0d;
+ /** internal id assigned in ParallelGridlet synchronized with ResParallelTasks */
+ private BBTaskModel model;
+ /**
+ * Creates a instance of a ParallelTask
+ * @param gridletTasksLength !!Warning. Not a copy, a reference to original, because is marked as final.
+ */
+ public BBParallelTask(BBTaskModel model) {
+ this.model=model;
+ }
+
+ /**
+ * Saves the progress state of this task, which is necessary to allow a task migration.
+ * @param finishedLength computations(MIPS/FLOPS) finished after the last communication
+ */
+ public void setTaskRemainingSoFar(double finishedLength) {
+ finishedMipsSoFar = finishedLength;
+ }
+ /**
+ * Gets the progress state of this task, which is necessary to allow a task migration.
+ * @param finishedLength computations(MIPS/FLOPS) finished after the last communication
+ */
+ public double getTaskRemainingSoFar() {
+ return finishedMipsSoFar;
+ }
+
+ public BBTaskModel getModel() {
+ return model;
+ }
+}
Added: branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/BBTaskModel.java
===================================================================
--- branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/BBTaskModel.java (rev 0)
+++ branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/BBTaskModel.java 2008-03-28 11:14:42 UTC (rev 164)
@@ -0,0 +1,15 @@
+package gridsim.parallel.BBModel;
+
+import gridsim.parallel.BBModel.BBModel.State;
+
+public interface BBTaskModel {
+
+ public abstract double getComputation();
+
+ public abstract State getState();
+
+ //to forecast
+ public abstract double getRemainingComputations();
+ public boolean isCheckpoint();
+
+}
\ No newline at end of file
Added: branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/MatrixBBModel.java
===================================================================
--- branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/MatrixBBModel.java (rev 0)
+++ branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/MatrixBBModel.java 2008-03-28 11:14:42 UTC (rev 164)
@@ -0,0 +1,122 @@
+package gridsim.parallel.BBModel;
+
+import java.util.Arrays;
+
+public class MatrixBBModel implements BBModel {
+ private double commData[];
+
+ private BBTaskModel[] tasksModel;
+
+ private double remainingData;
+
+ private int steps, currentStep;
+
+ private State state;
+
+ private double totalLength;
+
+ public MatrixBBModel(double[][] gridletTaskLength,
+ double[] gridletCommData) {
+ this.commData = gridletCommData;
+ tasksModel=new BBTaskModel[gridletTaskLength.length];
+ for (int i = 0; i < gridletTaskLength.length; i++)
+ tasksModel[i]=new MatrixBBTaskModel(gridletTaskLength[i],this);
+ steps = 2 * gridletCommData.length + 1;
+ currentStep = 0;
+ totalLength=0;
+ for(int i=0;i<gridletTaskLength.length;i++)
+ for(int j=0;j<gridletTaskLength[i].length;j++)
+ totalLength+=gridletTaskLength[i][j];
+
+ state = State.COMPUTATION;
+ // TODO Auto-generated constructor stub
+
+ remainingData = 0;
+ for (int i = 0; i < gridletCommData.length; i++)
+ remainingData += gridletCommData[i];
+ }
+ public MatrixBBModel(double[] gridletTaskLength,
+ double[] gridletCommData,int tasks) {
+ this.commData = gridletCommData;
+ tasksModel=new BBTaskModel[tasks];
+ Arrays.fill(tasksModel,new MatrixBBTaskModel(gridletTaskLength,this));
+ steps = 2 * gridletCommData.length + 1;
+ currentStep = 0;
+ totalLength=0;
+ for(int i=0;i<gridletTaskLength.length;i++)
+ totalLength+=gridletTaskLength[i];
+ totalLength*=tasks;
+
+ state = State.COMPUTATION;
+ // TODO Auto-generated constructor stub
+
+ remainingData = 0;
+ for (int i = 0; i < gridletCommData.length; i++)
+ remainingData += gridletCommData[i];
+ }
+
+ public boolean nextState() {
+ currentStep++;
+ if (currentStep < steps) {
+ if (currentStep % 2 == 0) {
+ state = State.COMPUTATION;
+ } else {
+ state = State.COMMUNICATION;
+ remainingData -= commData[currentStep / 2];
+ // TODO Fix round errors -> need to be 0;
+ }
+ return true;
+ } else {
+ state = State.FINISHED;
+ return false;
+ }
+ }
+
+
+ public double getCommunication() {
+ return ( state == State.COMMUNICATION ) ? commData[currentStep / 2] : 0;
+ }
+
+
+ public State getState() {
+ return state;
+ }
+
+
+
+ public double getRemainingData() {
+ // TODO Auto-generated method stub
+ return remainingData;
+ }
+
+ public int getRemainingCommunications() {
+ // TODO Auto-generated method stub
+ return commData.length - (1 + currentStep) / 2;
+ }
+
+ public void reset() {
+ // TODO Auto-generated method stub
+ currentStep = 0;
+ for (int i = 0; i < commData.length; i++)
+ remainingData -= commData[i];
+ }
+
+ public int getComputationStep() {
+ // TODO Auto-generated method stub
+ return currentStep/2;
+ }
+
+ public BBTaskModel[] getTaskModel() {
+ return tasksModel;
+ }
+ public double getTotalLength() {
+ // TODO Auto-generated method stub
+ return totalLength;
+ }
+
+ public void backToLastCheckpoint() {
+ // TODO Auto-generated method stub
+ System.err.println("Checkpointing in Matrix BBModel is not implemented yet");
+ }
+
+}
Added: branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/MatrixBBTaskModel.java
===================================================================
--- branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/MatrixBBTaskModel.java (rev 0)
+++ branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/MatrixBBTaskModel.java 2008-03-28 11:14:42 UTC (rev 164)
@@ -0,0 +1,39 @@
+package gridsim.parallel.BBModel;
+
+import gridsim.parallel.BBModel.BBModel.State;
+
+public class MatrixBBTaskModel implements BBTaskModel {
+ private double[] computations;
+ private MatrixBBModel model;
+
+ public MatrixBBTaskModel(double[] taskLength,MatrixBBModel model) {
+ computations=taskLength;
+ this.model=model;
+ // TODO Auto-generated constructor stub
+ }
+
+ public double getComputation() {
+ if (model.getState()== State.COMPUTATION)
+ return computations[model.getComputationStep()];
+ else
+ return 0;
+ }
+
+ public State getState() {
+ return model.getState();
+ }
+
+ public double getRemainingComputations() {
+ double remainingComputations=0.0;
+ for(int i=model.getComputationStep()+1;i<computations.length;i++)
+ remainingComputations+=computations[i];
+ // TODO Auto-generated method stub
+ return remainingComputations;
+ }
+
+ public boolean isCheckpoint() {
+ // TODO Auto-generated method stub
+ return false;
+ }
+
+}
Added: branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/ResBBParallelGridlet.java
===================================================================
--- branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/ResBBParallelGridlet.java (rev 0)
+++ branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/ResBBParallelGridlet.java 2008-03-28 11:14:42 UTC (rev 164)
@@ -0,0 +1,142 @@
+package gridsim.parallel.BBModel;
+
+
+import gridsim.parallel.InternalNetworkModel;
+import gridsim.parallel.ResParallelGridlet;
+
+public class ResBBParallelGridlet extends ResParallelGridlet {
+
+ private double remainCommTime = -1.0;
+
+ private double actualCommTime;
+ private ResBBParallelTask[] resourceTasks;
+ BBModel model;
+
+ public ResBBParallelGridlet(BBParallelGridlet pgridlet,
+ ResBBParallelTask[] resTasks, InternalNetworkModel internalNet, BBModel model) {
+ super(pgridlet, resTasks,internalNet);
+ this.model=model;
+ this.resourceTasks=resTasks;
+ //FIXME <-this is only to test algorims
+ }
+
+ public double updateGridletSimulationAdvance(double localLoad, double timeSpan) {
+ //ResParallelTask task;
+ boolean computationsFinished;
+ double lessTime;
+ double timeToSpent = timeSpan;
+ double searchTime,commTime;
+ double avaliableLoad=1 - localLoad;
+ // Updates the Gridlet length that is currently being executed
+ /*if (commPoint < 0) {
+ for (int i = 0; i < resourceTasks.length; i++) {
+ task = resourceTasks[i];
+ task.updateTaskFinishedSoFar(avaliableLoad,timeToSpent);
+ }
+ } else*/
+ while (timeToSpent > 0) {
+ switch(model.getState()){
+ case COMMUNICATION:
+ if (remainCommTime < 0)
+ remainCommTime = internalNet.getAssociatedCommunicationTime(model.getCommunication(),getNumPE());
+ if (remainCommTime > timeToSpent) {
+ remainCommTime -= timeToSpent;
+ pushdCommTime(timeToSpent);
+ timeToSpent = 0.0;
+ } else {
+ pushdCommTime(remainCommTime);
+ timeToSpent -= remainCommTime;
+ commTime=popdCommTime();
+ for (int i = 0; i < resourceTasks.length; i++)
+ resourceTasks[i].finishCommPoint(commTime);
+ model.nextState();
+ remainCommTime = -1.0;
+ }
+ break;
+ case COMPUTATION:
+ {
+ searchTime = timeToSpent;
+ computationsFinished = true;
+ for (int i = 0; i < resourceTasks.length; i++) {
+ // compoint deberia ser interno a task
+ lessTime = resourceTasks[i].updateTaskFinishedSoFar(
+ avaliableLoad, timeToSpent);
+ if (lessTime >= 0.0) {
+ searchTime = Math.min(searchTime, lessTime);
+ } else {
+ computationsFinished = false;
+ searchTime = 0.0;
+ }
+ }
+ if(computationsFinished) model.nextState();
+ timeToSpent = searchTime;
+ break;
+ }
+ case FINISHED:
+ return timeToSpent;
+ default:
+ break;
+ }
+ }
+ return -1.0;
+ }
+
+ // FIXME �Is really necesary?(To move not, but for a pause gridlet can be?
+ public void resetComm() {
+// double lostCommTime = remainCommTime;
+// return lostCommTime;
+ remainCommTime = -1.0;
+ }
+
+ //FIXME take care of different statistics times
+ @Override
+ public void backToLastCheckpoint() {
+ remainCommTime = -1.0;
+ for(ResBBParallelTask rbpt:resourceTasks)
+ rbpt.backToLastCheckpoint();
+ model.backToLastCheckpoint();
+ }
+
+ private void pushdCommTime(double execTime) {
+ actualCommTime += execTime;
+ }
+
+ //NOTE: If the gridlet is canceled in a comm state, this time is not updated in the tasks. Change it?
+ private double popdCommTime() {
+ double time = actualCommTime;
+ actualCommTime = 0.0;
+ return time;
+ }
+
+ /*public double getForecastFinishTime(InternalNetworkModel internalNet){
+ //TODO Check if exist some problem usind directly MIPSRating without a function call
+ return super.getForecastFinishTime();
+ }*/
+ /**
+ * Gets a forecast finish time of the task.
+ * @return estimated Tasks's finish time.
+ */
+ public double getForecastFinishTime()
+ {
+ double commTime=internalNet.getAssociatedCommunicationTime(model
+ .getRemainingData(), model.getRemainingCommunications(), getNumPE());
+ if (model.getState()==BBModel.State.COMMUNICATION){
+ if(remainCommTime < 0)
+ remainCommTime += internalNet.getAssociatedCommunicationTime(model.getCommunication(),getNumPE());
+ commTime=remainCommTime;
+ }
+ /* if(commData.length>0)
+ for (int i=commPoint;i<commData.length;i++)
+ commTime+=internalNet.getAssociatedCommunicationTime(commData[i],getNumPE());
+ */ return super.getForecastFinishTime()+commTime;
+ }
+
+ @Override
+ protected boolean isFinished() {
+ return this.model.getState().equals(BBModel.State.FINISHED);
+ }
+
+
+
+
+}
Added: branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/ResBBParallelTask.java
===================================================================
--- branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/ResBBParallelTask.java (rev 0)
+++ branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/ResBBParallelTask.java 2008-03-28 11:14:42 UTC (rev 164)
@@ -0,0 +1,169 @@
+package gridsim.parallel.BBModel;
+
+
+import gridsim.parallel.InternalNetworkModel;
+import gridsim.parallel.ParallelGridlet;
+import gridsim.parallel.ResParallelTask;
+
+public class ResBBParallelTask extends ResParallelTask {
+
+ /** Internal asocitated task */
+ private BBParallelTask task;
+
+ /** Base offset syncronization point in the execution */
+ // private ComplexBBParallelTask task;
+ private double completedMIPS;
+
+ BBTaskModel model;
+
+ private int internalCommPoint;
+
+ private double MIPSRating;
+
+ /*
+ * public ResSimpleBBParallelTask(SimpleBBModel model, double completedMIPS) { //
+ * TODO Auto-generated constructor stub // this.task=task;
+ * this.completedMIPS = completedMIPS; this.model = model; //
+ * remaining=task.getRemaingTaskLenght(); //
+ * baseCommPoint=task.getfinishedCommSoFar(); }
+ */
+
+ public ResBBParallelTask(BBParallelTask task) {
+ this.task = task;
+ this.completedMIPS = task.getTaskRemainingSoFar();
+ model = task.getModel();
+ // TODO Auto-generated constructor stub
+ }
+
+ @Override
+ /**
+ * This method is called when the execution of this task in this resource is
+ * finished. All data ought be fixed to the associated task.
+ */
+ public void finalizeTask() {
+ task.setTaskRemainingSoFar(completedMIPS);
+ // System.out.println("Overhead: " + overhead + "\t Inhead: " + inhead +
+ // "\t Underhead: " + underhead);
+ }
+
+ // TODO (all time or only time until next communication?)
+ public double getRemainingLength() {
+ // Remaining Gridlet length can't be negative number. This can be
+ // happening when this.updateGridletFinishedSoFar() keep calling.
+ if (model.getState() == BBModel.State.FINISHED)
+ return 0.0;
+ else if (model.getState() == BBModel.State.COMPUTATION)
+ return model.getRemainingComputations() + model.getComputation()
+ - completedMIPS;
+ else
+ return model.getRemainingComputations();
+ }
+
+ public void finishCommPoint(double comTime) {
+ completedMIPS = 0.0;
+ internalCommPoint++;
+ if (model.isCheckpoint())
+ pushdTaskTime(comTime,
+ ParallelGridlet.ParallelTaskState.chk_communication);
+ else
+ pushdTaskTime(comTime,
+ ParallelGridlet.ParallelTaskState.communication);
+ }
+
+
+ //Opional implementation - selected the other becouse in parallel programing, seems to be more probable
+ @SuppressWarnings("unused")
+ private double updateTaskFinishedSoFarV2(double avaliableCPU,
+ double timeSpan) {
+ // int comPoint) {
+ // TODO check speed of this structure ,another way?
+ // double stopPoint = length[] - maxFlops;
+ double rating = avaliableCPU * MIPSRating;
+ // internalCommPoint=comPoint-baseCommPoint;
+ double remaining = model.getComputation() - completedMIPS;
+ if (remaining <= 0)
+ return timeSpan;
+ double tryOps = rating * timeSpan;
+ if (remaining > tryOps) {
+ completedMIPS += tryOps;
+ fixExecTime(timeSpan);
+ // underhead++;
+ return -1.0;
+ } else if (remaining == tryOps) {
+ // remaining=0.0;
+ completedMIPS = model.getComputation();
+ fixExecTime(timeSpan);
+ return 0.0;
+ } else {
+ double timeSpent = remaining / rating;
+ fixExecTime(timeSpent);
+ completedMIPS = model.getComputation();
+ // remaining=0.0;
+ // overhead++;
+ return timeSpan - timeSpent;
+ }
+ }
+
+ private void fixExecTime(double time) {
+ if (model.isCheckpoint())
+ pushdTaskTime(time,
+ ParallelGridlet.ParallelTaskState.chk_execution);
+ else
+ pushdTaskTime(time, ParallelGridlet.ParallelTaskState.execution);
+
+ }
+
+ public double updateTaskFinishedSoFar(double avaliableCPU, double timeSpan) {
+ // int comPoint) {
+ // TODO check speed of this structure ,another way?
+ double rating = avaliableCPU * MIPSRating;
+ // internalCommPoint=comPoint-baseCommPoint;
+ double remaining = model.getComputation() - completedMIPS;
+ if (remaining <= 0)
+ return timeSpan;
+ double timeSpent = remaining / rating;
+ if (timeSpent < timeSpan) {
+ completedMIPS = model.getComputation();
+ // remaining = 0.0;
+ fixExecTime(timeSpent);
+ // underhead++;
+ return timeSpan - timeSpent;
+ } else if (timeSpent > timeSpan) {
+ // remaining -= rating * timeSpan;
+ completedMIPS += rating * timeSpan;
+ fixExecTime(timeSpan);
+ // overhead++;
+ return -1.0;
+ } else {
+ // remaining = 0.0;
+ completedMIPS = model.getComputation();
+ fixExecTime(timeSpent);
+ // inhead++;
+ return 0.0;
+ }
+ }
+
+ @Override
+ public int getCommsNumber() {
+ // TODO Auto-generated method stub
+ return internalCommPoint;
+ }
+
+ @Override
+ public double getForecastFinishTime(InternalNetworkModel internalNet,
+ int tasks) {
+ return getRemainingLength() / this.MIPSRating;
+ }
+
+ public void backToLastCheckpoint() {
+ // TODO fix statitistical times
+ completedMIPS=0d;
+ }
+
+ @Override
+ protected void setMIPSRating(int rating) {
+ MIPSRating=rating;
+ }
+
+ // public static long overhead = 0, underhead = 0, inhead = 0;
+}
Added: branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/SimpleBBModel.java
===================================================================
--- branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/SimpleBBModel.java (rev 0)
+++ branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/SimpleBBModel.java 2008-03-28 11:14:42 UTC (rev 164)
@@ -0,0 +1,191 @@
+package gridsim.parallel.BBModel;
+
+import java.util.Arrays;
+
+public class SimpleBBModel implements BBModel, BBTaskModel {
+ private double data, stepComputation;
+
+ private double remainingData, remainingComputations;
+
+ private int remainingComms;
+
+ private int steps, currentStep;
+
+ private State state;
+
+ private int checkpointFrequency = 0;
+
+ private boolean isCheckpoint = false;
+
+ private double checkpointComputations, checkpointCommData;
+
+ private BBTaskModel[] tasksModel;
+
+ // Cache data
+ private double totalLength;
+
+ public SimpleBBModel(double gridletLength, int gridletCommunications,
+ double gridletCommData, int tasks) {
+ this.data = gridletCommData;
+ this.stepComputation = gridletLength / (gridletCommunications + 1);
+ steps = 2 * gridletCommunications + 1;
+ currentStep = 0;
+ this.totalLength = tasks * gridletLength;
+
+ state = State.COMPUTATION;
+
+ tasksModel = new BBTaskModel[tasks];
+ Arrays.fill(tasksModel, this);
+ // TODO Auto-generated constructor stub
+
+ remainingComputations = gridletLength - stepComputation;
+ remainingData = gridletCommData * gridletCommunications;
+ remainingComms = gridletCommunications;
+ }
+
+ public SimpleBBModel(double gridletLength, int gridletCommunications,
+ double gridletCommData, int tasks, int commsBetweenCheckpoints,
+ double checkpointComputations, double checkpointCommData) {
+ int chekcpoints = (gridletCommunications - 1) / commsBetweenCheckpoints;
+ this.data = gridletCommData;
+ this.stepComputation = gridletLength / (gridletCommunications + 1);
+ steps = 2 * (gridletCommunications + chekcpoints) + 1;
+ currentStep = 0;
+ double extraComputations = checkpointComputations * chekcpoints;
+ this.totalLength = tasks * (gridletLength + extraComputations);
+
+ state = State.COMPUTATION;
+
+ tasksModel = new BBTaskModel[tasks];
+ Arrays.fill(tasksModel, this);
+ // TODO Auto-generated constructor stub
+
+ remainingComputations = gridletLength + extraComputations
+ - stepComputation;
+ remainingData = gridletCommData * gridletCommunications
+ + checkpointCommData * chekcpoints;
+ remainingComms = gridletCommunications + chekcpoints;
+
+ this.checkpointFrequency = commsBetweenCheckpoints + 1;
+ this.checkpointCommData = checkpointCommData;
+ this.checkpointComputations = checkpointComputations;
+ }
+
+ public boolean nextState() {
+ // TODO to make sure this implementation, uncoment the next line
+ // if (currentStep < steps)
+ currentStep++;
+ if (currentStep < steps) {
+ if (checkpointFrequency != 0)
+ isCheckpoint = ((currentStep / 2 + 1) % checkpointFrequency == 0)
+ & (currentStep + 1 < steps);
+ if (currentStep % 2 == 0) {
+ state = State.COMPUTATION;
+ remainingComputations -= isCheckpoint ? checkpointComputations
+ : stepComputation;
+ } else {
+ state = State.COMMUNICATION;
+ remainingData -= isCheckpoint ? checkpointCommData : data;
+ remainingComms--;
+ // TODO Fix round errors -> need to be 0;
+ }
+ return true;
+ } else {
+ state = State.FINISHED;
+ return false;
+ }
+ }
+
+ public double getComputation() {
+ if (state == State.COMPUTATION)
+ return isCheckpoint ? checkpointComputations : stepComputation;
+ else
+ return 0;
+ }
+
+ public double getCommunication() {
+ if (state == State.COMMUNICATION)
+ return isCheckpoint ? checkpointCommData : data;
+ else
+ return 0;
+ }
+
+ public State getState() {
+ return state;
+ }
+
+ public double getRemainingComputations() {
+ return remainingComputations;
+ }
+
+ public double getRemainingData() {
+ // TODO Auto-generated method stub
+ return remainingData;
+ }
+
+ public int getRemainingCommunications() {
+ // TODO Auto-generated method stub
+ return remainingComms;
+ }
+
+ public void reset() {
+ // TODO Auto-generated method stub
+ currentStep = 0;
+ remainingComms = steps / 2;
+ remainingComputations = stepComputation * remainingComms;
+ remainingData = data * remainingComms;
+ state = State.COMPUTATION;
+ }
+
+ public BBTaskModel[] getTaskModel() {
+ // TODO Auto-generated method stub
+ return tasksModel;
+ }
+
+ public double getTotalLength() {
+ // TODO Auto-generated method stub
+ return totalLength;
+ }
+
+ public boolean isCheckpoint() {
+ return isCheckpoint;
+ }
+
+ public void backToLastCheckpoint() {
+ // TODO Auto-generated method stub
+ if (state == State.FINISHED) {
+ System.err
+ .println("Is not posible came back to a checkpoint to a finished gridlet");
+ return;
+ }
+ if (checkpointFrequency != 0) {
+ if (currentStep < (checkpointFrequency * 2)) {
+ isCheckpoint = false;
+ currentStep = 0;
+ } else {
+ currentStep -= currentStep % (checkpointFrequency * 2) + 2;
+ isCheckpoint = true;
+ state=(currentStep % 2 == 0)?State.COMPUTATION:State.COMMUNICATION;
+ }
+ setResetedCheckpointingCacheData();
+ } else {
+ currentStep = 0;
+ reset();
+ }
+
+ }
+
+ private void setResetedCheckpointingCacheData() {
+ remainingComms = (steps - currentStep) / 2;
+ int remainingCheckPoints = (steps / 2) / checkpointFrequency
+ - (currentStep / 2) / checkpointFrequency;
+ remainingComputations = stepComputation
+ * (remainingComms - remainingCheckPoints + (isCheckpoint ? 1
+ : 0)) + (remainingCheckPoints - (isCheckpoint ? 1 : 0))
+ * checkpointComputations;
+
+ remainingData = data * (remainingComms - remainingCheckPoints)
+ + remainingCheckPoints * checkpointCommData;
+ }
+
+}
Added: branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/SimplifyResBBParallelGridlet.java
===================================================================
--- branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/SimplifyResBBParallelGridlet.java (rev 0)
+++ branches/gridsim-4.1-parallel/source/gridsim/parallel/BBModel/SimplifyResBBParallelGridlet.java 2008-03-28 11:14:42 UTC (rev 164)
@@ -0,0 +1,72 @@
+package gridsim.parallel.BBModel;
+
+
+import gridsim.parallel.InternalNetworkModel;
+import gridsim.parallel.ResParallelGridlet;
+
+public class SimplifyResBBParallelGridlet extends ResParallelGridlet {
+
+ private double remainingTotalSimplifyTime = -1;
+
+// private double remainCommTime = -1.0;
+
+ private BBModel model;
+
+ public SimplifyResBBParallelGridlet(BBParallelGridlet pgridlet,
+ ResBBParallelTask[] resTasks, InternalNetworkModel internalNet,
+ BBModel model) {
+ super(pgridlet, resTasks, internalNet);
+ this.model = model;
+ // FIXME <-this is only to test algorithms
+ }
+
+ // Checkpointing is not considered in this model.
+ public double updateGridletSimulationAdvance(double localLoad, double timeSpan) {
+ if (localLoad != 0)
+ System.err.println("Local load ignored in simplified model");
+ if (remainingTotalSimplifyTime < -0.1)
+ remainingTotalSimplifyTime = initForecastFinishTime();
+ if (timeSpan > remainingTotalSimplifyTime) {
+ timeSpan -= remainingTotalSimplifyTime;
+ remainingTotalSimplifyTime = 0;
+ while (model.nextState())
+ ;
+ return timeSpan;
+ } else {
+ remainingTotalSimplifyTime -= timeSpan;
+ return 0;
+ }
+ }
+
+ // FIXME �Is really necesary?(To move not, but for a pause gridlet can be?
+ public void resetComm() {
+ System.err.println("Comm reset ignored in simplified model");
+ }
+
+ // FIXME take care of different statistics times
+ @Override
+ public void backToLastCheckpoint() {
+ System.err.println("checkpointing ignored in simplified model");
+ }
+
+ /**
+ * Gets a forecast finish time of the task.
+ *
+ * @return estimated Tasks's finish time.
+ */
+ public double getForecastFinishTime() {
+ return remainingTotalSimplifyTime;
+ }
+ private double initForecastFinishTime(){
+ double commTime = internalNet.getAssociatedCommunicationTime(model
+ .getRemainingData(), model.getRemainingCommunications(),
+ getNumPE());
+ return super.getForecastFinishTime() + commTime;
+ }
+
+ @Override
+ protected boolean isFinished() {
+ return this.model.getState().equals(BBModel.State.FINISHED);
+ }
+
+}
Added: branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/BackFillingAlloc.java
===================================================================
--- branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/BackFillingAlloc.java (rev 0)
+++ branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/BackFillingAlloc.java 2008-03-28 11:14:42 UTC (rev 164)
@@ -0,0 +1,203 @@
+/*
+ * Title: GridSim Toolkit
+ * Description: GridSim (Grid Simulation) Toolkit for Modeling and Simulation
+ * of Parallel and Distributed Systems such as Clusters and Grids
+ * Licence: GPL - http://www.gnu.org/copyleft/gpl.html
+ *
+ * $Id: BackFillingAlloc.java,v 1.2 2007/11/14 09:56:10 julio Exp $
+ */
+
+package gridsim.parallel.allocs;
+
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.Set;
+import java.util.TreeMap;
+import java.util.TreeSet;
+import java.util.Map.Entry;
+
+import gridsim.GridSim;
+import gridsim.Gridlet;
+import gridsim.Machine;
+import gridsim.PE;
+import gridsim.PEList;
+import gridsim.parallel.InternalNetworkModel;
+import gridsim.parallel.ParallelAllocPolicy;
+import gridsim.parallel.ResParallelGridlet;
+
+/**
+ *
+ * @author Julio Lopez
+ * @invariant $none
+ */
+public class BackFillingAlloc extends ParallelAllocPolicy {
+ protected Set<ResParallelGridlet> sorteExecList;
+
+ protected boolean onlyExecutionFilling;
+
+ public BackFillingAlloc(String resourceName, String entityName,
+ InternalNetworkModel internalNet, boolean onlyExecutionFilling)
+ throws Exception {
+ super(resourceName, entityName, internalNet);
+ sorteExecList = new TreeSet<ResParallelGridlet>(
+ new Comparator<ResParallelGridlet>() {
+ public int compare(ResParallelGridlet o1,
+ ResParallelGridlet o2) {
+ if(o1.equals(o2)) return 0;
+ double estTime=((o1.getEstimatedTime() + o1
+ .getExecStartTime()) - (o2.getEstimatedTime() + o2
+ .getExecStartTime()));
+ //It's necessary give a order to
+ return (estTime>0)?1:-1;
+ //return (int)
+ }
+ });
+ this.onlyExecutionFilling = onlyExecutionFilling;
+
+ }
+
+
+
+ /**
+ * Allocates the first Gridlet in the Queue list (if any) to execution list
+ *
+ * @pre $none
+ * @post $none
+ */
+ protected void allocateQueueGridlet() {
+ // if there are many Gridlets in the QUEUE, then allocate a
+ // PE to the first Gridlet in the list since it follows FCFS
+ // (First Come First Serve) approach. Then removes the Gridlet from
+ // the Queue list
+
+ // FIXME improve performance
+
+ if (sGridletQueueList.size() > 0
+ && sGridletInExecList.size() < super.totalPE_) {
+ ResParallelGridlet rgl;
+
+ int free = super.resource_.getNumFreePE();
+
+ rgl = sGridletQueueList.peek();
+
+ while (rgl.getNumPE() <= free) {
+ // allocate the Gridlet into an empty PE slot and remove it
+ // from
+ // the queue list
+ boolean success = allocatePEstoGridlet(rgl);
+ if (success == true) {
+ sGridletQueueList.poll();
+ // sGridletQueueList.remove(rgl);
+ }
+ // FIXME Update with another threads, is it better
+ free -= rgl.getNumPE();
+ rgl = sGridletQueueList.peek();
+ if (rgl == null)
+ return;
+ }
+ // This check is duplicated, but this is not 100% sure and is not
+ // computational expensive
+ if (free > 0)
+ backfillingLN();
+ // else System.err.println("Avoid backfilling");
+
+ }
+ }
+
+ protected void backfillingLN() {
+
+ // FIXME improve performance
+ int free = super.resource_.getNumFreePE();
+ if (!(free > 0 & sGridletQueueList.size() > 0))
+ return;
+
+ int futureFree = free;
+ TreeMap<Double, Integer> timePE = new TreeMap<Double, Integer>();
+ timePE.put(0d, free);
+ sorteExecList.clear();
+ sorteExecList.addAll(sGridletInExecList);
+ Iterator<ResParallelGridlet> sIt = sorteExecList.iterator();
+ ResParallelGridlet rgl;
+ double time;
+ while (sIt.hasNext()) {
+ rgl = sIt.next();
+ futureFree += rgl.getNumPE();
+ time = (rgl.getExecStartTime() + rgl.getEstimatedTime())
+ - GridSim.clock() + 1;
+ timePE.put(time, futureFree);
+ }
+ if(futureFree!=totalPE_)
+ System.err.println("Mala iniciacion");
+ Iterator<ResParallelGridlet> it = sGridletQueueList.iterator();
+ while (it.hasNext() && free > 0) {
+ rgl = it.next();
+ // if(rgl.getNumPE()>free & onlyExecutionFilling) continue;
+ double starTime = -1d, endTime = -1;
+ boolean validating = false;
+ for (Entry<Double, Integer> mark : timePE.entrySet()) {
+ if (validating) {
+ if (((!onlyExecutionFilling) | (starTime == 0d))
+ & (mark.getKey() >= endTime)) {
+ // if(!onlyExecutionFilling) break;
+ break;
+ // if(!(onlyExecutionFilling&&(starTime != 0d))) break;
+ // else System.err.println("Special rejection");
+ } else if (mark.getValue() < rgl.getNumPE()) {
+ validating = false;
+ endTime = -1;
+ // break;
+ }
+ } else {
+ if (mark.getValue() >= rgl.getNumPE()) {
+ validating = true;
+ starTime = mark.getKey();
+ endTime = starTime + rgl.getEstimatedTime();
+ }
+ }
+ }
+ if (validating) {
+ for (Entry<Double, Integer> mark : timePE.subMap(starTime,
+ endTime).entrySet()) {
+ futureFree = mark.getValue();
+ mark.setValue(futureFree - rgl.getNumPE());
+ }
+ if (!timePE.containsKey(endTime))
+ timePE.put(endTime, futureFree);
+ if (starTime == 0d) {
+ if (rgl.getNumPE() > free) {
+ System.err
+ .println("Backfilling called before check completation. Gridlet "
+ + rgl.getGridletID() + " bad allocated");
+ continue;
+ }
+ // allocate the Gridlet into an empty PE slot and
+ // remove it from the queue list
+ boolean success = allocatePEstoGridlet(rgl);
+ if (success == true) {
+ sGridletQueueList.remove(rgl);
+ }
+ // FIXME Update with another threads, is it better
+ free -= rgl.getNumPE();
+ }
+ } else {
+ // if(!onlyExecutionFilling)
+ System.err.println("Never would be reached this point");
+ /*
+ * else System.err.println("Rejected candidate");
+ */
+ }
+ }
+
+ }
+
+
+ @Override
+ public String getPolicyName() {
+ if (onlyExecutionFilling)
+ return "ConservativeBackFillingExecution";
+ else
+ return "ConservativeBackFillingPredictive";
+ }
+
+
+}
Added: branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/BackFillingL1Alloc.java
===================================================================
--- branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/BackFillingL1Alloc.java (rev 0)
+++ branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/BackFillingL1Alloc.java 2008-03-28 11:14:42 UTC (rev 164)
@@ -0,0 +1,161 @@
+/*
+ * Title: GridSim Toolkit
+ * Description: GridSim (Grid Simulation) Toolkit for Modeling and Simulation
+ * of Parallel and Distributed Systems such as Clusters and Grids
+ * Licence: GPL - http://www.gnu.org/copyleft/gpl.html
+ *
+ * $Id: BackFillingL1Alloc.java,v 1.2 2007/11/14 09:56:10 julio Exp $
+ */
+
+package gridsim.parallel.allocs;
+
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.SortedSet;
+import java.util.TreeSet;
+
+import gridsim.GridSim;
+import gridsim.Gridlet;
+import gridsim.Machine;
+import gridsim.PE;
+import gridsim.PEList;
+import gridsim.parallel.InternalNetworkModel;
+import gridsim.parallel.ParallelAllocPolicy;
+import gridsim.parallel.ResParallelGridlet;
+
+/**
+ * SpaceParallelShared class is an allocation policy for GridResource that
+ * behaves exactly like First Come First Serve (FCFS). This is a modification to
+ * SpaceShared that allows each Gridlet to be executed in more than one
+ * Processing Element (PE). Versioned to add support to parallel gridlets.
+ *
+ * @author Julio Lopez, based on SpaceShared by Manzur Murshed and Rajkumar
+ * Buyya
+ * @since GridSim Toolkit 4.0
+ * @see gridsim.GridSim
+ * @see gridsim.ResourceCharacteristics
+ * @see gridsim.SpaceShare
+ * @invariant $none
+ */
+public class BackFillingL1Alloc extends ParallelAllocPolicy {
+ private SortedSet<ResParallelGridlet> sorteExecList;
+
+ public BackFillingL1Alloc(String resourceName, String entityName,
+ InternalNetworkModel internalNet) throws Exception {
+ super(resourceName, entityName, internalNet);
+ sorteExecList = new TreeSet<ResParallelGridlet>(
+ new Comparator<ResParallelGridlet>() {
+ public int compare(ResParallelGridlet o1,
+ ResParallelGridlet o2) {
+ if(o1.equals(o2)) return 0;
+ double estTime=((o1.getEstimatedTime() + o1
+ .getExecStartTime()) - (o2.getEstimatedTime() + o2
+ .getExecStartTime()));
+ return (estTime>0)?1:-1;
+ }
+ });
+
+ }
+
+
+ /**
+ * Allocates the first Gridlet in the Queue list (if any) to execution list
+ *
+ * @pre $none
+ * @post $none
+ */
+ protected void allocateQueueGridlet() {
+ // if there are many Gridlets in the QUEUE, then allocate a
+ // PE to the first Gridlet in the list since it follows FCFS
+ // (First Come First Serve) approach. Then removes the Gridlet from
+ // the Queue list
+
+ // FIXME improve performance
+
+ if (sGridletQueueList.size() > 0
+ && sGridletInExecList.size() < super.totalPE_) {
+ ResParallelGridlet rgl;
+
+ int free = super.resource_.getNumFreePE();
+
+ rgl = sGridletQueueList.peek();
+
+ while (rgl.getNumPE() <= free) {
+ // allocate the Gridlet into an empty PE slot and remove it
+ // from
+ // the queue list
+ boolean success = allocatePEstoGridlet(rgl);
+ if (success == true) {
+ sGridletQueueList.poll();
+ // sGridletQueueList.remove(rgl);
+ }
+ // FIXME Update with another threads, is it better
+ free -= rgl.getNumPE();
+ rgl = sGridletQueueList.peek();
+ if (rgl == null)
+ return;
+ }
+ if (free > 0)
+ backfillingL1();
+ }
+ }
+
+ protected void backfillingL1() {
+ int free = super.resource_.getNumFreePE();
+ if (!(free > 0 & sGridletQueueList.size() > 0))
+ return;
+ ResParallelGridlet rgl;
+ rgl = sGridletQueueList.peek();
+ double extraTime = rgl.getEstimatedTime();
+ // BACKFILLING code
+ sorteExecList.clear();
+ sorteExecList.addAll(sGridletInExecList);
+ Iterator<ResParallelGridlet> sIt = sorteExecList.iterator();
+ int extraPE = free - rgl.getNumPE();
+ while (extraPE < 0 && sIt.hasNext()) {
+ rgl = sIt.next();
+ extraPE += rgl.getNumPE();
+ }
+ double maxTime = rgl.getExecStartTime() + rgl.getEstimatedTime()
+ - GridSim.clock();
+ Iterator<ResParallelGridlet> it = sGridletQueueList.iterator();
+ while (it.hasNext() && free > 0) {
+ rgl = it.next();
+ if (rgl.getNumPE() <= free)
+ if (rgl.getEstimatedTime() < maxTime) {
+ // allocate the Gridlet into an empty PE slot and
+ // remove it from the queue list
+ boolean success = allocatePEstoGridlet(rgl);
+ if (success == true) {
+ sGridletQueueList.remove(rgl);
+ }
+ // FIXME Update with another threads, is it better
+ free -= rgl.getNumPE();
+ } else if (rgl.getEstimatedTime() < maxTime + extraTime
+ && rgl.getNumPE() <= extraPE) {
+ // allocate the Gridlet into an empty PE slot and
+ // remove it from the queue list
+ boolean success = allocatePEstoGridlet(rgl);
+ if (success == true) {
+ sGridletQueueList.remove(rgl);
+ }
+ // FIXME Update with another threads, is it better
+ free -= rgl.getNumPE();
+ extraPE -= rgl.getNumPE();
+ //System.err.println("Extra bacfilled with gridlet "+ rgl.getGridletID());
+ } /*else {
+ // System.err.println("Not bacfilled with gridlet
+ // "+rgl.getGridletID());
+ }*/
+ // FIXME this solution is correct, but the performance can
+ // decrease.
+ }
+
+ }
+
+ @Override
+ public String getPolicyName() {
+ return "ConservativeBackFillingL1";
+ }
+
+}
Added: branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/EASYBackFillingAlloc.java
===================================================================
--- branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/EASYBackFillingAlloc.java (rev 0)
+++ branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/EASYBackFillingAlloc.java 2008-03-28 11:14:42 UTC (rev 164)
@@ -0,0 +1,167 @@
+/*
+ * Title: GridSim Toolkit
+ * Description: GridSim (Grid Simulation) Toolkit for Modeling and Simulation
+ * of Parallel and Distributed Systems such as Clusters and Grids
+ * Licence: GPL - http://www.gnu.org/copyleft/gpl.html
+ *
+ * $Id: EASYBackFillingAlloc.java,v 1.2 2007/11/14 09:56:10 julio Exp $
+ */
+
+package gridsim.parallel.allocs;
+
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.SortedSet;
+import java.util.TreeSet;
+
+import gridsim.GridSim;
+import gridsim.Gridlet;
+import gridsim.Machine;
+import gridsim.PE;
+import gridsim.PEList;
+import gridsim.parallel.InternalNetworkModel;
+import gridsim.parallel.ParallelAllocPolicy;
+import gridsim.parallel.ResParallelGridlet;
+
+/**
+ * SpaceParallelShared class is an allocation policy for GridResource that
+ * behaves exactly like First Come First Serve (FCFS). This is a modification to
+ * SpaceShared that allows each Gridlet to be executed in more than one
+ * Processing Element (PE). Versioned to add support to parallel gridlets.
+ *
+ * @author Julio Lopez, based on SpaceShared by Manzur Murshed and Rajkumar
+ * Buyya
+ * @since GridSim Toolkit 4.0
+ * @see gridsim.GridSim
+ * @see gridsim.ResourceCharacteristics
+ * @see gridsim.SpaceShare
+ * @invariant $none
+ */
+public class EASYBackFillingAlloc extends ParallelAllocPolicy {
+ private SortedSet<ResParallelGridlet> sorteExecList;
+
+ public EASYBackFillingAlloc(String resourceName, String entityName,
+ InternalNetworkModel internalNet) throws Exception {
+ super(resourceName, entityName, internalNet);
+ sorteExecList = new TreeSet<ResParallelGridlet>(
+ new Comparator<ResParallelGridlet>() {
+ public int compare(ResParallelGridlet o1,
+ ResParallelGridlet o2) {
+ if(o1.equals(o2)) return 0;
+ double estTime=((o1.getEstimatedTime() + o1
+ .getExecStartTime()) - (o2.getEstimatedTime() + o2
+ .getExecStartTime()));
+ return (estTime>0)?1:-1;
+ }
+ });
+
+ }
+
+
+
+ /**
+ * Allocates the first Gridlet in the Queue list (if any) to execution list
+ *
+ * @pre $none
+ * @post $none
+ */
+ protected void allocateQueueGridlet() {
+ // if there are many Gridlets in the QUEUE, then allocate a
+ // PE to the first Gridlet in the list since it follows FCFS
+ // (First Come First Serve) approach. Then removes the Gridlet from
+ // the Queue list
+
+ // FIXME improve performance
+
+ if (sGridletQueueList.size() > 0
+ && sGridletInExecList.size() < super.totalPE_) {
+ ResParallelGridlet rgl;
+
+ int free = super.resource_.getNumFreePE();
+
+ rgl = sGridletQueueList.peek();
+
+ while (rgl.getNumPE() <= free) {
+ // allocate the Gridlet into an empty PE slot and remove it
+ // from
+ // the queue list
+ boolean success = allocatePEstoGridlet(rgl);
+ if (success == true) {
+ sGridletQueueList.poll();
+ // sGridletQueueList.remove(rgl);
+ }
+ // FIXME Update with another threads, is it better
+ free -= rgl.getNumPE();
+ rgl = sGridletQueueList.peek();
+ if (rgl == null)
+ return;
+ }
+ if (free > 0)
+ easyBackfilling();
+ // double extraTime = rgl.getEstimatedTime();
+ // BACKFILLING code
+ // FIXME this solution is correct, but the performance can
+ // decrease.
+
+ }
+
+ }
+
+ private void easyBackfilling() {
+ int free = super.resource_.getNumFreePE();
+ if (!(free > 0 & sGridletQueueList.size() > 0))
+ return;
+ ResParallelGridlet rgl;
+ rgl = sGridletQueueList.peek();
+ // TODO Auto-generated method stub
+ sorteExecList.clear();
+ sorteExecList.addAll(sGridletInExecList);
+ Iterator<ResParallelGridlet> sIt = sorteExecList.iterator();
+ int extraPE = free - rgl.getNumPE();
+ while (extraPE < 0 && sIt.hasNext()) {
+ rgl = sIt.next();
+ extraPE += rgl.getNumPE();
+ }
+ double maxTime = rgl.getExecStartTime() + rgl.getEstimatedTime()
+ - GridSim.clock();
+ Iterator<ResParallelGridlet> it = sGridletQueueList.iterator();
+ while (it.hasNext() && free > 0) {
+ rgl = it.next();
+ if (rgl.getNumPE() <= free)
+ if (rgl.getEstimatedTime() < maxTime) {
+ // allocate the Gridlet into an empty PE slot and
+ // remove it from the queue list
+ boolean success = allocatePEstoGridlet(rgl);
+ if (success == true) {
+ sGridletQueueList.remove(rgl);
+ }
+ // FIXME Update with another threads, is it better
+ free -= rgl.getNumPE();
+ } else if (rgl.getNumPE() <= extraPE) {
+ // allocate the Gridlet into an empty PE slot and
+ // remove it from the queue list
+ boolean success = allocatePEstoGridlet(rgl);
+ if (success == true) {
+ sGridletQueueList.remove(rgl);
+ }
+ // FIXME Update with another threads, is it better
+ free -= rgl.getNumPE();
+ extraPE -= rgl.getNumPE();
+ // System.err.println("Extra bacfilled with gridlet
+ // "+rgl.getGridletID());
+ } /*else {
+ // System.err.println("Not bacfilled with gridlet
+ // "+rgl.getGridletID());
+ }*/
+ }
+
+ }
+
+
+
+ @Override
+ public String getPolicyName() {
+ return "EASYBackFilling";
+ }
+
+}
Added: branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/FIFOAlloc.java
===================================================================
--- branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/FIFOAlloc.java (rev 0)
+++ branches/gridsim-4.1-parallel/source/gridsim/parallel/allocs/FIFOAlloc.java 2008-03-28 11:14:42 UTC (rev 164)
@@ -0,0 +1,155 @@
+/*
+ * Title: GridSim Toolkit
+ * Description: GridSim (Grid Simulation) Toolkit for Modeling and Simulation
+ * of Parallel and Distributed Systems such as Clusters and Grids
+ * Licence: GPL - http://www.gnu.org/copyleft/gpl.html
+ *
+ * $Id: FIFOAlloc.java,v 1.2 2007/11/14 09:56:10 julio Exp $
+ */
+
+package gridsim.parallel.allocs;
+
+import java.util.Iterator;
+
+import gridsim.Gridlet;
+import gridsim.Machine;
+import gridsim.PE;
+import gridsim.PEList;
+import gridsim.parallel.InternalNetworkModel;
+import gridsim.parallel.ParallelAllocPolicy;
+import gridsim.parallel.ResParallelGridlet;
+
+/**
+ * SpaceParallelShared class is an allocation policy for GridResource that
+ * behaves exactly like First Come First Serve (FCFS). This is a modification to
+ * SpaceShared that allows each Gridlet to be executed in more than one
+ * Processing Element (PE). Versioned to add support to parallel gridlets.
+ *
+ * @author Julio Lopez, based on SpaceShared by Manzur Murshed and Rajkumar
+ * Buyya
+ * @since GridSim Toolkit 4.0
+ * @see gridsim.GridSim
+ * @see gridsim.ResourceCharacteristics
+ * @see gridsim.SpaceShare
+ * @invariant $none
+ */
+public class FIFOAlloc extends ParallelAllocPolicy {
+
+ public FIFOAlloc(String resourceName, String entityName,
+ InternalNetworkModel internalNet) throws Exception {
+ super(resourceName, entityName, internalNet);
+ }
+
+ /**
+ * Allocates a Gridlet into a free PE and sets the Gridlet status into
+ * INEXEC and PE status into busy afterwards
+ *
+ * @param rgl
+ * a ResGridlet object
+ * @return <tt>true</tt> if there is an empty PE to process this Gridlet,
+ * <tt>false</tt> otherwise
+ * @pre rgl != null
+ * @post $none
+ */
+/* protected boolean allocatePEstoGridlet(ResParallelGridlet rpgl) {
+ // FIXME First basic implementation
+ // ResParallelGridlet rpgl = (ResParallelGridlet) rgl;
+ int tasks = rpgl.getNumPE();
+
+ int i = 0;
+ while (i < tasks) {
+
+ // IDENTIFY MACHINE which has a free PE and add this Gridlet to it.
+ Machine myMachine = resource_.getMachineWithFreePE();
+
+ // If a Machine is empty then ignore the rest
+ if (myMachine == null) {
+ System.out.println("Fallou");
+ return false;
+ // FIXME Esta salida no es valida
+ }
+
+ // gets the list of PEs and find one empty PE
+ PEList MyPEList = myMachine.getPEList();
+ while (MyPEList.getNumFreePE() > 0 && (i < tasks)) {
+ int freePEID = MyPEList.getFreePEID();
+ rpgl.setMachineAndPEID(myMachine.getMachineID(), freePEID,
+ MyPEList.getMIPSRating(freePEID));
+ i++;
+ // Set allocated PE to BUSY status
+ super.resource_.setStatusPE(PE.BUSY, myMachine.getMachineID(),
+ freePEID);
+ }
+
+ //FIXME Task could be not finished
+ // FIXME No sense set to a rgl, only fot a task
+ // rgl.setMachineAndPEID(myMachine.getMachineID(), freePE);
+
+ }
+
+ // ALLOCATE IMMEDIATELY
+ rpgl.setGridletStatus(Gridlet.INEXEC); // change Gridlet status
+ // add this Gridlet into execution list
+ sGridletInExecList.add(rpgl);
+
+ // Identify Completion Time and Set Interrupt
+ // int rating = machineRating_[ rgl.getMachineID() ];
+ double time = rpgl.getForecastFinishTime();
+ // forecastFinishTime( rating , rgl.getRemainingGridletLength() );
+
+ double roundUpTime = Math.ceil(time); // rounding up
+ rpgl.setFinishTime(roundUpTime);
+
+ // then send this into itself
+ super.sendInternalEvent(roundUpTime);
+ return true;
+ }*/
+
+ /**
+ * Allocates the first Gridlet in the Queue list (if any) to execution list
+ *
+ * @pre $none
+ * @post $none
+ */
+ protected void allocateQueueGridlet() {
+ // if there are many Gridlets in the QUEUE, then allocate a
+ // PE to the first Gridlet in the list since it follows FCFS
+ // (First Come First Serve) approach. Then removes the Gridlet from
+ // the Queue list
+ if (sGridletQueueList.size() > 0
+ && sGridletInExecList.size() < super.totalPE_) {
+ ResParallelGridlet rgl;
+
+ Iterator<ResParallelGridlet> it = sGridletQueueList.iterator();
+ int free =...
[truncated message content] |
