From 4fbbf90a4ac8a32e6701f608da6879cdb1b6964c Mon Sep 17 00:00:00 2001
From: Juan Marín Noguera <juan.marinn@um.es>
Date: Fri, 4 Dec 2020 20:50:27 +0100
Subject: Some initial progress

---
 aoc/n.lyx  | 187 +++++++++++++++++++++++++++++++
 aoc/n1.lyx | 365 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 552 insertions(+)
 create mode 100644 aoc/n.lyx
 create mode 100644 aoc/n1.lyx

diff --git a/aoc/n.lyx b/aoc/n.lyx
new file mode 100644
index 0000000..aafa697
--- /dev/null
+++ b/aoc/n.lyx
@@ -0,0 +1,187 @@
+#LyX 2.3 created this file. For more info see http://www.lyx.org/
+\lyxformat 544
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\begin_preamble
+\input{../defs}
+\end_preamble
+\use_default_options true
+\begin_modules
+algorithm2e
+\end_modules
+\maintain_unincluded_children false
+\language spanish
+\language_package default
+\inputencoding auto
+\fontencoding global
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\paperfontsize 10
+\spacing single
+\use_hyperref false
+\papersize a5paper
+\use_geometry true
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_minted 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\leftmargin 0.2cm
+\topmargin 0.7cm
+\rightmargin 0.2cm
+\bottommargin 0.7cm
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style swiss
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle empty
+\listings_params "basicstyle={\ttfamily}"
+\tracking_changes false
+\output_changes false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\end_header
+
+\begin_body
+
+\begin_layout Title
+Arquitectura y Organización de Computadores
+\end_layout
+
+\begin_layout Date
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+def
+\backslash
+cryear{2020}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "../license.lyx"
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Bibliografía:
+\end_layout
+
+\begin_layout Itemize
+Universidad de Murcia.
+ Diapositivas de Arquitectura y Organización de Computadores.
+\end_layout
+
+\begin_layout Itemize
+
+\lang english
+Wikipedia, the Free Encyclopedia
+\lang spanish
+ (
+\begin_inset Flex URL
+status open
+
+\begin_layout Plain Layout
+
+https://en.wikipedia.org/
+\end_layout
+
+\end_inset
+
+).
+ 
+\emph on
+\lang english
+Dark Silicon
+\emph default
+\lang spanish
+.
+ 
+\end_layout
+
+\begin_layout Chapter
+Introducción
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "n1.lyx"
+
+\end_inset
+
+
+\end_layout
+
+\end_body
+\end_document
diff --git a/aoc/n1.lyx b/aoc/n1.lyx
new file mode 100644
index 0000000..1d59a1f
--- /dev/null
+++ b/aoc/n1.lyx
@@ -0,0 +1,365 @@
+#LyX 2.3 created this file. For more info see http://www.lyx.org/
+\lyxformat 544
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\use_default_options true
+\begin_modules
+algorithm2e
+\end_modules
+\maintain_unincluded_children false
+\language spanish
+\language_package default
+\inputencoding auto
+\fontencoding global
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_minted 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style french
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tracking_changes false
+\output_changes false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+Llamamos 
+\series bold
+arquitectura
+\series default
+ de un computador a:
+\end_layout
+
+\begin_layout Enumerate
+La 
+\series bold
+ISA
+\series default
+ (
+\emph on
+\lang english
+Instruction Set Architecture
+\emph default
+\lang spanish
+), el conjunto de instrucciones del procesador.
+ Normalmente hay una ISA base, como x86, ARM o RISC-V, con extensiones.
+\end_layout
+
+\begin_layout Enumerate
+La 
+\series bold
+microarquitectura
+\series default
+, la implementación de cada instrucción de la ISA.
+\end_layout
+
+\begin_layout Enumerate
+El diseño del 
+\emph on
+\lang english
+hardware
+\emph default
+\lang spanish
+.
+\end_layout
+
+\begin_layout Standard
+Llamamos 
+\series bold
+tamaño característico
+\series default
+ (
+\emph on
+\lang english
+feature size
+\emph default
+\lang spanish
+) al tamaño mínimo de un transistor en un chip.
+ Fue reduciéndose de 
+\begin_inset Formula $\unit[10]{\mu m}$
+\end_inset
+
+ en 1971 a 
+\begin_inset Formula $\unit[10]{nm}$
+\end_inset
+
+ en 2019.
+ Así, la 
+\series bold
+ley de Moore
+\series default
+ afirma que se podrá construir un chip con el doble de transistores cada
+ 18–24 meses, y la 
+\series bold
+ley de Dennard
+\series default
+ (
+\emph on
+\lang english
+Dennard scaling
+\emph default
+\lang spanish
+ o 
+\emph on
+\lang english
+MOSFET scaling
+\emph default
+\lang spanish
+) afirma que a medida que disminuye el tamaño de los transistores, la densidad
+ de potencia consumida permanece constante.
+\end_layout
+
+\begin_layout Standard
+Al disminuir el tamaño característico, la frecuencia de reloj puede aumentar
+ de forma más o menos proporcional porque los transistores cambian de estado
+ más rápido; la 
+\series bold
+densidad de integración
+\series default
+, o densidad de transistores, aumenta cuadráticamente, y en general se podía
+ aumentar proporcionalmente el tamaño del chip.
+ Estos transistores se usan para aumentar los recursos del chip mediante
+ paralelismo y cachés, por lo que los programas limitados por CPU aumentaban
+ su velocidad de forma cuadrática sin cambios.
+ No obstante, actualmente esto plantea varios problemas.
+\end_layout
+
+\begin_layout Section
+Potencia consumida
+\end_layout
+
+\begin_layout Standard
+La energía debe ser traída al chip mediante pines, distribuida entre las
+ distintas capas y disipada para evitar el sobrecalentamiento.
+ La 
+\series bold
+potencia de diseño térmico
+\series default
+ (
+\series bold
+TDP
+\series default
+, 
+\emph on
+\lang english
+Thermal Design Power
+\emph default
+\lang spanish
+) es la usada como objetivo para la fuente de alimentación y el sistema
+ de refrigeración.
+ Se divide en 
+\series bold
+potencia estática
+\series default
+, producto del voltaje, la intensidad de potencia de fuga por transistor
+ y el número de transistores, y 
+\series bold
+potencia dinámica
+\series default
+, proporcional al nivel de uso, el cuadrado del voltaje y la frecuencia
+ de reloj.
+\end_layout
+
+\begin_layout Standard
+Inicialmente la potencia estática era casi despreciable.
+ Actualmente, al no poder bajar el voltaje por debajo de unos 
+\begin_inset Formula $\unit[0.5]{V}$
+\end_inset
+
+, la potencia dinámica sigue aumentando al seguir aumentando la frecuencia
+ y la potencia estática aumenta aun más rápido porque se sigue aumentando
+ el número de transistores, por lo que la potencia estática está en torno
+ al 
+\begin_inset Formula $\unit[\text{25--50}]{\%}$
+\end_inset
+
+ de la potencia total.
+ Además, deja de cumplirse la ley de Dennard y surge el 
+\series bold
+\emph on
+\lang english
+dark silicon
+\series default
+\emph default
+\lang spanish
+, un límite en el área total de un chip que se puede encender a la vez sin
+ superar el 
+\end_layout
+
+\begin_layout Standard
+La 
+\series bold
+densidad de potencia
+\series default
+ es la potencia disipada por unidad de superficie, y ha ido aumentando,
+ pero el 
+\series bold
+rendimiento por vatio
+\series default
+ también ha aumentado mucho.
+ Las soluciones de enfriamiento para alta densidad de potencia son caras
+ o poco prácticas, por lo que se busca reducir la potencia con técnicas
+ como:
+\end_layout
+
+\begin_layout Enumerate
+Reducir la frecuencia de reloj dinámicamente.
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+DVFS
+\series default
+ (
+\emph on
+\lang english
+Dynamic Voltage Frequency Scaling
+\emph default
+\lang spanish
+): Reducir el voltaje o la frecuencia de zonas que no se estén usando.
+\end_layout
+
+\begin_layout Enumerate
+Apagar selectivamente núcleos del procesador.
+\end_layout
+
+\begin_layout Enumerate
+Estados de bajo consumo en RAM, discos duros, etc.
+\end_layout
+
+\begin_layout Section
+Problemas
+\end_layout
+
+\begin_layout Standard
+Disminuir el CPI requiere aumentar el bus de datos.
+ Se suele hacer con segmentación, pero a partir de 10 etapas aparecen muchos
+ conflictos, por lo que se replica el cauce usando ejecución superescalar
+ (varias instrucciones empezando y terminando a la vez) fuera de orden y
+ especulativa.
+ Esto requiere mucho 
+\emph on
+\lang english
+hardware
+\emph default
+\lang spanish
+, por lo que consume mucha energía.
+\end_layout
+
+\begin_layout Section
+Acceso a memoria
+\end_layout
+
+\begin_layout Standard
+La mejora en los procesadores es más rápida que en la memoria, y el bus
+ entre ambas tiene muy alta latencia.
+ La ejecución fuera de orden solo puede mitigar este problema parcialmente.
+ 
+\end_layout
+
+\begin_layout Section
+Fiabilidad
+\end_layout
+
+\begin_layout Standard
+Al reducir el tamaño de los componentes, estos son más sensibles a partículas
+ cargadas en el ambiente, por lo que los bits pueden cambiar de valor.
+ Por ello se crean memorias y cachés con códigos de corrección (
+\series bold
+ECC
+\series default
+, 
+\emph on
+\lang english
+Error Correction Codes
+\emph default
+\lang spanish
+).
+ También surgen problemas de impedancia y capacitancia que dan lugar a 
+\series bold
+\emph on
+\lang english
+dark silicon
+\series default
+\emph default
+\lang spanish
+, parte del área del chip que no se puede usar por estos problemas.
+ Finalmente, al ser los diseños de procesadores más grandes, es más difícil
+ comprobar su corrección, y como los transistores reciben y alteran la señal
+ de reloj, al aumentar su número puede haber modificaciones perceptibles
+ en dicha señal, lo que llamamos 
+\series bold
+sesgo de reloj
+\series default
+ o 
+\series bold
+\emph on
+\lang english
+clock skew
+\series default
+\emph default
+\lang spanish
+.
+\end_layout
+
+\end_body
+\end_document
-- 
cgit v1.2.3


