Càlcul nombre π per Montecarlo

Context

Un mètode per calcular el nombre π amb precisió és el següent:

Imaginem un quadrant superior dret de radi 1 inscrit en un quadrat de costat 1. La raó d’àrees quadrant / quadrat és \({\pi \over 4}\). Aprofitem aquest fet per calcular el nombre π aplicant el mètode de Montecarlo. Es tracta de generar punts aleatoris distribuïts uniformement dins del quadrat i comptar els que cauen en el quadrant i els que cauen en el quadrat. Quants més punts estudiem, més precisió tindrà el valor de pi calculat. Vegeu la figura en l’article del nombre pi de la Viquipèdia.

Per calcular amb precisió π, cal posar molts punts i per tant el temps de càlcul pot ser força considerable. En aquest exercici, estudiarem la possibilitat de fer-ho en menys temps repartint els càlculs entre diversos processadors (cores de la CPU). Per això usarem la biblioteca multiprocessing

Es disposa

Es disposa del mòdul montecarlo.py. Es podem usar com a programa per calcular una aproximació de π. En la línia de comanda cal donar un argument que indiqui el nombre de punts a llençar sobre el quadrat. El programa també informarà del temps emprat en nanosegons.

Per exemple:

$ python3 montecarlo.py 100_000_000
Càlcul seqüencial via cua de punts
temps realització: 1021152107625 ns
estimació de π: 3.14122068
Càlcul seqüencial sense cua de punts
temps realització: 24702152155 ns
estimació de π: 3.14140848

Podeu descarregar-vos el programa montecarlo.py. El mòdul serà usat com a biblioteca de funcions que calculen π pel mètode de montecarlo. La descripció de les funcions del mòdul està a l’apèndix.

Es demana

Aprofitant les funcions del mòdul anterior desenvoluparem tres solucions per repartir els càlculs entre processos i estudiar la seva idoneïtat en termes d’eficiència. No avaluarem ni tindrem en compte la pobre i pèssima convergència del mètode per donar un valor de pi amb precisió.

La millora ideal en temps seria \(P\), on \(P\) és el nombre de processadors (un procés per cada processador) emprats en la solució paral·lela. La millora (guany) \(G\) es calcularà fent \(G=T_s/T_p\), on \(T_s\) és el temps emprat en la versió seqüencial del càlcul, i \(T_p\) és el temps emprat en la versió concurrent.

Observeu que tenim dos temps força diferents de càlcul en una sola seqüència d’execució. L´us d’una cua de punts versus l´ús d’iteradors marca una diferència important. Podem comparar amb els dos temps per justificar el que convingui.

Veurem que les proves fetes de cada implementació proposada s’allunyen del guany ideal en temps. Enumereu quin són els motius que porten aquestes situacions. Tingueu en compte la llei d’Amhdal

Per saber el nombre de processadors podeu fer servir la funció multiprocessing.cpu_count().

Aplicació del model productor-consumidor.

Es tracta de dissenyar un conjunt de processos seguint el model productor-consumidor que es comunicaran mitjançant cues de dades compartides.

  • Guardarem la solució en el fitxer montecarlo_pc.py

  • El productor genera punts que posa en la cua de punts a processar. Per la forma de generar-ne, tots el punts estàn en el quadrat. Si globalment s’encarreguen \(n\) punts, i hi han \(p\) productors, cada productor generarà \(\lfloor {n\over p} \rfloor\) punts.

  • El consumidor obté els punts de la cua de punts generada pel productor i compta els que cauen en el quadrant i el quadrat. Òbviament el nombre dels que cauen en el quadrat són tots els punts de la cua processats.

  • La seqüència principal d’execució crearà dues cues compartides: una per posar els punts del quadrat, i un altre per posar els tuples calculats pels consumidors (nombre de punts en quadrant, nombre de punts en quadrat).

  • La seqüència principal d’execució crearà els processos productor i consumidor, els iniciarà i els activarà.

  • Quan els productors acaben, el programa principal posa a la cua un punt sentinella \((2.0, 2.0)\) per indicar que s’ha acabat la generació de més punts. Cal posar un sentinella per cada consumidor existent.

  • Els consumidors quan reben el sentinella posen el resultat a una altre cua dedicada a recollir els resultats.

  • Finalment, un cop que la seqüència principal d’execució sap que han acabat els processos engegats a l’inici, processarà la cua de resultats per calcular el nombre pi i el mostrarà junt amb el temps emprat al canal estàndard de sortida.

