Вставка сортировки с openmp

Question

Я искал в Интернете, но не мог найти много о.

Мой код:

#include <stdio.h> 

void insertionsort(int vector[], int tam){ 
    int i, j, tmp; 
    for(i = 1; i < tam; i++){ 
     j = i; 
     while(j > 0 && vector[j-1] > vector[j]){ 
      tmp = vector[j]; 
      vector[j] = vector[j-1]; 
      vector[j-1] = tmp; 
      j--; 
     } 
    } 
} 

как распараллелить вставки рода с OpenMP?

Answer 1

Я не вижу возможности распараллеливать этот алгоритм.

Обратите внимание, что инвариант первого цикла состоит в том, что vector уже отсортирован с [0..i-1]. Вы не можете запускать первый цикл параллельно, в основном потому, что каждая итерация зависит от предыдущей, кроме первой.

О вложенном цикле while: алгоритм сдвигает вправо элементы, значения которых больше vector[i]. Я не уверен, как распараллелить его или если он достоин, но у меня есть сильное чувство, что я буду сложным: вам нужно будет изменить свой код и использовать больше памяти, чтобы избежать расследований данных. Что касается ракурсов данных: обратите внимание, что если мы будем запускать все итерации от j=[1..i] параллельно, некоторый элемент может быть прочитан и написан в одно и то же время, поэтому нам нужно позаботиться об этом. Кроме того, эта реализация, вероятно, будет иметь несбалансированную нагрузку.

Связанный вопрос: Insertion Sort in OpenMP