Multihilo explícito

El Multihilo Explícito ( XMT ) es un paradigma de la informática para la construcción y programación de ordenadores paralelos, diseñado en torno al modelo de computación paralela de la máquina de acceso aleatorio paralelo (PRAM). Una explicación más directa de XMT comienza con la abstracción rudimentaria que simplificó la computación en serie : que cualquier instrucción disponible para su ejecución en un programa en serie se ejecuta inmediatamente. Una consecuencia de esta abstracción es una explicación paso a paso (inductiva) de la siguiente instrucción disponible para su ejecución. La abstracción paralela rudimentaria detrás de XMT, denominada Ejecución Concurrente Inmediata (ICE) en Vishkin (2011) , es que un número indefinido de instrucciones disponibles para la ejecución concurrente se ejecutan inmediatamente. Una consecuencia de ICE es una explicación paso a paso (inductiva) de las siguientes instrucciones disponibles para la ejecución concurrente. Más allá del ordenador serial von Neumann (la única plataforma de propósito general exitosa hasta la fecha), la aspiración de XMT es que la informática pueda nuevamente complementar la inducción matemática con una abstracción de computación simple de una sola línea.

La máquina de acceso aleatorio (RAM) es un modelo abstracto de máquina utilizado en informática para estudiar algoritmos y complejidad en computación serial estándar. El modelo computacional PRAM es un modelo abstracto de máquina paralela que se introdujo para estudiar de forma similar algoritmos paralelos y su complejidad en computación paralela , cuando aún no se habían construido. Los investigadores han desarrollado un amplio conocimiento sobre algoritmos paralelos para el modelo PRAM. Estos algoritmos paralelos también se caracterizan por su simplicidad, en comparación con otros enfoques de algoritmos paralelos.

Este amplio conjunto de conocimientos sobre algoritmos paralelos para el modelo PRAM y su relativa simplicidad motivaron la construcción de computadoras cuya programación pudiera guiarse por dichos algoritmos. Dado que la productividad de los programadores paralelos se ha considerado crucial para el éxito de una computadora paralela, la simplicidad de los algoritmos es fundamental.

Los ordenadores multinúcleo se construyen alrededor de dos o más núcleos de procesador integrados en un único chip de circuito integrado . Se utilizan ampliamente en numerosos ámbitos de aplicación, incluyendo la informática de propósito general. El multihilo explícito (XMT) es un paradigma informático para la construcción y programación de ordenadores multinúcleo con decenas, cientos o miles de núcleos de procesador.

Los trabajos experimentales publicados en 2011 y 2012 demuestran una aceleración significativamente mayor de los algoritmos PRAM avanzados en prototipos XMT que en los mismos problemas en ordenadores multinúcleo de última generación.

Un trabajo publicado en 2018 demuestra que la programación paralela paso a paso (mediante ICE) puede alcanzar el mismo rendimiento que el código multihilo optimizado manualmente más rápido en sistemas XMT. Este enfoque inductivo paso a paso contrasta con los métodos de programación multihilo de muchos otros sistemas centrales, conocidos por su dificultad para los programadores.

El paradigma XMT fue introducido por Uzi Vishkin .

El paradigma de computación de multihilo explícito (XMT) integra varios niveles de abstracción.

El marco de trabajo de tiempo de trabajo (WT, por sus siglas en inglés), también conocido como marco de trabajo de profundidad de trabajo, introducido por Shiloach y Vishkin (1982) , proporciona una manera sencilla de conceptualizar y describir algoritmos paralelos. En el marco WT, un algoritmo paralelo se describe primero en términos de rondas paralelas. Para cada ronda, se caracterizan las operaciones a realizar, pero se pueden omitir varios aspectos. Por ejemplo, no es necesario especificar el número de operaciones en cada ronda, ni mencionar los procesadores, ni incluir información que pueda ayudar a asignar procesadores a las tareas. En segundo lugar, se proporciona la información omitida. La inclusión de esta información se basa, de hecho, en la demostración de un teorema de planificación de Brent (1974) . El marco WT resulta útil porque, si bien puede simplificar enormemente la descripción inicial de un algoritmo paralelo, insertar los detalles omitidos en dicha descripción inicial no suele ser muy difícil. Por ejemplo, el marco WT fue adoptado como marco de presentación básico en los libros de algoritmos paralelos (para el modelo PRAM) de JaJa (1992) y Keller, Kessler y Traeff (2001) , así como en los apuntes de clase de Vishkin (2009) . Vishkin (2011) explica la sencilla conexión entre el marco WT y la abstracción ICE más rudimentaria mencionada anteriormente.

