path: root/etc/n4.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
\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 swiss
\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
Hoy en día (a precio razonable) podemos construir memorias de gran capacidad
 pero lentas, o memorias rápidas pero con poca capacidad.
 Para crear la ilusión de que tenemos una memoria con ambas características,
 combinamos tipos de memoria con distintas velocidades y tamaños en una
 
\series bold
jerarquía de memoria
\series default
, formada normalmente por los siguientes componentes, de mayor a menor cercanía
 a la CPU:
\end_layout

\begin_layout Itemize
Registros de la CPU.
\end_layout

\begin_layout Itemize

\series bold
Memoria caché
\series default
 (SRAM).
 Suele haber 3 niveles (llamados L1–L3), donde el L3 puede estar fuera de
 la CPU (los demás están dentro) y L1 es el de menor capacidad pero menor
 tiempo de acceso, y por tanto el más cercano a la CPU.
\end_layout

\begin_layout Itemize
Memoria principal (
\series bold
SDRAM
\series default
, 
\emph on
\lang english
Synchronous DRAM
\emph default
\lang spanish
).
\end_layout

\begin_layout Itemize
Almacenamiento secundario local (discos SSD o magnéticos).
 Los 
\series bold
discos SSD
\series default
 (
\emph on
\lang english
Solid State Drive
\emph default
\lang spanish
) usan memoria flash para almacenar los datos y por tanto son más rápidos
 que los 
\series bold
discos duros
\series default
 o 
\series bold
magnéticos
\series default
, pues no presentan limitaciones mecánicas, si bien quedan lejos de las
 memorias RAM.
\end_layout

\begin_layout Itemize
Almacenamiento secundario remoto (sistemas de ficheros distribuidos, servidores,
 etc.).
\end_layout

\begin_layout Standard
El objetivo es proporcionar la máxima capacidad de memoria con la tecnología
 más barata pero con un tiempo medio de acceso similar al de la tecnología
 más rápida.
 Por lo general, los datos solo se transfieren entre niveles adyacentes.
\end_layout

\begin_layout Section
Funcionamiento
\end_layout

\begin_layout Standard

\series bold
Principio de localidad
\series default
: en un momento concreto, los programas acceden a una parte relativamente
 pequeña de su espacio de direcciones.
 Tipos:
\end_layout

\begin_layout Itemize

\series bold
Localidad temporal
\series default
: Si se consulta un dato, probablemente será consultado próximamente.
 En los programas aparecen multitud de bucles, por lo que se accederá repetidame
nte a instrucciones y datos.
\end_layout

\begin_layout Itemize

\series bold
Localidad espacial
\series default
: Si se consulta un dato, probablemente serán consultados otros cercanos.
 A las instrucciones se suele acceder secuencialmente, así como a los elementos
 de una tabla.
\end_layout

\begin_layout Standard
Para aprovechar la localidad espacial, la información se transfiere entre
 niveles adyacentes en 
\series bold
bloques
\series default
, cuyo tamaño depende de los niveles.
 El 
\series bold
tamaño de bloque
\series default
 es el número de bytes que contiene, y para las cachés suele ser 64.
 Decimos que hay un 
\series bold
acierto
\series default
 (
\emph on
hit
\emph default
) cuando la información pedida por el procesador se encuentra en el nivel
 superior, y un 
\series bold
fallo
\series default
 (
\emph on
miss
\emph default
) cuando no.
\end_layout

\begin_layout Standard
La 
\series bold
tasa de aciertos
\series default
 (
\emph on
hit rate
\emph default
) es la fracción de accesos a memoria que son aciertos, y se usa como medida
 del rendimiento, mientras que la 
\series bold
tasa de fallos
\series default
 (
\emph on
miss rate
\emph default
) es 1 menos la tasa de aciertos.
 El 
\series bold
tiempo de acierto
\series default
 es el tiempo necesario para acceder al nivel superior de la memoria, incluyendo
 el necesario para determinar si el acceso es un acierto o un fallo, y la
 
\series bold
penalización por fallo
\series default
 es el tiempo necesario para reemplazar un bloque del nivel superior por
 otro del nivel inferior.
\end_layout

\begin_layout Standard
Las direcciones de memoria se asignan a bytes individuales, lo que llamamos
 
\series bold
dirección de byte
\series default
 (
\begin_inset Formula $D_{byte}$
\end_inset

).
 Como las palabras (en general) son de varios bytes, cada palabra tiene
 varias direcciones de byte, a las que asignamos una 
\series bold
dirección de palabra
\series default
 con 
\begin_inset Formula $D_{palabra}=\left\lfloor \frac{D_{byte}}{T_{palabra}}\right\rfloor $
\end_inset

, donde 
\begin_inset Formula $T_{palabra}$
\end_inset

 es el número de bytes de la palabra, y el resto de esta división es el
 desplazamiento de byte dentro de la palabra.
 Igualmente, podemos asignar a cada bloque una 
