📄 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 + -