El paradigma XMT se puede programar utilizando XMTC , un lenguaje de programación paralelo multihilo que es una pequeña extensión del lenguaje de programación C. El paradigma XMT incluye un flujo de trabajo para el programador que comienza con la definición de un algoritmo en el marco de trabajo WT y continúa programándolo en XMTC.

Los sistemas informáticos multinúcleo XMT proporcionan equilibrio de carga en tiempo de ejecución para programas multihilo, incorporando varias patentes. Una de ellas ^{[ 1 ]} generaliza el concepto de contador de programa , fundamental para la arquitectura von Neumann, al hardware multinúcleo.

En enero de 2007, se completó una computadora de 64 procesadores ^{[ 2 ]} llamada Paraleap ^{[ 3 ]} , que demuestra el concepto general. El concepto XMT se presentó en Vishkin et al. (1998) y Naishlos et al. (2003) , y la computadora XMT de 64 procesadores en Wen & Vishkin (2008) . Dado que hacer que la programación paralela sea sencilla es uno de los mayores desafíos que enfrenta la informática hoy en día, la demostración también buscó incluir la enseñanza de los fundamentos de los algoritmos PRAM y la programación XMTC a estudiantes desde la escuela secundaria Torbert et al. (2010) hasta la escuela de posgrado.

El trabajo experimental reportado en Caragea y Vishkin (2011) para el problema del flujo máximo , y en dos artículos de Edwards y Vishkin ( 2012a , 2012b ) para los problemas de conectividad de grafos ( conectividad (teoría de grafos) ), biconectividad de grafos ( grafo biconectado ) y triconectividad de grafos ( componente triconectado ) demostró que para algunos de los algoritmos más avanzados en la literatura de algoritmos paralelos, el paradigma XMT puede ofrecer aceleraciones de 8 a más de 100 veces mayores que para los mismos problemas en computadoras multinúcleo de última generación. Cada aceleración reportada se obtuvo comparando los ciclos de reloj en un prototipo XMT con respecto al algoritmo serial más rápido ejecutándose en las máquinas seriales más rápidas. 

El prototipado de XMT culminó en Ghanim, Vishkin y Barua (2018) , quienes establecieron que la programación paralela paso a paso (usando ICE) puede lograr el mismo rendimiento que el código multihilo optimizado manualmente más rápido en sistemas XMT. Este resultado de 2018 acentúa el contraste entre la programación XMT y los enfoques de programación multihilo empleados por casi todos los demás sistemas de núcleos, cuyas condiciones de carrera y otras exigencias tienden a suponer un reto, e incluso a veces a hacer fracasar a los programadores (Vishkin, 2014) .

• Brent, Richard P. (1974), "La evaluación paralela de expresiones aritméticas generales", Journal of the ACM , 21 (2): 201– 208, CiteSeerX 10.1.1.100.9361 , doi : 10.1145/321812.321815 , S2CID 16416106  .
• Shiloach, Yossi; Vishkin, Uzi (1982), "Un algoritmo paralelo de flujo máximo O ( n² log n )", Journal of Algorithms , 3 ⁽ 2): 128–146 , doi : 10.1016/0196-6774(82)90013-X  .
• JaJa, Joseph (1992), Introducción a los algoritmos paralelos , Addison-Wesley, ISBN 978-0-201-54856-3
• Keller, Jorg; Kessler, Cristoph W.; Traeff, Jesper L. (2001), Programación práctica de PRAM , Wiley-Interscience, ISBN 978-0-471-35351-5
• Naishlos, Dorit; Nuzman, Joseph; Tseng, Chau-Wen; Vishkin, Uzi (2003), "Hacia un primer prototipo vertical de un enfoque de programación paralela de grano extremadamente fino" (PDF) , Theory of Computing Systems , 36 (5): 551– 552, doi : 10.1007/s00224-003-1086-6 , S2CID 1929495 .