\series bold
dirección de bloque
\series default
, de forma que 
\begin_inset Formula $D_{bloque}=\left\lfloor \frac{D_{byte}}{T_{bloque}}\right\rfloor $
\end_inset

, siendo 
\begin_inset Formula $T_{bloque}$
\end_inset

 el tamaño del bloque, y el resto de esta división es el desplazamiento
 de byte dentro del bloque.
 Tanto el tamaño de palabra como el de bloque son potencias de 2, por lo
 que el cálculo de las direcciones y desplazamientos es trivial.
\end_layout

\begin_layout Section
Estructura
\end_layout

\begin_layout Standard
Una caché esta organizada en una serie de 
\series bold
conjuntos
\series default
 de bloques o 
\series bold
huecos
\series default
, y una serie de 
\series bold
vías
\series default
, que son el número de bloques por conjunto.
 Llamamos 
\series bold
asociatividad
\series default
 de la caché al número de vías que contiene.
 A cada bloque le corresponde un conjunto, dado por el resto de la dirección
 de bloque entre el número de conjuntos, y dentro de este puede ocupar cualquier
a de los huecos.
\end_layout

\begin_layout Standard
Una mayor asociatividad aumenta la tasa de acierto por tener más libertad
 a la hora de elegir qué bloques quitar, pero también aumenta el número
 de comparaciones que hay que realizar, por lo que aumenta el coste al necesitar
 más comparadores, así como el tiempo de acierto.
\end_layout

\begin_layout Standard
Una caché se dice 
\series bold
de correspondencia directa
\series default
 si tiene sólo una vía (un bloque por conjunto), y 
\series bold
totalmente asociativa
\series default
 si sólo tiene un conjunto.
 A cada posición de la caché se le añade una 
\series bold
etiqueta
\series default
 (
\emph on
\lang english
tag
\emph default
\lang spanish
) dada por 
\begin_inset Formula $E=\left\lfloor \frac{D_{bloque}}{N_{S}}\right\rfloor $
\end_inset

, donde 
\begin_inset Formula $N_{S}$
\end_inset

 es el número de conjuntos.
 Además, es necesario un 
\series bold
bit de validez
\series default
 en cada hueco que indique que el bloque tiene información válida.
\end_layout

\begin_layout Section
Políticas de escritura
\end_layout

\begin_layout Itemize

\series bold
Escritura directa
\series default
 (
\emph on
\lang english
write through
\emph default
\lang spanish
): Las escrituras se hacen a la vez en la caché y en memoria.
 Si el bloque no está en caché, se suele escribir directamente la palabra
 en memoria principal (
\emph on
\lang english
no write allocate
\emph default
\lang spanish
), si bien también se puede traer el bloque a la caché (
\emph on
\lang english
write allocate
\emph default
\lang spanish
), pero esto es mucho menos común.
\end_layout

\begin_deeper
\begin_layout Standard
Esta política es más fácil de implementar y tiene la ventaja de que los
 fallos son menos costosos.
 Sin embargo, en la práctica es necesario un 
\series bold
\emph on
\lang english
buffer
\emph default
\lang spanish
 de escrituras
\series default
 que almacene los datos para ser escritos de forma que el procesador no
 tenga que detenerse hasta que acabe la escritura, salvo que el 
\emph on
\lang english
buffer
\emph default
\lang spanish
 esté lleno.
\end_layout

\end_deeper
\begin_layout Itemize

\series bold
Pos-escritura
\series default
 (
\emph on
\lang english
write back
\emph default
\lang spanish
): Las escrituras se hacen sólo en la caché, y sólo se actualiza la información
 en memoria al sacar el bloque de la caché.
 Es necesario un 
\series bold
bit de modificación
\series default
 o 
\series bold
de sucio
\series default
 (
\emph on
\lang english
dirty bit
\emph default
\lang spanish
) en cada bloque, y si el bloque no está en caché se debe traer a caché.
\end_layout

\begin_deeper
\begin_layout Standard
Esta política tiene la ventaja de que en caso de acierto se puede escribir
 más rápidamente, y que múltiples escrituras en un bloque requieren una
 sola escritura en memoria, pudiendo hacer uso de 
\series bold
escritura en ráfaga
\series default
 para conseguir mayor ancho de banda.
\end_layout

\end_deeper
\begin_layout Section
Políticas de reemplazo
\end_layout

\begin_layout Standard
En una caché asociativa (con más de una vía), al traer un bloque se puede
 poner en cualquier hueco del conjunto, y si el conjunto está lleno (como
 ocurre normalmente) hay que elegir qué bloque sacar de la cache.
 Para ello hay varias políticas:
\end_layout

\begin_layout Itemize

\series bold
Aleatoria
\series default
: Se elige un bloque al azar.
 Es la más sencilla de construir.
\end_layout

\begin_layout Itemize

\series bold
LRU
\series default
 (
\emph on
\lang english
Least Recently Used
\emph default
\lang spanish
, Menos Recientemente Usado): Se elige el bloque que haya estado más tiempo
 sin ser accedido.
 Consigue menores tasas de fallo que el aleatorio, pero al aumentar la asociativ
