并行多核体系结构基础——第二章知识点和课后习题

本书只找到pdf版本，全网没搜到答案，与老师也更多的为探讨，所以答案纯自己手写，若有错误欢迎使劲纠错

本章理解有难度，可能是上课没好好听，下来也没好好看，题目做的甚是迷茫，感觉很不对劲哎哎哎

知识点回头抽时间复习再补上吧o(￣ヘ￣o＃)

课后习题：

首先复习在两个处理器上进行矩阵相乘，将二维矩阵A和B相乘，结果放入Y

假设在不考虑性能开销和可拓展性下，矩阵乘的最内层"for k"循环进行优化。假设用一个线程执行循环的一半迭代，用另一个线程执行剩下的一半循环迭代。线程的ID为0和1

矩阵相乘代码如下：

#define MATRIX_DIM 500

double A[MATRIX_DIM][MATRIX_DIM],
	   B[MATRIX_DIM][MATRIX_DIM],
	   Y[MATRIX_DIM][MATRIX_DIM];
int i,j,k;

for(i=0;i<MATRIX_DIM;i++){
	for(j=0;j<MATRIX_DIM;j++){
		Y[i][J]=0.0;
		for(l=0;k<MATRIX_DIM;k++){
			Y[i][j]+=A[i][k]*B[k][j];
		} // for k
	} // for j
} // for i

基于以上假定，可得到上述代码的共享存储版本

#define MATRIX_DIM 500

double A[MATRIX_DIM][MATRIX_DIM],
	   B[MATRIX_DIM][MATRIX_DIM],
	   Y[MATRIX_DIM][MATRIX_DIM];
int i,j,k,tid;
int kpriv[2],startiter[2],enditerp[2]; //kprive（k——privatization）为线程特有的循环下标变量

for(i=0;i<MATRIX_DIM;i++){
	for(j=0;j<MATRIX_DIM;j++){
		Y[i][j]=0.0;

		tid=begin_parallel(); //创建一个附加线程
		startiter[tid]=tid*MATRIX_DIM/2;
		enditer[tid]=startiter[tid]+MATRIX_DIM/2;

		for(kpriv[tid]=startiter[tid];kpriv[tid]<enditer[tid];kpriv[tid]++){
			begin_critical(); //临界区的开始
				Y[i][j]+=A[i][kpriv[tid]]*B[kpriv[tid]][j];
			end_critical(); //临界区的结束
		} //for k
		barrier(); //确保所有线程都到达该同步点后，才允许任何线程通过该点继续执行
		end_paraller(); //结束附加线程
	} //for j
} //for i

在基础上，完成课后习题的（b）部分

将外层"for i"循环并行化，开销会有一定减少

int i,j ,k,tid;
float A[n][m],B[m][p],C[n][p],y[n][p]; //要计算Y=A*B+C 
int kpriv[2],startiter[2],enditer[2];

for(j=0;j<n/2;j++){
	for(k=0;k<n/2;k++){
		Y[i][j]=0.0;
		tid=begin_parallel(); //创建一个附加线程
		startiter[tid]=tid*n/2;
		enditer[tid]=startiter[tid]+n/2;

		for(kpriv[tid]=startiter[tid];kpriv[tid]<enditer[tid];kpriv[tid]++){
    		begin_critical(); //临界区的开始
    			Y[kpriv[tid]][j]+=A[kpriv[tid]][j]*B[j][j];
    		end_critical(); //临界区的结束
    	}//for i
	} //for k
} //for j
Y[kpriv[tid]][j]+=C[kpriv[tid]][j];

基于以上假定，可得到上述代码的消息传递版本

#define MATRIX_DIM 500

double A[MATRIX_DIM][MATRIX_DIM],
	   B[MATRIX_DIM][MATRIX_DIM],
	   Y[MATRIX_DIM][MATRIX_DIM];
int i,j,k,tid;
int startiter,enditer;
double temp,temp2;

tid=begin_parallel(); //创建一个附加线程
startiter=tid*MATRIX_DIM/2;
enditer=startiter+MATRIX_DIM/2;

if(tid==0){
	send(1,A[0][MATRIX_DIM/2-1]...A[MATRIX_DIM-1][MATRIX_DIM-1]);
	send(1,B[MATRIX_DIM/2-1][0]...B[MATRIX_DIM-1][MATRIX_DIM-1]);
}
else{
	recv(0,A[0][MATRIX_DIM/2-1]...A[MATRIX_DIM-1][MATRIX_DIM-1]);
	recv(0,B[MATRIX_DIM/2-1][0]...B[MATRIX_DIM-1][MATRIX_DIM-1]);
}

for(i=0;i<MATRIX_DIM;i++){
	for(j=0;j<MATRIX_DIM;j++){
		Y[i][j]=0.0;

		temp=Y[i][j];
		for(k=startiter;k<enditer;k++){
			temp+=A[i][k]*B[k][j];
		} //for k
		if(tid==0){
			recv(1,&temp2);
			Y[i][j]=temp+temp2;
		}
		else{
			send(0,temp);
		}
	} //for j
} //for i
end_parallel();

在基础上，完成课后习题的（a）部分

double A[n][m],
	   B[m][p],
	   C[n][p]
	   Y[n][p];
int i,j,k,tid;
int startiter,enditer;
double temp,temp2;

tid=begin_parallel(); //创建一个附加线程
startiter=tid*n/2;
enditer=startiter+n/2;

if(tid==0){
	send(1,A[n/2][0]...A[n-1][n-1]);
	send(1,B[0][0]...B[n-1][n-1]);
}
else{
	recv(0,A[n/2][0]...A[n-1][n-1]);
	recv(0,B[0][0]...B[n-1][n-1]);
}

for(j=0;j<n/2;j++){
	for(k=0;k<n/2;k++){
		Y[i][j]=0.0;

		temp=Y[k][j];
		for(k=startiter;k<enditer;k++){
			temp+=A[k][j]*B[j][j];
		} //for i
		if(tid==0){
			recv(1,&temp2);
			Y[k][j]=temp+temp2;
		}
		else{
			send(0,temp);
		}
	} //for k
} //for j
end_parallel();