从数据专用性解决，Openmp并发变慢的问题

作者: sea_monster | 来源:发表于2020-06-10 10:03 被阅读0次

从数据专用性解决，Openmp并发变慢的问题
IOS 数据源同步问题方案
GC - 并发的可达性分析
2018-07-09
mysql数据批量同步导入elasticsearch
Mvcc 学习笔记
java并发编程要点
java并发问题如何处理
MySQL锁：页锁、共享锁、行锁、表锁、悲观锁、乐观锁
阿里面试：蚂蚁金服/饿了么/淘宝三面技术面年末整理（附面试题和答

从数据专用性解决，Openmp并发变慢的问题

题目如下

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

void Usage(char prog_name[]);

void Get_args(
    char*    argv[]        /* in  */,
    long*     bin_count_p   /* out */,
    float*   min_meas_p    /* out */,
    float*   max_meas_p    /* out */,
    long*     data_count_p  /* out */);

void Gen_data(
    float   min_meas    /* in  */, 
    float   max_meas    /* in  */, 
    float   data[]      /* out */,
    long     data_count  /* in  */);

void Gen_bins(
    float min_meas      /* in  */, 
    float max_meas      /* in  */, 
    float bin_maxes[]   /* out */, 
    long   bin_counts[]  /* out */, 
    long   bin_count     /* in  */);

long Which_bin(
    float    data         /* in */, 
    float    bin_maxes[]  /* in */, 
    long      bin_count    /* in */, 
    float    min_meas     /* in */);

void Print_histo(
    float    bin_maxes[]   /* in */, 
    long      bin_counts[]  /* in */, 
    long      bin_count     /* in */, 
    float    min_meas      /* in */);

//////////////////////////////////////////////////////////////////////
    
//请修改该函数
int main(int argc, char* argv[]) 
{
    long bin_count, i, bin;
    float min_meas, max_meas;
    float* bin_maxes;
    long* bin_counts;
    long data_count;
    float* data;

    struct timeval begin_time, end_time;
    double run_time_ms;

    /* Check and get command line args */
    if (argc != 5) Usage(argv[0]); 
    Get_args(argv, &bin_count, &min_meas, &max_meas, &data_count);

    /* Allocate arrays needed */
    bin_maxes = malloc(bin_count*sizeof(float));
    bin_counts = malloc(bin_count*sizeof(long));
    data = malloc(data_count*sizeof(float));

    /* Generate the data */
    Gen_data(min_meas, max_meas, data, data_count);

    /* Create bins for storing counts */
    Gen_bins(min_meas, max_meas, bin_maxes, bin_counts, bin_count);

    gettimeofday(&begin_time, NULL);

    /*
        请将下面这个for循环用OpenMP并行化
        要求及注意事项：
            1）程序的命令行（即main函数）在最后面增加一个参数thread_count，表示线程数量；
            2）先用./histogram 10 0 1 200000000测试单线程的运行时间，然后分别以10 0 1 200000000 2和10 0 1 200000000 4作为参数进行测试；
            3）Which_bin函数参数的意义见函数实现处的说明。
    */
    /* Count number of values in each bin */
    for (i = 0; i < data_count; i++) {
        bin = Which_bin(data[i], bin_maxes, bin_count, min_meas);
        bin_counts[bin]++;
    }
   
    gettimeofday(&end_time, NULL);
    run_time_ms =
        (end_time.tv_sec - begin_time.tv_sec)*1000 +
        (end_time.tv_usec - begin_time.tv_usec)*1.0/1000;
    printf("run_time = %lfms\n", run_time_ms);

    /* Print the histogram */
    Print_histo(bin_maxes, bin_counts, bin_count, min_meas);

    free(data);
    free(bin_maxes);
    free(bin_counts);
    return 0;
}  /* main */

//请修改该函数
void Usage(char prog_name[] /* in */) 
{
    fprintf(stderr, "usage: %s ", prog_name); 
    fprintf(stderr, "<bin_count> <min_meas> <max_meas> <data_count>\n");
    exit(0);
}  /* Usage */

//请修改该函数
void Get_args(
    char*    argv[]        /* in  */,
    long*     bin_count_p   /* out */,
    float*   min_meas_p    /* out */,
    float*   max_meas_p    /* out */,
    long*     data_count_p  /* out */) 
{
    *bin_count_p = strtol(argv[1], NULL, 10);
    *min_meas_p = strtof(argv[2], NULL);
    *max_meas_p = strtof(argv[3], NULL);
    *data_count_p = strtol(argv[4], NULL, 10);
}  /* Get_args */


void Gen_data(
        float   min_meas    /* in  */, 
        float   max_meas    /* in  */, 
        float   data[]      /* out */,
        long     data_count  /* in  */) 
{
    long i;
    srandom(0);
    for (i = 0; i < data_count; i++)
        data[i] = min_meas + (max_meas - min_meas)*random()/((double) RAND_MAX);
}  /* Gen_data */


