Tag-Archive for » algoritmo «

C++ & OpenMP

Monday, May 24th, 2010 | Author:

Molto spesso a causa del mio lavoro mi trovo a dover implementare particolare algoritmi euristici sviluppati dal gruppo di ricerca con cui lavoro. Altrettanto spesso queste euristiche devono essere confrontate con la controparte esaustiva (o a forza bruta) per poter stimare quali sono i reali vantaggi nell’utilizzo dell’euristica rispetto ad un approccio a forza bruta. Fondamentalmente si è interessati a confrontare il rapporto qualità della soluzione rispetto al tempo “risparmiato” al crescere della dimensione del problema. Recentemente mi è capitato di dover lavorare su un problema la cui dimensione cresceva esponenzialmente rispetto ai dati di ingresso: come è facile immaginare la ricerca di una soluzione esaustiva diventava impraticabile (considerando i tempi necessari per poterla ricavare) anche con relativamente pochi dati iniziali. Proprio per questo ho fatto una veloce ricerca per vedere se riuscivo a trovare una libreria che mi permettesse con poco sforzo di parallelizzare l’algoritmo esaustivo in modo da poter sfruttare gli otto thread paralleli (ripartiti su 4 processori) disponibili sul mio Intel core i7 Q720.

Sono stato fortunato due volte:

  • prima fortuna: mi sono imbattuto in questa API: OpenMP (The OpenMP API specification for parallel programming);
  • seconda fortuna: viene supportata sia da MS Visual C++ (dalla versione 2005) che da GCC… anche se sotto Visual C++ non è possibile utilizzare la versione più recente (la 3.0) ma solamente la (2.0).

OpenMP mi è sembrata subito una risposta interessante al mio problema iniziale e quindi ho deciso di provarla sul campo e ne sono rimasto piacevolmente soddisfatto. Non potendo riportare qui quello su cui sto lavorando (l’articolo non è ancora uscito) vi presenterò un esempio ad hoc e vedremo come “modificarlo” (operazione necessaria utilizzando la versione 2.0 di OpenMP) e analizzeremo i miglioramenti di prestazioni ottenuti.

more…