From 4742cf648bb1e1f0995a4e2cceb979f307141e7e Mon Sep 17 00:00:00 2001
From: Juan Marín Noguera <juan.marinn@um.es>
Date: Fri, 4 Dec 2020 23:04:19 +0100
Subject: x

---
 aoc/n1.lyx | 447 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 421 insertions(+), 26 deletions(-)

diff --git a/aoc/n1.lyx b/aoc/n1.lyx
index 1d59a1f..186cd9a 100644
--- a/aoc/n1.lyx
+++ b/aoc/n1.lyx
@@ -183,7 +183,11 @@ densidad de integración
 \end_layout
 
 \begin_layout Section
-Potencia consumida
+Problemas
+\end_layout
+
+\begin_layout Subsection
+Potencia
 \end_layout
 
 \begin_layout Standard
@@ -286,26 +290,36 @@ Apagar selectivamente núcleos del procesador.
 Estados de bajo consumo en RAM, discos duros, etc.
 \end_layout
 
-\begin_layout Section
-Problemas
+\begin_layout Subsection
+Paralelismo
 \end_layout
 
 \begin_layout Standard
-Disminuir el CPI requiere aumentar el bus de datos.
- Se suele hacer con segmentación, pero a partir de 10 etapas aparecen muchos
- conflictos, por lo que se replica el cauce usando ejecución superescalar
- (varias instrucciones empezando y terminando a la vez) fuera de orden y
- especulativa.
- Esto requiere mucho 
+Disminuir el CPI requiere aumentar el bus de datos y usar segmentación,
+ pero a partir de 10 etapas aparecen muchos conflictos, por lo que se replica
+ el cauce usando ejecución superescalar (varias instrucciones empezando
+ y terminando a la vez) fuera de orden y especulativa.
+ Estas técnicas permiten conseguir 
+\series bold
+ILP
+\series default
+ (
+\emph on
+\lang english
+Instruction-Level Parallelism
+\emph default
+\lang spanish
+), en que varias instrucciones se ejecutan a la vez consiguiendo superar
+ la instrucción por ciclo, pero requiere mucho 
 \emph on
 \lang english
 hardware
 \emph default
 \lang spanish
-, por lo que consume mucha energía.
+ y por tanto consume mucha energía.
 \end_layout
 
-\begin_layout Section
+\begin_layout Subsection
 Acceso a memoria
 \end_layout
 
@@ -313,17 +327,18 @@ Acceso a memoria
 La mejora en los procesadores es más rápida que en la memoria, y el bus
  entre ambas tiene muy alta latencia.
  La ejecución fuera de orden solo puede mitigar este problema parcialmente.
- 
 \end_layout
 
-\begin_layout Section
+\begin_layout Subsection
 Fiabilidad
 \end_layout
 
 \begin_layout Standard