void Gen_bins(
      float min_meas      /* in  */, 
      float max_meas      /* in  */, 
      float bin_maxes[]   /* out */, 
      long   bin_counts[]  /* out */, 
      long   bin_count     /* in  */) 
{
    float bin_width;
    long   i;

    bin_width = (max_meas - min_meas)/bin_count;

    for (i = 0; i < bin_count; i++) {
        bin_maxes[i] = min_meas + (i+1)*bin_width;
        bin_counts[i] = 0;
    }
}  /* Gen_bins */

/*---------------------------------------------------------------------
 * Function:  Which_bin
 * Purpose:   Use binary search to determine which bin a measurement 
 *            belongs to
 * In args:   data:       the current measurement,              数据
 *            bin_maxes:  list of max bin values,               每个bin的上边界
 *            bin_count:  number of bins,                       bin的数量
 *            min_meas:   the minimum possible measurement,     数据的最小值
 * Return:    the number of the bin to which data belongs,      bin的编号
 * Notes:      
 * 1.  The bin to which data belongs satisfies
 *
 *            bin_maxes[i-1] <= data < bin_maxes[i] 
 *
 *     where, bin_maxes[-1] = min_meas
 * 2.  If the search fails, the function prlongs a message and exits
 */
long Which_bin(
      float   data          /* in */, 
      float   bin_maxes[]   /* in */, 
      long     bin_count     /* in */, 
      float   min_meas      /* in */) 
{
   long bottom = 0, top =  bin_count-1;
   long mid;
   float bin_max, bin_min;

   while (bottom <= top) {
      mid = (bottom + top)/2;
      bin_max = bin_maxes[mid];
      bin_min = (mid == 0) ? min_meas: bin_maxes[mid-1];
      if (data >= bin_max) 
         bottom = mid+1;
      else if (data < bin_min)
         top = mid-1;
      else
         return mid;
   }
   
   return top;    //bug? added by XiongZhi

   /* Whoops! */
    printf("bottom = %ld, top = %ld\n", bottom, top);
    fprintf(stderr, "Data = %f doesn't belong to a bin!\n", data);
    fprintf(stderr, "Quitting\n");
    exit(-1);
}  /* Which_bin */


void Print_histo(
        float  bin_maxes[]   /* in */, 
        long    bin_counts[]  /* in */, 
        long    bin_count     /* in */, 
        float  min_meas      /* in */) 
{
    long i, j;
    float bin_max, bin_min;

    for (i = 0; i < bin_count; i++) {
        bin_max = bin_maxes[i];
        bin_min = (i == 0) ? min_meas: bin_maxes[i-1];
        printf("%.3f-%.3f:\t", bin_min, bin_max);
        //for (j = 0; j < bin_counts[i]; j++)
            // printf("X");
        printf("%ld", bin_counts[i]);  //altered by XiongZhi
        printf("\n");
   }
}  /* Print_histo */

解决方案

主要代码详解
1）c_bin_counts二维数组初始化，大小为(NUM_THREADS, bin_count); 主要用于分别保存不同线程各自的计算结果，实现各个线程间的数据专用性。

image.png
2）主要代码详解：

image.png

感想：
之前学习openmp并发，一直弄不懂的问题，在本次实验中学会了。一开始使用openmp就是直接使用#pragma omp for schedule(dynamic, 10000)直接进行加速，但是一直不明白哪里出了问题。随后根据数据的专用性，使用临时的动态数组以及为每一个线程分配一个独立的数组，大大减少大家同时访问一块内存的可能性，大大加速了代码。本次实验加深了对openmp的理解，也充分的了解到了openmp的缺陷和易用性。

但本代码存在部分缺陷，有待有心人解决。

源代码

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <omp.h>
#include <string.h>
void Usage(char prog_name[]);
// g++ -o main main.cpp -fopenmp
void Get_args(
        char*    argv[]        /* in  */,
        long*     bin_count_p   /* out */,
        float*   min_meas_p    /* out */,
        float*   max_meas_p    /* out */,
        long*     data_count_p  /* out */,
        long*     thread_num   /* out */);

void Gen_data(
        float   min_meas    /* in  */,
        float   max_meas    /* in  */,
        float   data[]      /* out */,
        long     data_count  /* in  */);

void Gen_bins(
        float min_meas      /* in  */,
        float max_meas      /* in  */,
        float bin_maxes[]   /* out */,
        long   bin_counts[]  /* out */,
        long   bin_count     /* in  */);

long Which_bin(
        float    data         /* in */,
        float    bin_maxes[]  /* in */,
        long      bin_count    /* in */,
        float    min_meas     /* in */);

