path: root/aoc/n1.lyx

#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.
 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
Problemas
\end_layout

\begin_layout Subsection
Potencia
\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 Subsection
Paralelismo
\end_layout

\begin_layout Standard
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
 y por tanto consume mucha energía.
\end_layout

\begin_layout Subsection
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 Subsection
Fiabilidad
\end_layout

\begin_layout Standard
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
, 
\emph on
\lang english
Error Correction Codes
\emph default
\lang spanish
).
 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
clock skew
\series default
\emph default
\lang spanish
.
\end_layout

\begin_layout Standard
Podemos medir la fiabilidad en 
\series bold
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
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

\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 Subsection
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

\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