-Al reducir el tamaño de los componentes, estos son más sensibles a partículas
- cargadas en el ambiente, por lo que los bits pueden cambiar de valor.
- Por ello se crean memorias y cachés con códigos de corrección (
+También hay problemas problemas de fiabilidad, pues conforme los diseños
+ de procesadores se hacen más grandes es más difícil comprobar su corrección.
+ Además, al reducir el tamaño de los componentes, estos son más sensibles
+ a partículas cargadas en el ambiente capaces de cambiar el valor de los
+ bits, por lo que se crean memorias y cachés con códigos de corrección (
 \series bold
 ECC
 \series default
@@ -334,31 +349,411 @@ Error Correction Codes
 \emph default
 \lang spanish
 ).
- También surgen problemas de impedancia y capacitancia que dan lugar a 
+ Surgen problemas de impedancia y capacitancia, y como los transistores
+ reciben y alteran la señal de reloj, al aumentar su número puede haber
+ modificaciones perceptibles en dicha señal, lo que llamamos 
+\series bold
+sesgo de reloj
+\series default
+ o 
 \series bold
 \emph on
 \lang english
-dark silicon
+clock skew
 \series default
 \emph default
 \lang spanish
-, parte del área del chip que no se puede usar por estos problemas.
- Finalmente, al ser los diseños de procesadores más grandes, es más difícil
- comprobar su corrección, y como los transistores reciben y alteran la señal
- de reloj, al aumentar su número puede haber modificaciones perceptibles
- en dicha señal, lo que llamamos 
+.
+\end_layout
+
+\begin_layout Standard
+Podemos medir la fiabilidad en 
 \series bold
-sesgo de reloj
+tiempo medio hasta un fallo
+\series default
+ (
+\series bold
+MTTF
+\series default
+, 
+\emph on
+\lang english
+Mean Time To Failure
+\emph default
+\lang spanish
+), 
+\series bold
+tiempo medio para reparaciones
+\series default
+ (
+\series bold
+MTTR
+\series default
+, 
+\emph on
+\lang english
+Mean Time To Recover
+\emph default
+\lang spanish
+), 
+\series bold
+tiempo medio entre fallos
+\series default
+ (
+\series bold
+MTBF
+\series default
+, 
+\emph on
+\lang english
+Mean Time Between Failures
+\emph default
+\lang spanish
+, la suma de los dos anteriores) y 
+\series bold
+disponibilidad
+\series default
+ (el MTTF entre el MTBF).
+\end_layout
+
+\begin_layout Section
+Paralelismo
+\end_layout
+
+\begin_layout Standard
+Michael J.
+ Flynn clasifica las arquitecturas en:
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+SISD
+\series default
+ (
+\emph on
+\lang english
+Single Instruction Single Data
+\emph default
+\lang spanish
+): Procesador secuencial sin paralelismo.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+MISD
+\series default
+ (
+\emph on
+\lang english
+Multiple Instruction Single Data
+\emph default
+\lang spanish
+): Operaciones secuenciales pero redundantes, útil para sistemas de emergencia.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+SIMD
+\series default
+ (
+\emph on
+\lang english
+Single Instruction Multiple Data
+\emph default
+\lang spanish
+): Operaciones 
+\series bold
+vectorizadas
+\series default
+, en que una sola instrucción ejecuta la misma operación sobre varios datos.
+ Es la usada en GPUs, aunque las CPUs modernas suelen tener instrucciones
+ SIMD.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+MIMD
+\series default
+ (
+\emph on
+\lang english
+Multiple Instruction Multiple Data
+\emph default
+\lang spanish
+): Varios procesadores o 
+\series bold
+núcleos
+\series default
+ realizando operaciones distintas en datos distintos.
+\end_layout
+
+\begin_layout Subsection
+Multiprocesadores
+\end_layout
+
+\begin_layout Standard
+Son procesadores con 
+\series bold
+arquitecturas multinúcleo
+\series default
+ (MISD o MIMD).
+ Un 
+\series bold
+CMP
+\series default
+ (
+\series bold
+\emph on
+\lang english
+Chip Multiprocessor
+\series default
+\emph default
+\lang spanish
+) es un multiprocesador en un solo chip.
+ 
+\end_layout
+
+\begin_layout Standard
+Usar varios núcleos pequeños en vez de uno grande hace más fácil verificar
+ el diseño y permite reducir el voltaje y la frecuencia con el mismo rendimiento
+, con lo que la cantidad de transistores útiles es mayor.
+ Además, se mitigan los problemas eléctricos y, como cada núcleo tiene su
+ propio reloj, desaparece el sesgo de reloj.
+\end_layout
+
+\begin_layout Standard
+Así, la frecuencia de reloj de los procesadores no sigue aumentando, de
+ hecho disminuye, pero la ley de Moore se reinterpreta como que el número
+ de núcleos por chip se puede duplicar cada 2 años.
+\end_layout
+
+\begin_layout Subsection
+Acceso a memoria
+\end_layout
+
+\begin_layout Standard
+En un procesador MIMD, la memoria puede ser:
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Compartida
+\series default
+: Un único espacio de direcciones al que tienen acceso todos los procesadores,
+ y que puede usarse para la comunicación entre estos.
+ El acceso a memoria puede hacerse con un bus compartido o con una red más
+ directa como una malla.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Distribuida
+\series default
+: Cada procesador tiene su propia memoria local, y la comunicación se hace
+ por instrucciones de paso de mensajes.
+\end_layout
+
+\begin_layout Standard
+Los clústeres y centros de datos usan memoria distribuida entre los ordenadores,
+ aunque cada ordenador suele tener varios núcleos con memoria compartida
+ y vectorización SIMD.
+\end_layout
+
+\begin_layout Section
+Medidas de rendimiento
+\end_layout
+
+\begin_layout Standard
+Podemos medir el rendimiento de un procesador por el tiempo de ejecución
+ de algún programa o su productividad o 
+\emph on
+\lang english
+throughput
+\emph default
+\lang spanish
+ (operaciones de algún tipo por unidad de tiempo).
+ Se puede usar el tiempo de ejecución real, que incluye la sobrecarga de
+ todo el sistema, o el tiempo de CPU usado para el cálculo.
+ La 
+\begin_inset Quotes cld
+\end_inset
+
+
+\series bold
+aceleración
+\series default
+
+\begin_inset Quotes crd
+\end_inset
+
+ de un procesador o un programa respecto a otro (funcionalmente equivalente)
+ es el tiempo de ejecución del segundo entre el del primero.
+ El 
+\series bold
+ancho de banda
+\series default
+ es el trabajo total realizado en un tiempo determinado, y la 
+\series bold
+latencia
 \series default
  o 
 \series bold
+tiempo de respuesta
+\series default
+ es el tiempo entre el inicio y el final de una operación.
+\end_layout
+
+\begin_layout Standard
+Los 
+\series bold
 \emph on
 \lang english
-clock skew
+benchmarks
 \series default
 \emph default
 \lang spanish
-.
+ son programas usados para comparar el rendimiento.
+ Hay de varios tipos: 
+\emph on
+\lang english
+kernels
+\emph default
+\lang spanish
+ (como multiplicación de matrices), programas de juguete (como ordenación
+ de elementos), 
+\emph on
+\lang english
+benchmarks
+\emph default
+\lang spanish
+ sintéticos (como Dhrystone) o suites de 
+\emph on
+\lang english
+benchmarks
+\emph default
+\lang spanish
+ como SPEC06fp o TPC-C.
+\end_layout
+
+\begin_layout Standard
+La 
+\series bold
+intensidad aritmética
+\series default
+ es el número de operaciones en coma flotante por byte u operando leído
+ de memoria para un cierto algoritmo.
+ El 
+\series bold
+modelo de rendimiento 
+\emph on
+Roofline
+\series default
+\emph default
+ consiste en medir el rendimiento de coma flotante en 
+\series bold
+FLOPS
+\series default
+ (operaciones de punto flotante por segundo) en función de la intensidad
+ aritmética, midiendo así tanto el ancho de banda de memoria como el rendimiento
+ de punto flotante.
+\end_layout
+
+\begin_layout Standard
+Algunos aspectos relevantes son la frecuencia de reloj, el número de transistore
+s, el tamaño de la caché de cada nivel, la cantidad de memoria direccionable,
+ el ancho de banda del bus de memoria, el número de núcleos por chip, el
+ tamaño de la litografía y el tamaño de los operandos.
+\end_layout
+
+\begin_layout Section
+Límites del paralelismo
+\end_layout
+
+\begin_layout Standard
+Todos los programas paralelos tienen secciones secuenciales, debido a la
+ duplicación de trabajo entre varios procesadores o a la espera del resto
+ de procesadores a que uno acabe.
+ La 
+\series bold
+ley de Amdahl
+\series default
+ afirma que, si en un proceso una parte que ocupa una porción 
+\begin_inset Formula $p$
+\end_inset
+
+ del tiempo total se hace 
+\begin_inset Formula $S$
+\end_inset
+
+ veces más rápido, el proceso en total se hace
+\begin_inset Formula 
+\[
+\frac{1}{(1-p)+\frac{p}{S}}
+\]
+
+\end_inset
+
+veces más rápido.
+ En particular, como las partes paralelas se hacen tantas veces más rápido
+ como el total de procesadores, las partes secuenciales limitan la efectividad
+ del paralelismo con una cota superior inversa a la fracción de código secuencia
+l.
+\end_layout
+
+\begin_layout Standard
+En la práctica nunca se llega al rendimiento obtenido por la ley de Amdahl
+ porque los procesadores tienen que comunicarse.
+ La 
+\series bold
+ley de Gustafson
+\series default
+ afirma que, si un programa se ejecuta en 
+\begin_inset Formula $N$
+\end_inset
+
+ procesadores iguales con un tiempo secuencial 
+\begin_inset Formula $s$
+\end_inset
+
+ y un tiempo paralelo en cada uno 
+\begin_inset Formula $p$
+\end_inset
+
+, la aceleración por haberlo paralelizado es
+\begin_inset Formula 
+\[
+\frac{s+Np}{s+p},
+\]
+
+\end_inset
+
+con lo que un problema con parte paralela lo suficientemente grande puede
+ ser paralelizado eficientemente.
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Realmente esto es lo mismo que la ley de Amdahl y la misma conclusión se
+ puede obtener directamente de la ley de Amdahl, pero a los ingenieros les
+ gusta pensar que es otra cosa así que así sea.
+\end_layout
+
+\end_inset
+
+ 
+\end_layout
+
+\begin_layout Standard
+Esto cambia los objetivos hacia la formulación de problemas para poder soluciona
+r casos mayores en la misma cantidad de tiempo, de modo que a veces es preferibl
+e aumentar la cantidad total de cálculos a cambio de disminuir la parte
+ secuencial.
 \end_layout
 
 \end_body
-- 
cgit v1.2.3


From 7a3ad775c6143ec873d28a5b4bbea92e943aad8b Mon Sep 17 00:00:00 2001
From: Juan Marín Noguera <juan.marinn@um.es>
Date: Fri, 11 Dec 2020 20:38:00 +0100
Subject: AOC tema 1

---
 aoc/n1.lyx | 341 +++++++++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 233 insertions(+), 108 deletions(-)

diff --git a/aoc/n1.lyx b/aoc/n1.lyx
index 186cd9a..53fc5b4 100644
--- a/aoc/n1.lyx
+++ b/aoc/n1.lyx
@@ -179,7 +179,26 @@ densidad de integración
  Estos transistores se usan para aumentar los recursos del chip mediante
  paralelismo y cachés, por lo que los programas limitados por CPU aumentaban
  su velocidad de forma cuadrática sin cambios.
- No obstante, actualmente esto plantea varios problemas.
+ Por ejemplo, la empresa de procesadores Intel evoluciona sus diseños en
+ dos pasos: una fase 
+\emph on
+\lang english
+tick
+\emph default
+\lang spanish
+ en la que disminuye el tamaño de los componentes, optimiza el diseño de
+ los núcleos y aprovecha el aumento en densidad de transistores para conseguir
+ mejor rendimiento y eficiencia energética, y una fase 
+\emph on
+\lang english
+tock
+\emph default
+\lang spanish
+ en la que diseña una nueva arquitectura y amplia la ISA.
+\end_layout
+
+\begin_layout Standard
+No obstante, actualmente esto plantea varios problemas.
 \end_layout
 
 \begin_layout Section
@@ -416,6 +435,114 @@ disponibilidad
  (el MTTF entre el MTBF).
 \end_layout
 
+\begin_layout Section
+Medidas de rendimiento
+\end_layout
+
+\begin_layout Standard
+Podemos medir el rendimiento de un procesador por el tiempo de ejecución
+ de algún programa o su productividad o 
+\emph on
+\lang english
+throughput
+\emph default
+\lang spanish
+ (operaciones de algún tipo por unidad de tiempo).
+ Se puede usar el tiempo de ejecución real, que incluye la sobrecarga de
+ todo el sistema, o el tiempo de CPU usado para el cálculo.
+ La 
+\begin_inset Quotes cld
+\end_inset
+
+
+\series bold
+aceleración
+\series default
+
+\begin_inset Quotes crd
+\end_inset
+
+ de un procesador o un programa respecto a otro (funcionalmente equivalente)
+ es el tiempo de ejecución del segundo entre el del primero.
+ El 
+\series bold
+ancho de banda
+\series default
+ es el trabajo total realizado en un tiempo determinado, y la 
+\series bold
+latencia
+\series default
+ o 
+\series bold
+tiempo de respuesta
+\series default
+ es el tiempo entre el inicio y el final de una operación.
+\end_layout
+
+\begin_layout Standard
+Los 
+\series bold
+\emph on
+\lang english
+benchmarks
+\series default
+\emph default
+\lang spanish
+ son programas usados para comparar el rendimiento.
+ Hay de varios tipos: 
+\emph on
+\lang english
+kernels
+\emph default
+\lang spanish
+ (como multiplicación de matrices), programas de juguete (como ordenación
+ de elementos), 
+\emph on
+\lang english
+benchmarks
+\emph default
+\lang spanish
+ sintéticos (como Dhrystone) o suites de 
+\emph on
+\lang english
+benchmarks
+\emph default
+\lang spanish
+ como SPEC06fp o TPC-C.
+\end_layout
+
+\begin_layout Standard
+La 
+\series bold
+intensidad aritmética
+\series default
+ es el número de operaciones en coma flotante por byte u operando leído
+ de memoria para un cierto algoritmo.
+ El 
+\series bold
+modelo de rendimiento 
+\emph on
+\lang english
+Roofline
+\series default
+\emph default
+\lang spanish
+ consiste en medir el rendimiento de coma flotante en 
+\series bold
+FLOPS
+\series default
+ (operaciones de punto flotante por segundo) en función de la intensidad
+ aritmética, midiendo así tanto el ancho de banda de memoria como el rendimiento
+ de punto flotante.
+\end_layout
+
+\begin_layout Standard
+Algunos aspectos relevantes son la frecuencia de reloj, el número de transistore
+s, el tamaño de la caché de cada nivel, la cantidad de memoria direccionable,
+ el ancho de banda del bus de memoria, el número de núcleos por chip, el
+ tamaño de la litografía y el tamaño de los operandos.
+\end_layout
+
 \begin_layout Section
 Paralelismo
 \end_layout
@@ -565,113 +692,7 @@ Los clústeres y centros de datos usan memoria distribuida entre los ordenadores
  y vectorización SIMD.
 \end_layout
 
-\begin_layout Section
-Medidas de rendimiento
-\end_layout
-
-\begin_layout Standard
-Podemos medir el rendimiento de un procesador por el tiempo de ejecución
- de algún programa o su productividad o 
-\emph on
-\lang english
-throughput
-\emph default
-\lang spanish
- (operaciones de algún tipo por unidad de tiempo).
- Se puede usar el tiempo de ejecución real, que incluye la sobrecarga de
- todo el sistema, o el tiempo de CPU usado para el cálculo.
- La 
-\begin_inset Quotes cld
-\end_inset
-
-
-\series bold
-aceleración
-\series default
-
-\begin_inset Quotes crd
-\end_inset
-
- de un procesador o un programa respecto a otro (funcionalmente equivalente)
- es el tiempo de ejecución del segundo entre el del primero.
- El 
-\series bold
-ancho de banda
-\series default
- es el trabajo total realizado en un tiempo determinado, y la 
-\series bold
-latencia
-\series default
- o 
-\series bold
-tiempo de respuesta
-\series default
- es el tiempo entre el inicio y el final de una operación.
-\end_layout
-
-\begin_layout Standard
-Los 
-\series bold
-\emph on
-\lang english
-benchmarks
-\series default
-\emph default
-\lang spanish
- son programas usados para comparar el rendimiento.
- Hay de varios tipos: 
-\emph on
-\lang english
-kernels
-\emph default
-\lang spanish
- (como multiplicación de matrices), programas de juguete (como ordenación
- de elementos), 
-\emph on
-\lang english
-benchmarks
-\emph default
-\lang spanish
- sintéticos (como Dhrystone) o suites de 
-\emph on
-\lang english
-benchmarks
-\emph default
-\lang spanish
- como SPEC06fp o TPC-C.
-\end_layout
-
-\begin_layout Standard
-La 
-\series bold
-intensidad aritmética
-\series default
- es el número de operaciones en coma flotante por byte u operando leído
- de memoria para un cierto algoritmo.
- El 
-\series bold
-modelo de rendimiento 
-\emph on
-Roofline
-\series default
-\emph default
- consiste en medir el rendimiento de coma flotante en 
-\series bold
-FLOPS
-\series default
- (operaciones de punto flotante por segundo) en función de la intensidad
- aritmética, midiendo así tanto el ancho de banda de memoria como el rendimiento
- de punto flotante.
-\end_layout
-
-\begin_layout Standard
-Algunos aspectos relevantes son la frecuencia de reloj, el número de transistore
-s, el tamaño de la caché de cada nivel, la cantidad de memoria direccionable,
- el ancho de banda del bus de memoria, el número de núcleos por chip, el
- tamaño de la litografía y el tamaño de los operandos.
-\end_layout
-
-\begin_layout Section
+\begin_layout Subsection
 Límites del paralelismo
 \end_layout
 
@@ -756,5 +777,109 @@ e aumentar la cantidad total de cálculos a cambio de disminuir la parte
  secuencial.
 \end_layout
 
+\begin_layout Subsection
+Software paralelo
+\end_layout
+
+\begin_layout Standard
+Podemos usar 
+\series bold
+paralelismo de datos
+\series default
+, en que se ejecuta una misma tarea en varios datos a la vez, y 
+\series bold
+paralelismo de tareas
+\series default
+, en que se ejecutan distintas tareas a la vez.
+ No obstante, hay que tener en cuenta que comenzar un hilo o proceso, comunicar
+ datos compartidos, sincronizar o hacer computación redundante tiene un
+ coste en el rango de milisegundos.
+\end_layout
+
+\begin_layout Standard
+Debemos balancear la carga para evitar que haya núcleos rápidos esperando
+ a otros lentos y debemos gestionar los recursos compartidos de forma segura,
+ considerando estas cuestiones a la hora de decidir la granularidad de las
+ tareas y modelar el rendimiento.
+\end_layout
+
+\begin_layout Section
+Tipos de ordenadores
+\end_layout
+
+\begin_layout Standard
+Distinguimos:
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+Ordenadores empotrados
+\series default
+, usados para controlar dispositivos, pequeños y baratos.
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+Móviles
+\series default
+, 
+\emph on
+\lang english
+tablets
+\emph default
+\lang spanish
+, etc.
+ Con más potencia pero enfocados en la eficiencia energética y una baja
+ latencia.
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+Ordenadores de escritorio
+\series default
+: Enfocados en la relación rendimiento/precio.
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+Servidores
+\series default
+: Enfocados en la disponibilidad, la escalabilidad y el rendimiento.
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+\emph on
+\lang english
+Clusters
+\series default
+\emph default
+\lang spanish
+: Enfocados en disponibilidad y rendimiento/precio.
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+Supercomputadores
+\series default
+: Con gran velocidad en punto flotante, red de interconexión y consumo de
+ energía.
+ Se usan para ciencia, ingeniería, negocios y defensa.
+\end_layout
+
+\begin_layout Standard
+Se considera que el primer supercomputador es el CDC 6600, aunque el término
+ se acuñó para el Cray-1, un ordenador con arquitectura de carga y almacenamient
+o sin caché de datos ni memoria virtual y con control cableado, pero con
+ registros e instrucciones vectoriales, unidades funcionales muy segmentadas
+ y varios bancos de memoria.
+\end_layout
+
 \end_body
 \end_document
-- 
cgit v1.2.3


From 8f0ea7300a3a2777744906578cfe3285ad16046d Mon Sep 17 00:00:00 2001
From: Juan Marín Noguera <juan.marinn@um.es>
Date: Sun, 13 Dec 2020 12:04:48 +0100
Subject: AOC tema 2, inicio

---
 aoc/n.lyx  |  14 +++
 aoc/n2.lyx | 325 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 339 insertions(+)
 create mode 100644 aoc/n2.lyx

diff --git a/aoc/n.lyx b/aoc/n.lyx
index aafa697..87cd742 100644
--- a/aoc/n.lyx
+++ b/aoc/n.lyx
@@ -181,6 +181,20 @@ filename "n1.lyx"
 \end_inset
 
 
+\end_layout
+
+\begin_layout Chapter
+Arquitecturas superescalares
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "n2.lyx"
+
+\end_inset
+
+
 \end_layout
 
 \end_body
diff --git a/aoc/n2.lyx b/aoc/n2.lyx
new file mode 100644
index 0000000..2033406
--- /dev/null
+++ b/aoc/n2.lyx
@@ -0,0 +1,325 @@
+#LyX 2.3 created this file. For more info see http://www.lyx.org/
+\lyxformat 544
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\use_default_options true
+\begin_modules
+algorithm2e
+\end_modules
+\maintain_unincluded_children false
+\language spanish
+\language_package default
+\inputencoding auto
+\fontencoding global
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_minted 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style french
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tracking_changes false
+\output_changes false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+Para reducir por debajo de 1 los CPI de un núcleo del procesador, debemos
+ lanzar y ejecutar varias instrucciones en cada ciclo de reloj, pero esto
+ implica más presión sobre la memoria y los registros, más posibilidad de
+ riesgos, más área de silicio y más consumo.
+ Distinguimos:
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Arquitecturas superescalares
+\series default
+: Lanzan un número variable de instrucciones por ciclo, de 0 a 8, planificadas
+ de forma 
+\series bold
+estática
+\series default
+ por el compilador y 
+\series bold
+dinámica
+\series default
+ por el 
+\emph on
+\lang english
+hardware
+\emph default
+\lang spanish
+.
+ La ejecución puede ser en orden o fuera de orden, especulativa o no.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+VLIW
+\series default
+ (
+\series bold
+\emph on
+\lang english
+Very Long Instruction Word
+\series default
+\emph default
+\lang spanish
+): En cada ciclo se carga una 
+\series bold
+macro-instrucción
+\series default
+, formada por varias instrucciones independientes agrupadas por el compilador.
+ El 
+\emph on
+\lang english
+hardware
+\emph default
+\lang spanish
+ es más simple, lo que permite una mayor frecuencia de reloj y un menor
+ consumo, pero no se beneficia de las técnicas de planificación dinámica
+ y el código suele ser más grande e incompatible entre distintas versiones
+ del procesador, por lo que actualmente está casi en desuso.
+\end_layout
+
+\begin_layout Standard
+Un núcleo superescalar tiene un sistema de memoria de alto rendimiento y
+ unidades funcionales redundantes, que administra con técnicas como:
+\end_layout
+
+\begin_layout Itemize
+Renombrado de registros para eliminar las dependencias de nombre.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Planificación dinámica
+\series default
+: Reorganizar la secuencia de instrucciones separando la decodificación
+ de la comprobación de dependencias y la emisión.
+\end_layout
+
+\begin_layout Itemize
+Ejecución fuera de orden para mitigar la degradación de rendimiento por
+ dependencias de datos.
+\end_layout
+
+\begin_layout Itemize
+Ejecución especulativa para mitigar los riesgos de control.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+Obtención de instrucciones
+\series default
+ (
+\series bold
+IF
+\series default
+): Lee varias instrucciones por ciclo en orden y las añade a una 
+\series bold
+cola de instrucciones
+\series default
+, que suaviza los fallos de la caché de instrucciones.
+ También hace 
+\emph on
+\lang english
+prefetching
+\emph default
+\lang spanish
+ de instrucciones.
+ La predicción de saltos de puede hacer aquí o en ID, y es estática si siempre
+ se predice el mismo comportamiento para el mismo salto o dinámica si no.
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+Decodificación
+\series default
+ (
+\series bold
+ID
+\series default
+): Decodifica varias instrucciones por ciclo en orden para conocer su tipo,
+ las añade decodificadas en una 
+\series bold
+ventana de instrucciones
+\series default
+ y renombra los registros para evitar riesgos.
+ Si se quiere terminación en orden se almacenan las instrucciones en un
+ 
+\series bold
+ROB
+\series default
+ (
+\emph on
+\lang english
+Re-Order Buffer
+\emph default
+\lang spanish
+), un 
+\emph on
+\lang english
+buffer
+\emph default
+\lang spanish
+ circular FIFO que almacena las instrucciones y posteriormente los resultados
+ hasta que se escriben en orden.
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+Emisión
+\series default
+ (
+\series bold
+\emph on
+\lang english
+Issue
+\series default
+\emph default
+\lang spanish
+): Se comprueba que los operandos y recursos (unidades funcionales y puestos
+ de E/S) de cada instrucción estén disponibles y, cuando lo están, se manda
+ a ejecutar la instrucción.
+ Puede ser fuera de orden, permitiendo que instrucciones cuyos operandos
+ y recursos estén disponibles adelanten a otras más antiguas.
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+Ejecución
+\series default
+ (
+\series bold
+EX
+\series default
+, 
+\series bold
+X
+\series default
+): Fuera de orden, con varias unidades funcionales de cada tipo a ser posible
+ totalmente segmentadas.
+ Para que la latencia sea lo menor posible, se usa 
+\series bold
+adelantamiento
+\series default
+, difundiendo el resultado de una operación a las pendientes tan pronto
+ esta termina, y técnicas como la predicción de valor o la reutilización
+ de valores.
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+Pos-escritura
+\series default
+ (
+\series bold
+WB
+\series default
+): Se difunden los resultados sobre un 
+\series bold
+bus de resultados
+\series default
+, actualizando el ROB, del que otras instrucciones pueden tomar sus operandos.
+ Los almacenamientos no hacen nada.
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+Confirmación
+\series default
+ (
+\series bold
+\emph on
+\lang english
+Commit
+\series default
+\emph default
+\lang spanish
+): Actualiza el estado de la máquina (registros y almacenamientos en memoria)
+ en orden de programa desde el ROB, comprobando también las excepciones.
+ La terminación en orden facilita deshacer las instrucciones mal especuladas
+ y tratar las excepciones.`
+\end_layout
+
+\begin_layout Section
+Algoritmo de Tomasulo
+\end_layout
+
+\end_body
+\end_document
-- 
cgit v1.2.3


From a2537e87de51bbcd2c46c649b18dfd98e6fbb54b Mon Sep 17 00:00:00 2001
From: Juan Marín Noguera <juan.marinn@um.es>
Date: Sun, 13 Dec 2020 15:20:45 +0100
Subject: Algoritmo de Tomasulo

---
 aoc/n2.lyx | 316 +++++++++++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 236 insertions(+), 80 deletions(-)

diff --git a/aoc/n2.lyx b/aoc/n2.lyx
index 2033406..53ee52f 100644
--- a/aoc/n2.lyx
+++ b/aoc/n2.lyx
@@ -93,23 +93,7 @@ Para reducir por debajo de 1 los CPI de un núcleo del procesador, debemos
 \series bold
 Arquitecturas superescalares
 \series default
-: Lanzan un número variable de instrucciones por ciclo, de 0 a 8, planificadas
- de forma 
-\series bold
-estática
-\series default
- por el compilador y 
-\series bold
-dinámica
-\series default
- por el 
-\emph on
-\lang english
-hardware
-\emph default
-\lang spanish
-.
- La ejecución puede ser en orden o fuera de orden, especulativa o no.
+: Lanzan un número variable de instrucciones por ciclo, de 0 a 8.
 \end_layout
 
 \begin_layout Itemize
@@ -142,38 +126,172 @@ hardware
  del procesador, por lo que actualmente está casi en desuso.
 \end_layout
 
+\begin_layout Section
+Planificación
+\end_layout
+
+\begin_layout Standard
+Aunque la mayoría de compiladores reordenan las instrucciones para intentar
+ evitar riesgos, estos todavía pueden producirse.
+\end_layout
+
+\begin_layout Standard
+Un núcleo con arquitectura superescalar tiene planificación 
+\series bold
+estática
+\series default
+ si, cuando encuentra un riesgo, detiene el cauce hasta que el riesgo desaparece
+, y tiene planificación 
+\series bold
+dinámica
+\series default
+ si reordena las instrucciones para evitar detenciones, lo que aumenta la
+ velocidad y reduce la necesidad del compilador de conocer la microarquitectura
+ a cambio de necesitar más recursos.
+ Con planificación dinámica, la ejecución es fuera de orden, y la terminación
+ puede ser en orden o fuera de orden.
+ La predicción de saltos es 
+\series bold
+estática
+\series default
+ si siempre predice el mismo resultado para el mismo salto o 
+\series bold
+dinámica
+\series default
+ en otro caso.
+\end_layout
+
 \begin_layout Standard
-Un núcleo superescalar tiene un sistema de memoria de alto rendimiento y
- unidades funcionales redundantes, que administra con técnicas como:
+Los núcleos superescalares normalmente tienen un sistema de memoria de alto
+ rendimiento y unidades funcionales redundantes, que administra con técnicas
+ como planificación dinámica, ejecución especulativa para mitigar riesgos
+ de control y renombrado de registros para mitigar las dependencias de nombre.
+\end_layout
+
+\begin_layout Section
+Algoritmo de Tomasulo
+\end_layout
+
+\begin_layout Standard
+El 
+\series bold
+algoritmo de R.
+ M.
+ Tomasulo
+\series default
+ de 1971 es un método de planificación dinámica con renombrado de registros.
+ En su versión con terminación en orden, usa:
 \end_layout
 
 \begin_layout Itemize
-Renombrado de registros para eliminar las dependencias de nombre.
+Una 
+\series bold
+cola de instrucciones
+\series default
+ a decodificar, que también suaviza los fallos de caché.
 \end_layout
 
 \begin_layout Itemize
+Un 
+\series bold
+\emph on
+\lang english
+buffer
+\emph default
+\lang spanish
+ de re-ordenación
+\series default
+ (
+\series bold
+ROB
+\series default
+, 
+\emph on
+\lang english
+Re-Order Buffer
+\emph default
+\lang spanish
+), un 
+\emph on
+\lang english
+buffer
+\emph default
+\lang spanish
+ FIFO circular que almacena las instrucciones en curso
+\begin_inset Foot
+status open
 
+\begin_layout Plain Layout
+Si el procesador usa micro-instrucciones, serán estas las que se añadan
+ al ROB.
+\end_layout
+
+\end_inset
+
+ y, cuando terminan de ejecutarse, también el valor calculado por ellas
+ si lo hay, así como las excepciones que surjan.
+\end_layout
+
+\begin_layout Itemize
+Un 
 \series bold
-Planificación dinámica
+estado de los registros
 \series default
-: Reorganizar la secuencia de instrucciones separando la decodificación
- de la comprobación de dependencias y la emisión.
+, que indica si el último valor de cada registro se debe tomar del ROB y,
+ en tal caso, de qué entrada.
+ 
 \end_layout
 
 \begin_layout Itemize
-Ejecución fuera de orden para mitigar la degradación de rendimiento por
- dependencias de datos.
+
+\series bold
+Estaciones de reserva
+\series default
+ (
+\series bold
+ER
+\series default
+): Tablas asociadas a un grupo de unidades funcionales con las instrucciones
+ por ejecutar por dicho grupo, dados por un código de instrucción, la entrada
+ del ROB correspondiente y, para cada operando, su valor o la entrada del
+ ROB que lo producirá.
 \end_layout
 
 \begin_layout Itemize
-Ejecución especulativa para mitigar los riesgos de control.
+
+\series bold
+\emph on
+\lang english
+Buffer
+\emph default
+\lang spanish
+ de carga
+\series default
+: Tabla con una serie de direcciones a cargar junto con la entrada del ROB
+ en la que cargarla.
 \end_layout
 
-\begin_layout Standard
-\begin_inset Separator plain
-\end_inset
+\begin_layout Itemize
 
+\series bold
+Bus de resultados
+\series default
+ (
+\series bold
+CDB
+\series default
+, 
+\emph on
+\lang english
+Common Data Bus
+\emph default
+\lang spanish
+): Para transmitir los resultados al ROB y los ERs, implementando el adelantamie
+nto.
+\end_layout
 
+\begin_layout Standard
+Las instrucciones se segmentan en 6 etapas:
 \end_layout
 
 \begin_layout Enumerate
@@ -185,20 +303,19 @@ Obtención de instrucciones
 \series bold
 IF
 \series default
-): Lee varias instrucciones por ciclo en orden y las añade a una 
+, 
 \series bold
-cola de instrucciones
+F
 \series default
-, que suaviza los fallos de la caché de instrucciones.
- También hace 
+, 
 \emph on
 \lang english
-prefetching
+Instruction Fetch
 \emph default
 \lang spanish
- de instrucciones.
- La predicción de saltos de puede hacer aquí o en ID, y es estática si siempre
- se predice el mismo comportamiento para el mismo salto o dinámica si no.
+): Lee varias instrucciones por ciclo en orden y las añade a la cola de
+ instrucciones.
+ La predicción de saltos se puede hacer aquí o en ID.
 \end_layout
 
 \begin_layout Enumerate
@@ -210,33 +327,36 @@ Decodificación
 \series bold
 ID
 \series default
-): Decodifica varias instrucciones por ciclo en orden para conocer su tipo,
- las añade decodificadas en una 
-\series bold
-ventana de instrucciones
-\series default
- y renombra los registros para evitar riesgos.
- Si se quiere terminación en orden se almacenan las instrucciones en un
- 
+, 
 \series bold
-ROB
+D
 \series default
- (
-\emph on
-\lang english
-Re-Order Buffer
-\emph default
-\lang spanish
-), un 
+, 
 \emph on
 \lang english
-buffer
+Instruction Decode
 \emph default
 \lang spanish
- circular FIFO que almacena las instrucciones y posteriormente los resultados
- hasta que se escriben en orden.
+): Decodifica varias instrucciones por ciclo para conocer su tipo, en orden.
+ Si hay una entrada libre en el ROB y una en el ER para la instrucción,
+ añade la instrucción al ROB y al ER.
+ Para cada operando, carga el valor en el ER desde el ROB o el banco de
+ registros según indique el estado del registro o, si este no ha sido calculado,
+ el número de la entrada del ROB donde estará.
+ Finalmente guarda el número de la entrada del ROB en el estado del registro
+ de destino, si lo hay.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Los algoritmos con terminación fuera de orden usan una 
+\series bold
+ventana de instrucciones
+\series default
+ en vez de un ROB.
 \end_layout
 
+\end_deeper
 \begin_layout Enumerate
 
 \series bold
@@ -250,11 +370,15 @@ Issue
 \series default
 \emph default
 \lang spanish
-): Se comprueba que los operandos y recursos (unidades funcionales y puestos
- de E/S) de cada instrucción estén disponibles y, cuando lo están, se manda
- a ejecutar la instrucción.
- Puede ser fuera de orden, permitiendo que instrucciones cuyos operandos
- y recursos estén disponibles adelanten a otras más antiguas.
+): Fuera de orden.
+ Para cada ER, si un operando no está disponible, espera a que llegue por
+ el CDB para guardarlo en la ER.
+ En otro caso, si hay una unidad funcional disponible, le envía los operandos
+ para que ejecute la instrucción, y si no la hay espera.
+ Hay que asegurar que dos ERs no puedan enviar a la misma unidad funcional
+ a la vez.
+ Como mejora, se pueden usar técnicas como la predicción de valor o la reutiliza
+ción de valores.
 \end_layout
 
 \begin_layout Enumerate
@@ -270,31 +394,57 @@ EX
 \series bold
 X
 \series default
-): Fuera de orden, con varias unidades funcionales de cada tipo a ser posible
- totalmente segmentadas.
- Para que la latencia sea lo menor posible, se usa 
-\series bold
-adelantamiento
-\series default
-, difundiendo el resultado de una operación a las pendientes tan pronto
- esta termina, y técnicas como la predicción de valor o la reutilización
- de valores.
+, 
+\emph on
+\lang english
+Execute
+\emph default
+\lang spanish
+): Fuera de orden, preferiblemente con varias unidades funcionales de cada
+ tipo totalmente segmentadas, y llevando la cuenta de cuál es el destino
+ de la instrucción.
+ Los almacenamientos solo calculan la dirección.
+ Las cargas se dividen en las etapas X1, en que se calcula la dirección
+ de memoria, y X2, en que se accede a memoria, separadas por el 
+\emph on
+\lang english
+buffer
+\emph default
+\lang spanish
+ de carga.
+ Antes de una carga, se debe esperar a que los almacenamientos anteriores
+ en el ROB terminen, o a que se conozca su dirección de memoria y puede
+ que su valor, para evitar riesgos RAW de memoria.
 \end_layout
 
 \begin_layout Enumerate
 
 \series bold
 Pos-escritura
+\series default
+ o 
+\series bold
+escritura
 \series default
  (
 \series bold
 WB
 \series default
-): Se difunden los resultados sobre un 
+, 
+\series bold
+W
+\series default
+, 
+\emph on
+\lang english
+Write-Back
+\emph default
+\lang spanish
+): Se difunden los resultados al 
 \series bold
 bus de resultados
 \series default
-, actualizando el ROB, del que otras instrucciones pueden tomar sus operandos.
+, actualizando el ROB y las ER, y se libera la ER.
  Los almacenamientos no hacen nada.
 \end_layout
 
@@ -311,14 +461,20 @@ Commit
 \series default
 \emph default
 \lang spanish
-): Actualiza el estado de la máquina (registros y almacenamientos en memoria)
- en orden de programa desde el ROB, comprobando también las excepciones.
- La terminación en orden facilita deshacer las instrucciones mal especuladas
- y tratar las excepciones.`
-\end_layout
-
-\begin_layout Section
-Algoritmo de Tomasulo
+): Toma varias instrucciones del ROB por ciclo, en orden.
+ Si una causa una excepción, vacía el ROB con las instrucciones siguientes,
+ guarda el contador de programa para la siguiente instrucción e invoca a
+ una rutina de manejo de excepciones.
+ En otro caso, si el estado del registro de destino indica la misma entrada
+ del ROB, escribe el resultado al banco de registros y borra el estado del
+ registro; si es un almacenamiento, escribe el dato en memoria, normalmente
+ a través de un 
+\emph on
+\lang english
+buffer
+\emph default
+\lang spanish
+ de almacenamiento, y finalmente borra la entrada del ROB.
 \end_layout
 
 \end_body
-- 
cgit v1.2.3


From f3fe382159ae9018ac71bdc3f62e11f84cc11c00 Mon Sep 17 00:00:00 2001
From: Juan Marín Noguera <juan.marinn@um.es>
Date: Thu, 31 Dec 2020 13:57:02 +0100
Subject: AOC tema 2

---
 aoc/n2.lyx | 486 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 481 insertions(+), 5 deletions(-)

diff --git a/aoc/n2.lyx b/aoc/n2.lyx
index 53ee52f..281d772 100644
--- a/aoc/n2.lyx
+++ b/aoc/n2.lyx
@@ -111,7 +111,49 @@ Very Long Instruction Word
 \lang spanish
 ): En cada ciclo se carga una 
 \series bold
-macro-instrucción
+ma
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+\series bold
+
+\backslash
+-
+\end_layout
+
+\end_inset
+
+cro-ins
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+\series bold
+
+\backslash
+-
+\end_layout
+
+\end_inset
+
+truc
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+\series bold
+
+\backslash
+-
+\end_layout
+
+\end_inset
+
+ción
 \series default
 , formada por varias instrucciones independientes agrupadas por el compilador.
  El 
@@ -150,15 +192,28 @@ dinámica
  a cambio de necesitar más recursos.
  Con planificación dinámica, la ejecución es fuera de orden, y la terminación
  puede ser en orden o fuera de orden.
