日月明

并行与分布式计算导论——作业一
Based on markdown 推荐使用markdown阅读器阅读,或访问 并行与分布式计算导论——作业一作业...
扫描右侧二维码阅读全文
24
2019/03

并行与分布式计算导论——作业一

该部分仅登录用户可见

Based on markdown 推荐使用markdown阅读器阅读,或访问 并行与分布式计算导论——作业一

作业要求

完成以下OpenMP程序,提交作业报告,并在报告的最后附源码,格式为PDF。
Find Prime
矩阵乘法
Calculate π
报告的内容可以包括:
1.并行的核心代码或核心思想;
2.与参考串行/并行程序相比较,或使用不同的线程数量比较输出结果并简单分析;
3.使用OpenMP的心得或遇到的困难。

并行的核心代码与核心思想

并行计算一般是指将多个可同时运行的程序指令经由不同的处理器核心同时处理。在同时进行的前提下,可以将计算的过程分解成小部分,之后以并发方式来加以解决,最核心的部分就是找到可以并行处理的模块,将该模块的任务分为可同时处理的子任务,分配给不同的核心。并行计算可以划分成时间并行和空间并行,时间并行就是指令流水化,空间并行指的是多个处理器协同工作,我们进行并行程序编程一般考虑后者。

FindPrime

结果比较(本机8代酷睿i7-6核心)

问题规模线程数时间(ms)线程数时间(ms)线程数时间(ms)线程数时间(ms)
$10^4$15264666
$10^6$117218418619
$10^7$11272112496692
$10^8$11661213254122661189

结果比较(临湖草堂)

问题规模线程数时间(ms)线程数时间(ms)线程数时间(ms)线程数时间(ms)
$10^4$12.031522.117334.041447.3610
$10^6$110.89128.544537.1368410.641
$10^7$183.352259.296351.739438.473
$10^8$11121.12813.653762.174742.64

并附上4线程时,临湖草堂上的对比数据

reference serial impl.  : time_cost=1.1242e+00                   res:There are 5761455 primes less than or equal to 100000000

reference parallel impl.: time_cost=6.4164e-01 speedup=1.752e+00 res:There are 5761455 primes less than or equal to 100000000

your impl.              : time_cost=6.9772e-01 speedup=1.611e+00 res:There are 5761455 primes less than or equal to 100000000

从两张表中可以看出,当问题规模较小时(小于$10^6$),采用并行算法并没有正面的增益,反而使得运行时间被延长,而当数据规模较大时,例如$10^8$,此时采用并行算法可以显著的降低程序运行时间。

程序源码

/*
 *   This program uses the Sieve of Eratosthenes to determine the
 *   number of prime numbers less than or equal to 'n'.
 *
 *   Adapted from code appearing in "Parallel Programming in C with
 *   MPI and OpenMP," by Michael J. Quinn, McGraw-Hill (2004).
 */

#include <stdio.h>
#include <omp.h>
#include <stdlib.h>

int main (int argc, char *argv[])
{
    int    count;        /* Prime count */
    int    first;        /* Index of first multiple */
    int    i;
    int    index;        /* Index of current prime */
    char  *marked;       /* Marks for 2,...,'n' */
    int    n;            /* Sieving from 2, ..., 'n' */
    int    N;            /* Size of sieve and loop bounds */
    int    prime;        /* Current prime */
    int    threadnum;    /* Number of threads, only for parallelized code */

    if (argc != 3) {
        printf ("Command line: %s <threadnum> <n>\n", argv[0]);
        exit (1);
    }
    threadnum = atoi(argv[1]);
    n = atoi(argv[2]);
    N = n+1;

    marked = (char *) malloc (N);  //alocate slots for numbers in range [0,n]
    if (marked == NULL) {
        printf ("Cannot allocate enough memory\n");
        exit (1);
    }

    for (i = 0; i < N; i++) marked[i] = 1;
    marked[0] = 0;
    marked[1] = 0; // not primes
    index = 2;
    prime = 2;
    omp_set_num_threads(threadnum);
    do {
        first = 2 * prime;
#pragma omp parallel for
        for (i = first; i < N; i += prime) marked[i] = 0;
        while (!marked[++index]) ;
        prime = index;
    } while (prime * prime <= n);

    count = 0;
    for (i = 0; i < N; i++)
        count += marked[i];
    printf ("There are %d primes less than or equal to %d\n\n", count, n);
    return 0;
}

矩阵乘法

结果比较(临湖草堂)

mnp线程数时间(ms)speedup
10010010012.5461e-021.197e+00
10010010023.4905e-024.563e-01
10010010032.3823e-021.285e+00
10010010043.2910e-021.075e+00
10010010082.8407e-021.259e+00
10001000100012.6720e+001.064e+00
10001000100022.2224e+001.243e+00
10001000100032.0283e+001.333e+00
10001000100041.9699e+001.361e+00
10001000100081.8312e+001.515e+00

并附上1000*1000*1000规模4线程时,临湖草堂上的对比数据

reference serial impl.  : time_cost=2.6812e+00                  
reference parallel impl.: time_cost=1.9257e+00 speedup=1.392e+00
your impl.              : time_cost=1.9699e+00 speedup=1.361e+00 maximum error: 0.00

从表中可以看出,我所采用的大矩阵使用分块乘法,当并行运行时起到了一定的作用,对比参考的并行程序速度有小小的优势。

源代码

#include <stdio.h>
#include <stdlib.h>
#include "omp.h"

int m, p, n;
int threadnum;
double **matrix_c, **matrix_a, **matrix_b;

