> Intendi che non consideri ben scritte le recipes ?
No, immagino che siano scritte bene (non le conosco molto ma ne ho
sentito molto parlare) ma l'algoritmo e' una cosa e l'implementazione
efficiente una cosa del tutto diversa.
> non capisco bene la distinzione tra algoritmo e implementazione.
> Li considero quasi sinonimi, uno in lingua astratta, l'altra
Credo che poi tu abbia capito cosa intendo nel resto del mio primo
messaggio, ma per chiarire: l'implementazione non e' solo
"trascrivere" l'algoritmo in un qualche linguaggio, e' soprattutto
ottimizzarlo per la macchina su cui deve girare. Diventa quindi un
problema misto matematica/computer architecture. In genere non si e'
piu' limitati dal numero di unita' floating-point presenti nel
processore, ma dalla banda verso la memoria (cioe': le unita' di
calcolo ci sono, ma non si riesce ad alimentarle di operandi perche'
la memoria e' troppo lenta), il che porta ad equilibrismi estremi nel
modo in cui si spostano i dati, distribuendoli nei vari livelli di
cache per avere quello che ti serve il piu' vicino possibile. Gli
algoritmi cambiano completamente faccia :)
Esempio: moltiplicazione tra matrici (la cosa piu' semplice):
http://www.cs.berkeley.edu/~yelick/cs267-sp04/lectures/03/lect03-matmul.ppt
una volta che cominci ad aggiungere blocking, loop unrolling,
trasposizione di colonne per allinearle alla cache line, suddivisioni
ricorsive, microblocking per le unita' SIMD, eccetera, alla fine viene
fuori un codice di qualche migliaio di linee che nessuno riuscira'
piu' a riconoscere come uan moltiplicazione di matrici :)
> ecco, questo molto interessante. Visto che te ne intendi,
> avresti mica qualche link dove posso trovare il sorgente di
> quelle robe ? Immagino siano in C, vero ? Normalmente non mi
> da grossi problemi di traduzione (in C++ sarebbe peggio)
http://www.netlib.org/lapack/index.html
Se ben ricordo LAPACK e' in fortran, ma ci sono API per il C.
Cmq se scarichi il pacchetto della tua distribuzione linux puoi
guardarci dentro, immagino ci siano i sorgenti... l'ultima volta che
ci ho giocato e' stato 4 anni fa e non mi ricordo i dettagli.
Mi pare che alla fine sotto windows avessi usato le librerie ACML
della AMD perche' erano gratis (ma non open source) per applicazioni
non commerciali. Puoi googolare (e anche su quello Intel, magari le
cose son cambiate in questi anni).
> > ma immagino non siano ottimizzata bene come le
> > prime due. �Se invece vuoi lanciarti nella programmazione GPGPU,
> > CUBLAS e' BLAS per CUDA, non so se ci siano gia' delle librerie tipo
> > LAPACK open-source. Per OpenCL non so niente, ma immagino ci sia
> > qualcosa anche li'.
>
> routine grafiche x ora non me ne occorrono, ma se mi trovi
GPGPU non e' solo grafica, e' tutto :) viene usato nei supercomputer
per un sacco di algoritmi pesanti (da simulazioni di farmaci a ricerca
di idrocarburi).
Cmq mi pare decisamente fuori luogo qui, quindi non approfondisco.
Pleg
Received on Fri Feb 18 2011 - 23:47:53 CET