• Torbert, Shane; Vishkin, Uzi; Tzur, Ron; Ellison, David (2010), "¿Es posible enseñar pensamiento algorítmico paralelo a estudiantes de secundaria?", Actas del 41.º simposio técnico de la ACM sobre educación en ciencias de la computación - SIGCSE '10 , pág.  290, doi : 10.1145/1734263.1734363 , ISBN 9781450300063.
• Vishkin, Uzi; Dascal, Shlomit; Berkovich, Efraim; Nuzman, Joseph (1998), "Modelos puente de multihilo explícito (XMT) para el paralelismo de instrucciones" , Actas del Simposio ACM de 1998 sobre algoritmos y arquitecturas paralelas (SPAA) , págs. 140-151 . .
• Vishkin, Uzi (2009), Pensando en paralelo: algunos algoritmos y técnicas básicas de procesamiento paralelo de datos, 104 páginas (PDF) , Apuntes de clase de cursos sobre algoritmos paralelos impartidos desde 1992 en la Universidad de Maryland, College Park, la Universidad de Tel Aviv y el Technion.
• Wen, Xingzhi; Vishkin, Uzi (2008), "Prototipo basado en FPGA de un procesador PRAM en chip", Actas de la Conferencia ACM de 2008 sobre Fronteras de la Computación (Ischia, Italia) (PDF) , págs. 55–66 , doi : 10.1145/1366230.1366240 , ISBN  9781605580777, S2CID 11557669 .
• Vishkin, Uzi (2011), "Using simple abstraction to reinvent computing for parallelism", Communications of the ACM , 54 : 75–85 , doi : 10.1145/1866739.1866757.
• Caragea, George; Vishkin, Uzi (2011), "Anuncio breve: mejores aceleraciones para el flujo máximo paralelo", Actas del 23.er Simposio ACM sobre paralelismo en algoritmos y arquitecturas (SPAA) , págs. 131-134 , doi : 10.1145/1989493.1989511 , ISBN  9781450307437, S2CID 5511743 .
• Edwards, James A.; Vishkin, Uzi (2012a), "Mejores aceleraciones mediante programación paralela más sencilla para la conectividad y biconectividad de grafos", Actas del Taller Internacional de 2012 sobre Modelos de Programación y Aplicaciones para Multinúcleos y Manycores , pp. 103–114 , doi : 10.1145/2141702.2141714 , ISBN  9781450312110, S2CID 15095569 .
• Edwards, James A.; Vishkin, Uzi (2012b), "Anuncio breve: aceleraciones para la triconectividad de grafos paralelos", Actas del 24.º Simposio ACM sobre paralelismo en algoritmos y arquitecturas (SPAA) , págs. 190-192 , doi : 10.1145/2312005.2312042 , ISBN  9781450312134, S2CID 16908459 .
• Vishkin, Uzi (2014), "¿Está roto el hardware multinúcleo para el procesamiento paralelo de propósito general? Artículo de opinión", Communications of the ACM , 57 (4): 35–39 , doi : 10.1145/2580945 , S2CID 30098719 .
• Ghanim, Fady; Vishkin, Uzi; Barua, Rajeev (febrero de 2018), "Programación paralela de alto rendimiento basada en PRAM con ICE", IEEE Transactions on Parallel and Distributed Systems , 29 (2): 377–390 , doi : 10.1109/TPDS.2017.2754376 , hdl : 1903/18521.

• Página principal del proyecto XMT, con enlaces a una versión del software, un tutorial en línea y material para la enseñanza del paralelismo .