Optimización del CO variable en función de la frecuencia de las instrucciones

Una posibilidad a la hora de codificar las operaciones de un repertorio de instrucciones es utilizar algún criterio de óptimo. En este sentido tenemos dos alternativas:

a) Frecuencia de aparición en el programa → optimización de memoria
b) Frecuencia de ejecución en el programa → optimización del tráfico CPU-Memoria

La alternativa b) es la más interesante en la actualidad, pues prima la velocidad de ejecución sobre la memoria .necesaria para almacenar el programa.

Para optimizar el CO se puede utilizar la codificación de Huffman que veremos con el siguiente Ejemplo: Supongamos las siguientes frecuencias de ejecución de 7 tipos diferentes de instrucciones:

Con CO de longitud fija se necesitarían 3 bits. Para obtener el código de Huffman procedemos de la siguiente manera:

1) Se escriben en una columna las instrucciones y a su derecha su frecuencia de ejecución. Cada elemento de la columna será un nodos terminal del árbol de decodificación.
2) Se unen las dos frecuencias menores de la columna anterior con sendos arcos, obteniéndose un nuevo nodo cuyo valor será la suma de los nodos de procedencia.
3) Se repite el paso 2) hasta llegar a la raíz del árbol que tendrá valor 1.
4) Comenzando en la raíz, asignamos 0 (1) al arco superior y 1 (0) al inferior hasta llegar a los nodos terminales.
5) Se obtiene el código de cada instrucción recorriendo el árbol de la raíz a la instrucción y concatenando los valores de los arcos del camino.

Para nuestro ejemplo tendremos lo siguiente:

Longitud media del código resultante:

Fuente: Estructura de Computadores, Facultad de Informática, UCM