Prof. Luisa D’Amoremurli/didattica/2005_2006/cs/I_Lezione_2006.pdf · 52 82 14519715744 1 5 16 9...

A. Murli Corso di Calcolo Scientifico 1

Corso di Calcolo Scientifico

Prof. Luisa D’Amorewww.dma.unina.it/luisa.damore_web.htmlwww.dma.unina.it/luisa.damore_web.html

[email protected]@dma.unina.it

a.a. 2005/2006

Il materiale didattico è all’URL www.dma.unina.it/murli

http://www.dma.unina.it/luisa.damore_web.html

mailto:[email protected]

2

Cos’è il calcolo scientifico


Calcolo numerico

Computer Science

Matematica

Applicazioni

Comp

utatio

nal P

hysic

s Mathematical Physics

Compu

tation

al

Phy

sics

Computational Mathematics

Scientific Computing

Comp

utation

al Ma

them

atics


Cos’è il calcolo scientifico?

Genetica nanotecnologia climatologia astronomia

PC, WS, Linux,Windows F77, F90, C, C++, …

strumenti Hardware & software

CALCOLO SCIENTIFICO

applicazioni scientifiche

Strumenti computazionali (metodi, algoritmi e software)

necessari alla risoluzione di problemi scientifici mediante calcolatore


Cosa si intende per risoluzione computazione di un pb.

Pbroblem

Mabthematical model

Approximation

discretization

numerics

algorithm

software

system


La CSE

La descrizione attraverso livelli concentrici

del processo di risoluzione

computazionale di un problema

caratterizza la

Computational Science and Engineering


simulazione computazionale

L’ approccio computazionale nella CSE

StudioTeorico

dei modelli SperimentazioneIn laboratorio

The computer is providing a new window through which we can observe the

natural world in exquisite detail …..[Rapporto NSF, 2000]


Il prodotto del calcolo scientifico:il software matematico

Problemi reali

“…Software can be seen as a map of a real-worldproblem onto a computer…” [J. Rice, 1988]


Fattori che guidano lo sviluppo del sw

tecnologia hw: processori, memorie,

reti

sw di base: compilatori, strum. sw

engineering, …

applicazioni: multidisciplinarità,

collaboratività, crescente complessità, …

forte impatto su metodologie, tecniche e strumenti sullo sviluppo di software


Caratteristiche del software scientifico

Efficienza Accuratezza Affidabilità Modularità API standard Portabilità Facilità d’uso Facilità di manutenzione …

The “black-box!”IFIP Working Conference on "The

Quality of Numerical Software: Assessment and Enhancement“,

Oxford, 1996


l’obiettivo finale

SCE: “a scientific computing environment that provides all the computational facilities needed to solve a target class of problems. These features includeadvanced solution methods, automatic and semiautomatic selection of solution methods, and waysto easily incorporate novel solution methods…”.(J.Rice)


Dalle librerie ai PSE: principali motivazioni

♦ linguaggio di programmazione per l’utente problem-dependent

♦ minimo know-how dell’utente nello sviluppo di algoritmi e software

♦ interazione dinamica e trasparente delle componenti software

♦ differenti livelli di interazione con l’utente

♦ ausilio nella selezione dei componenti sw

♦ …


Obiettivo del corso

Introdurre alle problematiche proprie del calcolo scientifico e all’uso degli strumenti di base del calcolo scientifico

attraverso la progettazione e sperimentazioe del

software numerico che implementa algoritmi standard alla base delle applicazioni scientifiche

Il corso prevede una intensa attività di laboratorio !!


Alcune problematiche …

Il gap tra performance del processore e performance della memoria ha una crescita del 50%/anno

1980

1981

1983

1984

1985

1986

1987

1988

1989

1990

1991

1992

1993

1994

1995

1996

1997

1998

1999

2000

1982

1

Anni

perf. proc.:60%/anno

(2X/1.5anni)

perf. DRAM:9%/anno

(2X/10 anni)

10

100

1000

DRAM

CPU

Per

form

ance Legge di Moore


Soluzione: uso della memoria gerarchica

memoria centrale(DRAM)

cache L2 e L3(SRAM)

controllo

datapath

processore

registri

on-chip

cache (L

1)

memoria secondaria

(dischi)

memoria distribuita

