//============================================================================
//?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