#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