HPC - Merge Sort with OpenMP tasks

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-10-20

Il file omp-merge-sort.c contiene una implementazione ricorsiva dell'algoritmo Merge Sort; l'algoritmo dovrebbe essere noto dal corso di Algoritmi e Strutture Dati.

Il programma genera una permutazione casuale dei primi \(n\) interi \(0, 1, \ldots, n-1\), e la ordina usando Merge Sort. Il programma usa Selection Sort per ordinare i sottovettori la cui lunghezza sia inferiore ad una certa soglia, allo scopo da limitare il costo della ricorsione; questa è una ottimizzazione frequentemente usata.

Parallelizzare il programma sfruttando i task OpenMP, facendo in modo che ogni chiamata ricorsiva venga delegata ad un task. Verificare se la versione parallela sia più o meno veloce di quella seriale, variando il numero di thread OpenMP. Si utilizzi una lunghezza appropriata per l'array, in modo da ottenere tempi di esecuzione non troppo brevi che sarebbero soggetti ad una eccessiva variabilità.

Per compilare:

    gcc -std=c99 -Wall -Wpedantic -fopenmp omp-merge-sort.c -o omp-merge-sort

Per eseguire:

    ./omp-merge-sort 50000

File