多核编程和并行运算期末复习.doc

5题每题20分1. 1）简述MPI 6个函数格式定义，作用，参数含义。MPI简介：消息传递接口的标准，用于开发基于消息传递的并行程序，目的是为用户提供一个实际可用的、可移植的、高效和灵活的消息传递接口库，能够在PC Windows和所有主要的Unix工作站以及并行机上实现。MPI是一个库，不是一种语言，实现并行必须依托于某种语言：FORTRAN， MPI主要函数：MPI_Init，初始化函数：MPI程序通过调用MPI_Init函数进行MPI环境，并完成所有的初始化工作，这个函数通常是MPI程序的第一个函数调用。 格式如下： int MPI_Init( int *argc, char *argv )MPI_Finalize，结束函数：MPI通过调用MPI_Finalize函数从MPI环境中退出，它是MPI程序的最后一个MPI函数调用，否则程序的执行结果是不可预知的。 格式如下： int MPI_Finalize(void) ;MPI_Comm_rank，获取进程的编号：MPI程序通过MPI_Comm_Rank函数调用获取当前进程在指定通信域中的编号，有了该编号，不同的进程就可以将自身和其他进程区分开来，从而实现进程间的并行和合作。 格式如下：nt MPI_Comm_rank(MPI_Comm comm, int *rank)MPI_Comm_size，获取指定通信域的进程数：MPI通过调用MPI_Comm_size函数获取指定通信域的进程个数，进程可根据它来确定自己应该完成的任务比例。 格式如下：int MPI_Comm_size(MPI_Comm comm, int *size)MPI_Send消息发送函数：MPI_Send函数用于发送一个消息到目标进程。其格式如下： int MPI_Send( void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm_comm)buf : 消息发送的起始地址count ：发送消息的数量datatype: 发送数据的类型dest: 标识目标进程tag: 发送消息时打上的标签comm: 通信类型MPI_Recv，消息接收：MPI_Recv函数用于从指定进程接收一个消息，格式如下：int MPI_Recv( void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm, comm, MPI_Status *status )buf : 消息接收后存放地址count : 接收数量datatype : 接收数据类型source : 发送消息的进程tag : 消息的标签comm : 通信类型status : 接收状态1.2）举例简单的应用解释如何通信。每个进程会属于一个或多个通信域。一个简单的例子/* simple.c */#include “mpi.h” /*MPI头文件*/#include int main(argc, argv)int argc ;char *argv ; int rank, size, tag = 1 ; int senddata, recvdata ; MPI_Status status ; MPI_Init( &argc, &argv ) ; /*MPI的初始化*/ MPI_Comm_rank( MPI_COMM_WORLD, &rank ) ; /*该进程的编号 */ MPI_Comm_size( MPI_COMM_WORLD, &size ); /* 总的进程数目*/if ( rank = 0 ) int senddata, recvdata ; MPI_Status status ; MPI_Init( &argc, &argv ) ; /*MPI的初始化*/ MPI_Comm_rank( MPI_COMM_WORLD, &rank ) ; /*该进程的编号 */ MPI_Comm_size( MPI_COMM_WORLD, &size ); /* 总的进程数目*/ if ( rank = 0 ) senddata = 9999 ; MPI_Send( &senddata, 1, MPI_INT, 1, tag, MPI_COMM_WORLD ) ; /* 发送数据到进 程1 */ if ( rank = 1 ) MPI_Recv( &recvdata, 1, MPI_INT, 0, tag, MPI_COMM_WORLD, &status); /*从进程0接收数据*/ MPI_Finalize() ; /*MPI的结束函数*/ return (0) ;另一个例子实现 sum( a + b )，并且把求和结果打印出来。这里 a, b 都是n维空间的向量，并且每个元素都为整数。#include “mpi.h” /*MPI头文件*/#include #include int main(argc, argv)int argc ;char *argv ; int rank, size, i, tag = 1 ; int *a, *b, n; n = 100 ; a = (int*)malloc( sizeof( int ) * n ) ; b = (int*)malloc( sizeof( int ) * n ) ; for(i = 0 ; i n ; i+) ai = 1 ; bi = 2 ; MPI_Status status ; MPI_Init( &argc, &argv ) ; /*MPI的初始化*/ MPI_Comm_size( MPI_COMM_WORLD, &size ); /* 总的进程数目*/ int nSize = n / size ; MPI_Comm_rank( MPI_COMM_WORLD, &rank ) ; /*该进程的编号 */ if( rank != (size - 1) ) int sum = 0 ; for( i = 0 ; i nSize ; i+ ) sum += ai + rank * nSize + b i + rank * nSize ; MPI_Send( &sum, 1, MPI_INT, (size-1), tag, MPI_COMM_WORLD ) ; /* 发送求和数据到进程(size-1) */else int sum = 0, total = 0 ; for( i = (size - 1) * nSize ; i n ; i+ ) sum += ai + bi ; total += sum ; for( i = 0 ; i (size - 1) ; i+ ) MPI_Recv( &sum, 1, MPI_INT, i, tag, MPI_COMM_WORLD, &status); /*从各个进程接收部分求和数据*/ total += sum ; printf( total = %dn, total ) ; MPI_Finalize() ; /*MPI的结束函数*/ return (0) ;2. 1）通过MPI如何实现2个矢量相加。/* simple.c */#include /*MPI头文件*/#include #include int main(argc, argv)int argc ;char *argv ; int rank, size, tag = 1 ; int *a, *b , n = 100 ; a = (int*)malloc( sizeof( int ) * n ) ; b = (int*)malloc( sizeof( int ) * n ) ; int i ; for( i = 0 ; i n ; i+ ) ai = 1 ; bi = 2 ; MPI_Status status ; MPI_Init( &argc, &argv ) ; /*MPI的初始化*/ MPI_Comm_rank( MPI_COMM_WORLD, &rank ) ; /*该进程的编号 */ MPI_Comm_size( MPI_COMM_WORLD, &size ); /* 总的进程数目*/ int nSize = n / size ; int sum ; if( rank (size -1) ) sum = 0 ; for( i = 0 ; i nSize ; i+ ) sum += ai + bi ; else sum = 0 ; for( i = nSize * (size - 1) ; i n ; i+ ) sum += ai + bi ; printf(cpu = %d, sum = %dn, rank, sum ) ; MPI_Finalize() ; /*MPI的结束函数*/ return (0) ;2.2）通过MPI如何实现2个矢量相乘。#include /*MPI头文件*/#include #include int main(argc, argv)int argc ;char *argv ; int rank, size; int n = 100 ; int i ; MPI_Status status ; MPI_Init( &argc, &argv ) ; MPI_Comm_size( MPI_COMM_WORLD, &size ); int nSize = n / size ; MPI_Comm_rank( MPI_COMM_WORLD, &rank ) ; int *a, *b ; a = (int*)malloc( sizeof(int) * n ) ; b = (int*)malloc( sizeof(int) * n ) ; int( i = 0 ; i n ; i+ ) ai = 1 ; bi = 2 ; int tag = 1 ; if( rank != (size - 1) ) int sum = 0 ; for( i = 0 ; i nSize ; i+ ) sum += arank * nSize + i* brank * nSize + i; MPI_Send( &sum, 1, MPI_INT, (size-1), tag, MPI_COMM_WORLD ) ; else int sum = 0, total = 0 ; for( i = (size - 1) * nSize ; i n ; i+ ) sum += ai * bi; total += sum ; for( i = 0 ; i (size - 1) ; i+ ) MPI_Recv( &sum, 1, MPI_INT, i, tag, MPI_COMM_WORLD, &status); total += sum ; printf( total = %dn, total ) ; MPI_Finalize() ; /*MPI的结束函数*/ return (0) ; 3.1）n!如何用并行计算做（n给定）#include stdio.h#include stdlib.h#include math.h#include mpi.hint m,N;long jiech;int my_rank;int p;MPI_Status status;/* * 函数名: main * 输入：argc为命令行参数个数； * argv为每个命令行参数组成的字符串数组。 * 输出：返回0代表程序正常结束 */int main(int argc, char *argv) int i,my_rank,group_size; long lji=1; MPI_Init(&argc,&argv); /* 启动计算 */ MPI_Comm_size(MPI_COMM_WORLD,&group_size); /* 找进程数 */ MPI_Comm_rank(MPI_COMM_WORLD,&my_rank); /* 找自己的id */ p=group_size; if(my_rank=0) printf(Please input DATA:);scanf(%d,&N);MPI_Bcast(&N,1,MPI_INT,0,MPI_COMM_WORLD); /* 广播size到所有进程*/ for(i=my_rank;iN;i=i+p) lji=lji*(i+1); /* 求各个处理器中lji积，并将最终结果存放在0进程的jiech中*/ MPI_Reduce(&lji,&jiech,1,MPI_INT,MPI_PROD,0,MPI_COMM_WORLD); if (my_rank=0) /* 打印结果*/ printf(N! =%d,jiech); printf(n); / printf(Whole running time = %f secondsn,time2-starttime); MPI_Barrier(MPI_COMM_WORLD); /* 同步所有进程 */ MPI_Finalize(); /* 结束计算 */ return (0);3.2） 1+2+3+.+n如何用并行计算做（n给定，例子中n=100）#include /*MPI头文件*/#include #include int main(argc, argv)int argc ;char *argv ; int rank, size; int n = 100 ;int i ; MPI_Status status ; MPI_Init( &argc, &argv ) ; MPI_Comm_size( MPI_COMM_WORLD, &size ); int nSize = n / size ; MPI_Comm_rank( MPI_COMM_WORLD, &rank ) ; int tag = 1 ; if( rank != (size - 1) ) int sum = 0 ; for( i = 0 ; i nSize ; i+ ) sum += rank * nSize + i + 1; MPI_Send( &sum, 1, MPI_INT, (size-1), tag, MPI_COMM_WORLD ) ; elseint sum = 0, total = 0 ; for( i = (size - 1) * nSize ; i n ; i+ ) sum += i + 1; total += sum ; for( i = 0 ; i (size - 1) ; i+ ) MPI_Recv( &sum, 1, MPI_INT, i, tag, MPI_COMM_WORLD, &status); total += sum ; printf( total = %dn, total ) ; MPI_Finalize() ; /*MPI的结束函数*/ return (0) ; 4.1）不同的压缩矩阵如何实现矩阵乘。4.2） 给你一个矩阵，让你写出三种格式中的一种存储（写出三种压缩方式中的一种，矩阵和矢量乘你怎么做压缩及如何存储）16稀疏矩阵矢量乘(CSR)for(int i = 0 ; i n ; i+ ) int row_s = ptri ; int row_e = ptri+1 ; double sum = 0.0 ;for(int j = row_s ; j row_e ; j+)sum+=dataj*xindicesj; bi = sum ;稀疏矩阵矢量乘(DIA)for(int i = 0 ; i n ; i+)double sum = 0.0 ; for(int j = 0 ; j =0 & ncol n )double val = datai+j*n; sum += val * xncol ; bi = sum ;稀疏矩阵矢量乘(ELL)for(int i = 0 ; i n ; i+) double sum = 0.0 ;for(int j = 0 ; j cols; j+)double val = datai + j*n ; if( val != 0 )sum += val*xindicesi+j*n ; bi = sum ;#include /*MPI头文件*/#include #include int main(argc, argv)int argc ;char *argv ; int rank, size; double *data ; int *indices, *ptr ; double *b, *x ; data = (double*)malloc( sizeof( double ) * SIZE * 5 ) ; indices = (int*)malloc( sizeof( int ) * SIZE * 5 ) ; ptr = (int*)malloc( sizeof( int ) * (SIZE + 1) ) ; x = (double*)malloc( sizeof( double ) * SIZE ) ; b = (double*)malloc( sizeof( double ) * SIZE ) ; csr_scalar_sparse_matrix_cpu(data, indices, ptr) ;int i, j, k ;for( k = 0 ; k SIZE ; k+ )xk = 1.0 ; int i ; MPI_Status status ; MPI_Init( &argc, &argv ) ; MPI_Comm_size( MPI_COMM_WORLD, &size ); int nSize = n / size ; MPI_Comm_rank( MPI_COMM_WORLD, &rank ) ; int tag = 1 ; if( rank != (size - 1) ) for( i = 0 ; i nSize ; i+ ) int r_start = ptri + nSize * rank ;int r_end = ptri + 1 + nSize * rank ;double sum = 0.0 for( j = r_start ; j r_end ; j+ ) sum += dataj * xindicesj ; bi + nSize * rank = sum ; MPI_Send(b+rank*nSize, nSize, MPI_DOUBLE, (size-1), tag, MPI_COMM_WORLD ) ; if( rank = (size -1 ) ) for( i = 0 ; i (size - 1) ; i+ ) MPI_Recv( b + i * nSize, nSize, MPI_DOUBLE, i, tag, MPI_COMM_WORLD, &status); double sum = 0.0 ; for( i = 0 ; i SIZE ; i+ ) sum += bi ; printf( sum = %lfn, sum ) ; MPI_Finalize() ; /*MPI的结束函数*/ return (0) ; 5）GPU,范式，平方和3、#include #include #include #include #define SIZE 1048576#define BLOCK_NUM 32#define THREAD_NUM 256_global_ void sumOfSquares_gpu0( float *a, int n, float *result )int tid = threadIdx.x ;int bid = blockIdx.x ;float sum = 0.0 ;for( int i = bid * THREAD_NUM + tid ; i n ; i += BLOCK_NUM * THREAD_NUM )sum += ai * ai ;resultbid * THREAD_NUM + tid = sum ;int main( int argc, char *argv )cudaEvent_t start, stop ;float elapsedTime ;float *result, *dev_result, *a, *dev_a ;cudaMalloc( (void*)&dev_result, BLOCK_NUM * THREAD_NUM * sizeof(float) ) ;cudaMalloc( (void*)&dev_a, SIZE * sizeof(float) ) ;a = (float*)malloc( SIZE * sizeof( float ) ) ;result = (float*)malloc( BLOCK_NUM * THREAD_NUM * sizeof( float ) ) ;for( int i = 0 ; i SIZE ; i+ )ai = 1.0 ;cudaMemcpy(dev_a, a, SIZE * sizeof(float), cudaMemcpyHostToDevice ) ;cudaEventCreate( &start ) ;cudaEventCreate( &stop ) ;cudaEventRecord( start, 0 ) ;sumOfSquares_gpu0( dev_a, SIZE, dev_result ) ;cudaMemcpy(result, dev_result, BLOCK_NUM * THREAD_NUM * sizeof(float), cudaMemcpyDeviceToHost ) ; double sum = 0.0 ; for(int i = 0 ; i BLOCK_NUM * THREAD_NUM ; i+ ) sum += resulti ; cudaEventRecord( stop, 0 ) ; cudaEventSynchronize( stop ) ; cudaEventElapsedTime( &elapsedTime, start, stop ) ; printf( TotalTime = : %20.12f ms n , elapsedTime ) ; printf( sum = : %20.12fn , sum ) ; cudaEventDestroy( start ) ; cudaEventDestroy( stop ) ; free( a ) ; cudaFree( dev_a ) ; cudaFree( dev_result ) ; return 0 ;2、#include #include #include #include #define SIZE 1048576#define BLOCK_NUM 32#define THREAD_NUM 256_global_ void sumOfSquares_gpu0( float *a, int n, float *result )_shared_ float sharedTHREAD_NUM;int tid = threadIdx.x ;int bid = blockIdx.x ;sharedtid = 0.0 ;for( int i = bid * THREAD_NUM + tid ; i n ; i += BLOCK_NUM * THREAD_NUM )sharedtid += ai * ai ; _syncthreads(); if(tid = 0) for(int i = 1; i THREAD_NUM; i+) shared0 += sharedi; resultbid = shared0; int main( int argc, char *argv )cudaEvent_t start, stop ;float elapsedTime ;float *result, *dev_result, *a, *dev_a ;cudaMalloc( (void*)&dev_result, BLOCK_NUM * sizeof(float) ) ;cudaMalloc( (void*)&dev_a, SIZE * sizeof(float) ) ;a = (float*)malloc( SIZE * sizeof( float ) ) ;result = (float*)malloc( BLOCK_NUM * sizeof( float ) ) ;for( int i = 0 ; i SIZE ; i+ )ai = 1.0 ;cudaMemcpy(dev_a, a, SIZE * sizeof(float), cudaMemcpyHostToDevice ) ;cudaEventCreate( &start ) ;cudaEventCreate( &stop ) ;cudaEventRecord( start, 0 ) ;sumOfSquares_gpu0( dev_a, SIZE, dev_result ) ;cudaMemcpy(result, dev_result, BLOCK_NUM * sizeof(float), cudaMemcpyDeviceToHost ) ; double sum = 0.0 ; for(int i = 0 ; i BLOCK_NUM ; i+ ) sum += resulti ; cudaEventRecord( stop, 0 ) ; cudaEventSynchronize( stop ) ; cudaEventElapsedTime( &elapsedTime, start, stop ) ; printf( TotalTime = : %20.12f ms n , elapsedTime ) ; printf( sum = : %20.12fn , sum ) ; cudaEventDestroy( start ) ; cudaEventDestroy( stop ) ; free( a ) ; cudaFree( dev_a ) ; cudaFree( dev_result ) ; return 0 ;1、#include #include #include #include #define SIZE 1048576#define THREAD_NUM 256_global_ void sumOfSquares_gpu0( float *a, int n, float *result )int tid = threadIdx.x ;float sum = 0.0 ;for( int i = tid ; i n ; i += THREAD_NUM )sum += ai * ai ;resulttid = sum ;int main( int argc, char *argv )cudaEvent_t start, stop ;float elapsedTime ;float *result, *dev_result, *a, *dev_a ;cudaMalloc( (void*)&dev_result, THREAD_NUM * sizeof(float) ) ;cudaMalloc( (void*)&dev_a, SIZE * sizeof(float) ) ;a = (float*)malloc( SIZE * sizeof( float ) ) ;result = (float*)malloc( THREAD_NUM * sizeof( float ) ) ;for( int i = 0 ; i SIZE ; i+ )ai = 1.0 ;cudaMemcpy(dev_a, a, SIZE * sizeof(float), cudaMemcpyHostToDevice ) ;cudaEventCreate( &start ) ;cudaEventCreate( &stop ) ;cudaEventRecord( start, 0 ) ;sumOfSquares_gpu0( dev_a, SIZE, dev_result ) ;cudaMemcpy(result, dev_result, THREAD_NUM * sizeof(float), cudaMemcpyDeviceToHost ) ; double sum = 0.0 ; for(int i = 0 ; i THREAD_NUM ; i+ ) sum += resulti ; cudaEventRecord( stop, 0 ) ; cudaEventSynchronize( stop ) ; cudaEventElapsedTime( &elapsedTime, start, stop ) ; printf( TotalTime = : %20.12f ms n , elapsedTime ) ; printf( sum = : %20.12fn , sum ) ; cudaEventDestroy( start ) ; cudaEventDestroy( stop ) ; free( a ) ; cudaFree( dev_a ) ; cudaFree( dev_result ) ; return 0 ;4、#include #include #include #include #define SIZE 1048576#define BLOCK_NUM 32#define THREAD_NUM 256_global_ void sumOfSquares_gpu0( float *a, int n, float *resul