?? glj.cpp
字號:
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#define N 4
#define INF 100
#define BANDWITH 30
void main()
{
//int T[N][N]={{0,7,6,4},{2,0,9,2},{4,1,0,8},{7,2,3,0}};
int T[N][N]={{0,3,2,4},{2,3,0,2},{4,1,3,0},{2,0,2,3}};//以下的計算都是對特定的流量矩陣T而言
int constbackT[N][N],backupT[N][N],backup1T[N][N],backup2T[N][N]; //T的備份矩陣
int i,j,m,j1,j2,k,t,row=INF,line=INF;//row是元素之和最大的行號，從0開始計數，line是列...
int g[N],h[N];//g[N]存放T的各列按降序排列后的每行的最大值,h[N]存放T的各行按降序排列后每列的最大值
int minbandwith=0;
int max=0;
int minq[BANDWITH]; //存放分解得到的排列矩陣的系數
int bandsize=0;
int tag=0;
int endtag=0;
int notzerotag=1; //表示T是否為全零的標記，＝1為全零矩陣
int sum=0;//decr[i]為第i行元素和與最大值max的差；
int temp;
int p[N][N][BANDWITH];//存放排列矩陣，*這里預定義長度為20*
int lieb[N]; //保存BV分解時隨機產生的列坐標
int starttag,endlen;
double jitter;
int individualjitter;//臨時存放每個元素的抖動
int mininterval,maxinterval,tempinterval=0;
for(i=0;i<N;i++) //備份原流量矩陣T
{
g[i]=0;
h[i]=0;
for(j=0;j<N;j++)
{
backupT[i][j]=T[i][j];
backup1T[i][j]=T[i][j];
backup2T[i][j]=T[i][j];
constbackT[i][j]=T[i][j];
}
}
cout<<"原流量矩陣如下："<<endl;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
cout<<T[i][j]<<" ";
cout<<endl;
}
cout<<endl;
for(j=0;j<N;j++) //對T的列向量進行冒泡排序,按降序排列
{
for(k=0;k<N-1;k++)
{
for(i=0;i<N-k-1;i++)
{
if(backup1T[i][j]<backup1T[i+1][j])
{
temp=backup1T[i][j];
backup1T[i][j]=backup1T[i+1][j];
backup1T[i+1][j]=temp;
}
}
}
}
cout<<"列向量按降序排列后的流量矩陣如下："<<endl;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
cout<<backup1T[i][j]<<" ";
cout<<endl;
}
cout<<endl;
for(i=0;i<N;i++) //找出每行的最大值存入g[i]中
{
for(j=0;j<N;j++)
{
if(backup1T[i][j]>g[i])
g[i]=backup1T[i][j];
}
}
for(i=0;i<N;i++) //對T的行向量進行冒泡排序,按降序排列
{
for(k=0;k<N-1;k++)
{
for(j=0;j<N-k-1;j++)
{
if(backup2T[i][j]<backup2T[i][j+1])
{
temp=backup2T[i][j+1];
backup2T[i][j+1]=backup2T[i][j];
backup2T[i][j]=temp;
}
}
}
}
cout<<"行向量按降序排列后的流量矩陣如下："<<endl;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
cout<<backup2T[i][j]<<" ";
cout<<endl;
}
cout<<endl;
for(j=0;j<N;j++) //找出每列的最大值存入h[i]中
{
for(i=0;i<N;i++)
{
if(backup2T[i][j]>h[j])
h[j]=backup2T[i][j];
}
}
temp=0;
for(i=0;i<N;i++)
minbandwith+=g[i];
for(j=0;j<N;j++)
temp+=h[j];
if(temp>minbandwith)
minbandwith=temp;
cout<<"最小帶寬等于"<<minbandwith<<endl;
//下面進行LJ分解
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
for(k=0;k<BANDWITH;k++)
p[i][j][k]=0; //三維矩陣p保存分解的排列矩陣，預先附值為全零矩陣，
}
}
for(t=0;notzerotag;t++) //循環分解得到一組排列矩陣的集合，直到T為0為止
{
temp=1;
for(i=0;i<N;i++) //產生置換列向量（j1，j2，j3，j4）,并存放于lieb[]中
{
srand( (unsigned)time( NULL ) );
k=rand()%10%N;
if(i==2)
{
while(lieb[i-1]==k||lieb[i-2]==k)
{
srand( (unsigned)time( NULL ) );
k=rand()%10%N;
}
}
else if(i==3)
{
if(lieb[i-1]==k||lieb[i-2]==k||lieb[i-3]==k)
k=6-lieb[i-1]-lieb[i-2]-lieb[i-3];
}
else
{
for(j=0;j<i;j++)
{
while(lieb[j]==k)
{
srand( (unsigned)time( NULL ) );
k=rand()%10%N;
}
}
}
lieb[i]=k;
cout<<"i="<<i<<" "<<"lieb["<<i<<"]=="<<k<<endl;
j=lieb[i];
temp*=T[i][j];
} // for循環產生了一組置換列向量
endtag++;
cout<<"已經產生第"<<endtag<<"個列置換向量"<<endl;
if(temp)
{
max=0;
for(i=0;i<N;i++)
{
k=lieb[i];
if(T[i][k]>max)
max=T[i][k];
}
minq[t]=max;
for(i=0;i<N;i++)
{
temp=lieb[i];
p[i][temp][t]=1;
T[i][temp]=0;
}
endtag=0;
cout<<"第"<<t+1<<"個排列矩陣的系數＝"<<minq[t]<<endl;
cout<<"第"<<t+1<<"個排列矩陣如下："<<endl;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
cout<<p[i][j][t]<<",";
cout<<endl;
}
cout<<endl;
cout<<"分解剩下的矩陣T＝"<<endl;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
cout<<T[i][j]<<" ? ";
cout<<endl;
}
cout<<endl;
for(i=0;i<N;i++) //判斷分解后剩下的矩陣R是否為全零矩陣
for(j=0;j<N;j++)
{
if(T[i][j]!=0)
{
j=INF;
i=INF;
}
}
if(i==N) //是全零矩陣，則令notzerotag＝0，終止循環
notzerotag=0;
}//if(temp)
else if(endtag>9) //設置產生隨機數次數，若大于25則重新生成隨機數
{
k=0;
for(j=0;j<N;j++)
{
if(T[0][j]!=0)
k++;
}
if(k==1) //剩余的矩陣R中每一行中僅有一個非零元素
{
max=0;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(T[i][j]!=0&&T[i][j]>max)
max=T[i][j];
}
}
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(T[i][j]!=0)
{
p[i][j][t]=1;
minq[t]=max;
T[i][j]=0;
}
}
}
notzerotag=0;
cout<<"第"<<t+1<<"個排列矩陣的系數＝"<<minq[t]<<endl;
cout<<"第"<<t+1<<"個排列矩陣如下："<<endl;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
cout<<p[i][j][t]<<",";
cout<<endl;
}
cout<<endl;
cout<<"分解剩下的矩陣T＝"<<endl;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
cout<<T[i][j]<<" ? ";
cout<<endl;
}
cout<<endl;
}//if
else
{
endtag=0;
t--;
}
}//else if
else
t--;
} //for
cout<<"LJ分解共得到"<<t<<"個排列矩陣"<<endl;
for(i=0;i<t;i++)
bandsize+=minq[i];
cout<<"得到的帶寬＝"<<bandsize<<endl;
//下面對p[i][j][t]進行LJ調度 得到調度表schedul[N][t],每一列對應一個時隙的調度
//LJ調度與BV調度的區別是考慮了調度的開始時間starttime
int schedul[N][BANDWITH];
double temp2,tagclass[BANDWITH],select[BANDWITH];//存放t個排列矩陣的標記類
int mintag,selecttag[BANDWITH];
int position[BANDWITH];
int temp1,temp3[N];
int times;
int delet[BANDWITH];
int size=0; //存放調度表的長度，即各排列矩陣的系數的和
int schedullen;
double starttime[BANDWITH];
for(i=0;i<t;i++)
{
select[i]=1.0/minq[i]; //對t個排列矩陣預附標記的初值
tagclass[i]=select[i];
selecttag[i]=minq[i]; //對t個標記的被選擇標記附初值＝0：被調度完，!=0：未被調度完
position[i]=i;
starttime[i]=0; //*****對t個標記的開始時間賦初始值為0；
}
for(j=0;j<t;j++)
cout<<select[j]<<" 初始標記值 ";
cout<<endl;
for(i=0;i<t;i++) //進行size次調度
size+=minq[i];
for(k=0;k<size;k++)
{
for(i=0;i<t;i++) //對t個標記進行冒泡排序,按升序排列在select數組中
{
for(j=0;j<t-1;j++)
{
if(select[j]>select[j+1])
{
temp2=select[j+1];
select[j+1]=select[j];
select[j]=temp2;
temp1=position[j+1];
position[j+1]=position[j];
position[j]=temp1;
temp1=selecttag[j+1];
selecttag[j+1]=selecttag[j];
selecttag[j]=temp1;
}
}
} //一次排序完成
for(j=0;j<t;j++)
cout<<select[j]<<"?";
cout<<endl;
for(j=0;j<t;j++)
cout<<position[j]<<"??";
cout<<endl;
for(i=0;i<t;i++)
{
if(selecttag[i]!=0&&starttime[i]<=k)
{
mintag=position[i];
temp1=i;
i=t;
}
}
cout<<"對排列矩陣P"<<mintag<<"調度"<<endl;
//下面對p[][][mintag]調度
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(p[i][j][mintag]==1)
schedul[i][k]=j+1;
}
}
//修改被調度的排列矩陣的標記
starttime[temp1]=select[temp1];
select[temp1]=select[temp1]+tagclass[mintag];
selecttag[temp1]-=1;
cout<<endl<<"得到的調度向量："<<endl;
for(i=0;i<N;i++)
cout<<schedul[i][k]<<endl;
}//for
cout<<endl<<"得到的調度矩陣："<<endl;
for(i=0;i<N;i++)
{
for(j=0;j<size;j++)
cout<<schedul[i][j]<<",";
cout<<endl;
}
cout<<endl;
//修改得到的調度表,刪除冗余調度使其等于原流量
for(i=0;i<N;i++)
{
for(j=0;j<size;j++)
{
temp=schedul[i][j]-1;
if(backupT[i][temp]>=1)
backupT[i][temp]-=1;
else
schedul[i][j]=0;
}
}
cout<<"刪除冗余調動后得到的調度表如下："<<endl;
for(i=0;i<N;i++)
{
for(j=0;j<size;j++)
cout<<schedul[i][j]<<" ";
cout<<endl;
}
//合并調度向量
temp1=0;
for(j=0;j<size;j++)
{
for(i=0;i<N;i++)
{
if(schedul[i][j]==0)
{
delet[temp1]=j; //存放可能可以合并的調度向量
temp1++;
i=N;
}
}
}
temp=0;
for(times=0;times<2;times++)
{
for(k=0;k<temp1-1;k++) //進行合并
{
j1=delet[k];
for(j=k+1;j<temp1;j++)
{
j2=delet[j];
for(i=0;i<N;i++)
{
if(schedul[i][j1]&&schedul[i][j2])
i=INF;
}
if(i==N)//可能可以合并，但不知道是否有沖突，下面需要判斷
{
for(t=0;t<N;t++)
temp3[t]=schedul[t][j1]+schedul[t][j2];
for(t=0;t<N-1;t++) //檢查合并后是否有沖突，即是否有多個端口向同一個端口發送數據
{
for(m=t+1;m<N;m++)
{
if(temp3[t]==temp3[m])
t=N; //有沖突則跳出
}
}
if(t==N-1) //沒有沖突則合并
{
for(t=0;t<N;t++)
{
schedul[t][j1]=temp3[t];
schedul[t][j2]=0;
}
for(m=j2+1;m<size;m++)
for(t=0;t<N;t++)
schedul[t][m-1]=schedul[t][m];
for(m=0;m<N;m++)
schedul[m][size-1]=0;
for(m=j+1;m<temp1;m++)
select[m-1]=select[m];
temp1--;
temp++;//記錄刪除的向量的個數
cout<<"第"<<j1<<"和第"<<j2<<"列可以合并為："<<endl;
for(t=0;t<N;t++)
cout<<schedul[t][j1]<<endl;
}
}//if
}//for j
} //for k
}//for times
schedullen=size-temp;
cout<<endl<<"刪除"<<temp<<"個多余調度合并后的調度矩陣S如下："<<endl;
for(i=0;i<N;i++)
{
for(j=0;j<schedullen;j++)
cout<<schedul[i][j]<<",";
cout<<endl;
}
cout<<endl;
//下面對調度矩陣S計算抖動
jitter=0;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(constbackT[i][j]>1)
{
mininterval=schedullen;
maxinterval=1;
starttag=0;
endlen=schedullen;
for(k=0;k<endlen;k++)
{
t=k%schedullen;
if(starttag==0&&schedul[i][t]!=j+1)
endlen++;
else if(starttag==0&&schedul[i][t]==j+1)
{
endlen++;
starttag=1;
tempinterval=0;
}
else if(starttag==1&&schedul[i][t]==j+1)
{
tempinterval++;
if(tempinterval<mininterval)
mininterval=tempinterval;
if(tempinterval>maxinterval)
maxinterval=tempinterval;
tempinterval=0;
}
else if(starttag==1&&schedul[i][t]!=j+1)
tempinterval++;
}//for k
individualjitter=maxinterval-mininterval;
}//if
else
individualjitter=0;
jitter+=individualjitter;
}//for j
}//for i
jitter=jitter*0.1/(N*(N-1))*10;
cout<<"抖動＝"<<jitter<<endl;
}//main
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -