#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 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 aprovechar los recursos de un multiprocesador se suele usar el modelo \series bold STMD \begin_inset Foot status open \begin_layout Plain Layout Nadie lo llama así. \end_layout \end_inset \series default ( \emph on \lang english Single Thread, Multiple Data \emph default \lang spanish ) o \series bold SPMD \series default ( \emph on \lang english Single Program, Multiple Data \emph default \lang spanish ), una forma de MIMD consistente en ejecutar el mismo programa con distintas entradas en varios procesadores a la vez para obtener resultados más rápido. \end_layout \begin_layout Section Cachés \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash sremember{ETC} \end_layout \end_inset \end_layout \begin_layout Standard \series bold 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 [...] en memoria [...] ( \emph on \lang english no write allocate \emph default \lang spanish ), [...] también se puede traer el bloque a la caché ( \emph on \lang english write allocate \emph default \lang spanish ) [...] \end_layout \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 [...] memoria al sacar el bloque [...]. Es necesario un \series bold bit de modificación \series default [...] en cada bloque [...]. \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash eremember \end_layout \end_inset \end_layout \begin_layout Standard En la práctica se usan \series bold cachés multinivel \series default , con niveles normalmente de L1 a L3, siendo L1 la caché más cercana al procesador y con menor latencia pero menor capacidad. La \series bold política de inclusión \series default indica si los datos en un nivel de caché están también en los niveles inferiore s (de mayor número), y según esta la caché puede ser: \end_layout \begin_layout Itemize \series bold Inclusiva \series default : Todas las líneas en una caché están en las cachés de niveles inferiores, por lo que comprobar si un procesador tiene en su caché una copia de una línea solo requiere comprobar la caché externa. \end_layout \begin_layout Itemize \series bold Exclusiva \series default : Cada línea está en un único nivel de caché, y cuando un nivel requiere una línea de caché, intercambia la línea con la caché inferior. \end_layout \begin_layout Itemize \series bold Ni inclusiva ni exclusiva \series default ( \series bold \lang english NINE \series default \lang spanish , \emph on \lang english Non-Inclusive Non-Exclusive \emph default \lang spanish ): Las líneas de un nivel de caché pueden estar o no en el nivel inferior. \end_layout \begin_layout Standard Los fallos de caché pueden ser: \end_layout \begin_layout Itemize \series bold Obligatorios \series default , el primer acceso a una línea. Ocurrirían incluso con una caché infinita, aunque se pueden mitigar con \emph on \lang english prefetching \emph default \lang spanish . \end_layout \begin_layout Itemize \series bold De capacidad \series default , cuando la línea se expulsó previamente porque la caché no es lo suficientement e grande. Ocurrirían aun si la caché fuera totalmente asociativa. \end_layout \begin_layout Itemize \series bold De conflicto \series default , debidas a la falta de asociatividad. El resto. \end_layout \begin_layout Standard Los núcleos en un CMP suelen ser \series bold multiprocesadores simétricos \series default ( \series bold SMP \series default , \emph on \lang english symmetric multiprocessors \emph default \lang spanish ), que acceden a una memoria común con latencia de acceso uniforme, pero tienen cachés que pueden ser: \end_layout \begin_layout Enumerate Totalmente separadas, una caché por procesador. Es el caso de las cachés L1, de las que hay dos por procesador para datos e instrucciones. Dos cachés separadas pueden tener el mismo dato. \end_layout \begin_layout Enumerate Compartidas, para aprovechar mejor el espacio a cambio de un acceso más lento. \end_layout \begin_layout Enumerate \series bold NUCA \series default ( \emph on \lang english Non-Uniform Cache Access \emph default \lang spanish ): Una caché por procesador pero lógicamente compartida, de modo que si un procesador necesita un bloque que no está en su caché se lo pide a las cachés de los otros procesadores. \end_layout \begin_layout Standard También hay procesadores con \series bold DSM \series default ( \emph on \lang english Distributed Shared Memory \emph default \lang spanish ), una arquitectura \series bold NUMA \series default ( \emph on \lang english Non-Uniform Memory Access \emph default \lang spanish , acceso a memoria no uniforme) en la que cada núcleo tiene una porción de memoria y acceso a E/S y puede acceder a la porción de otros procesadores mediante una red de interconexión. \end_layout \begin_layout Section Coherencia de cachés \end_layout \begin_layout Standard Un sistema de memoria multiprocesador es \series bold coherente \series default si todas las copias accesibles de la misma posición de memoria tienen el mismo valor, esto es, si el resultado de cualquier ejecución de un programa es tal que, para una posición de memoria, se puede construir una ordenación secuencial de las operaciones realizadas sobre dicha posición y en la que las operaciones emitidas por un mismo procesador aparecen en el orden en que son emitidas por el procesador al sistema de memoria y el valor devuelto por una operación de lectura es el escrito en la última escritura con la ordenación secuencial. \end_layout \begin_layout Standard Equivalentemente, es coherente si el resultado de cualquier ejecución de un programa se puede obtener dividiendo la ejecución de cada hilo en una secuencia de épocas o momentos lógicos de forma que en cada época o bien hay un único procesador leyendo y escribiendo de una dirección o bien ningún procesador escribe en la dirección, y el valor en una dirección al comienzo de una época para cualquier lector es el mismo que el que tenía al final de la última época en que se escribió a la dirección. \end_layout \begin_layout Standard En sistemas de memoria compartida, el \emph on \lang english hardware \emph default \lang spanish mantiene la coherencia mediante un \series bold protocolo de coherencia \series default , que debe ser correcto y queremos que sea rápido sin consumir mucha energía y requiera poco \emph on \lang english hardware \emph default \lang spanish . Un procesador mononúcleo puede tener problemas de coherencia por la E/S, pues un controlador DMA puede escribir a una zona de memoria pero el procesador lee de caché. Lo que se hace entonces es desactivar el uso de caché para esa zona. Para procesadores multinúcleo los protocolos pueden ser: \end_layout \begin_layout Itemize \series bold Basados en invalidación \series default : Cuando un procesador modifica su copia, notifica al resto para que descarten la suya. Solo hay que comunicar la primera escritura, pues tras esta no existen más copias hasta que otro nodo vuelva a acceder al dato, y el resto de escrituras a la misma línea de caché son locales. \end_layout \begin_layout Itemize \series bold Basados en actualización \series default : Cuando un procesador modifica su copia, indica su modificación al resto para que la actualicen. No invalida copias de otros nodos, por lo que no aumenta la tasa de fallos, pero usa mucho ancho de banda en actualizaciones que en general no son accedidas de nuevo por otros nodos. \end_layout \begin_layout Standard La invalidación o actualización de un bloque en un nivel de caché debe transmiti rse a los niveles superiores. La mayoría de sistemas usan protocolos basados en invalidación. \end_layout \begin_layout Subsection MSI con fisgoneo \end_layout \begin_layout Standard Los protocolos \series bold \emph on \lang english snoopy \series default \emph default \lang spanish o basados en \series bold fisgoneo \series default se basan en que los nodos puedan ver los fallos de caché del resto y actuar en consecuencia, invalidando las copias si hace falta o proporcionando los datos. Esto requiere una red de interconexión ( \series bold NoC \series default , \emph on \lang english Network on Chip \emph default \lang spanish ) totalmente ordenada que permita la difusión, como un bus o cualquier otra red si se obliga a los mensajes a pasar por un punto de serialización, aunque hay sistemas modernos que usan variantes del fisgoneo que funcionan con redes que no garantizan un orden total, normalmente anillos. Los protocolos basados en fisgoneo funcionan bien cuando hay pocos nodos, pero con muchos nodos la red totalmente ordenada es un cuello de botella. \end_layout \begin_layout Standard El protocolo \series bold MSI \series default es un protocolo basado en invalidación en el que los bloques pueden estar en uno de tres estados: \end_layout \begin_layout Enumerate \series bold \emph on \lang english Modified \series default \emph default \lang spanish : Los datos están actualizados, la copia en memoria es obsoleta y ninguna otra caché tiene copia. \end_layout \begin_layout Enumerate \series bold \emph on \lang english Shared \series default \emph default \lang spanish : Los datos están actualizados en caché y memoria, y otras cachés pueden tener copia. \end_layout \begin_layout Enumerate \series bold \emph on \lang english Invalid \series default \emph default \lang spanish : Bloque inválido. \end_layout \begin_layout Standard Los mensajes intercambiados son: \end_layout \begin_layout Itemize Del procesador (o nivel de caché superior) a la caché, petición de lectura ( \family typewriter ReqRd \family default ) y de escritura ( \family typewriter ReqWr \family default ), a las que la caché siempre acaba respondiendo. \end_layout \begin_layout Itemize En el bus, petición de lectura ( \family typewriter BusRd \family default ), de lectura exclusiva (con intención de modificar, \family typewriter BusRdX \family default ) o de invalidación de bloque ( \family typewriter BusUpd \family default ), y envío de datos a otra caché ( \family typewriter Flush \family default ) o a memoria y opcionalmente a otra caché ( \family typewriter FlushM \family default ). \end_layout \begin_layout Standard El diagrama de estados resultante está en la figura \begin_inset CommandInset ref LatexCommand ref reference "fig:msi-snoopy" plural "false" caps "false" noprefix "false" \end_inset . Una versión simplificada del protocolo sustituye \family typewriter Flush \family default y \family typewriter FlushM \family default por un solo mensaje \family typewriter BusWr \family default , equivalente a \family typewriter FlushM \family default , y \family typewriter BusUpd \family default por \family typewriter BusRdX \family default . \end_layout \begin_layout Standard \begin_inset Float figure wide false sideways false status open \begin_layout Plain Layout \align center \begin_inset External template VectorGraphics filename n3.1.dot scale 50 \end_inset \end_layout \begin_layout Plain Layout \begin_inset Caption Standard \begin_layout Plain Layout \begin_inset CommandInset label LatexCommand label name "fig:msi-snoopy" \end_inset Diagrama de estados del protocolo MSI con fisgoneo. \end_layout \end_inset \end_layout \end_inset \end_layout \begin_layout Standard Cuando se recibe un \family typewriter BusRd \family default de un bloque modificado, hacer \family typewriter FlushM \family default y compartir el bloque permite que posteriores lecturas por el procesador original resulten en acierto de caché, pero si el nuevo procesador escribe en el bloque, tiene que notificar la actualización para invalidar el bloque y la latencia de la escritura aumenta. Si el patrón de acceso es migratorio; por ejemplo, si se va actualizando un contador compartido, se escribe el bloque continuamente a memoria (más comúnmente a caché L3 compartida), por lo que puede ser mejor hacer \family typewriter Flush \family default e invalidar el bloque. \end_layout \begin_layout Standard En general es preferible compartir cuando es más probable que el procesador original vuelva a leer y es preferible invalidar cuando es más probable que el patrón de acceso sea migratorio. Algunos procesadores adaptan el protocolo según el tipo de acceso observado. \end_layout \begin_layout Subsection Directorios \end_layout \begin_layout Standard Un directorio es una tabla cuyas entradas están formadas por la etiqueta de un bloque al que asocia bits de presencia, indicando en qué núcleos está el bloque normalmente mediante un vector de bits, y bits de estado. Se usa como punto de serialización para dar escalabilidad a los protocolos de fisgoneo. \end_layout \begin_layout Standard Puede ser centralizado, pero como tiene que ser consultado cada vez que un acceso a memoria falla en una caché local, es mejor que sea distribuido, con varios directorios cada uno encargado de un subconjunto de direcciones de memoria. La latencia de acceso es variable porque puede el directorio asociado a una dirección puede estar conectado al nodo local de la red o a uno más o menos remoto. \end_layout \begin_layout Standard Para que un protocolo de directorio sea escalable debe tener buen rendimiento, minimizando el ancho de banda por fallo, especialmente en el camino crítico, y la frecuencia de los fallos, y reduciendo la sobrecarga de memoria asociada al estado del directorio. \end_layout \begin_layout Standard El protocolo MSI basado en directorio usa 3 estados posibles para una entrada de directorio: NC ( \emph on \lang english Non-Cached \emph default \lang spanish ), S ( \emph on \lang english Shared \emph default \lang spanish ) y P ( \emph on \lang english Private \emph default \lang spanish ). Los mensajes son: \end_layout \begin_layout Enumerate Del procesador a la caché: Petición de lectura ( \family typewriter ReqRd \family default ) y de escritura ( \family typewriter ReqWr \family default ). \end_layout \begin_layout Enumerate Del directorio a las cachés: Petición de invalidación ( \family typewriter CInv \family default ), de obtener copia para lectura ( \family typewriter CRd \family default ) y de enviar copia para escritura ( \family typewriter CWr \family default ). \end_layout \begin_layout Enumerate De las cachés al directorio: Petición de lectura ( \family typewriter DirRd \family default ), escritura ( \family typewriter DirWr \family default ) y volcado en memoria ( \family typewriter DirWB \family default ); confirmación de invalidación ( \family typewriter CInvOK \family default ) y de envío de copia para lectura ( \family typewriter CRdOK \family default , contiene el dato leído) y escritura ( \family typewriter CWrOK \family default ). \end_layout \begin_layout Enumerate Respuesta con datos solicitados ( \family typewriter Data \family default ), de una caché a otra o, si el dato no estaba en ninguna caché, del directorio a la caché, tras solicitar el dato de memoria. \end_layout \begin_layout Standard \begin_inset Float figure wide false sideways false status open \begin_layout Plain Layout \align center \begin_inset External template VectorGraphics filename n3.2.dot scale 50 \end_inset \end_layout \begin_layout Plain Layout \begin_inset Caption Standard \begin_layout Plain Layout \begin_inset CommandInset label LatexCommand label name "fig:msi-dir" \end_inset Transiciones del directorio en MSI con directorios, donde \family typewriter c \family default es la caché peticionaria y \family typewriter r \family default es una caché remota que tiene el dato. \end_layout \end_inset \end_layout \end_inset \end_layout \begin_layout Standard \begin_inset Float figure wide false sideways false status open \begin_layout Plain Layout \align center \begin_inset External template VectorGraphics filename n3.3.dot scale 50 \end_inset \end_layout \begin_layout Plain Layout \begin_inset Caption Standard \begin_layout Plain Layout \begin_inset CommandInset label LatexCommand label name "fig:msi-dir-cache" \end_inset Transiciones de las cachés en MSI con directorios, donde \family typewriter c \family default es la caché que pide un dato a esta. \end_layout \end_inset \end_layout \end_inset \end_layout \begin_layout Standard Los diagramas de transición se muestran en las figuras \begin_inset CommandInset ref LatexCommand ref reference "fig:msi-dir" plural "false" caps "false" noprefix "false" \end_inset y \begin_inset CommandInset ref LatexCommand ref reference "fig:msi-dir-cache" plural "false" caps "false" noprefix "false" \end_inset . En la práctica queremos que varios procesadores puedan ejecutar transacciones a la vez, incluso hacia la misma línea de caché, lo que supone mucha complejida d. \end_layout \begin_layout Subsection Datos compartidos \end_layout \begin_layout Standard Cuando varios procesadores usan la misma línea de caché a la vez se dice que comparten la línea. En los protocolos de invalidación, las escrituras frecuentes a una línea compartida degradan el rendimiento. Distinguimos: \end_layout \begin_layout Itemize \series bold Verdadera compartición \series default : Los hilos usan la misma variable. Esto no es un problema si la variable es de sólo lectura, pero si se escribe frecuentemente se deberían usar copias de la variable por hilo si el algoritmo lo permite. \end_layout \begin_layout Itemize \series bold Falsa compartición \series default : Los hilos usan variables distintas en el mismo bloque. La solución es almacenar las variables en bloques distintos o evitar el entrelazamiento de los accesos. \end_layout \begin_layout Subsection Mejoras a MSI \end_layout \begin_layout Standard MSI se puede optimizar con nuevos estados: \end_layout \begin_layout Enumerate \series bold \emph on \lang english Exclusive \series default \emph default \lang spanish : No se ha modificado el bloque pero ninguna otra caché tiene una copia. Esto es habitual, y codificarlo en otro estado evita enviar mensajes de coherencia para datos privados. \end_layout \begin_layout Enumerate \series bold \emph on \lang english Owner \series default \emph default \lang spanish : Otras cachés pueden tener copias en estado \emph on \lang english Shared \emph default \lang spanish , pero la copia en memoria no está actualizada y esta caché es la encargada de dar los datos en caso de fallo. Esto evita escribir en memoria cuando otro núcleo quiere leer un dato que se ha modificado. \end_layout \begin_layout Standard Esto nos da los protocolos \series bold MESI \series default (MSI con \emph on \lang english Exclusive \emph default \lang spanish , figura \begin_inset CommandInset ref LatexCommand ref reference "fig:mesi-snoppy" plural "false" caps "false" noprefix "false" \end_inset ), \series bold MOSI \series default (MSI con \emph on \lang english Owner \emph default \lang spanish ) y \series bold MOESI \series default (MSI con \emph on \lang english Exclusive \emph default \lang spanish y \emph on \lang english Owner \emph default \lang spanish ). \end_layout \begin_layout Standard \begin_inset Float figure wide false sideways false status open \begin_layout Plain Layout \align center \begin_inset External template VectorGraphics filename n3.4.dot scale 50 \end_inset \end_layout \begin_layout Plain Layout \begin_inset Caption Standard \begin_layout Plain Layout \begin_inset CommandInset label LatexCommand label name "fig:mesi-snoppy" \end_inset Diagrama de transición de MESI basado en fisgoneo. Una señal \begin_inset Formula $E$ \end_inset se activa cuando ningún nodo ha solicitado el bloque. \end_layout \end_inset \end_layout \end_inset \end_layout \begin_layout Section Modelos de consistencia de memoria \end_layout \begin_layout Standard El compilador y los núcleos del procesador pueden cambiar el orden de cargas y almacenamientos, por lo que en principio un hilo no puede depender del orden en que otro carga y almacena los valores. Como hace falta un orden para la sincronización, necesitamos un \series bold modelo de memoria \series default , una especificación de las restricciones en el orden en que las operaciones de memoria de un hilo se hacen visibles al resto. Todos los modelos son coherentes, pero la \series bold consistencia \series default , la generalización de la coherencia a posiciones de memoria distintas, es rara. \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash begin{samepage} \end_layout \end_inset \end_layout \begin_layout Standard Algunos modelos: \end_layout \begin_layout Itemize \series bold Consistencia estricta \series default : La escritura a una variable por un procesador es vista instantáneamente por el resto. Este modelo es determinista y asume un reloj global en el procesador, y aunque es fácil de conseguir en procesadores mononúcleo cuando no hacen E/S, enlentece mucho los sistemas distribuidos. \end_layout \begin_layout Itemize \series bold Consistencia secuencial \series default : Las escrituras no tienen que hacerse visibles instantáneamente, pero son \series bold atómicas \series default , vistas en el mismo orden por todos los hilos, y en particular las de un mismo hilo se ven en el orden del programa. \end_layout \begin_deeper \begin_layout Standard Esto requiere esperar a que las escrituras terminen de propagarse antes de emitir otra operación de memoria, rompiendo optimizaciones como los \emph on \lang english buffers \emph default \lang spanish de escritura y el adelantamiento y dificultando mecanismos como la segmentación , lo que se puede aliviar con especulación pero añadiendo mucha complejidad. Además, muchas optimizaciones de compiladores se basan en reordenar el código fuente y en particular los accesos a memoria, o en usar registros. Por eso x86, ARM, MIPS, PowerPC y RISC-V no lo implementan. \end_layout \end_deeper \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash end{samepage} \end_layout \end_inset \end_layout \begin_layout Standard En la práctica se usan modelos de consistencia relajados: \end_layout \begin_layout Itemize \series bold Consistencia del procesador \series default o \series bold \emph on \lang english Processor Consistency \series default \emph default \lang spanish : Cada hilo ve las escrituras de un mismo procesador en orden. \end_layout \begin_layout Itemize \series bold Consistencia débil \series default : Los accesos a memoria pueden marcarse como de sincronización. Estos accesos tienen consistencia secuencial entre sí y todos los hilos ven el mismo conjunto de operaciones de memoria entre accesos de sincronización. \end_layout \begin_layout Itemize \series bold Consistencia de liberación \series default : Los accesos a memoria pueden marcarse como de \series bold adquisición \series default ( \emph on \lang english acquire \emph default \lang spanish ) o de \series bold liberación \series default ( \emph on \lang english release \emph default \lang spanish ). Los accesos de adquisición y liberación tienen consistencia del procesador entre sí, todos los accesos esperan a que los anteriores de adquisición hayan terminado y los de liberación esperan a que todos los anteriores hayan terminado. Normalmente las secciones críticas empiezan con una \emph on \lang english acquire \emph default \lang spanish y terminan con una \emph on \lang english release \emph default \lang spanish . \end_layout \begin_deeper \begin_layout Standard Este es el modelo usado por C, C++ y Java, \begin_inset Foot status open \begin_layout Plain Layout C, C++ y Rust usan el mismo modelo, que también incluye consistencia débil. \end_layout \end_inset y ARMv8 y RISC-V tienen modelos similares. \end_layout \end_deeper \begin_layout Standard Los accesos a memoria marcados especialmente se suelen traducir en ensamblador como barreras de memoria o \emph on \lang english memory fences \emph default \lang spanish . Programar con modelos relajados es más difícil, y se aconseja evitar las \series bold condiciones de carrera \series default , en que dos hilos acceden a la misma memoria sin ordenación y al menos uno escribe en ella, y usar las primitivas de sincronización del lenguaje de programación, que en general incluyen las \emph on \lang english fences \emph default \lang spanish necesarias. \end_layout \begin_layout Standard \begin_inset Newpage pagebreak \end_inset \end_layout \begin_layout Section Semáforos \end_layout \begin_layout Standard La comunicación y compartición de recursos entre procesos requiere de mecanismos de sincronización, como son: \end_layout \begin_layout Itemize Semáforos o cerrojos para la exclusión mutua. \end_layout \begin_layout Itemize \series bold Señales \series default para la sincronización punto a punto, en que uno o más hilos esperan a que otro envíe una señal. \end_layout \begin_layout Itemize \series bold Barreras \series default para sincronización global, que impiden que los hilos sigan avanzando hasta que todos lleguen a cierto punto de su ejecución. \end_layout \begin_layout Standard Las implementaciones de exclusión mutua constan de: \end_layout \begin_layout Enumerate Un \series bold método de adquisición \series default para obtener el cerrojo, con poca latencia si no hay más hilos intentando sincronizarse. \end_layout \begin_layout Enumerate Un \series bold algoritmo de espera \series default para esperar a que el cerrojo esté disponible cuando no lo esté, y que consuma poco ancho de banda de la red de interconexión. \end_layout \begin_layout Enumerate Un \series bold método de liberación \series default para notificar que el cerrojo está disponible, que sea suficientemente imparcial y no provoque inanición. \end_layout \begin_layout Standard Es importante que el protocolo sea escalable y requiera poca información para funcionar. Estos protocolos se pueden implementar con consistencia secuencial, pero el resultado es complicado e ineficiente, por lo que es más común ampliar el ISA con instrucciones atómicas de sincronización, que actúan como barreras. Algunas son: \end_layout \begin_layout Itemize \series bold \emph on Test&set \series default \emph default : Carga una posición de memoria en un registro y establece dicha posición a 1. Un cerrojo implementado como un booleano que está a 1 cuando el cerrojo está bloqueado se bloquearía con \family typewriter lock: t&s t0, MUTEX; bnez t0, lock \family default y se desbloquearía con \family typewriter sw r0, LOCK \family default . Cuando el cerrojo está ocupado, esto genera invalidaciones continuas, por lo que es preferible usar \emph on \lang english test&test&set \emph default \lang spanish , comprobando con una carga normal si el cerrojo está disponible antes de obtenerlo: \begin_inset listings inline false status open \begin_layout Plain Layout lock: lw t0, MUTEX \end_layout \begin_layout Plain Layout bnez t0, lock \end_layout \begin_layout Plain Layout t&s t0, MUTEX \end_layout \begin_layout Plain Layout bnz t0, lock \end_layout \end_inset Esto aumenta algo la latencia pero reduce el tráfico entre cachés y es más escalable. \end_layout \begin_layout Itemize \series bold \emph on \lang english Swap \series default \emph default \lang spanish : Intercambia los valores de un registro y una posición de memoria. Se puede usar como \family typewriter t&s \family default estableciendo el registro a 1. \end_layout \begin_layout Itemize \series bold \emph on \lang english Fetch&op \series default \emph default \lang spanish : Lee una posición de memoria un registro y escribe en memoria el valor obtenido al aplicar una cierta operación. \end_layout \begin_layout Itemize \series bold \emph on \lang english Compare&swap \series default \emph default \lang spanish : Compara el valor en una posición de memoria con el de un registro y, si coinciden, intercambia el contenido de la posición con el de otro registro. \end_layout \begin_layout Standard Estas instrucciones son difíciles de implementar y lentas, y una alternativa es el par \lang english LL \lang spanish / \lang english SC \lang spanish , formado por las instrucciones: \end_layout \begin_layout Itemize \series bold \emph on \lang english Load Linked \series default \emph default \lang spanish ( \lang english LL \lang spanish ): Lee una posición de memoria en un registro. \end_layout \begin_layout Itemize \series bold \emph on \lang english Store Conditional \series default \emph default \lang spanish ( \lang english SC \lang spanish ): Si, en el bloque (normalmente de caché) de la posición de memoria indicada, nadie ha escrito desde el último \lang english LL \lang spanish , escribe el valor del registro en la posición. Si alguien ha escrito antes, la instrucción falla; ni escribe ni hay invalidaci ones. \begin_inset Foot status open \begin_layout Plain Layout En la práctica esto puede ocurrir cuando hay una interrupción, cambio de contexto, otro LL, una escritura a otro bloque, etc. \end_layout \end_inset También establece algún registro para indicar si la instrucción tuvo éxito. \end_layout \begin_layout Standard Se ha de ejecutar el mínimo de operaciones posible entre \lang english LL \lang spanish y \lang english SC \lang spanish para favorecer que \lang english SC \lang spanish tenga éxito. Un cerrojo se bloquearía con \begin_inset listings inline false status open \begin_layout Plain Layout li t1, 1 \end_layout \begin_layout Plain Layout lock: ll t0, MUTEX \end_layout \begin_layout Plain Layout bnez t0, lock \end_layout \begin_layout Plain Layout sc t1, MUTEX \end_layout \begin_layout Plain Layout beqz t1, lock \end_layout \end_inset \end_layout \begin_layout Standard Esta implementación tiene buen rendimiento, pues la espera activa no genera tráfico ni invalidaciones, pero no es imparcial. \end_layout \begin_layout Section Redes de interconexión \end_layout \begin_layout Standard En sistemas con varias CPUs puede haber \series bold interconexión \emph on \lang english on-chip \series default \emph default \lang spanish , entre procesadores en un mismo chip, e \series bold interconexión \emph on \lang english off-chip \series default \emph default \lang spanish , entre procesadores de distintos chips, como en los clústeres de servidores. Las redes Ethernet suelen tener ancho de banda de \begin_inset Formula $0.1,1,10,\unit[100]{Gbps},\dots$ \end_inset y latencia de único salto de \begin_inset Formula $\unit[\text{25--100}]{\mu s}$ \end_inset , mientras que InfiniBand tiene \begin_inset Formula $20,40,54,\unit[80]{Gbps},\dots$ \end_inset y latencia de único salto de \begin_inset Formula $\unit[\text{1--3}]{\mu s}$ \end_inset . \end_layout \begin_layout Standard Las redes están formadas por enlaces; conmutadores ( \emph on \lang english switches \emph default \lang spanish o \emph on \lang english routers \emph default \lang spanish ), que conectan enlaces y pueden tener funciones de encaminamiento, y una interfaz de red en cada núcleo que lo conecta con un conmutador. \end_layout \begin_layout Standard La longitud de un cable determina la frecuencia a la que se puede operar y la potencia que puede haber que disipar. Interesa una red con alto ancho de banda (frecuencia por número de hilos) y baja latencia, simple (lo que suele llevar a mejor rendimiento), fiable (que no produzca fallos y soporte un número limitado de ellos) y con bajo coste económico y energético. Además, queremos estructurarla de forma escalable (que el ancho de banda aumente conforme lo haga el número de nodos) y fácilmente particionable (que se pueda dividir en subsistemas), pues al aumentar el número de núcleos, una mala red de interconexión puede consumir buena parte de la energía y dar lugar a cuellos de botella. \end_layout \begin_layout Subsection Topologías de red \end_layout \begin_layout Standard Un \series bold hipergrafo dirigido \series default es un par \begin_inset Formula $(V,H)$ \end_inset formado por un conjunto de \series bold nodos \series default \begin_inset Formula $V$ \end_inset y un conjunto de \series bold hiperarcos \series default \begin_inset Formula $H\subseteq\{(A,B)\in{\cal P}(V)\times{\cal P}(V)\mid A,B\neq\emptyset\}$ \end_inset . Un \series bold hipergrafo no dirigido \series default es un par \begin_inset Formula $(V,H)$ \end_inset donde \begin_inset Formula $V$ \end_inset es un conjunto de nodos y \begin_inset Formula $H\subseteq{\cal P}(V)\setminus\{\emptyset\}$ \end_inset es un conjunto de \series bold hiperejes \series default . Identificamos el hipergrafo no dirigido \begin_inset Formula $(V,H)$ \end_inset con el hipergrafo dirigido \begin_inset Formula $(V,\{(h,h)\}_{h\in H})$ \end_inset . con ancho de banda \begin_inset Formula $\omega(A,B)$ \end_inset . Un \series bold corte de bisección \series default de un hipergrafo no dirigido finito es un conjunto separador de hiperejes de tamaño mínimo, y el \series bold ancho de la bisección \series default ( \emph on \lang english bisection bandwidth \emph default \lang spanish ) es dicho tamaño. \end_layout \begin_layout Standard Una \series bold hiperred \series default es una tupla \begin_inset Formula $(V,H,\omega)$ \end_inset donde \begin_inset Formula $(V,H)$ \end_inset es un hipergrafo y \begin_inset Formula $\omega:H\to\mathbb{R}$ \end_inset es una función de pesos. Un corte de bisección de una hiperred no dirigida finita es un conjunto separador de hiperejes con mínima suma de los pesos, y el ancho de la bisección es dicha suma. \end_layout \begin_layout Standard Una \series bold topología de red \series default es un hipergrafo dirigido finito \begin_inset Formula $(V,H)$ \end_inset donde los nodos representan \emph on \lang english routers \emph default \lang spanish y un hiperarco \begin_inset Formula $(A,B)$ \end_inset es un enlace que transmite de los nodos de \begin_inset Formula $A$ \end_inset a los de \begin_inset Formula $B$ \end_inset . Si se añade una función de pesos, el peso de un enlace es su ancho de banda. La topología es \series bold simétrica \series default si el hipergrafo es no dirigido. Informalmente, es \series bold regular \series default si los nodos están conectados en un patrón definido, de modo que se pueden asignar coordenadas a los nodos y generalmente se pueden encaminar los mensajes solo según las coordenadas de los extremos, y es \series bold irregular \series default si los nodos se conectan sin estructura, lo que es más expansible, en cuyo caso se suele encaminar con algoritmos que intentan encontrar el camino más corto. \end_layout \begin_layout Standard Algunas topologías regulares simétricas, donde \begin_inset Formula $\mathbb{N}_{n}\coloneqq \{0,\dots,n-1\}$ \end_inset : \end_layout \begin_layout Itemize \series bold Buses \series default : \begin_inset Formula $(V,\{V\})$ \end_inset , con ancho de bisección 1 y grado 1. \end_layout \begin_layout Itemize \series bold Mallas \series default \begin_inset Formula $n$ \end_inset -dimensionales: \begin_inset Formula $(V,E)$ \end_inset con \begin_inset Formula $V\coloneqq \mathbb{N}_{d_{1}}\times\dots\times\mathbb{N}_{d_{n}}$ \end_inset y \begin_inset Formula \[ E:=\{\{(i_{1},\dots,i_{n}),(i_{1},\dots,i_{k-1},i_{k}+1,i_{k+1},\dots,i_{n})\}\}_{(i_{1},\dots,i_{n})\in V,k\in\mathbb{N}_{d},i_{k}+1y_{k}$ \end_inset . En un hipercubo esto se llama \series bold \emph on \lang english edge-cube routing \series default \emph default \lang spanish . \end_layout \begin_layout Subsection Estrategia de conmutación \end_layout \begin_layout Standard Es la forma en que los datos pasan a través de los conmutadores. \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash sremember{AR} \end_layout \end_inset \end_layout \begin_layout Description Conmutación \begin_inset space ~ \end_inset de \begin_inset space ~ \end_inset circuitos La red telefónica. [...] Conectan puertos de entrada y salida [...]. [...] El circuito es dedicado y con un ancho de banda fijo [...]. [La latencia es el tiempo de establecer el circuito y propagar los datos.] \end_layout \begin_layout Description \series bold Conmutación \begin_inset space ~ \end_inset de \begin_inset space ~ \end_inset mensajes \series default Los \emph on \lang english routers \emph default \lang spanish redirigen el mensaje por la interfaz adecuada usando información adicional en los mismos [...], y usan \emph on \lang english buffers \emph default \lang spanish para almacenar los mensajes [...] ( \emph on \lang english store-and-forward \emph default \lang spanish ). \end_layout \begin_layout Description Conmutación \begin_inset space ~ \end_inset de \begin_inset space ~ \end_inset paquetes Como la de mensajes, pero los mensajes se dividen en trozos pequeños llamados paquetes, enrutados individualmente [...]. [La latencia es proporcional a la distancia.] \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash eremember \end_layout \end_inset \end_layout \begin_layout Standard En redes \emph on \lang english on-chip \emph default \lang spanish se usan mecanismos de altas prestaciones: \end_layout \begin_layout Description \emph on \lang english Wormhole \emph default \lang spanish Los paquetes se dividen en \emph on \lang english flits \emph default \lang spanish , trozos con el tamaño exacto que cabe en el canal, de los que el primero contiene la cabecera con la dirección de destino. El \emph on \lang english switch \emph default \lang spanish encamina el paquete en cuanto recibe la cabecera, y solo almacena partes de este en \emph on \lang english buffers \emph default \lang spanish pequeños con baja latencia y poco sensibles a la distancia. \end_layout \begin_layout Description \emph on \lang english Virtual \begin_inset space ~ \end_inset Cut \begin_inset space ~ \end_inset Through \emph default \lang spanish Variante de \emph on \lang english wormhole \emph default \lang spanish en la que, si el canal de salida no está disponible, el paquete se almacena. La latencia es similar a la de \emph on \lang english wormhole \emph default \lang spanish , no afectada por la distancia, y da más prestaciones cuando hay congestión a cambio de necesitar \emph on \lang english buffers \emph default \lang spanish más grandes, capaces de almacenar un paquete completo. \end_layout \begin_layout Standard Para el control de flujo en altas prestaciones, cuando se alcanza un límite de uso \emph on \lang english stop \emph default \lang spanish procesando \emph on \lang english flits \emph default \lang spanish de un canal, se envía una señal al resto para que dejen de enviar y evitar el desbordamiento, y cuando el uso baja un límite \emph on \lang english go \emph default \lang spanish , se avisa al resto de que pueden volver a enviar. \end_layout \end_body \end_document