- La predicción de saltos es 
+\end_layout
+
+\begin_layout Standard
+Si la ejecución es fuera de orden, distintas instrucciones pueden producir
+ excepciones a la vez, puede pasar bastante tiempo desde que se produce
+ una excepción hasta que se reconoce y una instrucción puede producir una
+ excepción después de que una instrucción posterior se haya ejecutado.
+ Las excepciones son 
 \series bold
-estática
+precisas
 \series default
- si siempre predice el mismo resultado para el mismo salto o 
+ si, cuando se reconocen, el contador del programa apunta a una instrucción,
+ dicha instrucción provocó la excepción si esta es generada por el procesador,
+ las instrucciones anteriores se han completado y las posteriores no han
+ modificado el estado visible del procesador, y son 
 \series bold
-dinámica
+imprecisas
 \series default
  en otro caso.
+ Hoy en día las excepciones imprecisas son inviables, y la mayoría de procesador
+es implementan excepciones precisas impidiendo que una instrucción cambie
+ el estado si hay instrucciones previas sin terminar.
 \end_layout
 
 \begin_layout Standard
@@ -477,5 +532,426 @@ buffer
  de almacenamiento, y finalmente borra la entrada del ROB.
 \end_layout
 
+\begin_layout Standard
+Esto se puede combinar con ejecución especulativa, normalmente para instruccione
+s de salto y de memoria, ejecutando las instrucciones especuladas pero solo
+ confirmando los resultados si la predicción fue correcta.
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Se sabe que esto puede permitir ataques 
+\emph on
+\lang english
+side-channel
+\emph default
+\lang spanish
+.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Section
+Ejecución especulativa
+\end_layout
+
+\begin_layout Standard
+La predicción de saltos es 
+\series bold
+estática
+\series default
+ si siempre predice el mismo resultado para el mismo salto o 
+\series bold
+dinámica
+\series default
+ en otro caso.
+ Algunos mecanismos de predicción de saltos dinámicos son la predicción
+ básica de 
+\begin_inset Formula $n$
+\end_inset
+
+ bits, la de predicción con correlación y la predicción híbrida o de contienda.
+ También se suele usar un 
+\series bold
+\emph on
+\lang english
+buffer
+\emph default
+\lang spanish
+ de destino de saltos
+\series default
+ (
+\series bold
+BTB
+\series default
+, 
+\emph on
+\lang english
+Branch Target Predictor
+\emph default
+\lang spanish
+), que almacena la dirección de destino de saltos previos para poder cargar
+ las instrucciones de dichas direcciones directamente.
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Se sabe que esto puede permitir ataques 
+\emph on
+\lang english
+side-channel
+\emph default
+\lang spanish
+.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Si la longitud del 
+\emph on
+\lang english
+pipeline
+\emph default
+\lang spanish
+ del procesador aumenta, la penalización por fallo de predicción de saltos
+ aumenta al tardar más ciclos en detectar un fallo de predicción, y si el
+ ancho del procesador aumenta, llegan más instrucciones de salto por ciclo
+ (hay una medida de un salto por cada 8 instrucciones) y una mala predicción
+ afectará a más instrucciones.
+ Por ello, si la predicción de saltos es mala, el rendimiento se ve muy
+ afectado.
+\end_layout
+
+\begin_layout Standard
+Para reducir la latencia de memoria se pueden reordenar las instrucciones
+ que acceden a memoria.
+ Si una carga produce un fallo de caché, se pueden ejecutar cargas posteriores,
+ pero en principio, en cualquier caso, no se puede ejecutar una carga hasta
+ que se haya calculado la dirección de todos los almacenamientos anteriores
+ y ninguno de los que están pendientes de confirmar tiene la misma dirección
+ que la carga.
+\end_layout
+
+\begin_layout Standard
+Para mitigar los riesgos de datos, se suele permitir la ejecución especulativa
+ de las cargas aunque no se haya calculado la dirección de los almacenamientos
+ anteriores.
+ Cuando se sabe la dirección de un almacenamiento, se compara con las direccione
+s de las cargas posteriores y, si hay coincidencia, se descartan los resultados
+ de la carga y las instrucciones posteriores.
+\end_layout
+
+\begin_layout Section
+Procesamiento multihilo
+\end_layout
+
+\begin_layout Standard
+Aprovechar al máximo las unidades funcionales de un núcleo con un solo hilo
+ es difícil, por lo que se usa el 
+\series bold
+paralelismo a nivel de hilo
+\series default
+ (
+\series bold
+TLP
+\series default
+, 
+\emph on
+\lang english
+Thread-Level Parallelism
+\emph default
+\lang spanish
+) y se permite ejecutar varios hilos en el mismo núcleo.
+\end_layout
+
+\begin_layout Standard
+Tradicionalmente se reparten los ciclos entre los hilos según una 
+\series bold
+política de ejecución
+\series default
+:
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Entrelazado fijo
+\series default
+: Cada hilo toma un ciclo y ejecuta una instrucción, por turnos.
+ Si un hilo no está listo, se pone una 
+\series bold
+burbuja
+\series default
+ en el cauce, un ciclo en que no se hace nada.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Entrelazado controlado por el sistema operativo
+\series default
+: El sistema asigna una cantidad de 
+\emph on
+\lang english
+slots
+\emph default
+\lang spanish
+, mayor al número de hilos, y los reparte entre los hilos disponibles en
+ cada momento.
+\end_layout
+
+\begin_layout Itemize
+
+\series bold
+Entrelazado controlado por 
+\emph on
+\lang english
+hardware
+\series default
+\emph default
+\lang spanish
+: El 
+\emph on
+\lang english
+hardware
+\emph default
+\lang spanish
+ mantiene una lista de los hilos en ejecución y elige el siguiente hilo
+ a ejecutan según un esquema de prioridades.
+\end_layout
+
+\begin_layout Standard
+El 
+\series bold
+multihilo simultáneo
+\series default
+ (
+\series bold
+SMT
+\series default
+, 
+\series bold
+\emph on
+\lang english
+Simultaneous Multi-Threading
+\series default
+\emph default
+\lang spanish
+) permite ejecutar varios hilos en el mismo ciclo, usando uno los recursos
+ que no usa el otro, especialmente unidades funcionales.
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Se sabe que esto puede permitir ataques 
+\emph on
+\lang english
+side-channel
+\emph default
+\lang spanish
+.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+El sistema operativo debe manejar más hilos, y hay más conflictos de caché
+ y TLB salvo que se aumente el tamaño.
+ Cada hilo necesita sus propios registros, tanto de propósito general como
+ el contador de programa, el registro para la tabla de páginas y los de
+ manejo de excepciones, por lo que se debe propagar el identificador de
+ hilo por todo el cauce para saber qué registros usar.
+ Se replican las tablas de renombrado de registros, pero se comparten el
+ ROB, las cachés y las tablas de predicción de saltos.
+\end_layout
+
+\begin_layout Standard
+El SMT se puede adaptar para que cuando hay alto TLP el ancho de emisión
+ se comparta entre los hilos y cuando hay poco no se reparta y se dedique
+ al ILP.
+\end_layout
+
+\begin_layout Section
+Vectorización
+\end_layout
+
+\begin_layout Standard
+Las aplicaciones multimedia, como de realidad virtual, comunicaciones, procesami
+ento de imágenes, reconocimiento de voz, etc., así como la compresión y el
+ cifrado, requieren cálculo intensivo, a menudo con restricciones de tiempo
+ real, y es común que apliquen la misma operación a todos los elementos
+ de una lista.
+\end_layout
+
+\begin_layout Standard
+Los procesadores de propósito general no están optimizados para estas aplicacion
+es, por lo que surgen las 
+\series bold
+extensiones multimedia
+\series default
+ con instrucciones SIMD para explotar el paralelismo de datos con el coste
+ mínimo de recursos del chip.
+ En la arquitectura IA-32 de Intel y AMD, se crean:
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+MMX
+\series default
+ (
+\emph on
+Multi-Media Extensions
+\emph default
+): Operaciones con 8 enteros de 8 bits o 4 de 16 bits.
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+SSE
+\series default
+ (
+\emph on
+Streaming SIMD Extensions
+\emph default
+), SSE2 y SSE4.2: 16 enteros de 8 bits, 8 de 16 bits, 4 de 32 bits, 4 números
+ de punto flotante de 32 bits o 2 de 64 bits.
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+AVX
+\series default
+ (
+\emph on
+Advanced Vector Extensions
+\emph default
+) y 
+\series bold
+AVX2
+\series default
+: 4 números enteros o de punto flotante de 64 bits.
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+AVX-512
+\series default
+: 8 números enteros o de punto flotante de 64 bits.
+\end_layout
+
+\begin_layout Standard
+Intel también crea 
+\series bold
+IMCI
+\series default
+ (
+\emph on
+Intel Many-Core Instructions
+\emph default
+) para la primera generación de Intel Xeon 
+\lang english
+Phi
+\lang spanish
+, con registros de 512 bits.
+ En cualquier caso, los operandos deben estar en posiciones de memoria consecuti
+vas y alineadas al tamaño del registro.
+\end_layout
+
+\begin_layout Standard
+Esto es como lo que hacen los procesadores vectoriales en las GPUs, aunque
+ en general con modos de direccionamiento más sofisticados e instrucciones
+ para mover datos de una parte del registro a otra.
+ Muchas extensiones SIMD soportan instrucciones como 
+\family typewriter
+FMA
+\family default
+ (
+\emph on
+\lang english
+Fused Multiply-Add
+\emph default
+\lang spanish
+), que multiplica dos registros y suma otro al resultado elemento a elemento.
+\end_layout
+
+\begin_layout Standard
+Los compiladores suelen intentar usar instrucciones SIMD para los bucles
+ más internos del programa, pero el programador debe elegir el compilador
+ y las opciones adecuados, reordenar el código para hacer más visible lo
+ que ocurre y, si es necesario, usar 
+\emph on
+\lang english
+intrinsics
+\emph default
+\lang spanish
+, funciones que el compilador trata de forma especial, o escribir en ensamblador.
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Vectorizar
+\series default
+ es convertir bucles con instrucciones escalares para que usen instrucciones
+ SIMD, y lo suele hacer el compilador tras asegurarse de que esto no modifica
+ los resultados del cálculo, viendo si una iteración accede a los datos
+ producidos en iteraciones previas.
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Cuando hay un registro de acumulación, por ejemplo al sumar una lista de
+ números, este se suele convertir a un registro vectorial con varios acumuladore
+s a los que luego se les aplica una reducción.
+ Esto no se puede hacer en punto flotante porque las operaciones de punto
+ flotante no son conmutativas ni asociativas, pero muchos compiladores tienen
+ opciones para no respetar el estándar en este caso y tratar las operaciones
+ como conmutativas y asociativas.
+ Ejemplos son 
+\family typewriter
+gcc
+\family default
+ (
+\emph on
+\lang english
+GNU C Compiler
+\emph default
+\lang spanish
+) con la orden 
+\family typewriter
+-ffast-math
+\family default
+ y el software privativo 
+\family typewriter
+icc
+\family default
+ (
+\emph on
+\lang english
+Intel Compiler Collection
+\emph default
+\lang spanish
+), solo para arquitecturas Intel, que nunca respeta el estándar.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
 \end_body
 \end_document
-- 
cgit v1.2.3