Распараллеливание шага слияния и шага разделения в алгоритме слияния с OpenMP

От: Из: Общие

Мы написали код, который распараллеливает фазу разделения алгоритма сортировки слиянием. Т.е. каждый рекурсивный вызов назначается потоку, но наш учитель был разочарован, потому что он сказал, что мы также должны распараллелить функцию слияния. Я исследовал, как это можно сделать, и нашел их (алгоритм 3) конспект лекций который изменяет сложность функции слияния с O (n) на O (n (log (n)), но которую теперь можно распараллелить. Я хотел спросить предложения, как разработать код для максимально быстрого результата:

(оба должны скомпилироваться с g ++ / могут быть некоторые предупреждения, если используется педантичный флаг, но поскольку оба дают правильный результат, их можно игнорировать)

Старый код:

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/time.h>

#include <iostream>
#include <algorithm>

#include <cstdlib>
#include <cstdio>

#include <cmath>
#include <ctime>
#include <cstring>
#include <omp.h>
// Constants.h
#if !defined(MYLIB_CONSTANTS_H)
#define MYLIB_CONSTANTS_H 1

const int CUTOFF =11;

#endif


/**
  * helper routine: check if array is sorted correctly
  */
bool isSorted(int ref[], int data[], const size_t size){
    std::sort(ref, ref + size);
    for (size_t idx = 0; idx < size; ++idx){
        if (ref[idx] != data[idx]) {
            return false;
        }
    }
    return true;
}

/**
  * sequential merge step (straight-forward implementation)
  */
void MsMergeSequential(int *out, int *in, long begin1, long end1, long begin2, long end2, long outBegin) {
    long left = begin1;
    long right = begin2;
    long idx = outBegin;
    
    while (left < end1 && right < end2) {
        if (in[left] <= in[right]) {
            out[idx] = in[left];    
            left++;
        } else {
            out[idx] = in[right];
            right++;
        }
        idx++;
        }
    
    while (left < end1) {
        out[idx] = in[left];
        left++, idx++;
    }
    while (right < end2) {
        out[idx] = in[right];
        right++, idx++;
    }
}
bool myfunc (long i , long j){return (i<j);}
/**
  * sequential MergeSort
  */
void MsSequential(int *array, int *tmp, bool inplace, long begin, long end) {
  if( end <= begin + CUTOFF -1){

    std::sort(array+begin,array + end, myfunc);
  }
  else  if (begin < (end - 1)) {
           long half =(begin+end) / 2;


            #pragma omp taskgroup
         {
           #pragma omp task shared(array) untied if(end-begin >= (1<<15))

             MsSequential(array, tmp, !inplace, begin, half);

             MsSequential(array, tmp, !inplace, half, end);
              }
 if (inplace){
            MsMergeSequential(array, tmp, begin, half, half, end, begin);
 } else {
            MsMergeSequential(tmp, array, begin, half, half, end, begin);
 }
        
    } else if (!inplace) {

        tmp[begin] = array[begin];
    }
}

/**
  * Serial MergeSort
  */
void MsSerial(int *array, int *tmp, const size_t size) {

    MsSequential(array, tmp, true, 0, size);
}

/**

/**
  * @brief program entry point
  */
int main(int argc, char* argv[]) {
    // variables to measure the elapsed time
    struct timeval t1, t2;
    double etime;

    // expect one command line arguments: array size
    if (argc != 2) {
        printf("Usage: MergeSort.exe <array size> n");
        printf("n");
        return EXIT_FAILURE;
    }
    else {
        const size_t stSize = strtol(argv[1], NULL, 10);
        int *data = (int*) malloc(stSize * sizeof(int));
        int *tmp = (int*) malloc(stSize * sizeof(int));     
        int *ref = (int*) malloc(stSize * sizeof(int));
        printf("Initialization...n");

        srand(95);

        #pragma omp parallel for num_threads(100) schedule(static)
        for (size_t idx = 0; idx < stSize; ++idx){
            data[idx] = (int) (stSize * (double(rand()) / RAND_MAX));
        }
        std::copy(data, data + stSize, ref);

        double dSize = (stSize * sizeof(int)) / 1024 / 1024;
        printf("Sorting %zu elements of type int (%f MiB)...n", stSize, dSize);

        gettimeofday(&t1, NULL);
        #pragma omp parallel num_threads(80) 
        {
        #pragma omp single
        {
        MsSerial(data, tmp, stSize);
        }
        }
        gettimeofday(&t2, NULL);
        etime = (t2.tv_sec - t1.tv_sec) * 1000 + (t2.tv_usec - t1.tv_usec) / 1000;
        etime = etime / 1000;

        printf("done, took %f sec. Verification...", etime);
        if (isSorted(ref, data, stSize)) {
            printf(" successful.n");
        }
        else {
            printf(" FAILED.n");
        }

        free(data);
        //delete[] data;
        free(tmp);
        //delete[] tmp;
        free(ref);
        //delete[] ref;
    }

    return EXIT_SUCCESS;
}

Новый код — слияние можно распараллеливать:

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/time.h>

#include <iostream>
#include <algorithm>

#include <cstdlib>
#include <cstdio>

#include <cmath>
#include <ctime>
#include <cstring>
#include <omp.h>
// Constants.h
#if !defined(MYLIB_CONSTANTS_H)
#define MYLIB_CONSTANTS_H 1



#endif


//Takes a sorted list of size n and a value, puts the value in one of n+1 possible positions,
//if value is same to an element of the list take the position before the first occurence of the same element

int binarysearchfindlowerrank(int *in,int n,int value,int projection){

    int* array= in+projection;
    int L=0;
    int R=n;
    while(R-L>1){
        int middle = (R+L)/2;
        if(array[middle]==value){
            while(array[middle]==value&&middle>0){
                middle=middle-1;
            }
            if(middle==0&&array[middle]>=value){
                return 0;
            }
            else{
            return middle+1;
            }
        }
        if(array[middle]<value){
            L=middle;
        }
        if(array[middle]>value){
            R=middle;
        }
    }
    if(n==1){
        if(array[0]>=value){
            return 0;
        }
        else return 1;
    }
    if(L==0&&array[L]>value){
        return 0;
    }
    if(R==n && array[R-1]< value){
        return n;
    }
    if(R==n&& array[R-1]>=value){
        return R-1;
    }
    if(array[R]<value){
        return R+1;
    }
    if(array[L]<value){
        return R;
    }
    return L;
}


//Takes a sorted list of size n and a value, puts the value in one of n+1 possible positions,
//if value is same to an element of the list take the position after the last occurence of the same element


int binarysearchfinduperrank(int *in,int n,int value, int projection){

    int* array= in+projection;
    int L=0;
    int R=n;
    while(R-L>1){
        int middle = (R+L)/2;
        if(array[middle]==value){
            while(array[middle]==value&&middle<n){
                middle=middle+1;
            }
            return middle;
        }
        if(array[middle]<value){
            L=middle;
        }
        if(array[middle]>value){
            R=middle;
        }
    }
     if(n==1){
         if(array[0]> value){
             return 0;
        }
        else{
            return 1;
        }
    }
    if(L==0&&array[L]>value){
        return 0;
    }
    if(R==n && array[R-1]<= value){
        return n;
    }
    if(R==n&& array[R-1]>value){
        return R-1;
    }
    if(array[R]<=value){
        return R+1;
    }
    if(array[L]<=value){
        return R;
    }
    return L;
}

/**
  * helper routine: check if array is sorted correctly
  */
bool isSorted(int ref[], int data[], const size_t size){
    std::sort(ref, ref + size);
    for (size_t idx = 0; idx < size; ++idx){
        if (ref[idx] != data[idx]) {
            printf("nFalscher Index:%dn",idx);
            return false;
        }
    }
    return true;
}

/**
  * sequential merge step (straight-forward implementation)
  */
void MsMergeParallelized(int *out, int *in, long begin1, long end1, long begin2, long end2, long outBegin,int *data,int *tmp) {
    if(begin1==end2){
        out[begin1]=in[begin1];
    }
    if(begin1==begin2||begin2==end2){
        out[begin1+binarysearchfinduperrank(in,1,in[end2],begin1)]=in[end2];
        out[begin1+binarysearchfindlowerrank(in,1,in[begin1],end2)]=in[begin1];
    }
    else{
        for(int i=0;i<(end2-begin2);i++){
            out[begin1+i+binarysearchfinduperrank(in,(end1-begin1),in[begin2+i],begin1)]=in[begin2+i];
        }
        for(int i=0;i<(end1-begin1);i++){
            out[begin1+i+binarysearchfindlowerrank(in,(end2-begin2),in[begin1+i],begin2)]=in[begin1+i];
        }
    }
}
bool myfunc (long i , long j){return (i<j);}
/**
  * sequential MergeSort
  */
void MsParallelized(int *array, int *tmp, bool inplace, long begin, long end) {
  if (begin < (end - 1)) {
        long half =(begin+end) / 2;
        MsParallelized(array, tmp, !inplace, begin, half);
        MsParallelized(array, tmp, !inplace, half, end);
        if (inplace){
            MsMergeParallelized(array, tmp, begin, half, half, end, begin,array,tmp);
        }
        else {
            MsMergeParallelized(tmp, array, begin, half, half, end, begin,array,tmp);
        }
    }
    else if (!inplace) {
        tmp[begin] = array[begin];
    }
}

/**
  * Serial MergeSort
  */
void MsParallel(int *array, int *tmp, const size_t size) {

    MsParallelized(array, tmp, true, 0, size);
}

/**

/**
  * @brief program entry point
  */
int main(int argc, char* argv[]) {
    // variables to measure the elapsed time
    struct timeval t1, t2;
    double etime;

    // expect one command line arguments: array size
    if (argc != 2) {
        printf("Usage: MergeSort.exe <array size> n");
        printf("n");
        return EXIT_FAILURE;
    }
    else {
        const size_t stSize = strtol(argv[1], NULL, 10);
        int *data = (int*) malloc(stSize * sizeof(int));
        int *tmp = (int*) malloc(stSize * sizeof(int));
        int *ref = (int*) malloc(stSize * sizeof(int));
        printf("Initialization...n");

        srand(95);


        for (size_t idx = 0; idx < stSize; ++idx){
            data[idx] = (int) (stSize * (double(rand()) / RAND_MAX));
        }
        std::copy(data, data + stSize, ref);
        double dSize = (stSize * sizeof(int)) / 1024 / 1024;
        printf("Sorting %u elements of type int (%f MiB)...n", stSize, dSize);
        gettimeofday(&t1, NULL);
        // Mergesort starts
        MsParallel(data, tmp, stSize);

        gettimeofday(&t2, NULL);
        etime = (t2.tv_sec - t1.tv_sec) * 1000 + (t2.tv_usec - t1.tv_usec) / 1000;
        etime = etime / 1000;
        printf("done, took %f sec. Verification...", etime);
        if (isSorted(ref, data, stSize)) {
            printf(" successful.n");
        }
        else {
            printf(" FAILED.n");
        }
        free(data);
        //delete[] data;
        free(tmp);
        //delete[] tmp;
        free(ref);
        //delete[] ref;
    }
    return EXIT_SUCCESS;
}

2 ответа
2

/**
  * helper routine: check if array is sorted correctly
  */
bool isSorted(int ref[], int data[], const size_t size){

Просмотрите стандартную библиотеку, чтобы ознакомиться со всем, что в ней содержится. В частности, посмотрите на сортировочные операции где вы найдете стандартный алгоритм is_sorted. Не реализуйте повторно содержимое стандартной библиотеки, которое не является частью упражнения!

Что касается вашей реализации …
В int ref[] синтаксис параметра фактически означает int*. Вам следует избегать синтаксиса искусственного массива. Но если серьезно, переданы два «массива», и они нет отмечен const?

Первая строка — это звонок std::sort ????
Итак, похоже, он хочет, чтобы вы сделали копию данных, передали обе копии, затем эта функция сортирует одну из копий и проверяет, совпадают ли теперь две копии (повторная реализация вручную std::equals).

Обычно верно, что вы можете проверить свою «модную» версию функции, сравнив результаты с «нормальной» версией. Но в этом случае гораздо проще проверить, отсортирован ли массив и что подразумевает имя функции.

int *data = (int*) malloc(stSize * sizeof(int));
int *tmp = (int*) malloc(stSize * sizeof(int));     
int *ref = (int*) malloc(stSize * sizeof(int));
printf("Initialization...n");

Почему вы используете malloc (и printf)?

data[idx] = (int) (stSize * (double(rand()) / RAND_MAX));

Можно было бы более снисходительно rand() поскольку нам здесь не нужна особо качественная случайность; но вы делаете всю работу по кондиционированию и явное приведение, чтобы получить случайный int. Используйте библиотеку случайных чисел C ++ и просто спросите у него случайные целые числа в желаемом диапазоне.

Обратите внимание, что C ++ имеет время библиотека тоже. Кажется, вы используете C, а не C ++, за исключением вызова std::sort и std::copy.

Другой призыв к sortПонятно, это:

bool myfunc (long i , long j){return (i<j);}
  ...
std::sort(array+begin,array + end, myfunc);

Переходя в myfunc замедляет его. Простое восхождение через < является значением по умолчанию, поэтому вам вообще не нужно его передавать. Но если бы вам действительно нужно было предоставить функцию сравнения, указатель на простую функцию деоптимизируется, потому что оптимизатор обычно не следует указателям на функции, даже если они известны во время компиляции. То есть призыв к myfunc не будет встроен.

Ваша функция занимает long когда вы сортируете int. Эта функция объявляет begin и end в виде long, скорее, чем size_t. Это как если бы вы склеили части из разных программ или забыли, какие типы вы использовали.

    изменяет сложность функции слияния с O (n) на O (n (log (n)), но теперь можно распараллелить

    Для слияния двух отсортированных прогонов размера n наихудший случай для каждого экземпляра двоичного поиска — ⌈log2 (n) ⌉ чтения, а для большего n (> = 256 или около того) это приведет к слиянию параллельного двоичного поиска. медленнее, чем обычное однопоточное слияние.

    Более быстрый подход для т потоки будут разбивать массив на т части и использование т потоков для независимой сортировки каждого из т части. Затем объедините четные и нечетные пары отсортированных прогонов, первое слияние с использованием т/ 2 потока, следующее слияние с использованием т/ 4 потока и, наконец, один поток для объединения двух отсортированных прогонов. Пример этого с использованием собственных потоков Windows показан в этом вопросе:

    Многопоточная сортировка слиянием снизу вверх

    • Размер целевого массива составляет от 10 ^ 7 до 10 ^ 8. Это означает, что можно добиться ускорения, если, например, объединить последний массив параллельно. У нас доступно 240 тем. журнал (10 ^ 8) <27. Фактически нам нужно выполнить только 27/240 10 ^ 8 = 1,125 10 ^ 7 операций вместо 10 ^ 8 операций. Таким образом, должно быть ускорение, если мы могли запускать параллельный код только на первых подмассивах.

      — New2Math

    • @ New2Math — какая система может одновременно запускать 240 потоков? Я думал, что это настольный ПК. Максимум для них составляет от 16 до 18 ядер, с удвоенным количеством потоков с гиперпоточностью, но каждая пара гиперпотоков будет совместно использовать локальный кеш каждого ядра. Я предполагаю, что около 12 потоков на 12 ядрах процесс станет ограниченной пропускной способностью памяти, и в этом случае большее количество потоков не поможет.

      — rcgldr


    • мы используем узел hpc для университетского проекта

      — New2Math

    • @ New2Math — Даже с узлом hpc, я подозреваю, что программа станет связывать память и | или кеш-когерентность на уровне менее 240 потоков, поскольку все они записывают в один и тот же массив. Наихудший сценарий (бинарный поиск) — это, вероятно, случай, когда данные уже отсортированы или отсортированы обратным образом.

      — rcgldr


    Похожие записи:

    1. C ++ 20: я — матрица, вещание, np.dot () и np.matmul ()
    2. Решатель небоскребов для размера NxN, версия 4
    3. Программа для записи санации объекта
    4. Программы C и C ++, позволяющие увеличить время доступа к файлам
    5. Программа расчета небоскребов для размера NxN, версия 3 (с использованием битовых масок)

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *