Генерация той же случайной матрицы в OpenMP, чем последовательный код - PullRequest
Новая
       24

Генерация той же случайной матрицы в OpenMP, чем последовательный код

1 голос
/ 15 февраля 2020

Я хотел бы сгенерировать случайную матрицу с OpenMP, как если бы она была сгенерирована последовательной программой, то есть, если какой-либо генератор последовательных матриц выдает мне матрицу, подобную следующей: 

1.0 2.0 3.0 4.0
5.0 6.0 7.0 8.0
9.0 0.0 1.0 2.0
3.0 4.0 5.0 6.0

Я хочу параллельная версия OpenMP той же программы для генерации одной и той же матрицы без чередующихся строк .

Вот как я постепенно подошел к проблеме.

Учитывая мой сериал функция генератора C, генерирующая матрицу в виде одномерного массива: 

void generate_matrix_array(
    double *v,
    int rows,
    int columns,
    double min,
    double max,
    int seed
) {
    srand(seed);

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            v[i*rows + j] = min + (rand() / (RAND_MAX / (max - min)));
        }
    }
}

Сначала я наивно попробовал директиву #pragma omp parallel for для внешнего цикла for; тем не менее, нет никакой гарантии в отношении порядка строк, поскольку выполнение потоков чередуется, поэтому они генерируются в недетерминированном порядке c.

Добавление опции ordered решит проблему по цене создания бесполезная многопоточность в данном конкретном случае.

Чтобы решить эту проблему, я попытался разбить вручную матричный массив так, чтобы поток i генерировал i -й его фрагмент: 

void generate_matrix_array_par(
    double *v,
    int rows,
    int columns,
    double min,
    double max,
    int seed
) {
    srand(seed);

    #pragma omp parallel \
            shared(v)
    {
        int tid = omp_get_thread_num();
        int nthreads = omp_get_num_threads();
        int rows_per_thread = round(rows / (double) nthreads);
        int rem_rows = rows % (nthreads - 1) != 0?
            rows % (nthreads - 1):
            rows_per_thread;
        int local_rows = (tid == 0)?
            rows_per_thread:
            rem_rows;
        int lower_row = tid * local_rows;
        int upper_row = ((tid + 1) * local_rows);

        printf(
            "[T%d] receiving %d of %d rows from row %d to %d\n",
            tid,
            local_rows,
            rows,
            lower_row,
            upper_row - 1
        );
        printf("\n");
        fflush(stdout);

        for (int i = lower_row; i < upper_row; i++) {
            for (int j = 0; j < columns; j++) {
                v[i*rows + j] = min + (rand() / (RAND_MAX / (max - min)));
            }
        }
    }
}

Однако, несмотря на то, что матричный вектор правильно разделен между потоками, по какой-то неизвестной мне причине каждый поток генерирует свои строки в матрицу за детерминированный порядок c, т.е. если я хочу сгенерировать матрицу 8x8 с 4 потоками, а поток 3 назначен строкам 4 и 5, он будет генерировать две смежные строки в матричном массиве, но каждый раз в неправильной позиции, как если бы я не выполнял никакого разделения, и директива omp parallel for была на месте.

Я наконец скептически попытался вернуться к наивному подходу b y указав shared(v) и schedule(static, 16) опции для директивы omp parallel for, и это «волшебным образом» работает: 

void generate_matrix_array_par(
    double *v,
    int rows,
    int columns,
    double min,
    double max,
    int seed
) {
    srand(seed);

    int nthreads = omp_get_max_threads();
    int chunk_size = (rows * columns) / nthreads;

    #pragma omp parallel for \
            shared(v) \
            schedule(static, chunk_size)
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            v[i*rows + j] = min + (rand() / (RAND_MAX / (max - min)));
        }
    }
}

Опция schedule добавляется, так как я читаю где-то еще что он избавляется от конфликтов кэша. Редактировать: Похоже, schedule разбивает данные на потоки в циклическом порядке в соответствии с заданным размером чанка; поэтому, если я поделюсь потоками размером N / nthreads между потоками, данные будут назначены за один раунд.

Есть вопросы? ДА !!!

Теперь я хотел бы знать, пропустил ли я какое-то соображение по поводу проблемы, или не смог, поскольку я не убежден в справедливости моей последней версии программы, несмотря на то, что это работает.

...