MARL-Ped+Hitmap: aumentando la productividad de simulaciones basadas en agentes con una herramienta de arrays distribuidos

MARL-Ped+Hi map: Aumen ando la p oduc i idad de simulaciones basadas en agen es con una he amien a de a ays dis ibuidos Edua do Rod iguez-Gu iez 1, F ancisco Ma inez-Gil 2, Juan Manuel O du˜na-Hue as 3, A u o Gonzalez-Esc ibano 4 Resumen— Los sis emas Mul i-agen e es ´an cons i- uidos po piezas so wa e llamadas agen es que son capaces de pe cibi el en o no y ac ua en ´el de man- e a au ´onoma. MARL-Ped es un modelo Mul i-agen e de pea ones donde cada agen e (pea ´on) ap ende el compo amien o adecuado pa a la simulaci´on de di e en es si uaciones (aglome aciones, c uces, e ac- uaciones de ecin os ce ados,...). MARL-Ped u iliza el es ´anda de paso de mensajes MPI pa a su ex- plo aci´on en sis emas dis ibuidos de o ma po able. P og ama u ilizando di ec amen e sis emas de paso de mensajes equie e un g an es ue zo si se desean in- oduci pol´ı icas de epa o de ca ga lexibles y que se adap en a la pla a o ma de des ino. Hi map es una biblio eca de unciones pa a acili a la p og a- maci´on de aplicaciones pa alelas, basada en a ays dis- ibuidos. In oduce abs acciones pa a la pa ici´on y mapeo anspa en e de a ays, as´ı como pa a con- s ui pa ones de comunicaci´on lexibles que se adap- an a la pa ici´on de o ma au om´a ica. En es e abajo p esen amos la me odolog´ıa y ´ecnicas de Hi map aplicadas a la simulaci´on de agen es, u ilizando MARL-Ped como caso de es u- dio. Mos amos concep ual y expe imen almen e las en ajas de aplica Hi map pa a aumen a la p oduc- i idad de es e ipo de aplicaciones, an o en adap - abilidad como en endimien o, pe mi iendo ag upa agen es en p ocesos y educiendo los cos es de comu- nicaci´on y sob eca gas de o ma anspa en e. Palab as cla e— Agen es, simulaci´on de mul i udes, paso de mensajes, he amien as de p og amaci´on, a - ays dis ibuidos I. In oducci´ on Los sis emas Mul i-agen e [1], [2] es ´an basados en la cons ucci´on de p ocesos compu acionales in- dependien es denominados agen es que ienen la capacidad de pe cibi el en o no y, de mane a au ´onoma, oma decisiones ace ca de las ac i idades a lle a a cabo pa a consegui sus obje i os. Es e ipo de so wa e es especialmen e in e esan e pa a es udia sis emas complejos, como la din´amica de los pea ones, donde la in e acci´on au ´onoma de los indi iduos gene a compo amien os globales del sis- ema. MARL-Ped [3] es un modelo de pea ones Mul i-agen e dis ibuido donde cada agen e (pea ´on) ap ende un compo amien o p opio, que pe mi e 1Dp o. de In o m´a ica, Uni . Valladolid, e-mail: [email p o ec ed] 2Dp o. de In o m´a ica, Uni . Valencia, e-mail: [email p o ec ed] 3Dp o. de In o m´a ica, Uni . Valencia, e-mail: [email p o ec ed] 4Dp o. de In o m´a ica, Uni . Valladolid, e-mail: [email p o ec ed] simula a g upos de pea ones (desde unos pocos has a mul i udes) en di e en es escena ios como con- ges iones, c uces, a ance en colas e c. La can idad de agen es necesa ia pa a simula muchedumb es, as´ı como la g an ca ga compu acional que implica an o el p oceso de ap endizaje de los agen es como la sim- ulaci´on de su compo amien o y del en o no, hacen de MARL-Ped un buen ejemplo de aplicaci´on pa - alela ap opiada pa a en o nos de al o endimien o. La e si´on ac ual de MARL-Ped u iliza el es ´anda de paso de mensajes MPI pa a su explo aci´on en sis- emas dis ibuidos de o ma po able. P og ama u ilizando di ec amen e sis emas de paso de men- sajes equie e un g an es ue zo si se desean in o- duci pol´ı icas de epa o de ca ga lexibles y que se adap en a la pla a o ma de des ino. Po o a pa e, Hi map [4] es una biblio eca de unciones dise˜nada pa a acili a la p og amaci´on de aplicaciones pa alelas, basada en a ays dis ibuidos. In oduce abs acciones pa a la pa ici´on y mapeo au om´a ico de a ays, as´ı como pa a cons ui pa- ones de comunicaci´on lexibles que se adap an a la pa ici´on de o ma au om´a ica. En es e abajo p esen amos la me odolog´ıa y ´ecnicas de Hi map aplicadas a la simulaci´on de agen es, u ilizando MARL-Ped como caso de es udio. Mos amos las en ajas de aplica Hi map pa a au- men a la p oduc i idad de es e ipo de aplicaciones, an o en es ue zo de desa ollo, como en adap abil- idad y endimien o. Los esul ados mues an que la e si´on de MARL-Ped u ilizando Hi map es m´as simple en ´e minos de c´odigo, y a la ez m´as lex- ible. Hi map pe mi e de o ma anspa en e ag u- pa agen es en p ocesos pa a educi los cos es de comunicaci´on y e i a sob eca gas, pe mi iendo una mayo escalabilidad y una explo aci´on m´as e icien e de los ecu sos de c´ompu o. El es o del a ´ıculo se es uc u a de la siguien e o ma. La secci´on II p esen a abajo elacionado. La secci´on III desc ibe los undamen os de MARL- Ped y Hi map. La secci´on IV desc ibe la aplicaci´on de Hi map al p og ama o iginal. La secci´on V p e- sen a un es udio expe imen al en ´e minos de es- ue zo de desa ollo y escalabilidad de la soluci´on conseguida. Finalmen e la secci´on VI p esen a las conclusiones y abajo u u o. II. T abajo elacionado Los es udios de din´amicas de pea ones se han de- sa ollado a lo la go de los ´ul imos 75 a˜nos. Aunque la apa ici´on de los p ime os modelos de pea ones basados en modelos ´ısicos de luidos y las ecuaciones cin´e icas de gases son de los a˜nos 60 del siglo XX, el e dade o desa ollo de modelos acon eci´o con el auge del uso de compu ado es de bajo cos e a pa - i de la d´ecada de los 80 del pasado siglo. En e los modelos de pea ones que m´as ´exi o han enido en e la comunidad cien ´ı ica debido a su e sa ili- dad y simplicidad se encuen a el modelo de ue zas sociales [5], los modelos basados en au ´oma as celu- la es [6], los modelos con inuos basados en ecuaciones de cin´e ica de gases [7] y los basados en agen es [8]. Den o de es e ´ul imo g upo, en los ´ul imos a˜nos se han ealizado abajos pa a inco po a ´ecnicas de ap endizaje m´aquina (machine lea ning) a es e campo [9]. Los sis emas de ap endizaje aplicado al modelado de pea ones iene ca ac e ´ıs icas muy in- e esan es que los se˜nalan como una al e na i a a los sis emas m´as cl´asicos indicados an e io men e. En- e ellas la m´as des acada consis e en que es el p opio agen e o pea ´on el que ap ende su compo amien o, libe ando al p og amado de es a a ea. Siendo la din´amica de g upos de pea ones un p oblema com- plejo, es a a ea se ha con e ido en la di icul ad p incipal de odo modelo de pea ones. Po o a pa e, a ni el compu acional la simulaci´on mic osc´opica de pea ones en escena ios de g andes densidades (mul i udes) cons i uyen un desa ´ıo en el que son necesa ias nue as es a egias de p oce- samien o pa alelo y o ganizaci´on y paso de in o - maci´on. En es e sen ido, en el abajo de Lozano e al. [10] se p opone una a qui ec u a escalable basada en un sis ema clien e-se ido je ´a quico que sopo a del o den de miles de agen es. En los abajos pos- e io es [11], [12], [13] se p opone una a qui ec u a pa alela pa a simulaci´on de muchedumb es en la que se ido es in e conec ados compa en la ca ga com- pu acional p o enien e de dos cuellos de bo ella: el se ido de acciones y la base de da os que ep esen a el e eno. En el abajo de Yilmaz e al. [14] se p o- pone una a qui ec u a basada en CUDA con l´ogica di usa que se us´o pa a simula un ma a ´on con m´as de un mill´on de co edo es. Hi map o ece una capa de abs acci´on in e me- dia en e el manejo manual en paso de mensajes de es uc u as dis ibuidas y los lenguajes PGAS (Pa - i ioned Global Ad ess Space), como Chapel [15], o UPC [16]. Es os modelos no p opo cionan su icien es he amien as pa a pe mi i el pa alelismo de p oce- sos je ´a quicos en en o nos h´ıb idos como Hi map. Hi map pe mi e adem´as cons ui pa ones de co- municaci´on eu ilizables en iempo de ejecuci´on que se adap an a la pa ici´on de da os, gene ando un n´ume o m´ınimo de comunicaciones ag egadas. Es o pe mi e consegui , po ejemplo, una e iciencia com- pa able a UPC educiendo incluso la complejidad de p og amaci´on [4]. Hi map se u iliza como capa de ejecuci´on en el sis ema de p og amaci´on pa alela ENVIRONMENT AGENT LEARNING AGENT M3 M4 M5 M0 M1 M2 Communica ion Module Si ua ion Awa eness & Rewa d Func ion Ac ion Rewa d & Senso iz. Communica ion Module Raw Senso iza ion Ac ions ODE Physics Module Rewa ds Ac ion Fea u e Ex ac ion Module Gene . S a e + Rewa d Lea ning Algo i hm Value Func ion ∑iɸiθi Decision Module Gene aliza ion Module i Fig. 1. Esquema de los ipos de agen es y su elaci´on en MARL-Ped. T asgo [17], que o ece una ap oximaci´on simila a los lenguajes PGAS. Hi map ex iende las uncionali- dades de c eaci´on de je a qu´ıas y de epa o de da os de o as biblio ecas o modelos de a ays dis ibuidos, po ejemplo HTAs [18] o Pa ay [19]. En e o as cosas pe mi e la u ilizaci´on de pol´ı icas de pa ici´on anspa en es e in e cambiables, egula es o i egu- la es, de inidas como m´odulos con un in e az com´un. Es o elimina la necesidad de oma decisiones sob e la g anula idad y sinc onizaci´on en di e en es ni eles je ´a quicos. Hi map ha sido ambi´en ex endido pa a sopo a es uc u as de da os como ma ices dispe - sas o g a os, usando la misma me odolog´ıa e in e - az [20]. III. MARL-Ped y Hi map A. MARL-Ped MARL-Ped es un sis ema mul iagen e pa a mod- elado y simulaci´on de pea ones que u iliza ap en- dizaje po e ue zo ( ein o cemen lea ning, RL) pa a ap ende el compo amien o indi idual de cada pea ´on (agen e) en un de e minado escena io (con- ges i´on, e acuaci´on de un ecin o ce ado, ci culaci´on po un pasillo con lujos de mo imien o con a - ios,...). El obje i o del algo i mo de ap endizaje RL consis e en calcula una unci´on de con ol (lla- mada unci´on de alo en el campo de RL) que in- dica ´a al pea ´on qu´e acci´on oma en cada momen o en unci´on del es ado local pe cibido. Exis en en MARL-Ped dos clases de agen es: los agen es pea ´on, que ejecu an los algo i mos de ap endizaje po e- ue zo y almacenan la unci´on de con ol ap endida, y el agen e en o no que ejecu a el sis ema ´ısico que simula a los pea ones en el escena io y que senso iza el es ado en el que se encuen a cada pea ´on den- o de es e escena io. El escena io es un mundo i - ual 3D en el que el mo o ´ısico Open Dynamic En- gine (ODE) se enca ga de simula las colisiones y las ue zas que mue en a los pea ones. En la Figu a 1 apa ece una desc ipci´on g ´a ica del sis ema. Es posible obse a en la Figu a 1 que an o los agen es pea ones (en la igu a “Lea ning Agen s”) como el agen e en o no (en la igu a “En i onmen agen ”) es ´an compues os de di e en es m´odulos un- cionales. Exis en dos modos de uncionamien o en MARL-Ped: modo de ap endizaje y modo de sim- ulaci´on. Ambos modos es ablecen el mismo ipo de comunicaci´on en e los agen es y el en o no. La ´unica di e encia es que en el modo de ap endizaje los algo- i mos de RL es ´an ac i os y la unci´on de con ol se a calculando inc emen almen e. El modo de uncionamien o es s´ınc ono y consis e en un ciclo cl´asico compues o de obse aci´on-acci´on- ecompensa. Conc e amen e el ciclo se compone de los siguien es pasos: 1. El agen e en o no consul a a ODE la si uaci´on din´amica de cada pea ´on que consis e en posici´on, elocidad, dis ancia a los npea ones m´as ce canos y dis ancia a los nobje os m´as ce canos. Si es amos en el modo ap endizaje, el agen e en o no p epa a una ecompensa pa a cada uno de los agen es pea ones en unci´on de a ios hechos:que el pea ´on haya llegado a su ob- je i o, que se haya chocado con a o o pea ´on u obje o, e c. 2. El agen e en o no ansmi e la in o maci´on del es ado y la ecompensa de cada agen e al sis- ema pa a que sea ecogida po los agen es. 3. Cada agen e ecibe la in o maci´on del en o no y p epa a con ella las ca ac e ´ıs icas espec´ı icas que de inen el es ado pa a el algo i mo de ap en- dizaje y la se˜nal de ecompensa. Ambas in- o maciones son usadas po el algo i mo de RL pa a modi ica la unci´on de con ol que ambi´en es ´a ges ionada po el agen e pea ´on (“Lea ning agen ” en la Figu a 1). En el modo de simu- laci´on, la in o maci´on del es ado si e pa a con- sul a di ec amen e ala unci´on de con ol mien- as que los algo i mos de RL es ´an desac i a- dos. 4. El agen e consul a a la unci´on de con ol la nue a acci´on que, en el es ado ac ual, se debe de ejecu a . Las acciones consis en en una mod- i icaci´on de la di ecci´on y apidez con la que se mue e el pea ´on. 5. Los agen es ansmi en las acciones al agen e en o no que es el enca gado de aduci las a ac- ciones ´ısicas que son ejecu adas po ODE en el en o no i ual. La comunicaci´on de da os en MARL-Ped se es ablece en e el agen e en o no y los agen es pea ones, no habiendo comunicaci´on en e los agen es pea ones. Exis e un doble lujo de da os, que se puede obse a en la Figu a 1. Un lujo co- munica los da os de senso izaci´on del es ado de cada agen e y la co espondien e ecompensa desde el en- o no has a cada uno de los agen es ( lechas de colo e de). O o lujo comunica la siguien e acci´on a e- aliza po cada uno de los agen es al en o no ( lechas de colo ama illo). Es e ciclo desc i o se ejecu a un n´ume o de eces que es a su ez un pa ´ame o de con- igu aci´on del sis ema. En el modo ap endizaje con decenas de agen es, es e ciclo puede epe i se desde cien os de miles de eces has a millones de eces. B. Hi map Hi map [4] es una biblio eca de unciones pa a la ges i´on y dis ibuci´on je ´a quica de es uc u as de da os en iempo de ejecuci´on. T abaja sob e a ays densos y ha sido ambi´en ex endida pa a sopo a es- uc u as de da os como ma ices dispe sas o g a os, usando la misma me odolog´ıa e in e az [20]. Se basa en un modelo SPMD (Single P og am Mul iple Da a) y en el pa adigma de paso de mensajes. Hi map de- ine a ias abs acciones pa a esc ibi p og amas pa - alelos que manejan es uc u as de da os dis ibuidas. La biblio eca se puede di idi en es pa es: B.1 M´e odos de iling De inici´on y manipulaci´on de a ays y iles. Es- os m´e odos se pueden usa de mane a independien e al es o de uncionalidades de Hi map, pa a mejo a la localidad en el c´odigo secuencial, as´ı como pa a gene a dis ibuciones de da os manualmen e pa a la ejecuci´on en pa alelo. Se de inen obje os pa a ep e- sen a los dominios de ´ındices de las es uc u as de da os de o ma compac a. Se de ine una clase de ob- je os denominada Tile que ep esen a la asociaci´on en e elemen os del espacio de ´ındices y los da os, y pe mi en el acceso o modi icaci´on de los mismos. Los iles pueden c ea se c ea se de o ma que en un p o- ceso s´olo se dispone localmen e de una pa e del espa- cio de ´ındices ob eni´endose la es uc u a dis ibuida. B.2 M´e odos de mapping Incluye m´odulos in e cambiables que imple- men an pol´ı icas pa a pa iciona dominios au- om´a icamen e, dependiendo de una opolog´ıa i - ual seleccionada en iempo de ejecuci´on. Pe mi en c ea obje os denominados Layou s que pueden se consul ados espec o a la pa e de un dominio de ´ındices que es asignada an o localmen e, como o a cualquie o o p oceso emo o. Adem´as, se es able- cen elaciones de ecindad en ´e minos de las eglas de la opolog´ıa i ual escogida. B.3 M´e odos de comunicaciones Es as unciones son una abs acci´on del modelo de paso de mensajes pa a comunica iles o pa es de iles en e p ocesado es i uales. Pe mi e c ea ob- je os que almacenan la in o maci´on necesa ia pa a empaque a e in e cambia los da os seleccionados en e p ocesado es. Hi map p o ee de m´ul iples in- e aces de c eaci´on que implemen an di e sos ipos de comunicaciones pun o-a-pun o, colec i as, o pa- ones m´as complejos compues os de m´ul iples co- municaciones de di e sa na u aleza o sob e di e - sos iles. Las in e aces de c eaci´on incluyen un ob- je o de ipo Layou , que es consul ado in e namen e pa a decidi qu´e iene que comunica se y a qui´en, gene ´andose au om´a icamen e la in o maci´on in e na necesa ia. Po an o, es os obje os se adap an ans- pa en emen e en el momen o de su c eaci´on a la pla a o ma de ejecuci´on y la dis ibuci´on de da os A P... A Pk-1 E Pk A P0 A P1 A A A A A A A A A A A A P0 E A A A P1 A A A P... A A A Pk A A A A A A A A A A A A A A A Fig. 2. Es uc u a gene al de la simulaci´on y el epa o de a eas en e p ocesado es en MARL-Ped o iginal (a iba) y as aplica Hi map (abajo). u ilizada. Los obje os de comunicaci´on son eu iliz- ables. El m´e odo que ealmen e ejecu a la comu- nicaci´on se puede in oca en cualquie momen o de- spu´es de su c eaci´on, an as eces como sea necesa io a lo la go de la aplicaci´on. In e namen e se basan en el es ´anda MPI, u ilizando ´ecnicas e icien es como la c eaci´on de ipos de da os de i ados, comunica- ciones as´ınc onas, e c. IV. Aplicaci´ on de la me odolog ´ ıa y ´ ecnicas de Hi map En es a secci´on se desc ibe c´omo aplica la me odolog´ıa y ´ecnicas p opias de Hi map a aplica- ciones de simulaci´on basadas en agen es, u ilizando MARL-Ped como caso de es udio. A. Cambios es uc u ales La es uc u a de la aplicaci´on MARL-Ped ha sido edise˜nada. La e si´on de Hi map aplica el concep o de a ays dis ibuidos pa a ag upa agen es en p o- cesos, en luga de u iliza un p oceso MPI pa a cada agen e, m´as o o pa a la simulaci´on del en o no. En la pa e supe io de la igu a 2 se ap ecia la dis- ibuci´on concep ual de la compu aci´on en MARL- Ped o iginal. Cada p oceso ejecu a el c´odigo de un agen e. El ´ul imo p oceso ejecu a el c´ompu o de la simulaci´on del en o no. Los obje os de clase RLA- gen yRLEn i onmen ienen un m´e odo que in e - namen e ejecu a epe i i amen e el bucle de simu- laci´on. Una p ime a decisi´on de dise˜no pa a la nue a e si´on es epa i los agen es en e los p ocesos disponibles sin ese a un p oceso pa a el en o no. El c´odigo del en o no lo ejecu a ´a uno de los p oce- sos que ambi´en iene agen es asignados ya que la compu aci´on p incipal de los agen es y del en o no se al e nan sin solapa se en el iempo. Hi map p o ee de las he amien as necesa ias pa a dis ibui equi a i amen e los agen es en e los p ocesos disponibles ( e la pa e de abajo en la igu a 2). Cada p oceso iene que pode ejecu a en cada i e aci´on de simulaci´on el c´odigo de a ios agen es, y en el caso del p oceso designado pa a ello, adem´as ejecu a el c´odigo del en o no. Po an o, el bucle de simulaci´on no puede es a den o de los ob- je os de agen e o en o no. Es necesa io edise˜na la aplicaci´on pa a que el bucle de simulaci´on lo ejecu e el p og ama p incipal, que debe i e a a su ez depen- diendo del n´ume o de agen es asignados al p oceso. Pa a ello se elimina el bucle de simulaci´on den o del co espondien e m´e odo de la clase de agen es y en o no. Se ans o man los m´e odos a los que se in- ocaba den o de ese bucle en m´e odos p´ublicos. Y se aslada la l´ogica de con ol de dichas in ocaciones al nue o bucle de i e aciones de simulaci´on en el p o- g ama p incipal. Se ealiza lo mismo con el en o no, odeando la l´ogica de con ol del mismo, aho a en el p og ama p incipal, con un condicional pa a que s´olo sea ejecu ado po un p oceso. Hi map dis ingue pa a cada g upo de p ocesos a uno de ellos como el l´ıde del g upo. Es e p oceso puede iden i ica se a si mismo a a ´es de una llamada a una unci´on, y po an o es el seleccionado pa a ejecu a la l´ogica del en o no. B. A ays dis ibuidos y pa ones de comunicaci´on Las comunicaciones basadas en MPI de MARL- Ped o iginal se han subs i uido po el manejo de a - ays dis ibuidos con Hi map. Pa a ello, las es uc- u as de da os implicadas en las comunicaciones se subs i uyen po es uc u as de ipo Hi Tile. La es- uc u a Hi Tile debe especializa se al comienzo del p og ama seg´un los di e en es ipos de da os de cada a ay que se aya a decla a y maneja con Hi map. En ase de inicializaci´on del p og ama se c ean los a ays dis ibuidos y obje os de ipo Hi Com con las especi icaciones de las comunicaciones que se ´an in- ocadas en las i e aciones del bucle de simulaci´on. Pa a las se˜nales de con ol s´olo es necesa ia una a i- able de ipo en e o en cada p oceso, independien e- men e del n´ume o de agen es que se le asignen. Pa a cada lujo de da os en e el agen e que ges iona el en- o no y los agen es pea on, se decla an dos a ays dis- ibuidos con un dominio de ´ındices igual al n´ume o de agen es pea ´on. En uno se u iliza una pol´ı ica de dis ibuci´on que epa e y asigna los elemen os de o ma equi a i a en e los p ocesos. En el o o se u i- liza una pol´ı ica que dis ibuye odos los elemen os al p oceso que ejecu a el en o no. Hi map pe mi e con una ´unica llamada a una unci´on cons ui un obje o Hi Com que implemen a un pa ´on que e- dis ibuye los da os desde un a ay dis ibuido con una pol´ı ica cualquie a, a los co espondien es ele- men os locales o emo os de o o a ay con el mismo dominio, pe o dis ibuido con o a pol´ı ica di e en e. Es a ´ecnica pe mi e cons ui obje os de comuni- caci´on que mo e ´an de o ma anspa en e los da os en e las dos copias de cada a ay, la ealmen e dis- ibuida y la que iene odo el dominio en el p oceso del en o no. El pa ´on de comunicaci´on se adap a a los esul ados de las pol´ı icas de pa ici´on inde- pendien emen e del n´ume o de agen es y p ocesos. Es e mecanismo soluciona de una o ma ´unica la con- s ucci´on de los lujos de comunicaci´on necesa ios. V. Es udio expe imen al Es a secci´on desc ibe el es udio expe imen al eal- izado pa a comp oba las en ajas de aplica Hi map en p og amas de simulaci´on basados en agen es como MARL-Ped. El es udio se ocaliza en mos a la mayo capacidad de escalado en cuan o a n´ume o de agen es, y la p edic ibilidad de los pa ´ame os de ejecuci´on pa a ob ene un mayo endimien o. A. Me odolog´ıa de expe imen aci´on En es e es udio expe imen al se ob ienen medi- das de iempos de ejecuci´on de las dos e siones de c´odigo; MARL-Ped o iginal y la e si´on u ilizando Hi map. Se p esen an los mismos en ´e minos de escalabilidad. En es e a ´ıculo nos ocalizamos en la pa e del p oceso de ap endizaje, que es compu acional- men e la m´as cos osa, y que no implica ope a- ciones de en ada/salida du an e la ase de com- pu aci´on/comunicaci´on. Los c´odigos han sido in- s umen ados pa a medi el iempo de ejecuci´on de cada p oceso dis ibuido desde el momen o en que comienza la inicializaci´on de es uc u as elacionadas con el pa alelismo (MPI o Hi map), has a el mo- men o en que e mina la ejecuci´on del ap endizaje, jus o an es de comenza a esc ibi en iche os los e- sul ados. De las mediciones ob enidas en cada p o- ceso, se u iliza como esul ado de la medida el iempo mayo , es deci , el del p oceso que ha a dado m´as en e mina . Cada expe imen o se epi e a ias eces pa a pode comp oba ambi´en la a iabilidad en los esul ados. Dado que los iempos de ejecuci´on de un en e- namien o comple o son ex emadamen e la gos, pa a pode explo a un espacio de b´usqueda amplio en cuan o a pa ´ame os de ejecuci´on, se ha limi ado el p og ama a la ejecuci´on de s´olo 100 i e aciones de en enamien o en odos los casos. Como se e ´a en los esul ados, es e n´ume o de i e aciones p oduce una ca ga y un n´ume o de ases de comunicaci´on y sinc onizaci´on su icien emen e ep esen a i os. En odos los casos se ejecu a un escena io de ejemplo u ilizado y alidado en abajos an e io es [3]. El escena io ep oduce un dilema de na egaci´on cl´asico en din´amica de pea ones denominado “sho es pa h s quickes pa h”. En es e escena io un g upo de pea ones debe pasa de una habi aci´on a un luga obje i o si uado ue a de ´es a. Exis en dos salidas y una es ´a mas ce ca del obje i o que la o a. Los agen es deben ap ende que si odos in en an sali po la pue a m´as ce cana, se o ma ´a una aglom- e aci´on que alen iza ´a la e acuaci´on. Una soluci´on ´op ima es la di isi´on del g upo en pea ones que eli- gen la salida con el camino m´as co o y agen es que eligen la o a salida, lo que p opo ciona ´a una e ac- uaci´on m´as ´apida. En la con igu aci´on seleccionada se han si uado 28 agen es en una habi aci´on ec angula de longi ud de 18 m. con dos salidas posibles de 1 m.de anchu a que di icul a el paso simul ´aneo de m´as de un pea ´on. El obje i o de los agen es es alcanza un pun o de encuen o al o o lado de las salidas. Los c´odigos se han ejecu ado en di e en es pla a o mas mul ico e donde las comunicaciones son menos cos osas y des acan m´as los po enciales o e - heads asociados, en e o as cosas, a los cambios en la es uc u a de ejecuci´on, al manejo de las es uc- u as p opias de Hi map, o a los c´alculos y decisiones sob e las comunicaciones. En es e abajo mos amos esul ados ob enidos en una m´aquina denominada Chime a. Tiene dos CPUs In el E5-2620 2, a 2˙ 10 GHz, con un o al de 12 co es eales, con la opci´on de hype h eading ac- i ada. Dispone de 8 Gb de memo ia DDR4. El sis ema ope a i o es Cen OS 7.0 1406 x64. El com- pilado u ilizado es GCC 4.8.2 con el lag de op i- mizaci´on -O3. La implemen aci´on de MPI u ilizada es Mpich 3.1.3. B. Escalabilidad en n´ume o de agen es Uno de los obje i os de es e abajo es consegui una mayo escalabilidad en ´e minos de n´ume o de agen es, g acias a la es a egia de asocia a ios agen es a un mismo p oceso con Hi map. El p ime es udio ealizado comp ueba expe imen almen e la di e encia de escalabilidad en e la e si´on o iginal de MARL-Ped y la e si´on que u iliza Hi map. Los p og amas se han ejecu ado en ase de en enamien o ijando el n´ume o de p ocesos MPI al n´ume o de co es disponibles en la m´aquina, aumen ando p o- g esi amen e el n´ume o de agen es po encima de ese n´ume o. Los esul ados se mues an en la igu a 3. En el caso de MARL-Ped o iginal, el n´ume o de p o- cesos MPI necesa ios c ece con el n´ume o de agen es (siendo el n´ume o de agen es m´as uno). La es uc- u a de es as aplicaciones de simulaci´on, que u ilizan comunicaciones colec i as con pun os cla os de sin- c onizaci´on global al ededo de la ejecuci´on del mo o de simulaci´on, no p esen an la p opiedad de pa allel slackness, que apa ece en cie as aplicaciones cuando a ios p ocesos asignados al mismo elemen o de p o- ceso solapan al e na i amen e ases de compu aci´on y comunicaci´on. En los esul ados se obse a c´omo el sob ecos e de ealiza o e subsc ibing (lanza m´as p ocesos que elemen os de p oceso disponibles) iene un impac o nega i o en el endimien o y la escala- bilidad de la aplicaci´on. En la m´aquina Chime a, con 12 co es y que iene ac i ado hype h eading, el e ec o es mucho m´as no able a pa i de 24 agen es, donde MARL-Ped ya u iliza 25 p ocesos MPI. La o ma en los que los p ocesos se o an en los plan- i icado es adquie e ele ancia. Po ello se obse an mayo es di e encias en e los iempos de ejecuci´on m´ınimos y m´aximos. La e si´on que u iliza Hi map, man iene una buena escalabilidad, ya que limi a el n´ume o de p ocesos y ejecu a secuencialmen e den- o de cada uno el c´odigo de a ios agen es de una o ma m´as e icien e. 0 50 100 150 200 250 300 350 400 450 500 12 14 16 18 20 22 24 26 28 30 Time (seconds) Numbe o agen s Execu ion ime s numbe o agen s (Chime a) MARL-Ped min MARL-Ped a g MARL-Ped max Hi map 12 p oc min Hi map 12 p oc a g Hi map 12 p oc max Fig. 3. Tiempos de ejecuci´on en elaci´on al n´ume o de agen es. La g ´a ica mues a el iempo de ejecuci´on de 100 i e aciones de en enamien o pa a un n´ume o c ecien e de agen es. En el caso MARL-Ped o iginal el n´ume o de p ocesos c ece con el n´ume o de agen es. En el caso de MARL-Ped+Hi map el n´ume o de p ocesos MPI es ijo, e igual al n´ume o de elemen os de p oceso (co es) eales disponibles. 50 100 150 200 250 300 350 0 5 10 15 20 25 Time (seconds) Numbe o p ocesses execu ing agen s Execu ion ime s p ocesses (Chime a) 28 Agen s Hi map 28 Agen s Hi map 28 Agen s Hi map 28 Agen s Hi map 28 Agen s Hi map 28 Agen s Hi map MARL-Ped a g Fig. 4. Tiempos de ejecuci´on en elaci´on al n´ume o de p ocesos pa a un n´ume o de agen es ijo. La g ´a ica mues a el iempo de ejecuci´on de 100 i e aciones de en enamien o. En el caso de MARL-Ped o iginal el n´ume o de p ocesos MPI depende po dise˜no del n´ume o de agen es y es igual a 29. Pa a MARL-Ped+Hi map se mues an a ias l´ıneas co espondien es a a ios expe imen os consecu i os, pa a mos a la a iabilidad de los esul ados. C. Impac o del n´ume o de p ocesos En es a secci´on se es udia el impac o de modi ica el n´ume o de p ocesos, y po an o la dis ibuci´on de agen es po p oceso, en MARL-Ped+Hi map. En la igu a 4 se obse an los esul ados ob enidos pa a 28 agen es. En odos los casos los esul ados en iem- pos de ejecuci´on de MARL-Ped+Hi map son mejo es que en MARL-Ped o iginal debido al e ec o de o e - subsc ip ion comen ado en la secci´on an e io . Se obse a que los esul ados u ilizando Hi map mejo an lige amen e al i epa iendo los agen es en- e un n´ume o peque˜no pe o c ecien e de p ocesos, ya que aumen a el pa alelismo. Al supe a el n´ume o de p ocesos al n´ume o de co es eales (sin con a con hype h eading), los esul ados empeo an y se uel- en m´as ines ables, ya que apa ecen e ec os nega- i os de i ados del o e subsc ip ing. Las pol´ı icas de plani icaci´on comienzan ambi´en a hace los e- sul ados m´as imp edecibles. En algunos casos se ob- iene iempos an buenos como an es de comenza el o e subsc ip ing, pe o en muchos o os casos em- peo an. Al supe a el l´ımi e del n´ume o de h eads disponibles con ando con hype h eading los esul a- dos, como e a de espe a empeo an no ablemen e. Es os esul ados indican que en MARL- Ped+Hi map el n´ume o de p ocesos a escoge pa a el en enamien o es p edecible. Los iempos de ejecuci´on son meno es y m´as es ables cuando se u iliza un n´ume o de p ocesos igual al n´ume o de elemen os de p oceso eales, sin ene en cuen a la opci´on de hype h eading. VI. Conclusiones En es e a ´ıculo se p esen a la aplicaci´on de las ´ecnicas y he amien as de la biblio eca de manejo de a ay dis ibuidos Hi map a la simulaci´on basada en agen es. Se u iliza la aplicaci´on mul i-agen e pa a simulaci´on de pea ones MARL-Ped como caso de es- udio. Se mues a c´omo la u ilizaci´on de a ays dis- ibuidos y pol´ı icas de pa ici´on au om´a icas pe - mi e ob ene una mayo p oduc i idad y escalabili- dad, g acias a la capacidad de Hi map de dis ibui la ca ga en e p ocesos de o ma anspa en e al p o- g amado . MARL-Ped+Hi map pe mi e hace sim- ulaciones con un n´ume o mucho mayo de agen es man eniendo iempos de ejecuci´on es ables y p edeci- bles. El abajo u u o incluye ex ende la aplicaci´on de Hi map a o os ipos de aplicaciones de simulaci´on elacionadas; in es iga la po encial eliminaci´on de cuellos de bo ella en las ases de simulaci´on; y u i- liza la nue a e si´on de MARL-Ped+Hi map pa a p o undiza en el es udio de la calidad y esul ados de las simulaciones de muchedumb es con un n´ume o mucho mayo de agen es. Ag adecimien os Es a in es igaci´on ha sido pa cialmen e inanciada po el Minis e io de Econom´ıa y Compe i i idad (Spain) y el p og ama ERDF de la Uni´on Eu o- pea: P oyec o HomP og-He Sys TIN2014-58876-P, P oyec o TIN2015-66972-C5-5-R y COST P og am Ac ion IC1305: Ne wo k o Sus ainable Ul ascale Compu ing (NESUS). Re e encias [1] M.J. Woold idge and N.R. Jennings, “In elligen agen s: heo y and p ac ice,” The Knowledge Enginee ing Re- iew, ol. 10, pp. 115–152, 1995. [2] M. Woold idge, Mul i-Agen Sys ems 2nd Edi ion, chap- e In elligen Agen s, pp. 3–50, MIT P ess, 2013. [3] F ancisco Ma inez-Gil, Miguel Lozano, and Fe nando Fe n´andez, “MARL-ped: A mul i-agen ein o cemen lea ning based amewo k o simula e pedes ian g oups,” Simula ion Modelling P ac ice and Theo y, ol. 47, pp. 259–275, 2014. [4] A. Gonzalez-Esc ibano, Y. To es, J. F esno, and D.R. Llanos, “An ex ensible sys em o mul ile el au oma ic da a pa i ion and mapping,” IEEE T ansac ions on Pa allel and Dis ibu ed Sys ems, ol. 25, no. 5, pp. 1145– 1154, 2014. [5] D. Helbing and P. Moln´a , “Social o ce model o pedes- ian dynamics,” Phys. Re . E, ol. 51, pp. 4282–4286, 1995. [6] V. J. Blue and J. L. Adle , “Cellula au oma a mic osim- ula ion o modeling bi-di ec ional pedes ian walkways,” T anspo a ion Resea ch Pa B: Me hodological, ol. 35, no. 3, pp. 293–312, 2001. [7] R. L. Hughes, “The low o human c owds,” Annu. Re . Fluid Mech., ol. 35, pp. 169–182, 2003. [8] C. Reynolds, “S ee ing beha io s o au onomous cha - ac e s,” in Game De elope s Con e ence, San F ancisco, Cali o nia., 1999, pp. 763–782, Mille F eeman Game G oup. [9] F ancisco Ma inez-Gil, Miguel Lozano, and Fe nando Fe n´andez, “Mul i-agen ein o cemen lea ning o sim- ula ing pedes ian na iga ion,” in Adap i e and Lea n- ing Agen s: In e na ional Wo kshop, ALA 2011, Held a AAMAS 2011, Taipei, Taiwan. 2012, pp. 54–69, Sp inge Be lin Heidelbe g. [10] M. Lozano, P. Mo illo, J. M. O du˜na, V. Ca e o, and G. Vigue as, “A new sys em a chi ec u e o c owd sim- ula ion,” J. Ne wo k and Compu e Applica ions, ol. 32, no. 2, pp. 474–482, 2009. [11] G. Vigue as, M. Lozano, J. M. O du˜na, and F. G imaldo, “A compa a i e s udy o pa i ioning me hods o c owd simula ions,” Appl. So Compu ., ol. 10, no. 1, pp. 225–235, Jan. 2010. [12] Guille mo Vigue as, Juan M. O du˜na, and Miguel Lozano, “A ead-copy upda e based pa allel se e o dis ibu ed c owd simula ions,” The Jou nal o Supe - compu ing, ol. 64, no. 1, pp. 156–166, 2013. [13] Guille mo Vigue as, Juan M. O du˜na, Miguel Lozano, and Y on J´egou, “A scalable mul iagen sys em a chi ec- u e o in e ac i e applica ions,” Science o Compu e P og amming, ol. 78, no. 6, pp. 715 – 724, 2013, Special sec ion: The P og amming Languages ack a he 26 h {ACM}Symposium on Applied Compu ing (SAC 2011); Special sec ion on Agen -o ien ed Design Me hods and P og amming Techniques o Dis ibu ed Compu ing in Dynamic and Complex En i onmen s. [14] E. Yilmaz, V. Isle , and Y. Y. Ce in, “The i ual ma a hon: Pa allel compu ing suppo s c owd simula- ions,” IEEE Compu e G aphics and Applica ions, ol. 29, no. 4, pp. 26–33, 2009. [15] B.L. Chambe lain, D. Callahan, and H.P. Zima, “Pa allel p og ammabili y and he chapel language,” In . J. High Pe o m. Compu . Appl., ol. 21, no. 3, pp. 291–312, aug 2007. [16] D. A. Mall´on, A. G´omez, J. C. Mou i˜no, G. L. Taboada, C. Teijei o, J. Tou i˜no, B. B. F aguela, R. Doallo, and B. Wibecan, “Upc pe o mance e alua ion on a mul i- co e sys em,” in P oceedings o he Thi d Con e ence on Pa i ioned Global Add ess Space P og aming Mod- els, New Yo k, NY, USA, 2009, PGAS ’09, pp. 9:1–9:7, ACM. [17] A u o Gonzalez-Esc ibano and Diego R. Llanos, “T asgo: a nes ed-pa allel p og amming sys em,” The Jou nal o Supe compu ing, ol. 58, no. 2, pp. 226–234, 2011. [18] Basilio B. F aguela, Ganesh Bikshandi, Jia Guo, Ma ´ıA J. Ga za ´aN, Da id Padua, and Ch is oph Von P aun, “Op imiza ion echniques o e icien h a p o- g ams,” Pa allel Compu ., ol. 38, no. 9, pp. 465–484, sep 2012. [19] Yi eng Chen, Xiang Cui, and Hong Mei, “Pa ay: A uni- ying a ay ep esen a ion o he e ogeneous pa allelism,” SIGPLAN No ., ol. 47, no. 8, pp. 171–180, eb 2012. [20] J. F esno, A. Gonzalez-Esc ibano, and D.R. Llanos, “Blending ex ensibili y and pe o mance in dense and spa se pa allel da a managemen ,” IEEE T ansac ions on Pa allel and Dis ibu ed Sys ems, ol. 25, no. 10, pp. 2509–2519, 2014.