Memoria terziaria

(dischi/tape)

memoria remota

1 ns 10 ms –1 msvelocità: 10 ns 100 ns

100 bytecapacità: KB MB

10 s – 10 ms

GB, TB TB, PB


BLAS:Basic Linear Algebra Subprograms

la libreria software per il calcolo matriciale ottimizzata pe calcolatori a memoria

gerarchica

C. Lawson, R. Hanson, D. Kincaid, F.Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM TOMS, 1979

J. Dongarra, J. DuCroz, S. Hammarling, R. Hanson, An Extended set of Fortran Basic Linear Algebra Subprograms, ACM TOMS, 1988

J. Dongarra, J. DuCroz, I. Duff, S. Hammarling, A Set of Level 3 Basic Linear Algebra Subprograms, ACM TOMS, 1990


Confronto BLAS1, BLAS2, BLAS3

IBM RS/6000 Power 3 (200 MHz, 800 Mflop/s Peak)

0

200

400

600

800

10 100 200 300 400 500Order of vector/Matrices

Mfl

op

/s

BLAS 3

BLAS 2

BLAS 1

sviluppare algoritmi a blocchi è di fondamentale importanza per la performance


LAPACKLibreria di software matematico per la

risoluzione di problemi di algebra lineare su architetture a memoria gerarchica

Problemi risoluzione sistemi lineari risoluzione pb. minimi quadrati calcolo autovalori e autovettori fattorizzazioni LU, Cholesky, QR,

valori singolari, Schur stima indice condizionamento …………

Matrici generali dense, a banda,

tridiagonali, triangolari simmetriche o Hermitiane

definite positive dense, a banda, tridiagonali

ortogonali Hessenberg superiori …………

E. Anderson et al., LAPACK User’ Guide, SIAM, 1995


Alcuni problemi ..

♦ L’architettura dei microprocessori diventa sempre più complessa

♦ Elevate prestazioni possibili solo con ottimizzazioni machine-dependent

♦ Molti parametri da gestire nell’implementazione degli algoritmi (dimensione dei blocchi, permutazione di indici dei loop, profondità dell’unrolling, numero di processi, topologia, ...)

Necessità di approcci adattativi e automaticinello sviluppo di software


Automated Empirical Optimization of Software(AEOS)

Applicazione di tecniche di ottimizzazione che consentono un adattamento del codice all’architettura

(portabilità della performance)


AEOS: esempi

♦ ATLAS, Automatically Tuned Linear Algebra Softwarehttp://www.netlib.org/atlas/

BLAS + alcune routine di LAPACK• PHiPAC, Portable, High-Performance, ANSI C Software

http://www.icsi.berkeley.edu/~bilmes/phipac/ Prodotto tra matrici

• Sparsity, un toolbox per versioni ottimizzate del prodotto matrice sparsa-vettore

http://www.cs.berkeley.edu/~yelick/sparsity/

• FFTW, the Fastest Fourier Transform in the Westhttp://www.fftw.org/

DFT in una o più dimensioni, di dati reali o complessi, di sequenze di dimensione qualunque.

http://www.icsi.berkeley.edu/~bilmes/phipac/










http://www.fftw.org/


Altre problematiche….

uso di risorse hw/sw/dati distribuite:le risorse devono essere localizzate, selezionate e accedute in modo agevole, trasparente, efficiente e affidabile

• adattività• scalabilità• load balancing• tolleranza alla latenza di rete• algoritmi e sw parametrizzati e

annotati• definizione e uso efficace di modelli

di performance e history database• ...


Network-enabled computational servers

NetSolve

, http://icl.cs.utk.edu/netsolve

grid-based hw/sw server, che consente l’accesso a LAPACK, ScaLAPACK, PETSc, Aztec, ...

http://www-neos.mcs.anl.gov

web server per problemi di ottimizzazione, fornisce accesso e guida per una vasta collezione di solver

http://ninf.apgrid.org

grid-based hw/sw server, sperimentato con tool di visualizzazione e PDE solver di tipo domain-decomposition

WebPDELab web server che consente l’accesso a //ELLPACK

http://www.webpdelab.org

http://www-neos.mcs.anl.gov/neos/server-solvers.html


Network-enabled computational server

fornisce l’accesso on-demand a risorse hw/sw/dati, remote, usando meccanismi di selezione/allocazione

