conflictfreeaccess.cpp

一种n×n矩阵在n个存储体中的无冲突访问存储方案

//无访问冲突存储模拟程序
//n=pow(4,p),p=1,2,3,...
//n*n的二维数据所需的并行存储体数n.
//下标i,j可以用2p位二进制表示:
//	i=i(2*p-1)...i(1)i(0); 
//	j=j(2*p-1)...j(1)j(0);
//对任意的a[i][j]有对准网络:
//	体号M:		for(k=0;k<p;k++) M+=pow(4,k)*[2*(i(2*k)^j(2*k+1))+i(2*k)^i(2*k+1)^j(2*k)];
//	体内地址L:	j
//2007,10,20，23:52

# include <stdio.h>
# include <math.h>
# include <iostream.h>
typedef struct{
	int i;	//
	int j;	//
}dataAddr;	//数据在矩阵中的位置
int getThekthBit(int i,int k)	//取整数i(0~256)二进制表示的第k(0~7)位；如果该位是1返回1，否则返回0。
{								//0<=i<=255; k=0,1,2,3,4,5,6,7
	switch (k)
	{
	case 0 :{if(i&1)  return 1;	else return 0;}
	case 1 :{if(i&2)  return 1;	else return 0;}
	case 2 :{if(i&4)  return 1;	else return 0;}
	case 3 :{if(i&8)  return 1;	else return 0;}
	case 4 :{if(i&16) return 1;	else return 0;}
	case 5 :{if(i&32) return 1;	else return 0;}
	case 6 :{if(i&64) return 1;	else return 0;}
	case 7 :{if(i&128)return 1;	else return 0;}
	default: return -1;
	};
}
int formijToM(int i,int j,int p)//实现对准映射;i,j为数据在矩阵中的行列坐标，pow(4,p)=n(n是矩阵的维数)
{								//返回元素(i,j)在无访问冲突存储中的体号
	int M=0;
	int temp;
	for(int k=0;k<p;k++)
	{
		temp=2*k;
		M+=int(
			pow(2,temp)*	(
			2*(	(getThekthBit(i,temp)^getThekthBit(j,temp+1))	)
			+getThekthBit(i,temp)^getThekthBit(i,temp+1)^getThekthBit(j,temp)	)
			);
	}
	return M;
}

void main()
{

	/* 显示待存储矩阵 */
	dataAddr matrix[256][256];	//模拟存储体，存储数据在矩阵中的位置
	int n=4;					//待存储矩阵维数
	cout<<"请输入待存储矩阵维数(4|16|64|256):\nn=";
	cin>>n;
	printf("待存储矩阵数据为:\n\n");
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			printf("a(%d,%d) ",i,j);
	printf("\n");
	}
	/* 计算p */
	int p=1;
	for(p=1;pow(4,p)<n-1;p++);
	printf("n=%d\np=%d,",n,p);
	/*交互*/
	char cntn;
	cout<<"输入'c'+'回车键'继续"<<endl;
	cin>>cntn;
	cout<<endl;
	/*显示映射方式*/
	printf("上述矩阵存于n个存储体的无冲突访问存储方式:\n\n");
	for(i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			matrix[j][formijToM(i,j,p)].i=i;
			matrix[j][formijToM(i,j,p)].j=j;
			printf("a(%d,%d)——>b(%d,%d)\n\n",i,j,i,formijToM(i,j,p));
		}
	printf("\n");
	}
	/*显示无冲突访问存储方案*/
	cout<<"结果："<<endl;
	for(i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(matrix[i][j].j<0)
				printf("m[ ][ ] ");
			else
				printf("a[%d][%d] ",matrix[i][j].i,matrix[i][j].j);
		}
	printf("\n\n");
	}
	/*交互*/
	cout<<"输入'f'+'回车键'退出"<<endl;
	cin>>cntn;
}
//	double ldexp(double x, int exponent)//计算x*2的exponent次幂，即2*pow(2,exponent)的数值
//	double sqrt(double x)//求平方根
//	double pow(double x, double y)//计算以x为底数的y次幂