parallel - Sin ganancia de rendimiento después de usar openMP en un programa optimiza para la ejecución secuencial

openmp tutorial

Question

He optimizado tanto como pude mi función para la ejecución secuencial. Cuando uso openMP no veo ganancia en el rendimiento. Probé mi programa en una máquina con 1 núcleo y en una máquina con 8 núcleos, y el rendimiento es el mismo.
Con el año establecido en 20, tengo
1 núcleo: 1 seg.
8 núcleos: 1 seg.

Con el año establecido en 25 tengo
1 núcleo: 40 seg.
8 núcleos: 40 seg.

1 máquina central: intel core 2 duo de mi laptop 1.8 GHz, ubuntu linux
Máquina de 8 núcleos: 3,25 GHz, Ubuntu Linux

Mi programa enumera toda la ruta posible de un árbol binomial y hace algo de trabajo en cada ruta. Así que mi tamaño de bucle aumenta exponencialmente y espero que la huella de hilo openMP sea cero. En mi ciclo, solo hago una reducción de una variable. Todas las otras variables son de solo lectura. Solo uso la función que escribí, y creo que son seguros para subprocesos.

También ejecuto Valgrind cachegrind en mi programa. No entiendo completamente el resultado, pero parece que no hay falta de caché o uso compartido falso.

Compilo con

gcc -O3 -g3 -Wall -c -fmessage-length=0 -lm -fopenmp -ffast-math

Mi programa completo es el siguiente. Lo siento por publicar un montón de código. No estoy familiarizado con openMP ni con C, y no pude reanudar mi código más sin perder la tarea principal.

¿Cómo puedo mejorar el rendimiento cuando uso openMP?
¿Son algunos indicadores del compilador o trucos de C que harán que el programa se ejecute más rápido?

test.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <omp.h>
#include "test.h"

int main(){

    printf("starting/n");
    int year=20;
    int tradingdate0=1;

    globalinit(year,tradingdate0);

    int i;
    float v=0;
    long n=pow(tradingdate0+1,year);
    #pragma omp parallel for reduction(+:v)
    for(i=0;i<n;i++)
        v+=pathvalue(i);

    globaldel();
    printf("finished/n");
    return 0;
}

//***function on which openMP is applied
float pathvalue(long pathindex) {
    float value = -ctx.firstpremium;
    float personalaccount = ctx.personalaccountat0;
    float account = ctx.firstpremium;
    int i;
    for (i = 0; i < ctx.year-1; i++) {
        value *= ctx.accumulationfactor;
        double index = getindex(i,pathindex);
        account = account * index;
        double death = fmaxf(account,ctx.guarantee[i]);
        value += qx(i) * death;
        if (haswithdraw(i)){
            double withdraw = personalaccount*ctx.allowed;
            value += px(i) * withdraw;
            personalaccount = fmaxf(personalaccount-withdraw,0);
            account = fmaxf(account-withdraw,0);
        }
    }

    //last year
    double index = getindex(ctx.year-1,pathindex);
    account = account * index;
    value+=fmaxf(account,ctx.guarantee[ctx.year-1]);

    return value * ctx.discountfactor;
}



int haswithdraw(int period){
    return 1;
}

float getindex(int period, long pathindex){
    int ndx = (pathindex/ctx.chunksize[period])%ctx.tradingdate;
    return ctx.stock[ndx];
}

float qx(int period){
    return 0;
}

float px(int period){
    return 1;
}

//****global
struct context ctx;

void globalinit(int year, int tradingdate0){
    ctx.year = year;
    ctx.tradingdate0 = tradingdate0;
    ctx.firstpremium = 1;
    ctx.riskfreerate = 0.06;
    ctx.volatility=0.25;
    ctx.personalaccountat0 = 1;
    ctx.allowed = 0.07;
    ctx.guaranteerate = 0.03;
    ctx.alpha=1;
    ctx.beta = 1;
    ctx.tradingdate=tradingdate0+1;
    ctx.discountfactor = exp(-ctx.riskfreerate * ctx.year);
    ctx.accumulationfactor = exp(ctx.riskfreerate);
    ctx.guaranteefactor = 1+ctx.guaranteerate;
    ctx.upmove=exp(ctx.volatility/sqrt(ctx.tradingdate0));
    ctx.downmove=1/ctx.upmove;

    ctx.stock=(float*)malloc(sizeof(float)*ctx.tradingdate);
    int i;
    for(i=0;i<ctx.tradingdate;i++)
        ctx.stock[i]=pow(ctx.upmove,ctx.tradingdate0-i)*pow(ctx.downmove,i);

    ctx.chunksize=(long*)malloc(sizeof(long)*ctx.year);
    for(i=0;i<year;i++)
        ctx.chunksize[i]=pow(ctx.tradingdate,ctx.year-i-1);

    ctx.guarantee=(float*)malloc(sizeof(float)*ctx.year);
    for(i=0;i<ctx.year;i++)
        ctx.guarantee[i]=ctx.beta*pow(ctx.guaranteefactor,i+1);
}

void globaldel(){
    free(ctx.stock);
    free(ctx.chunksize);
    free(ctx.guarantee);
}

test.h