idad se vuelve demasiado costoso, pues necesita mantener mucha información.
\end_layout

\begin_layout Itemize

\series bold
Pseudo-LRU
\series default
: Esquemas que 
\begin_inset Quotes cld
\end_inset

imitan
\begin_inset Quotes crd
\end_inset

 al LRU pero con implementación más sencilla.
 Por ejemplo, el que utiliza un 
\series bold
bit de uso
\series default
 o 
\series bold
de referencia
\series default
 en cada bloque, que se pone a cero al traer el bloque y a 1 cada vez que
 se accede a él, volviéndose a poner a cero en todos los bloques periódicamente.
 A la hora de elegir un bloque que sustituir, se prefiere uno que tenga
 a 0 el bit de uso.
\end_layout

\begin_layout Itemize

\series bold
NRU
\series default
 (
\emph on
\lang english
Not Recently Used
\emph default
\lang spanish
): Para una caché de asociatividad 2, se puede implementar el LRU con un
 sólo bit por conjunto.
\end_layout

\begin_layout Section
Tamaño real y rendimiento
\end_layout

\begin_layout Standard
Si 
\begin_inset Formula $N_{S}$
\end_inset

 es el número de conjuntos de la caché, 
\begin_inset Formula $A$
\end_inset

 es la asociatividad, 
\begin_inset Formula $T_{bloque}$
\end_inset

 es el tamaño de bloque, 
\begin_inset Formula $W_{dir}$
\end_inset

 el número de bits de las direcciones de memoria y 
\begin_inset Formula $N_{bits-control}$
\end_inset

 el número de bits de control necesarios por bloque (de 1 a 3 según lo visto
 y puede que algunos más en una caché real), el tamaño útil de la caché
 en bytes será 
\begin_inset Formula $T_{útil}=N_{S}AT_{bloque}$
\end_inset

.
\end_layout

\begin_layout Standard
Por su parte, el tamaño total en bits será 
\begin_inset Formula $T_{total}=N_{S}T_{conjunto}$
\end_inset

, con 
\begin_inset Formula $T_{conjunto}=AT_{entrada}$
\end_inset

, 
\begin_inset Formula $T_{entrada}=N_{bits-control}+W_{etiqueta}+8T_{bloque}$
\end_inset

 y 
\begin_inset Formula $W_{etiqueta}=W_{dir}-\log_{2}N_{S}-\log_{2}T_{bloque}$
\end_inset

.
 En resumen,
\begin_inset Formula 
\[
T_{total}=N_{S}A(8T_{bloque}+N_{bits-control}+W_{dir}-\log_{2}N_{S}-\log_{2}T_{bloque})
\]

\end_inset


\end_layout

\begin_layout Standard
Para hallar el rendimiento de la caché usamos que 
\begin_inset Formula $T_{ejec}=T_{CPU}+T_{bloqueo}$
\end_inset

, siendo 
\begin_inset Formula $T_{CPU}$
\end_inset

 el tiempo de ejecución normal de CPU, contando aciertos en accesos de memoria,
 y 
\begin_inset Formula $T_{bloqueo}$
\end_inset

 el bloqueo debido a fallos de caché.
 Así, 
\begin_inset Formula $T_{bloqueo}=N_{accesos}T_{F}P_{F}$
\end_inset

, donde 
\begin_inset Formula $N_{accesos}$
\end_inset

 es el total de accesos, 
\begin_inset Formula $T_{F}$
\end_inset

 la tasa de fallos y 
\begin_inset Formula $P_{F}$
\end_inset

 la penalización por fallos.
\end_layout

\begin_layout Standard
Ahora bien, normalmente un procesador tiene cachés separadas para datos
 e instrucciones para evitar que los datos 
\begin_inset Quotes cld
\end_inset

expulsen
\begin_inset Quotes crd
\end_inset

 instrucciones y viceversa y mejorar así el rendimiento.
 Por tanto, si la caché de instrucciones tiene tasa de fallos 
\begin_inset Formula $T_{Fi}$
\end_inset

 y penalización 
\begin_inset Formula $P_{Fi}$
\end_inset

 y la de datos tiene tasa de fallos 
\begin_inset Formula $T_{Fd}$
\end_inset

 y penalización 
\begin_inset Formula $P_{Fd}$
\end_inset

, y 
\begin_inset Formula $D/I$
\end_inset

 es la tasa de acceso a datos por instrucción (accesos a datos por número
 de instrucciones), nos queda que
\begin_inset Formula 
\[
T_{bloqueo}=N_{instrucciones}(T_{Fi}P_{Fi}+D/I\cdot T_{Fd}P_{Fd})
\]

\end_inset

donde 
\begin_inset Formula $N_{instrucciones}$
\end_inset

 es el número de instrucciones que se ejecutan.
\end_layout

\end_body
\end_document