4.2. PROCESADORES DE MÚLTIPLES CONTEXTOS.

  1. El modelo de procesador mejorado.
  2. Políticas de cambio de contexto.
  3. Eficiencia del procesador.

Los sistemas multihilo están construidos con procesadores de múltiples contextos (multithreaded processors). Saavedra y otros [SAA90] realizaron un modelo abstracto para su estudio. Presentan la eficiencia del procesador como función de la latencia de memoria L, el número de contextos N, y la sobrecarga por cambio de contexto C.

El modelo de procesador mejorado.

Un procesador convencional de un simple hilo esperará durante una referencia remota, de esta forma está desocupado durante un periodo de tiempo L. Un procesador multihilo suspenderá el contexto actual y conmutará a otro, y tras un determinado número de ciclos volverá a estar trabajando de forma útil, y sólo estará desocupado si todos los contextos están bloqueados.

Es claro que el objetivo es maximizar la fracción de tiempo que el procesador está ocupado, de esta forma se emplea la eficiencia del procesador como índice de rendimiento:

Eficiencia = t_ocupado / ( t_ocupado + t_conmutación + t_desocupado )

donde t_ocupado, t_conmutación y t_desocupado representan la cantidad de tiempo que el procesador se encuentra en el estado correspondiente, medida en un intervalo de tiempo considerable. La idea básica en una máquina multihilo es entremezclar la ejecución de un gran número de contextos para reducir de forma importante el valor del tiempo de desocupación, sin sobrecargarlo aumentando en exceso el tiempo de conmutación de contexto.

Durante su tiempo de vida un contexto pasa por los siguientes estados: listo (ready), ejecutando (running), saliendo (leaving), bloqueado (blocked). Siempre existirá al menos un contexto ejecutando o saliendo. El procesador estará ocupado si existe un contexto en el estado ejecutando; el procesador está en conmutación mientras realiza la transición de un contexto a otro, por ejemplo cuando un contexto está saliendo. Si todos los contextos están bloqueados, el procesador está desocupado.

Un contexto en ejecución mantiene el procesador ocupado hasta que se produce una operación que requiere un cambio de contexto. El contexto emplea C ciclos en el estado saliendo para pasar al estado bloqueado durante L ciclos, y finalmente regresar al estado listo.

Figura 4-6 Modelo multihilo.

Cada hilo tiene un contexto, y cada contexto consta de un contador de programa (PC), un conjunto de registros y la palabra de estado del procesador (PSW).

Políticas de cambio de contexto.

Existen diferentes arquitecturas multihilo según la política de cambio de contexto adoptada. Existen cuatro políticas básicas :

  1. Conmutación por fallo de caché: Esta política corresponde al caso en el que un contexto es seleccionado cuando causa un fallo en la cache. En este caso, R se toma como el intervalo medio entre fallos (en ciclos), y L el tiempo requerido para satisfacer la falta. El procesador cambia de contexto cuando se conoce que el contexto actual se retrasará durante un número de ciclos significativo.
  2. Conmutación en cada carga: Esta política permite conmutar en cada carga, independientemente de que produzca un fallo o no. Aquí, R es el intervalo medio entre cargas. En un modelo genérico se supone que el contexto es bloqueado durante L ciclos tras la conmutación, pero en este caso sólo sucede cuando la carga causa un fallo de cache. El modelo genérico puede ser empleado si es postulado suponiendo la existencia de dos fuentes de latencia L1 y L2, con probabilidades p1 y p2 de ocurrir en cada conmutación. Si L1 representa la latencia de un fallo de cache, entonces p1 corresponde al ratio de fallos. L2 es la latencia de memoria de cero ciclos con probabilidad p2.
  3. Conmutación en cada instrucción: Esta política permite la conmutación en cada instrucción, independientemente de que se produzca una carga o no. Se trata de entremezclar las instrucciones de diferentes hilos ciclo a ciclo. De esta forma las sucesivas instrucciones son independientes lo que beneficia la ejecución en pipeline. A veces, los fallos de cache pueden aumentar debido a la ruptura del principio de localidad.
  4. Conmutación en bloque de instrucciones: Bloques de instrucciones de diferentes hilos son entremezclados. Esto mejora el ratio de aciertos de cache debido a la localidad, y también beneficia el rendimiento de un contexto simple.

