PDF de programación - Tesis: Miguel Castro - Balance Dinámico de Carga en un Sistema Paralelo con Memoria Distribuida

».FB0000014126CtSÍK»DtINVtSlItACItRY■&ESTU0I6S*v»*ZaMIIILI.P.N.■IBLIOTEOA"^FNIEAIAELÉCTRICACENTRODEINVESTIGACIÓNYDEESTUDIOSAVANZADOSDELI.P.N.UNIDADZACATENCODEPARTAMENTODEINGENIERÍAELÉCTRICASECCIÓNCOMPUTACIÓNBalanceDinámicodeCargaenunSistemaParaleloconMemoriaDistribuidaTesisquepresentaMiguelAlfonsoCastroGarcíaParaobtenerelGradodeMaestroenCienciasEnlaespecialidaddect!,T*9ot'"UsuucimytifSTUOies*VA«ZA80SBELIngenieríaEléctricaI.P.N■'■LlOTtOA'■"KNIEAIAELECTASDra.GracielaRománAlonsoDirectorDr.AdrianodeLucaPennacchiaCodirectorMéxico,D.F.,Mayodel2001CINVESTAV¡IPNADQUISICIÓNDELIBROS■'■LlOTío.'^NIEK,AELECTA,?,ÍNDICERESUMEN4INTRODUCCIÓN5CAPITULO1ASIGNACIÓNYBALANCEDINÁMICODECARGA71.1ElementodeInformación81.1.1.Cuantificaciondelacarga81.1.2.Informaciónglobaloparcial91.2ElementodeControl91.3EjemplosdeAlgoritmosdeAsignaciónDinámicadeCarga111.3.1Algoritmodetipoglobalcentralizado121.3.2Algoritmodetipoglobaldistribuido131.3.3Cíclico141.3.4Vecinosdirectos151.3.5Vectorial16CAPITULO2PLATAFORMAPROPUESTAPARALAIMPLEMENTACIÓNYESTUDIODEALGORITMOSDEREPARTICIÓNDINÁMICA2.1MódulosBásicos182.1.1ElmódulodeinformaciónA192.1.2ElmódulocuantificadorB202.1.3ElmódulodeasignaciónC212.2DescripcióndelaPlataforma222.2.1Inicialización222.2.2Administradordeinformación232.2.3Contabilizadordecarga232.2.4Asignadordeprocesos242.2.4.1Mecanismosinrechazo262.2.4.2Mecanismoconrechazo262.3ImplementacióndelosAlgoritmosdeAsignaciónennuestraplataforma262.3.1.Algoritmoglobalcentralizado262.3.2.Algoritmoglobaldistribuido282.3.3.Algoritmocíclico302.3.4.Algoritmodevecinosdirectos302.3.5.Algoritmovectorial32CAPITULO3PROGRAMASEJECUTADOS3.1GrafosdeCreacióndelosProgramasdePrueba353.2PrimerGrupodeProgramasdePrueba:ProcesosIntercambiandounsoloMensaje393.3SegundoGrupodeProgramasdePrueba:ProcesosIntercambiandoVariosMensajes41CAPITULO4RESULTADOS4.1EjecucióndeProgramasdondelosProcesosIntercambianunsoloMensaje474.2EjecucióndeProgramasdondelosProcesosIntercambianVariosMensajes514.3AjustedeParámetrosparaunAlgoritmodeAsignaciónDinámica57CAPITULO5CONCLUSIONESYPERSPECTIVAS60ANEXOSAnexoAPVM62AnexoBProgramadeÁrbolCompletoconH=7yK=264AnexoCProgramadeÁrbolIrregularconN=769BIBLIOGRAFÍA73CiBTM»tIMVtSlIlACIMYtiESTUDIASavavza&OIl£LI.P.N.■IBLIOTCOA"^ENIERIAELÉCTRICA3RESUMENEstatesisesunacontribucióndentrodeláreadelossistemasdistribuidosenfocándoseenlaproblemáticadelaasignacióndinámicadecarga.Losalgoritmospropuestospararesolveresteproblemaconsideranunconjuntodeprocesadoresenloscualestienenquedistribuirlacarga(procesos),detalformaqueelrendimientodelsistemayeltiempodeejecucióndelasaplicacionesmejoren.Unodelosobjetivosdeestosalgoritmospuedeserlaasignaciónequitativadetrabajo,tomandoencuentacriteriosdebalancedecarga.Paraapoyarelestudioylaevaluacióndelrendimientodelosalgoritmosdeasignacióndinámicadecarga,enestatesisseproponeunaplataformadeexperimentación.EstaplataformafuedesarrolladautilizandolaherramientaPVMlacualpermitióimplantarloselementosdecontrolydeinformaciónquerigenelfuncionamientodecincoalgoritmosdeasignacióndecarga:algoritmocentralizado,cíclico,distribuido,vecinosdirectosyalgoritmovectorial.Lasaportacionesprincipalesdelaplataformapropuesta,sonlassiguientes:•Facilitaelestudiodelcomportamientodeunalgoritmoparticulardeasignacióndinámicadeprocesos,permitiendoelajustedesusparámetros.•Permiteobtenerunacomparaciónderendimientoentrevariosalgoritmosdeasignacióndinámica.•Posibilitaimplantaryevaluarnuevaspropuestasdealgoritmosdeasignacióndinámica.•Permiteelegirunalgoritmodeasignaciónquereduzcaeltiempodeejecucióndeunaaplicaciónenparticular.Losresultadosobtenidossebasaronprincipalmenteenlaejecucióndeunconjuntodeprogramasdepruebadetiposintético(suobjetivoesgenerarcargasobreelsistema).Losexperimentosseefectuaronsobreuncúmulocon9procesadoresPentiumlll-LINUX,interconectadosbajounatopologíatipobus.«■;■•«ift'Uiitu-ruTiiíSTuniis.vw.0flmI.P.N.■•■LlOTeoA'^ENIEAIAEIECTAICIINTRODUCCIÓNNoesraroescucharlafrase"Doscabezaspiensanmejorqueuna",apartirdelafraseanterior,esfácilpensarque2computadorastendránunamejoreficienciaorendimientoqueunasola.Porloqueuntrabajoejecutadoendoscomputadorassedeberíaejecutarenlamitaddeltiempo.Pero,¿quésepuededeciracercade3,10,100ó1000computadoras?,¿Tendránmejorrendimientoquedos?.EstatesissituadadentrodeláreadelosSistemasParalelosyDistribuidos,presentaunestudioacercadelaasignacióndinámicadecarga.Elproblemadedistribuirequitativamenteprocesosylaactividaddecomunicaciónatravésdeunareddecomputadorasafindequeningúndispositivoestésobrecargado,puedeentendersecomoBalancedeCarga.Elbalancedecargageneralmenteesconsideradodentrodeunalgoritmodeasignación.Cuandolaasignacióndeprocesosserealizaentiempodeejecuciónsehabladeasignacióndinámicadecarga,estaesespecialmenteimportanteparalossistemasdondeesdifícilpredecirelnúmerodepeticionesqueseránenviadasaunservidor[1],asícomolacantidaddetrabajodevariosusuarios.Pararesolverelproblemadeladistribuciónsehanpropuestociertosalgoritmosdeasignacióndinámica[8],loscualesentiempodeejecucióntratandedecidirsiciertoprocesooprocesosseránejecutadosdeformalocaloserántransferidoshaciaotrosprocesadoresdelsistema[21,8,4,7].Unejemploprácticodebalancedinámico,esenlosWebServers(Figura0),endondesiunservidorcomienzaasaturarse,laspeticionessonredireccionadasaotroservidorconmáscapacidad.Figura0.RedireccionamientodePeticionesenWebServers5Alafechavariosalgoritmossehanpropuestoparalaasignacióndeprocesos.Granpartedeellos,hansidomásbiendetipoestático,loscualesanalizanelusodelosrecursos(memoria,cpu)entiempodecompilaciónydecidenunaasignacióndelosprocesossobrelosprocesadores,antesdecomenzarlaejecución[15,18,20,17].Otrosestudiosdetipodinámico,sehanencaminadoalavariaciónyajustesdeparámetrosenlasaplicaciones,medianteunanálisisdecostosdeejecuciónlocaldeprocesoscontracostosdecomunicaciónentreprocesos[9,6,2].Enestatesissepresentalarealizacióndeunaplataformaparaelestudioycomparacióndealgoritmosdeasignacióndinámicadeprocesos,utilizandolaherramientaPVM[3].Despuésdeimplantar5algoritmoscondiferentescaracterísticasencuantolaasignacióndecargayelmanejodelainformación,seobtuvounacomparacióndesusrendimientos,mediantelaejecucióndeunconjuntodeprogramasdepruebasintéticos.Losresultadosqueguiaronnuestracomparaciónobtenidosparacadaprograma,básicamenteeseltiempodeejecución,aunquetambién,esposibleobtenerelfactordeaceleración,elnúmerodeprocesadoresusadosyelnúmerodeprocesosejecutadosporcadaprocesador.LaOrganizacióndeestaMemoriaeslasiguiente:EnelCapítuloI,sepresentalaproblemáticadelaAsignaciónyBalanceDinámicodeCarga.EnelCapítuloII,sedescribenlos5algoritmosdeAsignaciónDinámica(Centralizado,Distribuido,Cíclico,VectorialyVecinosDirectos)estudiados.LosprogramassintéticosdepruebasondescritosenelCapítulo3,presentandodespuéslosresultadosobtenidos.Porúltimo,sepresentanlasconclusionesylosanexosreferentesalaherramientaPVMyalgunosprogramasdeprueba.CAPITULO1ASIGNACIÓNYBALANCEDINÁMICODECARGAEstudiosenlaactualidad[22,23],hanreflejadoqueensistemasaloscualesseleshaaplicadounatécnicadebalancedecargasobresusprocesos,eltiempototaldeejecucióndelsistemaesreducidoalamitaddeltiempoquetomaríaejecutarlosinelbalance.Pormencionarunejemplo,lasimulacióndeunapartículadeunacélulaentresdimensionesendondeeltiempodecómputopararealizarestasimulaciónesdealrededorde4mesessobreunamáquinaCray,mTD3con256procesadores,aplicandociertosalgoritmosdebalancedecarga,eltiempoesreducidoalamitad[4].Laasignacióndecargapuedeserdedostipos:•AsignaciónEstática•AsignaciónDinámicaLaasignaciónestáticadecargaseaplicacuandoenunsistemasepuedeestimarlautilizacióndelosrecursos(usodeprocesadorydecomunicaciones),conociendocuántosprocesosseejecutarán,lasrelacionesdecomunicaciónydeprecedencia.Laasignacióndelosprocesosdelaaplicaciónsobrelosprocesadores,sedecidedirectamenteantesdecomenzarlaejecuciónysonejecutadosdeinicioafinenelprocesadorcorrespondiente,independientementedelavariacióndelacargaenelsistema.Estetipodeasignaciónestáticanosiempreeseladecuado,yaquesilosprocesosseejecutanenunsistemamultiusuarioelestadodecargadelsistemapuedevariardurantelaejecución.Enestecasonosepuedehacernadahastaquetodoslosprocesosterminen.Porelcontrario,enlaasignaciónybalancedinámicodecargalaasignacióndeprocesossobrelosprocesadoressedecideatiempodeejecución,considerandolacargaactualdelsistemacomolautilizacióndelosprocesadoresolacantidaddemensajesenlascolasdeentrada/salida.Paralarealizacióndecualquiertécnicadeasignaciónybalancedinámico,sonnecesariosdoselementos(Figura1):1.Informaciónrelacionadaalestadodecargadelsistema(ElementodeInformación).2.Alguienqueconociendolainformacióndelacargaglobaloparcialasignemáscargaalosprocesadoresmenoscargadosyporelcontrario,evitemáscargadeprocesamientoalosqueesténmásocupados(Elementode_....ElementodeInformación^~~ElementowdeControl4I-:wx.■m*Figura1.MódulosbásicosenlaAsignaciónDinámica.Enlasecciónsiguientesepresentanmásadetalledichoselementos.1.1ElementodeInformaciónDospreguntasimportantesseplanteanrespectoaesteelemento:¿cómosecuantificaelestadodecargadelosprocesadores?y¿cómoseestimaelestadodecargadelsistema?.Pararesponderaesaspreguntas,unproceso(ejecutadosobrecadaprocesador)seponeenmarchaconlatareadeintercambiarinformaciónconotrosprocesadoresenelsistema.Paraobtenerlainformaciónsobreelestadodecargadelsistema,sonnecesariasdoscosas,primerocuantificarlacargadecadaunodelosprocesadoresparaobtenersusestadosdecargalocales.Posteriormente,enbaseadichosestados,recolectarunainformaciónglobaloparcialdelsistema,paraquesepuedadecidirellugarmásadecuadodeasignacióndelosprocesos.1.1.1CuantificacióndelacargaExistendiversasformasdepodercuantificarlacargaenunprocesadoronodo,unaaproximaciónpuedeserconsiderandoelnúmerototaldeprocesossobreunprocesador(loscualespuedenestarenejecuciónolistosparaserejecutados),otramedianteelporcentajedeutilizacióndelCPUotomandolalongituddelacoladeE/S.Laprimeraformareferenteacontabilizarelnúmerototaldeprocesos,eslaqueseutilizóenlaconstruccióndelaplataformapropuesta.8Paramanteneractualizadounelementodeinformación,sehaceusodelconceptodefrecuenciadecuantificación,lacualesunparámetroqueindicacadacuántossegundossedebecuantificarlacargadeunprocesadorparaverificarsisuestadod