Uzi Vishkin (nacido en 1953) es un científico informático en la Universidad de Maryland, College Park , donde es profesor de Ingeniería Eléctrica e Informática en el Instituto de Estudios Informáticos Avanzados de la Universidad de Maryland (UMIACS). Uzi Vishkin es conocido por su trabajo en el campo de la computación paralela . En 1996, fue admitido como miembro de la Association for Computing Machinery , con la siguiente cita: "Uno de los pioneros de la investigación de algoritmos paralelos, las contribuciones fundamentales del Dr. Vishkin desempeñaron un papel de liderazgo en la formación y configuración de lo que el pensamiento en paralelo ha venido". que significa en la teoría fundamental de la informática ". [1]
Uzi Vishkin | |
---|---|
Nació | 1953 |
alma mater | Technion de la Universidad Hebrea |
Carrera científica | |
Campos | algoritmos paralelos |
Instituciones | IBM Thomas J. Watson Research Center Universidad de Nueva York Universidad de Tel Aviv Universidad de Maryland, College Park |
Asesor de doctorado | Yossi Shiloach |
Influencias | Robert Aumann , asesor principal |
Biografía
Uzi Vishkin nació en Tel Aviv, Israel. Completó su B.Sc. (1974) y M.Sc. en Matemáticas en la Universidad Hebrea , antes de obtener su D.Sc. en Informática en el Technion (1981). Luego pasó un año trabajando en IBM Thomas J. Watson Research Center en Yorktown Heights, Nueva York. De 1982 a 1984, trabajó en el departamento de informática de la Universidad de Nueva York y permaneció afiliado a él hasta 1988. De 1984 a 1997 trabajó en el departamento de informática de la Universidad de Tel Aviv, siendo su presidente de 1987 a 1988. Desde 1988 está en la Universidad de Maryland, College Park .
PRAM en chip
Una abstracción rudimentaria notable —que cualquier instrucción individual disponible para su ejecución en un programa en serie se ejecuta inmediatamente— simplificó la computación en serie. Una consecuencia de esta abstracción es una explicación paso a paso (inductiva) de la instrucción disponible a continuación para su ejecución. La abstracción paralela rudimentaria detrás del concepto PRAM-on-chip, denominado Immediate Concurrent Execution (ICE) en Vishkin (2011) , es que indefinidamente muchas instrucciones disponibles para ejecución concurrente se ejecutan inmediatamente. Una consecuencia de ICE es una explicación paso a paso (inductiva) (también conocida como paso de bloqueo) de las instrucciones disponibles a continuación para la ejecución concurrente. Más allá de la computadora en serie von Neumann (la única plataforma de propósito general exitosa hasta la fecha), la aspiración del concepto PRAM-on-chip es que la ciencia de la computación podrá nuevamente aumentar la inducción matemática con una simple abstracción computacional de una línea. A continuación, se presenta una descripción general cronológica de la evolución del concepto PRAM-on-chip y su creación de prototipos de hardware y software . En las décadas de 1980 y 1990, Uzi Vishkin fue coautor de varios artículos que ayudaron a construir una teoría de algoritmos paralelos en un modelo matemático llamado máquina de acceso aleatorio paralelo (PRAM), que es una generalización para la computación paralela del modelo de computación en serie estándar de acceso aleatorio. máquina (RAM). Las máquinas paralelas necesarias para implementar el modelo PRAM aún no se han construido en ese momento, y bastantes desafiaron la capacidad de construir tales máquinas. Concluyendo en 1997 [2] que el recuento de transistores en el chip como implica la Ley de Moore permitirá construir una poderosa computadora paralela en un solo chip de silicio dentro de una década, desarrolló una visión PRAM-On-Chip que requería construir una computadora paralela en un solo chip que permite a los programadores desarrollar sus algoritmos para el modelo PRAM. Continuó inventando la arquitectura de computadora explícita de subprocesos múltiples (XMT) que permite la implementación de esta teoría PRAM, y llevó a su equipo de investigación a completar en enero de 2007 una computadora de 64 procesadores [3] llamada Paraleap, [4] que demuestra la concepto general. El concepto XMT se presentó en Vishkin et al. (1998) , Naishlos et al. (2003) , la computadora XMT de 64 procesadores en Wen & Vishkin (2008) , en Vishkin (2011) y más recientemente en Ghanim, Vishkin & Barua (2018) , donde se demostró que la programación paralela de paso de bloqueo (usando ICE) puede lograr el mismo rendimiento que el código multiproceso ajustado a mano más rápido en los sistemas XMT. Este enfoque de paso de bloqueo inductivo contrasta con los enfoques de programación de subprocesos múltiples de otros muchos sistemas centrales que son conocidos por los programadores desafiantes. La demostración de XMT comprendió varios componentes de hardware y software, así como la enseñanza de algoritmos PRAM para programar el XMT Paraleap, utilizando un lenguaje llamado XMTC . Dado que facilitar la programación paralela es uno de los mayores desafíos que enfrentan las ciencias de la computación en la actualidad, la demostración también buscó incluir la enseñanza de los conceptos básicos de los algoritmos PRAM y la programación XMTC a estudiantes que van desde la escuela secundaria hasta la escuela de posgrado.
Algoritmos paralelos
En el campo de los algoritmos paralelos, Uzi Vishkin fue coautor del artículo Shiloach & Vishkin (1982b) que contribuyó con el marco del tiempo de trabajo (WT) (a veces llamado profundidad de trabajo) para conceptualizar y describir algoritmos paralelos. El marco WT fue adoptado como marco de presentación básico en los libros de algoritmos paralelos JaJa (1992) y Keller, Kessler & Traeff (2001) , así como en las notas de clase de Vishkin (2009) . En el marco de 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 suprimir varias cuestiones. Por ejemplo, no es necesario que quede claro el número de operaciones en cada ronda, no es necesario mencionar los procesadores y no es necesario contabilizar cualquier información que pueda ayudar con la asignación de procesadores a los trabajos. En segundo lugar, se proporciona la información suprimida. La inclusión de la información suprimida está, de hecho, guiada por la demostración de un teorema de programación debido a Brent (1974) . El marco WT es útil ya que, si bien puede simplificar en gran medida la descripción inicial de un algoritmo paralelo, insertar los detalles suprimidos por esa descripción inicial a menudo no es muy difícil. De manera similar, lanzar primero un algoritmo en el marco WT puede ser muy útil para programarlo en XMTC . Vishkin (2011) explica la conexión simple entre el marco WT y la abstracción ICE más rudimentaria mencionada anteriormente.
En el campo de los algoritmos paralelos y distribuidos, uno de los artículos fundamentales en coautoría de Uzi Vishkin es Cole & Vishkin (1986) . Este trabajo introdujo una técnica paralela eficiente para colorear gráficos . El algoritmo de Cole-Vishkin encuentra un vértice coloración en un n - ciclo en O (log * n ) rondas de comunicación sincrónica. Este algoritmo se presenta hoy en día en muchos libros de texto, incluida la Introducción a los algoritmos de Cormen et al., [5] y forma la base de muchos otros algoritmos distribuidos para colorear gráficos. [6]
Otras contribuciones de Uzi Vishkin y varios coautores incluyen algoritmos paralelos para la clasificación de listas , ancestro común más bajo , árboles de expansión y componentes biconectados .
Publicaciones Seleccionadas
- Shiloach, Yossi; Vishkin, Uzi (1982a), "Un algoritmo de conectividad paralela O (log n )", Journal of Algorithms , 3 : 57–67, doi : 10.1016 / 0196-6774 (82) 90008-6.
- Shiloach, Yossi; Vishkin, Uzi (1982b), "Un algoritmo de flujo máximo paralelo O ( n 2 log n )", Journal of Algorithms , 3 (2): 128-146, doi : 10.1016 / 0196-6774 (82) 90013-X.
- Mehlhorn, Kurt; Vishkin, Uzi (1984), "Simulaciones aleatorias y deterministas de PRAM mediante máquinas paralelas con granularidad restringida de memorias paralelas", Acta Informatica , 21 (4): 339–374, doi : 10.1007 / BF00264615 , S2CID 29789494.
- Tarjan, Robert; Vishkin, Uzi (1985), "Un algoritmo de biconnectividad paralela eficiente", SIAM Journal on Computing , 14 (4): 862–874, CiteSeerX 10.1.1.465.8898 , doi : 10.1137 / 0214061.
- Vishkin, Uzi (1985), "Coincidencia óptima de patrones paralelos en cadenas", Información y control , 67 (1-3): 91-113, doi : 10.1016 / S0019-9958 (85) 80028-0.
- Cole, Richard; Vishkin, Uzi (1986), "Lanzamiento de moneda determinista con aplicaciones para la clasificación de lista paralela óptima", Información y control , 70 (1): 32-53, doi : 10.1016 / S0019-9958 (86) 80023-7.
- Vishkin, Uzi; Dascal, Shlomit; Berkovich, Efraim; Nuzman, Joseph (1998), "Modelos de puenteo explícito de subprocesos múltiples (XMT) para el paralelismo de instrucciones" , Proc. 1998 Simposio ACM sobre arquitecturas y algoritmos paralelos (SPAA) , págs. 140–151.
- Naishlos, Dorit; Nuzman, Joseph; Tseng, Chau-Wen; Vishkin, Uzi (2003), "Towards a First Vertical Prototyping of an Extremely-Grained Parallel Programming Approach" (PDF) , Theory of Computing Systems , 36 (5): 551–552, doi : 10.1007 / s00224-003-1086 -6 , S2CID 1929495.
- Wen, Xingzhi; Vishkin, Uzi (2008), "Prototipo basado en FPGA de un procesador PRAM en chip", Proc. Conferencia de la ACM sobre fronteras informáticas de 2008 (Ischia, Italia) (PDF) , págs. 55–66, doi : 10.1145 / 1366230.1366240 , ISBN 978-1-60558-077-7, S2CID 11557669.
- Vishkin, Uzi (enero de 2011), "Uso de la abstracción simple para reinventar la computación para el paralelismo", Communications of the ACM , 54 (1): 75–85, doi : 10.1145 / 1866739.1866757.
- Ghanim, Fady; Vishkin, Uzi; Barua, Rajeev (febrero de 2018), "Easy PRAM-Based High-Performance Parallel Programming with ICE", IEEE Transactions on Parallel and Distributed Systems , 29 (2): 377–390, doi : 10.1109 / TPDS.2017.2754376 , hdl : 1903 / 18521.
Notas
- ^ ACM: Premio de becarios / Uzi Vishkin .
- ^ Vishkin, Uzi. Arquitectura de conjunto de instrucciones spawn-join para proporcionar multiproceso explícito. Patente de Estados Unidos 6.463.527. Véase también Vishkin et al. (1998) .
- ^ Universidad de Maryland, comunicado de prensa, 26 de junio de 2007: "Profesor de Maryland crea supercomputadora de escritorio" .
- ^ Universidad de Maryland, A. James Clark School of Engineering, comunicado de prensa, 28 de noviembre de 2007: "Próximo gran salto" en tecnología informática obtiene un nombre " .
- ^ Primera ed., Sección 30.5.
- ^ Véase, por ejemplo, Goldberg, Plotkin y Shannon (1988) .
Referencias
- Baase, Sara; Van Gelder, Allen (2000), Introducción a los algoritmos informáticos al diseño y análisis (tercera edición), Addison-Wesley, ISBN 978-0-201-61244-8
- Brent, Richard P. (1974), "La evaluación paralela de expresiones aritméticas generales", Journal of the ACM , 21 (2): 201-208, doi : 10.1145 / 321812.321815 , S2CID 16416106.
- Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990), Introducción a los algoritmos (Primera edición), MIT Press y McGraw-Hill, ISBN 978-0-262-03141-7
- Eppstein, David ; Galil, Zvi (1988), "Técnicas algorítmicas paralelas para la computación combinatoria", Annu. Rev. Comput. Sci. , 3 : 233–283, doi : 10.1146 / annurev.cs.03.060188.001313
Este artículo de la encuesta cita 16 artículos escritos en coautoría por Vishkin
- Goldberg, Andrew V .; Plotkin, Serge A .; Shannon, Gregory E. (1988), "Ruptura de simetría paralela en gráficos dispersos", SIAM Journal on Discrete Mathematics , 1 (4): 434–446, CiteSeerX 10.1.1.39.269 , doi : 10.1137 / 0401044
- JaJa, Joseph (1992), Introducción a los algoritmos paralelos , Addison-Wesley, ISBN 978-0-201-54856-3
Cita 36 artículos en coautoría de Vishkin
- Karp, Richard M .; Ramachandran, Vijaya (1988), "Un estudio de algoritmos paralelos para máquinas de memoria compartida", Universidad de California, Berkeley, Departamento de EECS, Tech. Representante UCB / CSD-88-408
Este artículo de la encuesta cita 20 artículos escritos en coautoría por Vishkin
- Keller, Jorg; Kessler, Cristoph W .; Traeff, Jesper L. (2001), Programación práctica de PRAM , Wiley-Interscience, ISBN 978-0-471-35351-5
Cita 19 artículos escritos en coautoría por Vishkin
- Manber, Udi (1989), Introducción a los algoritmos: un enfoque creativo , Addison-Wesley, ISBN 978-0-201-12037-0
- Vishkin, Uzi (2009), Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 páginas (PDF) , Notas de clase de cursos sobre algoritmos paralelos impartidos desde 1992 en la Universidad de Maryland, College Park, la Universidad de Tel Aviv y la Technion
- Proyecto de genealogía matemática: Uzi Vishkin .
- ISI Web of Knowledge, investigadores muy citados: Uzi Vishkin .
enlaces externos
- Página de inicio de Uzi Vishkin .
- Página de inicio del proyecto XMT, con enlaces a una versión de software, tutorial en línea y material para enseñar el paralelismo .
- Uzi Vishkin en DBLP .