The Hybrid ColorAnt-RT Algorithms and an Application to Register Allocation
Fuente:
Redalyc
Saved in:
| Main Author: | |
|---|---|
| Format: | Artículo científico |
| Language: | es |
| Published: |
Asociación Española para la Inteligencia Artificial
2015
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1876480370654838784 |
|---|---|
| author | Carla Negri Lintzmayer |
| author_facet | Carla Negri Lintzmayer |
| contents | The Hybrid ColorAnt-RT Algorithms and an Application to Register Allocation Carla Negri Lintzmayer Mauro Henrique Mulati Anderson Faustino da Silva Ingeniería RT CARTRA ColorAnt Register Allocation Graph Coloring Problem Ant Colony Optimization is a metaheuristic used to cr eate heuristic algorithms to find good solutions for combinatorial optimization problems. This metaheuris tic is inspired on the behavior present in ants. This specie explores the environment to find and transport food to th e nest. Several works have proposed the use of Ant Colony Optimization algorithms to solve problems such as vehicle routing, frequency assignment, scheduling and graph coloring. The graph coloring problem essentially consists in finding a number k of colors to assign to its vertices, so that there are no two adjacent vertices with the same color. This paper presents the hybrid ColorAnt- RT algorithms, a class of algorithms for graph coloring proble ms, which is based on the Ant Colony Optimization metaheuristic and uses Tabu Search as local search. The exper iments with ColorAnt-RT algorithms indicate that changing the way to reinforce the pheromone trail results in better results. The results with ColorAnt-RT show that it is a promising option in finding good approximations of k . The good results obtained by ColorAnt-RT motivated it use on a register allocation based on Ant Colony Optimization, called CARTRA . As a result, this paper also presents CARTRA , an algorithm that extends a classic graph coloring register allocator to use the graph coloring algorithm ColorAnt-RT . CARTRA minimizes the number of spills, thereby improving the quality of the generated code. 2015 artículo científico 1137-3601 https://www.redalyc.org/articulo.oa?id=92538718007 es http://www.redalyc.org/revista.oa?id=925 Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial application/pdf Asociación Española para la Inteligencia Artificial Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial (España) Num.55 Vol.18 |
| format | Artículo científico |
| id | redalyc_92538718007 |
| institution | Redalyc |
| language | es |
| publishDate | 2015 |
| publisher | Asociación Española para la Inteligencia Artificial |
| spellingShingle | The Hybrid ColorAnt-RT Algorithms and an Application to Register Allocation Carla Negri Lintzmayer Ingeniería RT CARTRA ColorAnt Register Allocation Graph Coloring Problem The Hybrid ColorAnt-RT Algorithms and an Application to Register Allocation Carla Negri Lintzmayer Mauro Henrique Mulati Anderson Faustino da Silva Ingeniería RT CARTRA ColorAnt Register Allocation Graph Coloring Problem Ant Colony Optimization is a metaheuristic used to cr eate heuristic algorithms to find good solutions for combinatorial optimization problems. This metaheuris tic is inspired on the behavior present in ants. This specie explores the environment to find and transport food to th e nest. Several works have proposed the use of Ant Colony Optimization algorithms to solve problems such as vehicle routing, frequency assignment, scheduling and graph coloring. The graph coloring problem essentially consists in finding a number k of colors to assign to its vertices, so that there are no two adjacent vertices with the same color. This paper presents the hybrid ColorAnt- RT algorithms, a class of algorithms for graph coloring proble ms, which is based on the Ant Colony Optimization metaheuristic and uses Tabu Search as local search. The exper iments with ColorAnt-RT algorithms indicate that changing the way to reinforce the pheromone trail results in better results. The results with ColorAnt-RT show that it is a promising option in finding good approximations of k . The good results obtained by ColorAnt-RT motivated it use on a register allocation based on Ant Colony Optimization, called CARTRA . As a result, this paper also presents CARTRA , an algorithm that extends a classic graph coloring register allocator to use the graph coloring algorithm ColorAnt-RT . CARTRA minimizes the number of spills, thereby improving the quality of the generated code. 2015 artículo científico 1137-3601 https://www.redalyc.org/articulo.oa?id=92538718007 es http://www.redalyc.org/revista.oa?id=925 Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial application/pdf Asociación Española para la Inteligencia Artificial Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial (España) Num.55 Vol.18 |
| title | The Hybrid ColorAnt-RT Algorithms and an Application to Register Allocation |
| topic | Ingeniería RT CARTRA ColorAnt Register Allocation Graph Coloring Problem |
| url | https://www.redalyc.org/articulo.oa?id=92538718007 |