Please use this identifier to cite or link to this item:
https://rinacional.tecnm.mx/jspui/handle/TecNM/3167| 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 |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| G08070650_donacion_tesis_bib.pdf | 2.49 MB | Adobe PDF | View/Open |
This item is protected by original copyright |
This item is licensed under a Creative Commons License
