heft任务调度算法

heft算法，任务调度算法，任务调度过程使用，可结合其他算法，可自己调节参数。。。。。。。。。。。。。。

//============================================================================
// Name        : heft.cpp
// Author      : 曹建立
// Version     :1
// Description :  实现HEFT算法
//============================================================================

#include 
using namespace std;
//多机调度问题
#include 
#include
#define v 10	//任务个数、顶点个数
#define q 3		//处理器个数
#define x 0	//定义无效替代字符


//全部下标从1开始，0行0列不使用。
//计算代价矩阵W
float W[v+1][q+1]=
{
	{x xxx}
	{x 14169}
	{x 131918}
	{x 111319}
	{x 13817}
	{x 121310}
	{x 13169}
	{x 71511}
	{x 51114}
	{x 181220}
	{x 21716}
};
//通信代价矩阵C
float C[v+1][v+1]=
{
{x x x x x x x x x x x}
{x x 18 12 9 11 14 x x x x}
{x x x x x x x x 19 16 x}
{x x x x x x x 23 x x x}
{x x x x x x x x 27 23 x}
{x x x x x x x x x 13 x}
{x x x x x x x x 15 x x}
{x x x x x x x x x x 17}
{x x x x x x x x x x 11}
{x x x x x x x x x x 13}
{x x x x x x x x x x x}
};

float B[q+1][q+1]=
{
{x x x}
{x011}
{x101}
{x110}
};
//启动开销数组L
float L[q+1]={x000};

//平均通信代价矩阵初始化0，值待计算；
float AverC[v+1][v+1]={0};
//ranku 向上rank，初始化0，值待计算；
float Ranku[v+1]={0};
//averW，初始化0，值待计算；
float AverW[v+1]={0};
//avail[]记录各cpu最早可用时间
float Avail[q+1]={0};
//AFT[]记录每个任务调度后的完成时间
float AFT[v+1]={0};
int RunCPU[q+1]={0};

void printArray（float arr[][v+1]int n）
{
	printf（“------------------------\n“）;
	for（int i=1;i<=n;i++）
	{
		for（int j=1;j<=n;j++）
			if（arr[i][j]>0）
				printf（“%4.1f“arr[i][j]）;
			else
				printf（“ -- “）;
		printf（“\n“）;
	}
}

void GetRanku（	）{
	Ranku[v]=AverW[v];
	for（int i=v-1;i>=1;i--）{
		float max=0;
		// find succ [k]
		for（int k=1;k<=v;k++）{
			if（AverC[i][k]>0）{
				float temp=AverC[i][k]+Ranku[k];
				if（max			}
		}//for k
		Ranku[i]=AverW[i]+max;
	}//for i
	for（int j=1;j<=v;j++）
			printf（“%4.1f\t“Ranku[j]）;
	printf（“\n“）;
}

void HEFT（ ）{
	//共循环v次，把v个任务分配
	for（int i=1;i<=v;i++）{
		//找到ranku目前最大值
		float maxRanku=0;
		//找到应该调度的任务task（ranku值最大的）
		int task=0;
		for（int k=1;k<=v;k++）
			if（Ranku[k]>maxRanku）
			{
				maxRanku=Ranku[k];
				task=k;				
			}
		//将该任务从队列中清除
		Ranku[task]=0;
		//计算q的cpu上的EST
		float est[q+1]={0};
		float eft[q+1]={0};
		//计算每个cpu的est
		for（int cpu=1;cpu<=q;cpu++）{
			//遍历当前任务的前驱节点，找到最晚（值最大）的前驱完成时间+传输时间；
			float maxWaitPredReady=0;
			for（int f=0;f<=v;f++）
				if（C[f][task]>0）{
					//f为其前驱父节点必须等待前驱运行完成					
					float waitPredReady=AFT[f];
					//如果前驱不在一个cpu上，则要加上传输时间（这里假设速率=1，启动时间=0）
					if（RunCPU[f]!=cpu）
						waitPredReady+=C[f][task];
					if（waitPredReady>maxWaitPredReady）
						maxWaitPredReady=waitPredReady;
				}
			//est=cpu最早空间时间和该任务前驱最早完成时间的较大者
			est[cpu]=Avail[cpu]>maxWaitPredReady?Avail[cpu]:maxWaitPredReady;
			eft[cpu]=est[cpu]+W[task][cpu];
		}//f

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2014-06-08 17:21  heft\
     目录           0  2014-06-08 17:15  heft\Debug\
     文件      262187  2014-06-08 17:15  heft\Debug\heft.exe
     文件      374156  2014-06-08 17:15  heft\Debug\heft.ilk
     文件       19709  2014-06-08 17:14  heft\Debug\heft.obj
     文件     2001156  2014-06-07 18:16  heft\Debug\heft.pch
     文件      574464  2014-06-08 17:15  heft\Debug\heft.pdb
     文件       74752  2014-06-08 17:15  heft\Debug\vc60.idb
     文件      102400  2014-06-08 17:14  heft\Debug\vc60.pdb
     文件        4443  2014-06-08 17:14  heft\heft.cpp
     文件        3377  2014-06-08 16:06  heft\heft.dsp
     文件         514  2014-06-08 17:21  heft\heft.dsw
     文件       41984  2014-06-08 17:21  heft\heft.ncb
     文件       48640  2014-06-08 17:21  heft\heft.opt
     文件         742  2014-06-08 17:15  heft\heft.plg