void Print_histo(
        float    bin_maxes[]   /* in */,
        long      bin_counts[]  /* in */,
        long      bin_count     /* in */,
        float    min_meas      /* in */);

//////////////////////////////////////////////////////////////////////

//请修改该函数
int main(int argc, char* argv[])
{
    long NUM_THREADS;
    long bin_count, i, bin;
    float min_meas, max_meas;
    float* bin_maxes;
    long* bin_counts;
    long data_count;
    float* data;
    long** c_bin_counts;
    struct timeval begin_time, end_time;
    double run_time_ms;

    /* Check and get command line args */
    if (argc != 6) Usage(argv[0]);
    Get_args(argv, &bin_count, &min_meas, &max_meas, &data_count, &NUM_THREADS);
    /* Allocate arrays needed */
    bin_maxes =(float*)malloc(bin_count*sizeof(float));
    bin_counts = (long*)malloc(bin_count*sizeof(long));
    data = (float*)malloc(data_count*sizeof(float));
    c_bin_counts = (long**)malloc(NUM_THREADS*sizeof(long));

    for(int k=0; k<NUM_THREADS; ++k){
        c_bin_counts[k] = (long*)malloc(bin_count*sizeof(long));
        memset(c_bin_counts[k], 0, sizeof(long)*bin_count);
    }
    /* Generate the data */
    Gen_data(min_meas, max_meas, data, data_count);

    /* Create bins for storing counts */
    Gen_bins(min_meas, max_meas, bin_maxes, bin_counts, bin_count);


    gettimeofday(&begin_time, NULL);

    /*
        请将下面这个for循环用OpenMP并行化
        要求及注意事项：
            1）程序的命令行（即main函数）在最后面增加一个参数thread_count，表示线程数量；
            2）先用./histogram 10 0 1 200000000 测试单线程的运行时间，然后分别以10 0 1 200000000 2和10 0 1 200000000 4作为参数进行测试；
            3）Which_bin函数参数的意义见函数实现处的说明。
    */
    /* Count number of values in each bin */

    omp_set_num_threads(NUM_THREADS);
    int rank;
#pragma omp parallel private(i, bin, rank) shared(c_bin_counts)
    {
        rank = -1;
        long* a;
#pragma omp for  schedule(guided)
        for(int i=0; i<data_count; ++i){
            bin = Which_bin(data[i], bin_maxes, bin_count, min_meas);
            if(rank==-1){
                rank = omp_get_thread_num();
                a = (long*)malloc(bin_count*sizeof(long));
                memset(a, 0, sizeof(long)*bin_count);
            }
            a[bin] += 1;
        }
        for(int k=0; k<bin_count; ++k){
            c_bin_counts[rank][k] += a[k];
        }
        free(a);
    }
    for (int k = 0; k < NUM_THREADS; ++k) {
        for (int j = 0; j < bin_count; ++j) {
            bin_counts[j] += c_bin_counts[k][j];
        }
    }
    
    gettimeofday(&end_time, NULL);
    run_time_ms =
            (end_time.tv_sec - begin_time.tv_sec)*1000 +
            (end_time.tv_usec - begin_time.tv_usec)*1.0/1000;
    printf("run_time = %lfms\n", run_time_ms);

    /* Print the histogram */
    Print_histo(bin_maxes, bin_counts, bin_count, min_meas);
    
    for(int k=0; k<NUM_THREADS; ++k){
        free(c_bin_counts[k]);
    }
    free(c_bin_counts);
    free(data);
    free(bin_maxes);
    free(bin_counts);
    return 0;
}  /* main */

//请修改该函数
void Usage(char prog_name[] /* in */)
{
    fprintf(stderr, "usage: %s ", prog_name);
    fprintf(stderr, "<bin_count> <min_meas> <max_meas> <data_count> <thread_num>\n");
    exit(0);
}  /* Usage */

//请修改该函数
void Get_args(
        char*    argv[]        /* in  */,
        long*     bin_count_p   /* out */,
        float*   min_meas_p    /* out */,
        float*   max_meas_p    /* out */,
        long*     data_count_p  /* out */,
        long*     thread_num  /* out */)
{
    *bin_count_p = strtol(argv[1], NULL, 10);
    *min_meas_p = strtof(argv[2], NULL);
    *max_meas_p = strtof(argv[3], NULL);
    *data_count_p = strtol(argv[4], NULL, 10);
    *thread_num = strtol(argv[5], NULL, 10);
}  /* Get_args */


void Gen_data(
        float   min_meas    /* in  */,
        float   max_meas    /* in  */,
        float   data[]      /* out */,
        long     data_count  /* in  */)
{
    long i;
    srand(0);
    for (i = 0; i < data_count; i++)
        data[i] = min_meas + (max_meas - min_meas)*rand()/((double) RAND_MAX);
}  /* Gen_data */


