El algoritmo de Chaitin es un algoritmo de asignación de registros de coloración de gráficos de abajo hacia arriba que utiliza costo / grado como métrica de derrame . Lleva el nombre de su diseñador, Gregory Chaitin . El algoritmo de Chaitin fue el primer algoritmo de asignación de registros que utilizó la coloración del gráfico de interferencia tanto para la asignación de registros como para el derrame.
El algoritmo de Chaitin se presentó en el Simposio SIGPLAN sobre Construcción de Compiladores de 1982 y se publicó en las actas del simposio. Era una extensión de un artículo anterior de 1981 sobre el uso de colores de gráficos para la asignación de registros. El algoritmo de Chaitin formó la base de una gran parte de la investigación sobre los asignadores de registros.
Referencias
- Gregory Chaitin (abril de 2004). "Registrar la asignación y el derrame mediante la coloración del gráfico". Avisos ACM SIGPLAN . 39 (4): 66–74. doi : 10.1145 / 989393.989403 .