1. Repositorio Institucional del Tecnológico Nacional de México (RI - TecNM)
2. Tesis de Posgrado
3. Tamaulipas
4. Instituto Tecnológico de Ciudad Madero
5. Tesis
6. Tesis de Maestría
7. Maestría en Ciencias de la Computación

Title:	Optimización del problema de programación de tareas independientes en sistemas de procesamiento paralelo
Authors:	Soto Monterrubio, Jose Carlos.
Issue Date:	2015-03-01
Publisher:	Tecnológico Nacional de México
metadata.dc.publisher.tecnm:	Instituto Tecnológico de Ciudad Madero
Description:	En esta tesis el problema de investigaci´on que se aborda es el problema de asignaci´on de tareas independientes en sistemas de procesamiento paralelo. Este problema nace debido al crecimiento de los grandes centros de datos o clusters, en los cuales se tiene que buscar una manera optima de asignar las tareas en las maquinas que ser´an ejecutadas. Esta asignaci´on tiene que aprovechar la energ´ıa consumida y, ademas que el tiempo en que se terminan de ejecutar todas las tareas sea m´ınimo. Por lo tanto el objetivo de este problema es minimizar el makespan y el consumo de energ´ıa. Para el control de la energ´ıa utilizada en una m´aquina se usa la t´ecnica de escalamiento din´amico de voltaje y frecuencia. En este trabajo se realiz´o un estudio comparativo entre dos m´etodos exactos y dos metaheur´ısticas. El primer m´etodo exacto es un modelo de Programaci´on Lineal Entera Mixta (MILP, por sus siglas en ingl´es) propuesto en este trabajo y el segundo es un Branch and Bound. Ambos m´etodos est´an implementados en dos fases, la primer fase consiste en minimizar el makespan y la segunda fase en minimizar la energ´ıa consumida. Des pu´es se realiz´o una comparaci´on con los resultados obtenidos de ambos m´etodos. Los resultados experimentales muestran que el mejor m´etodo exacto es el MILP. La siguiente experimentaci´on realizada es entre dos metaheur´ısticas multiobjetivo el NSGA–II y el MOEA/D. En el algoritmo NSGA–II se implementaron diversas t´ecnicas de cruza y mutaci´on de los algoritmos evolutivos. Aplicando los indicadores de calidad se selecciono la mejor t´ecnica. Para el algoritmo MOEA/D se implementaron nueve fun ciones de descomposici´on y se selecciono la mejor funci´on de acuerdo a los indicadores de calidad. Con las mejores t´ecnicas de cada metaheur´ıstica se realizo una experimentaci´on comparativa entre el NSGA–II y el MOEA/D. Los resultados muestran que la mejor cruza y mutaci´on para el NSGA–II es una cruza uniforme y una mutaci´on propuesta denominada mutaci´on de balanceo de cargas. La mejor funci´on para el MOEA/D es la funci´on Augmented Tchebycheff Kaliszewski. Los resultados experimentales entre ambas metaheur´ıstica con sus mejores t´ecnicas muestran que el mejor fue el MOEA/D.
metadata.dc.type:	info:eu-repo/semantics/masterThesis
Appears in Collections:	Maestría en Ciencias de la Computación

This item is protected by original copyright View License

This item is licensed under a Creative Commons License