www.pudn.com > ghs1.2.rar > ghsscheduler.cpp

/*
 * Copyright (c) 2000-2003 Illinois Institute of Technology.
 *                         All rights reserved.
 *
 * This file is part of the GHS software package.  For license
 * information, see the LICENSE file in the top level directory of the
 * GHS source distribution.
 *
 * Released Date: August 18 2005
 * This is the GHS I release by the
 *   SCS Group,
 *   http://www.cs.iit.edu/~scs
 *   Department of Computer Science,
 *   Illinois Institute of Technology.
 *
 * This release has been tested under SUN OS 5.9.
 *
 * Supervisor
 * ----------
 * Illiniois Institute of Technology:
 * -Dr. Xian-He Sun
 *
 * Author(s)
 * -----------------
 * Illinois Institute of Technology:
 * -Ming Wu
 * -Xian-He Sun
 *
 */

#include
#include
#include
#include
#include
#include
#include "ghs.h"

using namespace std;

extern double GetParaMean(int numOfinte);
extern double GetParaVari(double paramean, int numOfinte);
extern void ReadTaskPara(const vector& ut, const vector& ar, const vector& ss, const vector& wo, int mNum);

/*  read resource parameters
 *	resource name, utilization, arrival rate, servicestd
 */
void 
GHSScheduler::GetResoPara(char *configFile) 
{

  fstream resoFile;
  resoFile.open(configFile, fstream::in);
  
  if (!resoFile.is_open()) 
  {
    cout << "Error in open the resource parameter file" << endl;
    exit(1);
  }

  int i = 0;
  string line;
  string tmpName;
  float tmpUtil, tmpArri, tmpServ, tmpSpeed;

  while (getline(resoFile, line) && i < MAX_WS_NUM) 
  {
    stringstream oss;
    oss << line;
    oss >> tmpName >> tmpUtil >> tmpArri >> tmpServ >> tmpSpeed;
    machName.push_back(tmpName);
    util_p.push_back(tmpUtil);
    arri_p.push_back(tmpArri);
    serv_p.push_back(util_p[i]/arri_p[i]);
    servstd_p.push_back(tmpServ);
    speed_p.push_back(tmpSpeed);
    //cout << util_p[i] << " " << arri_p[i] << " " << servstd_p[i] << " " << speed_p[i] <1->01->11->001->101->011->111
void 
GHSScheduler::AddArray()
{
  int i = 0;
  int endSign = 0;

  while (i < wsNum && endSign == 0 )
  {
    if ( machID[i] == 0)
    {
      machID[i] = 1;
      endSign = 1;
    }
    else // machID is 1 already
    {
      machID[i] = 0;
    }
    i++;
  }

}

int 
GHSScheduler::IsArrayFull()
{
  int i = 0;
  int full = 0;

  while (i < wsNum && machID[i] == 1) i++;

  if (i == wsNum) full = 1;
  return full;

}

/* sort the machine list according to (1-utilization)* speed 
 * the result is stored in machsOrder array
 */
void 
GHSScheduler::SortMachID()
{
  int i, j, orderTmp;
  vector uspeed;
  double ustemp;

  for (i = 0; i < wsNum; i++)
  {
    machsOrder[i] = i;
    uspeed.push_back((1-arri_p[i] * serv_p[i]) * speed_p[i]);
  }

  for (i = 0; i < wsNum - 1; i++)
  {
    for (j = i + 1; j < wsNum; j++)
    {
      if ( uspeed[i] < uspeed[j] ) 
      {
        ustemp = uspeed [i];
        uspeed[i] = uspeed[j];
        uspeed[j] = ustemp;

        orderTmp = machsOrder[i];
        machsOrder[i] = machsOrder[j];
        machsOrder[j] = orderTmp;
      }
    }
  }

}

/* generate the machine id array according to the machsOrder array */
void 
GHSScheduler::GenerateMachID(int machNum)
{

  int i;
  for (i = 0; i < wsNum; i++) machID[i] = 0;

  for (i = 0; i < machNum; i++)
  {
    machID[machsOrder[i]] = 1;
  }

}

/* optimal scheduling algorithm, return parallel task run time */
double 
GHSScheduler::OptimalSchedule()
{
  int i;
  double evMin, evTmp = 0.0;

  for (i = 0; i < wsNum; i++) machID[i] = 0;

  i = 0;
  while (IsArrayFull() == 0)
  {
    AddArray();
    //PartitionWorkload(machID);
    evTmp = CalculateRuntime(machID);
    if (i == 0) 
    {
      evMin = evTmp;
      PlanRecord();
    }
    if ( evMin > evTmp )
    {
      evMin = evTmp;
      PlanRecord();
    }
    i++;
  }

  return(evMin);

}

/* heuristic scheduling algorithm, return parallel task run time */
double 
GHSScheduler::HeuristicSchedule()
{

  int maxNum;
  double maxServ = 0;

  SortMachID();

  for (int i = 0; i < wsNum; i++)
  {
    if (maxServ < serv_p[i] ) maxServ = serv_p[i];
  }

  //**********************need modification ****************************
  maxNum = (int)(totalWorkload / (2 * maxServ));

  int a, b, c;
  a = 1;
  if (wsNum > maxNum)
  {
    b = maxNum;
  } else b = wsNum;

  double runa, runb, runc, runc1;

  while ( a + 1 < b) 
  {
    c = (a + b) / 2;
    GenerateMachID(a);
    runa = CalculateRuntime(machID);
    GenerateMachID(b);
    runb = CalculateRuntime(machID);
    GenerateMachID(c);
    runc = CalculateRuntime(machID);

    if ( (runa < runb) && (runa < runc))
    {
      b = c;
    }
    else if ( (runb < runa) && (runb < runc) )
    {
      a = c;
    }
    else
    {
      GenerateMachID(c + 1);
      runc1 = CalculateRuntime(machID);
      if ( runc < runc1) 
      {
        b = c;
      }
      else a = c;
    }
  }

  GenerateMachID(a);
  runa = CalculateRuntime(machID);
  PlanRecord();

  GenerateMachID(b);
  runb = CalculateRuntime(machID);

  double evMin;
  double subtaskTime;

  if ( runa < runb) evMin = runa;
  else 
  {
    evMin = runb;
    PlanRecord();
  }

  if (  evMin == runb) GenerateMachID(b);
  else GenerateMachID(a);

  for (int i = 0; i < wsNum; i++) 
  {
    if (machID[i] == 1) 
    {
      subtaskTime = work_p[i] / speed_p[i];
      //cout << "the machine is " << i << " and subtaskTime is " << subtaskTime << endl;
    }
  }

  return(evMin);

}