Eficiencia del procesador.

Un procesador de hilo simple ejecuta un contexto hasta que se produce una referencia remota (R ciclos) y entonces se encuentra desocupado hasta que se completa la referencia (L ciclos). No existe cambio de contexto y naturalmente no existe sobrecarga debida a conmutación. Se puede modelar este comportamiento como una renovación de proceso alternante que tiene un ciclo de R+L.

E1 = R / (R+L) = 1 / (1 + L/R)

R y L corresponden a la cantidad de tiempo durante un ciclo que el procesador está ocupado o desocupado, respectivamente. Esto muestra claramente la reducción del rendimiento del procesador en un sistema paralelo con una latencia de memoria grande.

Con contextos múltiples, la latencia de memoria puede ser ocultada por la conmutación a un nuevo contexto, pero la conmutación emplea C ciclos de sobrecarga. Suponiendo que la longitud de ejecución entre conmutaciones es constante y con un número suficiente de contextos, siempre existirá un contexto listo para ser ejecutado cuando se produce una conmutación, de esta forma el procesador nunca estará desocupado.

La eficiencia del procesador se analiza bajo dos condiciones diferentes:

1) La región de saturación: En esta región saturada, el procesador funciona con una utilización máxima. El ciclo de la renovación del proceso en este caso es R+C, y la eficiencia es:

Esat = R / (R+C) = 1 / (1 + C/R)

La eficiencia de saturación es, en este caso, independiente de la latencia y tampoco cambia con un incremento del número de contextos.

Figura 4-7 Ejemplo de cambio de contexto en la región de saturación.

La saturación se alcanza cuando el tiempo que el procesador emplea sirviendo a los otros hilos supera el tiempo requerido para procesar una solicitud, esto es, cuando

(N-1)*(R+C) > L. Así pues, el punto de saturación con longitud de ejecución constante es:

Nd = 1 + L / (R+C)

2) La región lineal: Cuando el número de contextos está por debajo del punto de saturación, puede no haber contextos listos después de un cambio de contexto, y entonces el procesador realiza ciclos desocupado. El tiempo requerido para conmutar a un contexto preparado, ejecutarlo hasta que se produzca una referencia remota, y procesar la referencia es R+C+L. Suponiendo que N está por debajo del punto de saturación, durante este tiempo el resto de contextos tienen un turno en el procesador. Así, la eficiencia es:

Elin = N*R / (R+C+L)

Figura 4-8 Ejemplo de cambio de contexto en la región lineal.

Se puede observar que la eficiencia crece linealmente con el número de contextos hasta alcanzar el punto de saturación, y después permanece constante. La ecuación de la eficiencia de saturación establece el límite de la eficiencia para un procesador multihilo y subraya la importancia del ratio C/R. A menos que el cambio de contexto sea extremadamente barato, el ratio de referencias remotas debe mantenerse bajo.

Figura 4-9 Curva de eficiencia.

Saavedra [SAA90] proporciona unos resultados que están basados en un modelo de Markov de una arquitectura multihilo :

Figura 4-10 Gráficos de la eficiencia del procesador.

La eficiencia del procesador se representa como una función de la latencia de memoria L con una longitud de ejecución media R = 16 ciclos. La curva con C = 0 corresponde al caso en que la sobrecarga de conmutación es nula. Con C = 16 ciclos, se alcanza el 50% de eficiencia. Se puede comprobar que los hilos múltiples incrementan la eficiencia del procesador pero a costa de aumentar también el tráfico de red, lo que lleva a buscar un punto de acuerdo entre estos dos objetivos opuestos.