diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | aoc/n.lyx | 29 | ||||
| -rw-r--r-- | aoc/n3.lyx | 316 |
3 files changed, 328 insertions, 18 deletions
@@ -22,7 +22,6 @@ # *.pdf ## Generated if empty string is given at "Please type another file name for output:" -.pdf ## Bibliography auxiliary files (bibtex/biblatex/biber): *.bbl @@ -178,7 +178,7 @@ Release consistency \emph default , \emph on -Hypergraph +Load-link/store-conditional, Hypergraph \emph default . \end_layout @@ -203,6 +203,33 @@ ACM SIGARCH Computer Architecture News 234-243. \end_layout +\begin_layout Itemize + +\lang english +MIPS Technologies Inc +\lang spanish +. + (2008). + +\emph on +\lang english +MIPS32® Instruction Set Quick Reference +\emph default +\lang spanish + ( +\begin_inset Flex URL +status open + +\begin_layout Plain Layout + +https://www.cs.duke.edu/courses/fall13/compsci250/MIPS32_QRC.pdf +\end_layout + +\end_inset + +). +\end_layout + \begin_layout Chapter Introducción \end_layout @@ -1292,8 +1292,7 @@ Este es el modelo usado por C, C++ y Java, status open \begin_layout Plain Layout -C, C++ y Rust usan el mismo modelo, que también incluye consistencia débil, - aunque esta se puede implementar a través de consistencia de liberación. +C, C++ y Rust usan el mismo modelo, que también incluye consistencia débil. \end_layout \end_inset @@ -1304,7 +1303,7 @@ C, C++ y Rust usan el mismo modelo, que también incluye consistencia débil, \end_deeper \begin_layout Standard Los accesos a memoria marcados especialmente se suelen traducir en ensamblador - como + como barreras de memoria o \emph on \lang english memory fences @@ -1328,6 +1327,295 @@ fences \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 @@ -1390,12 +1678,15 @@ routers \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. - Queremos una red con alto ancho de banda (frecuencia por número de hilos) - y baja latencia, que sea 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, y 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). + 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 @@ -1929,13 +2220,6 @@ edge-cube routing . \end_layout -\begin_layout Standard -\begin_inset Newpage pagebreak -\end_inset - - -\end_layout - \begin_layout Section Estrategia de conmutación \end_layout |