1. Introducción… ¿Por qué surge la necesidad de segmentación?
La arquitectura de Von Neumann tiene limitaciones significativas debido a que la memoria actúa como un cuello de botella cuando se requiere procesar un número de instrucciones elevado. Además, la tecnología sobre la que se implementa esta arquitectura también limita la velocidad que puede alcanzar. Por lo tanto, se hace imprescindible aumentar:
a) El throughput (cantidad de cálculo realizada en el tiempo) de los computadores
b) La eficiencia relación entre la velocidad y la cantidad de procesadores utilizados
2. ¿De qué opciones disponemos si queremos aumentar la cantidad de operaciones en el tiempo y la eficiencia?
Como solución, surge la idea del procesamiento paralelo para poder favorecer los procesos concurrentes. Los tipos de paralelismos son:
3. Paralelismo explícito… ¿por qué no?
El uso de varios procesadores (paralelismo explícito) tiene frente a la segmentación un gran inconveniente: existe un límite cuando añadimos procesadores en cuanto a la eficiencia. Expliquemos esto; aplicando la ley de Amdahl si se quiere ejecutar un 90 % de las instrucciones de manera paralela, podemos ver que el aumento de la velocidad no es mayor que 10 veces:
El coste es también más elevado.
4. ¿En qué consiste la segmentación o pipelining?
En los procesadores actuales, para optimizar al máximo su rendimiento se recurre a técnicas como la segmentación. Esta técnica permite dividir un proceso de ejecución en varias etapas por medio de software y de hardware, consiguiendo solapar la ejecución de múltiples instrucciones. Por lo tanto, la finalidad de la segmentación es realizar procesadores más rápidos. Por ello, casi todos los DSP del mercado incorporan el uso de la segmentación en mayor o menor medida.
Pensemos en la segmentación como una cadena de producción donde cada etapa completa una parte de la instrucción. Una instrucción se descompone en pequeñas partes, cada una de las cuales necesita una fracción del tiempo total necesario para completar la instrucción. Cada uno de estos pasos se denomina etapa de la segmentación o segmento. Las etapas están conectadas cada una con la siguiente para formar una especie de cauce o tubería; las instrucciones entran por un extremo, son procesadas en cada etapa y salen por el otro extremo.
Con la segmentación se consigue aumentar el número de instrucciones que se ejecutan simultáneamente y la velocidad a la cual se empiezan y terminan, pero no reduce el tiempo que se necesita para ejecutar una instrucción completa. Es decir, la segmentación mejora la productividad de las instrucciones, no el tiempo de ejecución de una instrucción individual. Un incremento en la productividad de las instrucciones significa que un programa se ejecuta más rápido y que tiene un tiempo total de ejecución menor, aún cuando cada instrucción particular no se ejecute con más rapidez. Con la segmentación se consigue reducir el tiempo medio de ejecución de cada instrucción.
La productividad de la segmentación está determinada por la frecuencia con que las instrucciones salen del cauce o tubería. Como las etapas están conectadas entre sí, todas deben estar listas para actuar al mismo tiempo, así el número de instrucciones que salen del cauce no debe exceder el número de instrucciones que entran. El tiempo requerido para desplazar una instrucción a lo largo del cauce es idealmente, un ciclo de reloj. Como todas las etapas evolucionan a la misma velocidad, el tiempo requerido por la etapa más lenta fijará la duración del ciclo de reloj. Por ello, el objetivo del diseñador es equilibrar la duración de las etapas de la segmentación.
Aunque la mayoría de los DSP utilizan la técnica de segmentación, su profundidad o número de etapas varía de un procesador a otro. En general, cuanto mayor sea el número de etapas menor tiempo tardará el procesador en ejecutar una instrucción. Casi todos los DSP incorporan algún tipo de mejora en el uso de la segmentación con el propósito de reducir su posible ineficiencia temporal.
5. ¿Podemos cuantificar la velocidad de segmentación?
El incremento de la velocidad de la segmentación puede transformarse en una fórmula. Si las etapas están perfectamente equilibradas, el tiempo entre instrucciones en una máquina segmentada (suponiendo condiciones ideales) es igual a:
Hay que tener bien presente que la segmentación incrementa el número de instrucciones que se están ejecutando a la vez y la rapidez con que las instrucciones empiezan y acaban, pero no reduce el tiempo que se tarda en completar una instrucción individual.
6. ¿Qué riesgos conlleva la segmentación?
Hay situaciones, llamadas riesgos (hazards), que impiden que se ejecute la siguiente instrucción del flujo de instrucciones durante su ciclo de reloj designado. Los riesgos reducen el rendimiento de la velocidad ideal lograda por la segmentación. Hay tres clases de riesgos:
– Riesgos estructurales: Significa que el hardware no puede soportar la combinación de instrucciones que se quieren ejecutar en el mismo ciclo, por ejemplo dos instrucciones accediendo a la memoria
– Riesgos de control: Se debe a la necesidad de tomar una decisión basada en los resultados de una instrucción mientras las otras se están ejecutando, por ejemplo un salto condicional
– Riesgos de datos: Se debe a que una instrucción depende del resultado de otra previa que todavía se encuentra en el cauce.
Los riesgos en la segmentación pueden hacer necesario detenerla. La diferencia principal entre detenciones en una máquina segmentada y en una no segmentada se presenta porque hay múltiples instrucciones ejecutándose a la vez. Una detención en una máquina segmentada requiere, con frecuencia, que prosigan algunas instrucciones, mientras se retardan otras. Normalmente, cuando una instrucción está detenida, todas las instrucciones posteriores a esta instrucción también se detienen. Las instrucciones anteriores a la instrucción detenida pueden continuar, pero no se buscan instrucciones nuevas durante la detención. Una cuestión importante, es que una detención hace que el rendimiento de la segmentación se degrade con relación al rendimiento ideal. Para calcular la aceleración real de la segmentación podríamos emplear la siguiente ecuación:
Así pues, y con el fin de favorecer la segmentación, a la hora de diseñar el repertorio de instrucciones se debe tener en cuenta:
a) Que todas las instrucciones tengan la misma longitud
b) Que existan pocos formatos de instrucción y con campos sistemáticos
c) Optar por una arquitectura registro-registro
d) Garantizar que los accesos a memoria se encuentren alineados
7. ¿Cómo solucionar riegos estructurales, control y datos?
Riesgos estructurales
Un dispositivo sin riesgos estructurales tendrá siempre un CPI más bajo, pero lo cierto es que no se adoptan soluciones para intentar eliminar los riesgos estructurales. Sería lógico cuestionarnos… ¿por qué se permiten los riesgos estructurales?. Hay dos razones: para reducir el coste y para reducir la latencia de la unidad. Si los riesgos estructurales no se presentan con frecuencia, puede no merecer la pena el coste de evitarlos. Por otro lado, reducir la latencia tiene otros beneficios de rendimiento y, frecuentemente, pueden superar las desventajas de los riesgos estructurales.
Solución de riesgos de control y datos
Un efecto importante de la segmentación es cambiar la temporización de las instrucciones al solapar su ejecución. Esto introduce riesgos por dependencias de datos y de control. Los riesgos por dependencias de datos se presentan cuando el orden de acceso a los operandos los cambia la segmentación, con relación al orden normal que se sigue en las instrucciones que se ejecutan secuencialmente.
Imaginemos una operación donde los operandos provengan de una memoria para operaciones aritméticas. Será preciso detener la segmentación en la mitad de la instrucción para esperar que se complete el acceso a memoria. En lugar de permitir que se detenga la segmentación, el compilador puede intentar realizar una planificación que evite estas paradas, reorganizando la secuencia de código para eliminar el riesgo. En el caso de que el compilador no pueda realizar esta “reorganización”, se puede insertar una instrucción de no operación. Esto no afecta al tiempo de ejecución, pero incrementa el espacio de código.
Tanto si el hardware detecta este riesgo y detiene la segmentación como si no, el rendimiento mejorará si el compilador planifica instrucciones. Si se presenta una detención, el impacto sobre el rendimiento será el mismo, tanto si la máquina ejecuta un ciclo inactivo como si ejecuta una no operación.
8. ¿Existen otras alternativas a la técnica de compilación para solucionar riesgos de control y datos?
Si. Además de la técnica de compilación, se ha diseñado la segmentación software para ayudar a explotar el paralelismo entre las instrucciones. Esta se basa en “desplegar” bucles para crear secuencias más largas de código, que se pueden utilizar para explotar más el paralelismo a nivel de instrucción.
Así pues, la segmentación software es una técnica para reorganizar bucles, de tal forma que, cada iteración en el código segmentado por software se haga a partir de secuencias de instrucciones escogidas en diferentes iteraciones del segmento de código original. Un bucle segmentado por software, intercala instrucciones de diferentes iteraciones sin desenrollar el bucle. Esta técnica es la contrapartida software a lo que el algoritmo de Tomasulo hace en hardware. También hay código de arranque que se necesita antes que comience el bucle, así como código para concluir una vez que se complete el bucle.
La principal ventaja de la segmentación software es que consume menos espacio de código, por lo que reduce la porción de tiempo en la que el bucle no se ejecuta a la velocidad máxima a una única vez al comienzo y al final del bucle. Existe otra técnica alternativa denominado planificación de trazas que no entra en los objetivos del presente artículo.
9. ¿Hay algo más después de la segmentación?
Para conseguir procesadores aún más rápidos se han seguido tres direcciones que extienden los procesadores segmentados:
a) Supersegmentación: Consiste en hacer más larga la segmentación, dividiendo la misma en un mayor número de etapas. Computadores recientes emplean 8 o más etapas.
b) Superescalar: Consiste en la replicación de los elementos internos del computador de manera que se puedan ejecutar múltiples instrucciones en cada etapa. Al ejecutar varias instrucciones por ciclo de reloj tendríamos un CPI <1.
c) Segmentación dinámica: Consiste en que sea le hardware el que evite los riegos estructurales, de datos y de control según se van ejecutando las instrucciones
10. Aumentar la velocidad no tiene coste cero… ¿qué inconvenientes encontramos con las técnicas de segmentación avanzadas?
La mejora de la velocidad hace que se complique el control de la segmentación y el modelo de ejecución de las instrucciones. Así que si se propone mejorar el rendimiento ofrecido por la segmentación, se debería decrementar el CPI a menos de la unidad. Así pues, el CPI solo podrá reducirse por debajo de uno si emitimos más de una instrucción cada ciclo de reloj. El objetivo será permitir múltiples instrucciones en un ciclo de reloj.
Debemos tener en mente que para mantener el procesador a pleno rendimiento, se debe explotar el paralelismo entre las instrucciones buscando secuencias de instrucciones no relacionadas que se puedan solapar en la segmentación. Dos instrucciones relacionadas deben estar separadas por una distancia igual a la latencia de la segmentación de la primera de las instrucciones.
Los inconvenientes que presentan las técnicas de segmentación avanzadas es que se complican los riesgos de la segmentación siendo más arduo el diseño de aplicaciones (software o hardware) para evitar la pérdida de eficiencia.
11. En los últimos años… ¿qué sabemos de los nuevos enfoques alternativos a la segmentación?
Hace ya algunos años, ha habido una serie de artículos que tenía como finalidad estudiar los distintos enfoques alternativos de segmentación. Jouppi y Wall [1989] examinan las diferencias de rendimiento entre sistemas supersegmentados y superescalares, concluyendo que su rendimiento es similar, pero que las máquinas supersegmentadas pueden necesitar menos hardware para conseguir el mismo rendimiento.
Sohi y Vajapeyam [1989] dan medidas de paralelismo disponibles para máquinas de grandes palabras de instrucciones. Smith, Johnson y Horowitz [1989] presentan estudios de paralelismo disponibles a nivel de instrucción en código no científico, utilizando un esquema hardware ambicioso que permite la ejecución de múltiples instrucciones.
Bibliografía:
“Arquitectura de computadores un enfoque cuantitativo”. D. Patterson.
Ya que el artículo realizado por David es muy interesante a la par que útil, pues siempre nos abordan preguntas y con esta forma de presentar la información muchas de ellas pueden estar resueltas, tan sólo voy a aportar un poco más de información acerca de uno de las formas de mejorar la segmentación: la supersegmentación y los procesadores superescalares.
ResponderEliminar“Una solución alternativa para alcanzar mayores prestaciones es la supersegmentación basada en el hecho de que muchas etapas del cauce realizan tareas que requieren menos de la mitad de un ciclo de reloj, por lo que se dobla la velocidad de reloj interno, para entonces realizar dos tareas en un ciclo de reloj externo.
El procesador supersegmentado toma más tiempo para ejecutar el mismo número de instrucciones respecto al procesador superescalar al comienzo del programa y en cada destino de un salto.
Ahora bien, la aproximación superescalar depende de la habilidad para ejecutar múltiples instrucciones en paralelo. El paralelismo a nivel de instrucciones se refiere al grado en el que, en promedio, las instrucciones de un programa se pueden ejecutar en paralelo. Para maximizar se puede usar una combinación de optimizaciones realizadas por el compilador y de técnicas hardware. Las limitaciones fundamentales del paralelismo son:
- Dependencia de datos verdadera
- Dependencia relativa al procedimiento
- Otras limitaciones: conflicto con los recursos, dependencia de salida (dependencia lectura-escritura), antidependencia,…”
Para una información más detallada:
www.fismat.umich.mx/~htejeda/posgrado/super.ps
o en su defecto
http://209.85.229.132/search?q=cache:RFZjjv1ptXMJ:www.fismat.umich.mx/~htejeda/posgrado/super.ps+supersegmentacion&hl=es&ct=clnk&cd=1&gl=es
Buenas! Sólo me gustaría añadir un pequeño comentario acerca del principal problema que parece que tiene la segmentación: las instrucciones de salto. Me pareció curioso cuando se comentó en clase el hecho de que existen métodos basados en la predicción del comportamiento del algoritmo para paliar los efectos de tener el procesador parado en esos instantes, por lo que he buscado algo de información al respecto.
ResponderEliminarSegún he podido leer, estas técnicas cuya finalidad es predecir el resultado de los saltos se dividen en dos grandes grupos: técnicas de predicción estática y técnicas de predicción dinámica.
Las técnicas de predicción estática, denominadas así porque se realizan en tiempo de compilación, realizan predicciones de carácter relativamente simple (por ejemplo, tomar desde un principio un camino como el que va a ocurrir, basarse en datos estadísticos para realizar una elección o utilizar modelos de programa y asumir el mismo comportamiento) pero no necesitan una gran complejidad hardware, por lo que son técnicas viables en la gran mayoría de procesadores.
Las estrategias de predicción dinámica, llamadas así porque se realiza la predicción en tiempo de ejecución, realizan unas predicciones mucho más fiables que las anteriores (por ejemplo, creando predicciones en base a las decisiones tomadas en los anteriores saltos o en base a las zonas de memoria a las que llevan los mismos) pero necesitan una mayor complejidad a nivel hardware, siendo por tanto más costoso de implementar.
Sólo añadir al comentario que esto ha sido extraído de un artículo de la UPC que se encuentra en esta dirección:
ftp://ftp.ac.upc.edu/pub/reports/DAC/1996/UPC-DAC-1996-30.ps.Z
Interesante artículo que amplía todo lo leído en el ejercicio mandado la semana pasada sobre la segmentación. Buscando información sobre la segmentación también encontré la comparación de la segmentación con una cadena de producción. Mientras que un artesano (no segmentación) tiene que hacer todo el proceso el solo con lo cual el tiempo es superior; una cadena de producción (segmentación) va haciendo cada tarea por separado y repetitivamente, con lo que el ahorro de tiempo es mucho mayor. El problema surge cuando un eslabón de la cadena se atrasa (se puede comparar con el salto) y ahí es cuando quiebra todo el sistema montado.
ResponderEliminarCreo que con este ejemplo se entiende más o menos la principal característica de la segmentación. Sería como un resumen de las 11 preguntas.