Estrategias de asignación de programas en computadores paralelos

Résumé

EL PRESENTE TRABAJO SE CENTRA EN EL ESTUDIO DEL PROBLEMA DEL "MAPPING", ES DECIR, EN DETERMINAR LA ASIGNACION DE LAS TAREAS DE UN PROGRAMA A LOS PROCESADORES DEL COMPUTADOR PARALELO. SE ANALIZAN LOS DISTINTOS MODELOS Y SOLUCIONES PROPUESTAS EN LA LITERATURA, Y A PARTIR DE ESE ANALISIS, SE PROPONE UN CONJUNTO DE NUEVAS ESTRATEGIAS PARA LA RESOLUCION DEL MENCIONADO PROBLEMA. LAS ESTRATEGIAS HAN SIDO DISEÑADAS CON OBJETO DE PROPORCIONAR BUENAS ASIGNACIONES EN TIEMPOS RAZONABLES, DE FORMA QUE SEAN APLICABLES PARA CUALQUIER PROGRAMA MODELABLE COMO UN TIG Y PARA CUALQUIER SISTEMA PARALELO HOMOGENEO CON RED DE INTERCONEXION DIRECTA O INDIRECTA. LA BASE DE LAS ESTRATEGIAS LA CONSTITUYE UNA FASE DE CONTRACCION REALIZADA MEDIANTE UNA HEURISTICA MIXTA DE AGRUPACION Y REASIGNACION DE LA QUE SE DEMOSTRO SU EFICIENCIA COMPARANDOLA CON UN METODO OPTIMO Y CON OTRAS HEURISTICAS DE LA LITERATURA. EN EL SUPUESTO DE SISTEMAS CON REDES DIRECTAS SE DESARROLLARON NUEVAS HEURISTICAS PARA REALIZAR UNA FASE ADICIONAL DE ASIGNACION FISICA Y SE COMPARO TAMBIEN LA EFICIENCIA DE LAS MISMAS. EN ESTE CASO SE FORMULARON DOS ESTIMADORES TEORICOS QUE ACOTAN EL COSTE EN EL QUE VAN A INCURRIR LAS DISTINTAS HEURISTICAS DE ASIGNACION FISICA. FINALMENTE, SE PRESENTAN LOS RESULTADOS DE UN EXPERIMENTO REALIZADO PARA CORROBORAR EL GRADO DE CORRELACION EXISTENTE ENTRE FUNCION DE COSTE Y TIEMPO DE EJECUCION.