Блог

Главная - Вопросы по программированию - Параллельный omp с большим массивом

Параллельный omp с большим массивом

#c #arrays #algorithm #search #openmp

#c #массивы #алгоритм #Поиск #openmp

Вопрос:

Я пытаюсь оптимизировать поиск в массиве, чтобы создать максимально быстрый алгоритм с помощью omp. Прямо сейчас это занимает слишком много времени (около 5-10 минут на 4 ядрах, 8 потоков linux)

У меня есть большой 2D массив комбинаций, в котором хранится комбинация и ее идентификатор (не связанный с индексом массивов).

В этом массиве мне нужно найти комбинации, которые имеют одинаковое значение, но другой идентификатор.

Размер массива или комбинаций, combinationsSize, может варьироваться от 600 000 до 3 000 000. Однако идентификаторы находятся в диапазоне от 0 до 500.

итак, я попробовал следующее. Он работает довольно прилично с размером ниже 90 КБ (около 5 секунд), но большие массивы занимают целую вечность.

 #pragma omp parallel for schedule(dynamic)
for(unsigned int i=0; i<combinationsSize; i  )
{
    for(unsigned int j=i 1; j<combinationsSize; j  )
    {   
        // if different ids
        if(combinations[i][1] != combinations[j][1])
        {
            // if the same combination
            if(combinations[i][0] == combinations[j][0])
            {
               // omp critical add to another array
            }
        } 
     } 
  }

У меня также есть возможность хранить комбинации в 3D-массиве, где
они хранятся в порядке идентификатора, но 2-й член может иметь любой размер, в зависимости от того, сколько у него комбинаций.
Однако это также приводит к длительным вычислениям (я предполагаю, из-за кэша) вот код:

     for(int id1=0; id1<maxIDs; id1  )
    { 
        #pragma omp parallel for schedule(dynamic,1)
        for(unsigned int i=0; i<idSizes[id1]; i  )
        {  
            for(int id2=id1 1; id2<maxIDs; id2  )
            {   
                for(unsigned int j=0; j<idSizes[id2]; j  )
                {
                    if(combinations[id1][i][0] == combinations[id2][j][0])
                    {
                        //omp critical add to another array
                    }
                }
             }
        }
  }

idSizes = — это массив, в котором хранится размер каждой из комбинаций идентификаторов в 3D-массиве

Максимальные значения = 500

Я перепробовал много разных подходов (логических, а также проб и ошибок) параллельного for, динамического расписания и т. Д. безрезультатно.

Просто перефразирую: моя цель — оптимизировать этот поиск в массиве, чтобы он мог выполнить задачу за считанные секунды, если это возможно. Он хранится в 2D и 3D массивах, поскольку с ними поступает другая информация, однако это не имеет значения в рамках этого вопроса.

РЕДАКТИРОВАТЬ, извините, я должен был упомянуть об этом: что касается критических значений, у меня есть критическое значение omp { добавьте эти идентификаторы и комбинации в массив}, мне это нужно.

Комментарии:

1. number вводит очень проблематичную зависимость. вы можете улучшить его, присвоив каждому заданию свой собственный счетчик (объявив number его как omp private и записывая num[i]=number; , когда каждое задание выходит j из цикла), и выполнить окончательную сумму num[] , когда openmp выходит i из цикла.

2. @user3528438, и это именно то, что reduction( :number) делает.

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

4. В идеале вы должны записать это в форме, подходящей для внутреннего цикла simd vector и параллельного внешнего цикла omp, возможно, в зависимости от вашего выбора компилятора.

5. Устранение критического из внутреннего цикла было бы первоочередной задачей; тогда вам понадобится векторизованный внутренний цикл, даже если вы не используете параллельный omp.