PDF de programación - Batería de operadores en lenguaje ensamblador para algoritmos genéticos

Subsecretaría de Educación Superior
Dirección General de Educación Superior Tecnológica
Instituto Tecnológico de La Paz

INSTITUTO TECNOLÓGICO DE LA PAZ

DIVISIÓN DE ESTUDIOS DE POSGRADO E INVESTIGACIÓN

MAESTRÍA EN SISTEMAS COMPUTACIONALES

Batería de operadores en lenguaje ensamblador

para algoritmos genéticos

T E S I S

QUE PARA OBTENER EL GRADO DE

MAESTRO EN SISTEMAS COMPUTACIONALES

PRESENTA:

JORGE BRAVO ESPINOZA

DIRECTOR DE TESIS:

DR. MARCO ANTONIO CASTRO LIERA

MIEMBROS DEL JURADO:

MC. JESÚS ANTONIO CASTRO, UNAM.

MATI. LUIS ARMANDO CÁRDENAS FLORIDO, ITESM.

MSC. ILIANA CASTRO LIERA, ITLP.

LA PAZ, BAJA CALIFORNIA SUR, MÉXICO, DICIEMBRE 2013.

RESUMEN

Los compiladores, así como sus capacidades, han ido evolucionando a lo largo del
tiempo. Actualmente una de las facetas más importantes de dicha evolución involucra la
optimización que pueden lograr sobre el código de máquina generado, con el fin de que
se ejecute lo más rápido posible. Si bien los compiladores actuales logran un nivel de
optimización aceptable, presentan todavía algunas deficiencias en este rubro.

Esta tesis propone el empleo del lenguaje ensamblador como estrategia de optimización
de código. Se presenta una aplicación, escrita completamente en lenguaje C, que
implementa un algoritmo genético a ejecutar en una máquina paralela virtual. De la
aplicación se seleccionan algunas rutinas para ser optimizadas manualmente, esto es,
para ser escritas en lenguaje ensamblador. Se establecen las estrategias para la
comprobación de confiabilidad de las rutinas programadas y para la comparación de
eficiencia entre la versión original y la optimizada manualmente. Se incluyen también
los resultados obtenidos y las conclusiones a que se ha llegado.

ABSTRACT

Compilers and their capabilities have evolved over time; currently one of the most
important facets of compiler evolution involves automatic code optimization, in order to
generate machine-code that run as fast as possible. While current compilers achieve an
acceptable level of optimization, still have some shortcomings in this area.

This thesis proposes the use of assembly language as code optimization strategy. An
application, written entirely in C language, that implements a genetic algorithm to run
on a virtual parallel machine is presented. Some routines of the application are selected
to be optimized manually, that is, to be written in assembly language. Strategies for
checking reliability of programmed routines and for efficiency comparison between the
original version and the manually optimized one are set. The results obtained and the
conclusions that have been reached are also included.

AGRADECIMIENTOS

A mi director de tesis, Marco Castro, por el gran apoyo que me brindó y por su
paciencia para conmigo.

ÍNDICE

Capítulo 1. Introducción............................................................................................5
1.1 Problemas de optimización.......................................................................6
1.2 Algoritmos bioinspirados..........................................................................6
1.3 Programación de algoritmos bioinspirados...............................................7
1.4 Objetivo general........................................................................................8
1.5 Objetivos específicos................................................................................9

Capítulo 2. Optimización de código........................................................................10
2.1 Lenguajes de alto nivel vs lenguaje ensamblador...................................11
2.2 Estrategias generales de optimización de código....................................13
2.3 El compilador GNU C y la optimización de código................................16
2.3.1 Plegado de constantes (Constant folding).......................................17
2.3.2 Propagación de constantes (Constant propagation).......................17
2.3.3 Eliminación de código muerto (Dead Code Elimination)...............18
2.3.4 Eliminación de subexpresiones comunes (Common

Subexpression Elimination)............................................................22

2.3.5 Variables de inducción (Strength Reduction using

Induction Variable)........................................................................28

Capítulo 3. Algoritmos genéticos...........................................................................31
3.1 Descripción.............................................................................................32
3.2 Operadores genéticos..............................................................................33
3.3 Algoritmos genéticos distribuidos con migración (AG-DM)..................34

Capítulo 4. Batería de operadores en lenguaje ensamblador....................................36
4.1 Aplicación a considerar...........................................................................37

4.2 Estructura general de la aplicación AG-DM...........................................40
4.3 Herramientas y plataforma de ejecución.................................................41
4.3.1 Software de base.............................................................................41
4.3.2 Cluster............................................................................................41
4.3.3 Habilitación del cluster con PVM...................................................42

4.4 Programación de rutinas..........................................................................46
4.4.1 Funciones de aptitud.......................................................................47
4.4.2 Generador de números pseudo-aleatorios ......................................69
4.4.3 Operadores AG ..............................................................................82
4.4.4 Funciones auxiliares.......................................................................98
4.4.5 Estructura de la aplicación AG-DM optimizada...........................107

4.5 Pruebas de confiabilidad a las rutinas programadas..............................109
4.6 Estrategia de comparación de tiempos de ejecución.............................110

Capítulo 5. Resultados y trabajo futuro..................................................................111
5.1 Tiempos de ejecución en el cluster PVM..............................................112
5.2 Conclusiones.........................................................................................114
5.3 Trabajo futuro.......................................................................................116

Apéndice A. Módulos en lenguaje C del algoritmo AG-DM original....................118
A.1 Módulo maestro...................................................................................119
A.2 Módulo esclavo y operadores...............................................................125
A.3 Funciones de aptitud............................................................................132
A.3.1 Ackley.......................................................................................132
A.3.2 Rastrigin...................................................................................133
A.3.3 Schwefel...................................................................................134
A.3.4 Weierstrass................................................................................135

2

Apéndice B. Módulos en lenguaje C del algoritmo AG-DM optimizado..............137
B.1 Módulo maestro...................................................................................138
B.2 Módulo esclavo....................................................................................143

Apéndice C. Módulos en lenguaje ensamblador del algoritmo AG-DM

Optimizado......................................................................................149
C.1 Función GeneraPoblacion()..................................................................150
C.2 Función OrdenaPoblacion().................................................................152
C.3 Función CopiaPoblacion()....................................................................155
C.4 Operador Seleccion()...........................................................................155
C.5 Operador Cruce().................................................................................158
C.6 Operador Mutacion()............................................................................161

Apéndice D. Funciones de aptitud en lenguaje ensamblador del algoritmo AG-DM
Optimizado.......................................................................................165
D.1 Rastrigin()............................................................................................166
D.2 Ackley()...............................................................................................167
D.3 Schwefel()............................................................................................169
D.4 Weierstrass()........................................................................................170

Apéndice E. Código en lenguaje ensamblador para el generador de números
pseudoaleatorios MT19937..............................................................174

Apéndice F. Resultados de las pruebas de confiabilidad a los módulos programados
en lenguaje ensamblador...................................................................181
F.1 Ackley()................................................................................................182
F.2 Rastrigin().............................................................................................183

3

F.3 Schwefel()............................................................................................184
F.4 Weierstrass()....................