Detalls implementació

Les cues compartides es crearan mitjançant multiprocessing.Queue que és una cua amb proteccions per tractar l’exclusió mútua.

Useu la funció montecarlo.puntsQuadrat() com a procés productor.

Pel procés consumidor desenvolupeu la següent funció:

montecarlo_pc.puntsQuadrant2(punts, resultats):
Parameters:

Guarda el resultat de montecarlo.puntsQuadrant(punts) al final de la cua resultats

Per posar els sentinelles a la cua un cop han acabat els productors la generació de punts, podeu usar montecarlo.afegirSentinella().

Pel càlcul de π podeu usar la funció montecarlo.pi_segons(), aportant com a paràmetres les dues àrees obtingudes de processar la cua de resultats. Pel càlcul del temps emprat feu servir time.perf_counter_ns(). Per mostrar els resultats useu la funció montecarlo.escriuResultats().

La seqüència principal d’execució obtindrà de la línia de la comanda, tres arguments: el nombre de punts a calcular, el nombre de productors, i el nombre de consumidors.

Exemple

$ python3 montecarlo_pc.py 100_000_000 2 2
Càlcul Productors punts quadrat- Consumidors cal. punts quadrant
detectat 8 processadors
temps realització: 702345524877 ns
estimació de π: 3.14122308

Processos idèntics

  • Guardarem la solució en el fitxer montecarlo_pr.py

  • Cada procés calcula els punts i els compta en les àrees que cauen. Un cop comptats, es posen a la cua de resultats.

  • La seqüència principal d’execució distribuirà el nombre de punts a calcular entre cadascun del processos i crearà una cua compartida per que cada procés posi els resultat dels càlculs (tuple de dos nombres).

  • Un cop que la seqüència principal d’execució sap que han acabat els processos que ha activat, llegirà la cua de resultats, i a partir de l’acumulació de valors d’aquesta, calcularà el nombre pi i mostrarà els resultat final.

Detalls implementació

El procés inclourà la següent funció:

montecarlo_pr.puntsQuadrantQuadrat2(n, resultats):
Parameters:

  • n (int) – nombre de punts a calcular

  • resultats (multiprocessing.Queue) – cua de resultats dels processos calculadors.

Invoca montecarlo.puntsQuadrantQuadrat() i guarda el resultat a la cua resultats

Pel càlcul de π podeu usar la funció montecarlo.pi_segons(), aportant com a paràmetres dues àrees obtingudes de processar la cua de resultats. Pel càlcul del temps emprat feu servir time.perf_counter_ns(). Per mostrar els resultats useu la funció montecarlo.escriuResultats().

La seqüència principal d’execució obtindrà de la línia de la comanda dos arguments: el nombre de punts a calcular, i el nombre de processos.

Exemple

$ python3 montecarlo_pr.py 100_000_000 3
Càlcul mitjançant comunicació resultats en una cua compartida
detectat 8 processadors
temps realització: 7226854179 ns
estimació de π: 3.141680591416806

Pool

  • Guardarem la solució en el fitxer montecarlo_pool.py

  • Cada procés calcula els punts i els compta en les dues àrees que cauen. Un cop comptats, retorna els valors trobats.

  • El procés principal distribuirà el nombre de punts a calcular entre cadascun del processos i crearà una cua compartida per que cada procés posi els resultat dels càlculs (tuple de dos nombres).

  • El procés principal invocarà els processos mitjançant multiprocessing.Pool.

  • Un cop els processos han acabat, Pool retorna un iterable amb els resultats retornats per cadascun dels processos. A partir de l’iterable, acumularem els resultats parcials per obtenir el nombre final de punts en quadrant i el nombre de punts en quadrat. Amb les dades finals calcularem el nombre pi i mostrarem el resultat final i el temps emprat.

Detalls implementació

El procés serà la mateixa funció montecarlo.puntsQuadrantQuadrat().

Pel càlcul de π podeu usar la funció pi_segons(), aportant com a paràmetres dues àrees obtingudes de processar l’iterable de Pool. Pel càlcul del temps emprat feu servir time.perf_counter_ns(). Per mostrar els resultats useu la funció montecarlo.escriuResultats().

La seqüència principal d’execució obtindrà de la línia de la comanda dos arguments: el nombre de punts a calcular, i el nombre de processos.

