Resumen:
El problema de mapping surge en el contexto de la programación paralela, y fue definido por S. Bokhari en 1981. Una instancia de este problema está dada por un grafo de tareas y un grafo de procesadores, con igual número de nodos. En el primero, los nodos representan las tareas y los ejes indican pares de tareas que se deben comunicar, mientras que el grafo de procesadores representa la arquitectura paralela (los nodos indican los procesadores y los ejes unen pares de procesadores conectados). El objetivo del problema es asignar cada tarea a un solo procesador (cada procesador puede recibir sólo una tarea), de modo tal de maximizar los pares de tareas vecinas que se asignan sobre procesadores conectados. Se presenta una formulación del problema como un problema de programación lineal entera, en base a la cual se realiza un estudio poliedral, con el objetivo principal de implementar un algoritmo branch&cut para su resolución. Se encuentra un conjunto de desigualdades válidas para el poliedro asociado, que constituyen la base fundamental de un algoritmo de este tipo. Se halla también la dimensión del poliedro, lo cual permite decidir la calidad de las desigualdades válidas, logrando probar que algunas de ellas definen facetas. Se describe la implementación del algoritmo branch&cut, realizada con el entorno Abacus, y se presentan los resultados obtenidos. La implementación de una heurística primal basada en la técnica chained local optimization contribuye a reducir sensiblemente los tiempos de ejecución.
Abstract:
The mapping problem arises in parallel programming environments, and was first defined by S. Bokhari in 1981. An instance of this problem is given by a task interaction graph and a processors graph, with the same number of vertices. The vertices of the first graph represent the tasks, and its edges join pairs of tasks with communication demands. The second graph represents the parallel arquitecture (its vertices denote processors, which are joined by an edge when they are directly connected). The objective of the problem is to assign each task to one processor (each processor can receive only one task) such that the number of adjacent tasks assigned to connected processors is maximum. An integer programming formulation for this problem is presented. A polyhedral investigation is carried out, aiming at the implementation of a branch&cut algorithm for this problem. A number of valid inequalities are presented, which constitute the cornerstone of these algorithms. The dimension of the associated politope is found, which allows to determine the strength of these inequalities, proving in some cases that they are facet-defining. The implementation, performed with the framework Abacus, is described and its computational results are presented. The implementation of a primal heuristic, based on chained local optimization metaheuristic, contributes to reduce execution times.
Citación:
---------- APA ----------
Marenco, Javier Leonardo. (1999). Un algoritmo branch y cut para el problema de mapping. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000106_Marenco
---------- CHICAGO ----------
Marenco, Javier Leonardo. "Un algoritmo branch y cut para el problema de mapping". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 1999.https://hdl.handle.net/20.500.12110/seminario_nCOM000106_Marenco
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000106_Marenco.pdf
Distrubución geográfica