void Gen_bins(
        float min_meas      /* in  */,
        float max_meas      /* in  */,
        float bin_maxes[]   /* out */,
        long   bin_counts[]  /* out */,
        long   bin_count     /* in  */)
{
    float bin_width;
    long   i;

    bin_width = (max_meas - min_meas)/bin_count;

    for (i = 0; i < bin_count; i++) {
        bin_maxes[i] = min_meas + (i+1)*bin_width;
        bin_counts[i] = 0;
    }
}  /* Gen_bins */

/*---------------------------------------------------------------------
 * Function:  Which_bin
 * Purpose:   Use binary search to determine which bin a measurement
 *            belongs to
 * In args:   data:       the current measurement,              数据
 *            bin_maxes:  list of max bin values,               每个bin的上边界
 *            bin_count:  number of bins,                       bin的数量
 *            min_meas:   the minimum possible measurement,     数据的最小值
 * Return:    the number of the bin to which data belongs,      bin的编号
 * Notes:
 * 1.  The bin to which data belongs satisfies
 *
 *            bin_maxes[i-1] <= data < bin_maxes[i]
 *
 *     where, bin_maxes[-1] = min_meas
 * 2.  If the search fails, the function prlongs a message and exits
 */
long Which_bin(
        float   data          /* in */,
        float   bin_maxes[]   /* in */,
        long     bin_count     /* in */,
        float   min_meas      /* in */)
{
    long bottom = 0, top =  bin_count-1;
    long mid;
    float bin_max, bin_min;

    while (bottom <= top) {
        mid = (bottom + top)/2;
        bin_max = bin_maxes[mid];
        bin_min = (mid == 0) ? min_meas: bin_maxes[mid-1];
        if (data >= bin_max)
            bottom = mid+1;
        else if (data < bin_min)
            top = mid-1;
        else
            return mid;
    }

    return top;    //bug? added by XiongZhi

    /* Whoops! */
    printf("bottom = %ld, top = %ld\n", bottom, top);
    fprintf(stderr, "Data = %f doesn't belong to a bin!\n", data);
    fprintf(stderr, "Quitting\n");
    exit(-1);
}  /* Which_bin */


void Print_histo(
        float  bin_maxes[]   /* in */,
        long    bin_counts[]  /* in */,
        long    bin_count     /* in */,
        float  min_meas      /* in */)
{
    long i, j;
    float bin_max, bin_min;

    for (i = 0; i < bin_count; i++) {
        bin_max = bin_maxes[i];
        bin_min = (i == 0) ? min_meas: bin_maxes[i-1];
        printf("%.3f-%.3f:\t", bin_min, bin_max);
        //for (j = 0; j < bin_counts[i]; j++)
        // printf("X");
        printf("%ld", bin_counts[i]);  //altered by XiongZhi
        printf("\n");
    }
}  /* Print_histo */

从数据专用性解决，Openmp并发变慢的问题
从数据专用性解决，Openmp并发变慢的问题题目如下解决方案主要代码详解1）c_bin_counts二维数组...
IOS 数据源同步问题方案
目的解决UI刷新错乱的问题解决方案 1.并发访问数据拷贝 2.串行访问并发访问数据拷贝也就是说数据拷...
GC - 并发的可达性分析
并发的可达性分析 CMS和G1都有一个并发标记的过程，并发标记要解决什么问题？带来了什么问题？怎么解决这些问题呢？...
2018-07-09
乐观锁 VS 悲观锁 1、锁是为了解决，并发（同时修改数据）的问题；2、事务是为了保证数据的原子性（要么都成功要么...
mysql数据批量同步导入elasticsearch
背景：对于数据的列表拉取响应变慢，数据需要从mysql迁移到es，从而数据从es进行读取；解决思路：由于数据...
Mvcc 学习笔记
MVCC 笔记 MVCC为了解决什么问题？多版本并发控制，针对在并发访问数据库时对于数据版本的控制以及隔离性问题...
java并发编程要点
Java并发问题主要有三个核心概念：原子性，可见性，顺序性。原子性并发问题的原子性的概念和数据库事务的原子性是...
java并发问题如何处理
java并发问题如何处理如何解决并发带来的脏数据问题？ 1、使用synchronized来起到同步加锁的作用，首...
MySQL锁：页锁、共享锁、行锁、表锁、悲观锁、乐观锁
我们在操作数据库的时候，可能会由于并发问题而引起的数据的不一致性（数据冲突），如何保证数据并发访问的一致性、有效性...
阿里面试：蚂蚁金服/饿了么/淘宝三面技术面年末整理（附面试题和答
我们在操作数据库的时候，可能会由于并发问题而引起的数据的不一致性（数据冲突）。如何保证数据并发访问的一致性、有效性...