automatici e dinamici per meglio soddisfare la richiesta

agent

richiestascelta

output

AgenteResource Discovery Load Balancing

Resource Allocation Fault Tolerance


Facciamo un esempio …:

Sviluppo di algoritmi e software matematico per

l’analisi di immagini provenienti da

apparecchiature mediche

(Disgnostica medica per immagini)


Il problema: analisi dati SPECT

Acquisizione

Ricostruzione/Elaborazione


Il problema: ecocardiografia

Ricostruzione

Acquisizione


La Metodologia del PROBLEM SOLVING

Implementazione del sw in uno specifico ambiente di

calcolo

Sviluppo dell’algoritmo

approssimazione di M(P) mediante

metodi numerici

Formulazione delproblema P

Descrizione di Pmediante un modello

matematico:M(P)


Il primo passo…

| |t

uu u div

u=

∂ I∂ t

=div [ g ∣∇ I∣2 ∇ I ]I x , y ,0 =I 0

∂ I∂ n

=0


matematico:M(P)


g=∫I x

∫I y

∫I z

f ×k dxdydz


Il terzo passo…

discretizzazione


matematico:M(P)


2 4 6 8 10 12 14 16

2

4

6

8

10

12

14

16

-8 -6 -4 -2 0 2 4 6 8-8

-6

-4

-2

0

2

4

6

8

68 73 83 80 91 119122115123 118133 113104 10699 85

27 26 45 63 73 74 60 58 74 73 85 67 71 72 63 48

35 28 15 6 27 19 8 3 10 9 32 33 23 31 32 25

0 0 24 47 103 99 97 74 44 11 4 0 0 0 8 12

3 51 117 156182 174177153120 79 44 5 0 0 2 3

67 115112 75 26 0 0 0 0 8 29 30 16 9 0 0

58 66 47 17 46 0 0 0 0 0 0 5 8 1 0 0

52 82 145 197157 44 1 5 16 9 2 8 3 7 23 46

158 184217 197175 69 19 33 37 51 68 58 47 78 131 144

155 178212 200199 172144134135 123103 93 68 99 151 165

134 147173 167165 178164141121 82 51 56 79 104151 165

132 134143 133131 11511010471 43 53 79 127 139172 178

164 163160 146122 98 102114111 124160 183194 189202 195

192 195199 186202 211208199207 224228 220214 199202 185

196 203220 221204 235235225238 244230 222218 198195 175

193 199228 238226 242244244247 235229 243218 195188 162


Grid of voxels (3x3x3)

Discretizzazione: il modello numerico

Hu=g

b pn u p

nτ ∑q∈N p

a pqn u pn−uqn=b pn u pn−1

nucleo computazionale

• Sparsa (10 % elementi n.z.)

• Grande ( 1012 per 2D)• Mal condizionata (µ=106)


Sviluppo dell’algoritmorisolutivo M h P

Implementazione in uno specifico ambiente di calcolo

approssimazione di M(P) mediante

metodi numerici: M h P


matematico:M(P)


Lo sviluppo dell’algoritmo e la sua implementazione …


Alcuni nuclei ..

• operazioni tra vettori

• Prodotti matrice-vettore

• FFT

• risoluzione sistemi lineari

•……


Aspetti importanti del calcolo scientifico

♦ Numerical algorithms ➣ Mathematical software

♦ Software engineering♦ Compiler technology♦ Programming languages♦ Visualization and feature identification♦ Grid and distributed systems♦ Databases, database federation♦ Networks


Informatics challenges for scientific computing

♦ Scale (data management, workflow management, ..)

♦ Heterogeneity (risorse di calcolo, reti, dati, ..)

♦ Distribution (monitoraggio, scheduling, ..)♦ Dynamic variation (fault tolerance, on-

demand computing, resource allocation, ..)


Producing software is still a people intensive

activity.

There is no Moore’s laws for software


Prerequisiti del corso

Aver risolto un problema

con il calcolatore!

Date post:	25-Jun-2020
Category:	Documents
Upload:	others
View:	0 times
Download:	0 times

Prof. Luisa D’Amoremurli/didattica/2005_2006/cs/I_Lezione_2006.pdf · 52 82 14519715744 1 5 16 9...

Documents