Exemple

$ python3 montecarlo_pool.py 100_000_000 3
Càlcul mitjançant Pool
detectat 8 processadors
temps realització: 7343238966 ns
estimació de π: 3.1414079514140796

Anàlisi de proves

Executeu alguns casos en cada versió i determineu quines causes fan que alguns temps no siguin millors de l’esperat.

Apèndix

montecarlo

Disposa de funcions per fer el mètode de montercarlo per calcular pi.

Les següents són pels programes que separen el càlcul en dos processos: generació de punts dins del quadrat unitari, i comptatge dels punts del quadrat incidents en el quadrant inscrit de radi unitari. La comunicació entre processos es fa mitjançant una cua compartida.

montecarlo.puntsQuadrant(punts)
Parameters:

punts (Queue) – cua de punts dins del quadrat \(((0,0), (1,0), (1,1), (0,1))\) excepte un punt sentinella (2.0, 2.0). Un punt és un tuple \((x, y)\) tal que \(0\le x \le 1.0\) i \(0\le y \le 1.0\) o \((2.0,2.0)\) (punt sentinella)

Returns:

tuple (nombre de punts dins quadrant, nombre de punts dins quadrat)

Donada una cua de punts dins del quadrat, compta els punts que cauen dins del quadrant inscrit. Quan llegeix el sentinella, retorna (nombre de punts dins quadrant, nombre de punts llegits). El nombre de punts llegits, excepte el sentinella, estan dins del quadrat.

montecarlo.puntsQuadrat(n, punts)
Parameters:

  • n (int) – nombre de punts

  • punts (Queue) – cua de punts dins del quadrat \(((0,0), (1,0), (1,1), (0,1))\) Un punt és un tuple \((x, y)\) tal que \(0\le x \le 1.0\) i \(0\le y \le 1.0\) o \((2.0,2.0)\) (punt sentinella)

Calcula aleatòriament una cua de n punts dins del quadrat. Modifica punts

Pel programes que no fan la separació anterior, disposem de la funció puntsQuadrantQuadrat() que fa íntegrament el càlcul de punts en les dues àrees.

montecarlo.puntsQuadrantQuadrat(n_quadrat)
Parameters:

n (int) – nombre de punts a calcular

Returns:

tuple (nombre de punts dins quadrant, nombre de punts dins quadrat)

Return type:

tuple (int, int)

A partir d’una generació distribuïda uniformement de n punts inclosos en el quadrat q de coordenades \(((0,0), (1,0), (1,1), (0,1))\) (és a dir \(\forall (x, y): \vert 0\le x \le 1\) i \(0\le y \le 1\)) calcula el nombre d’incidents en el quadrant inscrit en el quadrat

Finalment, el fil principal del programa té les funcions afegeixSentinella() per posar a la cua compartida dels processos calculadors que la llegeixen, i així saber quan acaba els punts a calcular. S’ha de posar un sentinella per cada procés actiu.

A partir del nombre de punts dins del quadrant i dels quadrat podem calcular pi amb la funció pi_segons() i mostrar els resultats amb la funció escriuResultats()

montecarlo.afegeixSentinella(punts)
Parameters:

punts (Queue) – cua de punts

Afegeix el punt sentinella (2.0, 2.0) a la cua punts.

montecarlo.escriuResultats(inici, fi, pi)
Parameters:

  • inici (int) – temps inici tros de programa a temporitzar en nanosegons

  • fi (int) – temps d’acabem del tros de programa temporitzat en nanosegons

  • pi (float) – valor estimat de pi

Escriu pel canal estandard de sortida el temps emprat pel programa (\(fi - inici\)) i el valor de pi calculat

montecarlo.pi_segons(n_quadrant, n_quadrat)
Parameters:

  • n_quadrant (int) – nombre de punts dins del quadrant

  • n_quadrat (int) – nombre de punts dins del quadrant

Returns:

\(4 {n\_quadrant \over n\_quadrat}\)

Return type:

float

Avalua pi segons el nombre de punts inicidents en el quadrat i el quadrant

La seqüència principal d’execució que acompanya el mòdul és un bon exemple d’ús:

montecarlo.main(n)
Parameters:

n (int) – nombre de punts per estimar el valor de pi

Calcula el nombre pi pel mètode de montecarlo. Escriu pel canal estàndard de sortida el temps emprat en el càlcul en nanosegons i el valor de pi calculat