.. py:module:: montecarlo Càlcul nombre π per Montecarlo =============================== .. contents:: 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 :math:`{\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 :py:mod:`multiprocessing` Es disposa ---------- Es disposa del mòdul :download:`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: .. literalinclude:: test-montecarlo.txt Podeu descarregar-vos el programa :download:`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 :ref:`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 :math:`P`, on :math:`P` és el nombre de processadors (un procés per cada processador) emprats en la solució paral·lela. La millora (guany) :math:`G` es calcularà fent :math:`G=T_s/T_p`, on :math:`T_s` és el temps emprat en la versió seqüencial del càlcul, i :math:`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ó :py:func:`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 :file:`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 :math:`n` punts, i hi han :math:`p` productors, cada productor generarà :math:`\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 :math:`(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 :py:class:`multiprocessing.Queue` que és una cua amb proteccions per tractar l'exclusió mútua. Useu la funció :py:func:`montecarlo.puntsQuadrat` com a procés productor. Pel procés consumidor desenvolupeu la següent funció: .. py:function:: montecarlo_pc.puntsQuadrant2(punts, resultats): :param multiprocessing.Queue punts: cua de punts a calcular :param multiprocessing.Queue resultats: cua de resultats dels processos calculadors. Guarda el resultat de :code:`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 :py:func:`montecarlo.afegirSentinella`. Pel càlcul de π podeu usar la funció :py:func:`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 :py:func:`time.perf_counter_ns`. Per mostrar els resultats useu la funció :py:func:`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 """"""" .. literalinclude:: test-montecarlo_pc.txt Processos idèntics ^^^^^^^^^^^^^^^^^^ * Guardarem la solució en el fitxer :file:`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ó: .. py:function:: montecarlo_pr.puntsQuadrantQuadrat2(n, resultats): :param int n: nombre de punts a calcular :param multiprocessing.Queue resultats: cua de resultats dels processos calculadors. Invoca :py:func:`montecarlo.puntsQuadrantQuadrat` i guarda el resultat a la cua `resultats` Pel càlcul de π podeu usar la funció :py:func:`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 :py:func:`time.perf_counter_ns`. Per mostrar els resultats useu la funció :py:func:`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 """"""" .. literalinclude:: test-montecarlo_pr.txt Pool ^^^^ * Guardarem la solució en el fitxer :file:`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 :py:class:`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ó :py:func:`montecarlo.puntsQuadrantQuadrat`. Pel càlcul de π podeu usar la funció :py:func:`pi_segons`, aportant com a paràmetres dues àrees obtingudes de processar l'iterable de Pool. Pel càlcul del temps emprat feu servir :py:func:`time.perf_counter_ns`. Per mostrar els resultats useu la funció :py:func:`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 """"""" .. literalinclude:: test-montecarlo_pool.txt Anàlisi de proves ^^^^^^^^^^^^^^^^^ Executeu alguns casos en cada versió i determineu quines causes fan que alguns temps no siguin millors de l'esperat. .. _apendix: 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. .. automodule:: montecarlo :members: puntsQuadrant, puntsQuadrat Pel programes que no fan la separació anterior, disposem de la funció :py:func:`puntsQuadrantQuadrat` que fa íntegrament el càlcul de punts en les dues àrees. .. automodule:: montecarlo :members: puntsQuadrantQuadrat Finalment, el fil principal del programa té les funcions :py:func:`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ó :py:func:`pi_segons` i mostrar els resultats amb la funció :py:func:`escriuResultats` .. automodule:: montecarlo :members: afegeixSentinella, pi_segons, escriuResultats La seqüència principal d'execució que acompanya el mòdul és un bon exemple d'ús: .. automodule:: montecarlo :members: main