void init(double ** &matrix, int r, int c) {
    matrix = (double **) malloc(sizeof(double *) * r);
    matrix[0] = (double *) malloc(sizeof(double) * r * c);
    for (int i = 1; i < r; i++)
        matrix[i] = matrix[i - 1] + c;
}

void matrix_multiply(int upperOfRow , int bottomOfRow , int leftOfCol , int rightOfCol , int transLeft ,int transRight) {
    int i, j, k;
#pragma omp parallel for
    for (i = upperOfRow; i <= bottomOfRow; i++)
        for (j = leftOfCol; j <= rightOfCol; j++) {
            matrix_c[i][j] = 0;
            for (k = transLeft; k <=transRight ; k++)
                matrix_c[i][j] += matrix_a[i][k] * matrix_b[k][j];
        }
}

void large_matrix_multiply(int upperOfRow , int bottomOfRow , int leftOfCol , int rightOfCol , int transLeft ,int transRight ){
    if(bottomOfRow-upperOfRow<100 )
        matrix_multiply(upperOfRow , bottomOfRow , leftOfCol , rightOfCol, transLeft , transRight);
    else {
#pragma omp task
        {
            matrix_multiply(upperOfRow,(upperOfRow+bottomOfRow)/2,leftOfCol,(leftOfCol+rightOfCol)/2,transLeft,transRight);
        }
#pragma omp task
        {
            matrix_multiply(upperOfRow,(upperOfRow+bottomOfRow)/2,(leftOfCol+rightOfCol)/2+1,rightOfCol,transLeft,transRight);
        }
#pragma omp task
        {
            matrix_multiply((upperOfRow+bottomOfRow)/2+1,bottomOfRow,leftOfCol,(leftOfCol+rightOfCol)/2,transLeft,transRight);
        }
#pragma omp task
        {
            matrix_multiply((upperOfRow+bottomOfRow)/2+1,bottomOfRow,(leftOfCol+rightOfCol)/2+1,rightOfCol,transLeft,transRight);
        }
    }
}

int main(int argc, char* argv[]) {
    if (argc != 2)
        exit(1);
    threadnum = atoi(argv[1]);
    int i, j;
    scanf("%d%d%d", &m, &p, &n);
    init(matrix_a, m, p);
    init(matrix_b, p, n);
    init(matrix_c, m, n);
    for (i = 0; i < m; i++)
        for (j = 0; j < p; j++)
            scanf("%lf", &matrix_a[i][j]);
    for (i = 0; i < p; i++)
        for (j = 0; j < n; j++)
            scanf("%lf", &matrix_b[i][j]);
    omp_set_num_threads(threadnum);
    large_matrix_multiply(0,m-1,0,n-1,0,p-1);
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++)
            printf("%f ", matrix_c[i][j]);
        printf("\n");
    }
    return 0;
}

Calculate π

对比结果(本机8代酷睿i7-6核)

线程数时间(ms)线程数时间(ms)线程数时间(ms)
1126268350
441533629

对比结果(临湖草堂)

线程数时间线程数时间线程数时间线程数时间
14.6725e-0224.4431e-0233.4582e-0242.6790e-02

并附上4线程时,临湖草堂上的数据对比

reference serial impl.  : time_cost=9.2600e-02                   pi:3.141593
reference parallel impl.: time_cost=3.3666e-02 speedup=2.751e+00 pi:3.141593
your impl.              : time_cost=2.6790e-02 speedup=3.457e+00 pi:3.141593

从表中可以看出,使用并行计算PI值,能够有效的减少计算时间。且在本机上,计算时间与线程数大致成反比关系,可见加速算法的有效性。

源码

#include <stdio.h>
#include <omp.h>
static long num_steps = 10000000;
double step;
int main(int argc, char* argv[])
{
    int tnum;//thread number
    sscanf(argv[1], "%d", &tnum);

    omp_set_num_threads(tnum);
    int i;
    double x, pi, sum = 0.0;

    step = 1.0 / (double)num_steps;
#pragma omp parallel for reduction(+:sum) private(x)
    for (i = 1; i <= num_steps; i++) {
        x = (i - 0.5)*step;
        sum = sum + 4.0 / (1.0 + x * x);
    }

    pi = step * sum;
    printf("%f", pi);
}

使用OpenMP的心得或遇到的困难。

记录一下自己掉进的坑

  1. 首先遇到的困难是需要对编译器进行配置,而由于我习惯采用Mac端的CLion IDE,配置有一定复杂度,配置相关教程放到了[Mac 系统使用 CLion 进行 OpenMP 并行编程
    ](https://www.ruixiaolu.com/archives/51/)
  2. 在本地测试程序时,我一开始是使用的time.h中的clock()函数进行计时,但我发现,明明感觉到并行程序速度更快,但输出的时间不减反增,这使得我去搜索了其定义,发现计算的并不是真是时间。于是我才用time系统命令time ./FindPrime threads_num n来测量时间

心得与收获

  1. 首先最清楚的感受到,OpenMP的使用十分简单,简单的几个#pragma就可以实现程序的并行处理,使得程序员可以专注于代码逻辑与功能,而不必关系多线程的实现。
  2. 其次是感觉到OpenMP的并行处理确实能够加快大规模数据的计算速度,自己写的程序也终于可以利用处理器的多个核心了!
  3. 之后是感觉到OpenMP其实适合于小型业务,即单机处理业务,由于它适用于共享内存型的多处理器,所以如果要利用计算机集群进行告诉计算就不可以采用它进行编程了。
最后修改:2019 年 05 月 06 日 02 : 52 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论