float pathvalue(long pathindex);
int haswithdraw(int period);
float getindex(int period, long pathindex);
float qx(int period);
float px(int period);
//***global
struct context{
    int year;
    int tradingdate0;
    float firstpremium;
    float riskfreerate;
    float volatility;
    float personalaccountat0;
    float allowed;
    float guaranteerate;
    float alpha;
    float beta;
    int tradingdate;
    float discountfactor;
    float accumulationfactor;
    float guaranteefactor;
    float upmove;
    float downmove;
    float* stock;
    long* chunksize;
    float* guarantee;
};
struct context ctx;
void globalinit();
void globaldel();

EDITAR Simplifico todas las variables globales como constante. Durante 20 años, el programa se ejecuta dos veces más rápido (¡genial!). Intenté establecer el número de subprocesos con OMP_NUM_THREADS=4 ./test por ejemplo. Pero no me dio ninguna ganancia de rendimiento.
¿Puede mi gcc tener algún problema?

test.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <omp.h>
#include "test.h"


int main(){

    starttimer();
    printf("starting/n");
    int i;
    float v=0;

    #pragma omp parallel for reduction(+:v)
    for(i=0;i<numberofpath;i++)
        v+=pathvalue(i);

    printf("v:%f/nfinished/n",v);
    endtimer();
    return 0;
}

//function on which openMP is applied
float pathvalue(long pathindex) {
    float value = -firstpremium;
    float personalaccount = personalaccountat0;
    float account = firstpremium;
    int i;
    for (i = 0; i < year-1; i++) {
        value *= accumulationfactor;
        double index = getindex(i,pathindex);
        account = account * index;
        double death = fmaxf(account,guarantee[i]);
        value += death;
        double withdraw = personalaccount*allowed;
        value += withdraw;
        personalaccount = fmaxf(personalaccount-withdraw,0);
        account = fmaxf(account-withdraw,0);
    }

    //last year
    double index = getindex(year-1,pathindex);
    account = account * index;
    value+=fmaxf(account,guarantee[year-1]);

    return value * discountfactor;
}



float getindex(int period, long pathindex){
    int ndx = (pathindex/chunksize[period])%tradingdate;
    return stock[ndx];
}

//timing
clock_t begin;

void starttimer(){
    begin = clock();
}

void endtimer(){
    clock_t end = clock();
    double elapsed = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("/nelapsed: %f/n",elapsed);
}

test.h

float pathvalue(long pathindex);
int haswithdraw(int period);
float getindex(int period, long pathindex);
float qx(int period);
float px(int period);
//timing
void starttimer();
void endtimer();
//***constant
const int year= 20 ;
const int tradingdate0= 1 ;
const float firstpremium= 1 ;
const float riskfreerate= 0.06 ;
const float volatility= 0.25 ;
const float personalaccountat0= 1 ;
const float allowed= 0.07 ;
const float guaranteerate= 0.03 ;
const float alpha= 1 ;
const float beta= 1 ;
const int tradingdate= 2 ;
const int numberofpath= 1048576 ;
const float discountfactor= 0.301194211912 ;
const float accumulationfactor= 1.06183654655 ;
const float guaranteefactor= 1.03 ;
const float upmove= 1.28402541669 ;
const float downmove= 0.778800783071 ;
const float stock[2]={1.2840254166877414, 0.7788007830714049};
const long chunksize[20]={524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1};
const float guarantee[20]={1.03, 1.0609, 1.092727, 1.1255088100000001, 1.1592740743, 1.1940522965290001, 1.2298738654248702, 1.2667700813876164, 1.304773183829245, 1.3439163793441222, 1.384233870724446, 1.4257608868461793, 1.4685337134515648, 1.512589724855112, 1.557967416600765, 1.6047064390987882, 1.6528476322717518, 1.7024330612399046, 1.7535060530771016, 1.8061112346694148};

Answer 1

Parece como si debería funcionar. Probablemente necesites especificar el número de hilos para usar. Puede hacerlo configurando la variable OMP_NUM_THREADS. Por ejemplo, para usar 4 hilos:

OMP_NUM_THREADS=4 ./test

EDITAR: Acabo de compilar el código y observo aceleraciones significativas cuando cambio el número de subprocesos.

Answer 2

Incluso si su programa se beneficia del uso de OpenMP, no lo verá porque está midiendo el momento equivocado.

clock() devuelve el tiempo total de CPU gastado en todos los hilos . Si ejecuta con cuatro hilos y cada uno ejecuta 1/4 del tiempo, clock() aún devolverá el mismo valor puesto que 4 * (1/4) = 1. En su lugar, debe medir el reloj de pared .

Reemplazar llamadas a clock() con omp_get_wtime() o gettimeofday() . Ambos proporcionan sincronización de reloj de pared de alta precisión.

PD: ¿Por qué hay tanta gente alrededor que usa clock() para cronometrar?

Answer 3

No veo ninguna sección en la que especifique la cantidad de núcleos que usará OpenMP. Se supone que, de manera predeterminada, use la cantidad de CPU que ve, pero para mi propósito, siempre la obligué a usar todas las que he especificado.

Agregue esta línea antes de su construcción paralela:

#pragma omp parallel num_threads(num_threads)
{
   // Your parallel for follows here
}

... donde num_threads es un número entero entre 1 y la cantidad de núcleos en su máquina.

EDITAR: Aquí está el archivo MAKE utilizado para construir el código. Coloque esto en un archivo de texto llamado Makefile en el mismo directorio.

test: test.c test.h
    cc -o $@ $< -O3 -g3 -fmessage-length=0 -lm -fopenmp -ffast-math