Encontrar elemento mínimo en matriz, y su índice de

Question

Con OpenMP 3.1, es posible tener una cláusula reduction con min:

double m; 
#pragma omp parallel for reduction(min:m) 
for (int i=0;i< n; i++){ 
    if (a[i]*2 < m) { 
    m = a[i] * 2; 
} 
return m; 

Supongamos que también necesitan la índice del elemento mínimo; ¿Hay alguna manera de usar la cláusula reduction para esto? Creo que la alternativa es escribir la reducción manualmente usando nowait y critical.

Answer 1

Supongamos que también necesito el índice del elemento mínimo; ¿Hay alguna manera de usar la cláusula de reducción para esto?

Lamentablemente, no. la lista de posibles reducciones en OpenMP es muy ... pequeña. En particular, min y max son las únicas funciones de "nivel superior" y no son personalizables. En absoluto.

Tengo que admitir que no me gusta el enfoque de las reducciones de OpenMP, precisamente porque no es extensible en lo más mínimo, es diseñado solo para trabajar en casos especiales. De acuerdo, esos son casos especiales interesantes pero aún así es fundamentalmente un mal enfoque.

Para tales operaciones, debe implementar la reducción usted mismo al acumular resultados locales de subprocesos en variables locales de subprocesos y combinarlos al final.

La manera más fácil de hacer esto (y de hecho bastante cerca de cómo OpenMP implementa reducciones) es tener una matriz con elementos para cada hilo, y usar omp_get_thread_num() para acceder a un elemento. Sin embargo, tenga en cuenta que esto provocará una degradación del rendimiento debido a la compartición falsa si los elementos en la matriz comparten una línea de caché. Para mitigar esto, rellene la matriz:

struct min_element_t { 
    double min_val; 
    size_t min_index; 
}; 

size_t const CACHE_LINE_SIZE = 1024; // for example. 
std::vector<min_element_t> mins(threadnum * CACHE_LINE_SIZE); 

#pragma omp parallel for 
for (int i = 0; i < n; ++i) { 
    size_t const index = omp_get_thread_num() * CACHE_LINE_SIZE; 
    // operate on mins[index] … 
}