Uzi Vishkin (nacido en 1953) es un científico informático de 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 incluido 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 seminales del Dr. Vishkin desempeñaron un papel principal en la formación y configuración de lo que el pensamiento en paralelo ha llegado a significar en la teoría fundamental de la informática". [1]
Uzi Vishkin nació en Tel Aviv, Israel. Completó su licenciatura (1974) y maestría en Matemáticas en la Universidad Hebrea , antes de obtener su doctorado en Ciencias de la Computación en el Technion (1981). Luego pasó un año trabajando en el Centro de Investigación Thomas J. Watson de IBM 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, desempeñándose como su presidente desde 1987 hasta 1988. Desde 1988 está en la Universidad de Maryland, College Park .
Una notable abstracción rudimentaria (que cualquier instrucción individual disponible para ejecución en un programa serial se ejecuta inmediatamente) hizo que la computación serial fuera simple. Una consecuencia de esta abstracción es una explicación paso a paso (inductiva) de la siguiente instrucción disponible para ejecución. La abstracción paralela rudimentaria detrás del concepto PRAM-on-chip, llamada Ejecución Concurrente Inmediata (ICE) en Vishkin (2011), es que un número indefinido de 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 lock-step) de las siguientes instrucciones disponibles para ejecución concurrente. Más allá de la computadora serial 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 pueda nuevamente aumentar la inducción matemática con una simple abstracción de computación de una línea. A continuación, se presenta una descripción cronológica de la evolución del concepto PRAM-on-chip y su prototipado de hardware y software . En los años 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 paralela (PRAM), que es una generalización para la computación paralela del modelo de computación serial estándar, la máquina de acceso aleatorio (RAM). Las máquinas paralelas necesarias para implementar el modelo PRAM aún no se habían construido en ese momento, y unas cuantas desafiaron la capacidad de construir tales máquinas. En 1997 [2], concluyó que el recuento de transistores en el chip, tal como lo implica la Ley de Moore, permitirá construir una computadora paralela poderosa en un solo chip de silicio en una década, y desarrolló una visión PRAM-On-Chip que exigía construir una computadora paralela en un solo chip que permita a los programadores desarrollar sus algoritmos para el modelo PRAM. Luego inventó la arquitectura de computadora explícita multiproceso (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 el concepto general. El concepto XMT fue presentado 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 pasos de bloqueo (usando ICE) puede lograr el mismo rendimiento que el código multihilo ajustado a mano más rápido en sistemas XMT. Este enfoque inductivo de pasos de bloqueo contrasta con los enfoques de programación multihilo de otros muchos sistemas centrales que son conocidos por desafiar a los programadores. 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, usando un lenguaje llamado XMTC . Dado que hacer que la programación paralela sea fácil 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 conceptos básicos de los algoritmos PRAM y la programación XMTC a estudiantes desde la escuela secundaria hasta la escuela de posgrado.
En el campo de los algoritmos paralelos, Uzi Vishkin fue coautor del artículo Shiloach & Vishkin (1982b) que contribuyó con el marco de tiempo de trabajo (WT) (a veces llamado profundidad de trabajo) para conceptualizar y describir algoritmos paralelos. El marco WT se adoptó como el 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 WT, un algoritmo paralelo se describe primero en términos de rondas paralelas. Para cada ronda, se caracterizan las operaciones que se realizarán, pero se pueden suprimir varios problemas. Por ejemplo, no es necesario que esté claro el número de operaciones en cada ronda, no es necesario mencionar los procesadores y no es necesario dar cuenta de ninguna información que pueda ayudar con la asignación de procesadores a trabajos. En segundo lugar, se proporciona la información suprimida. La inclusión de la información suprimida está, de hecho, guiada por la prueba 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, primero convertir 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 escritos en coautoría con Uzi Vishkin es Cole & Vishkin (1986). Este trabajo introdujo una técnica paralela eficiente para la coloración de grafos . El algoritmo Cole-Vishkin encuentra una coloración de vértice en un ciclo n en O (log * n ) rondas de comunicación sincrónica. Este algoritmo se presenta actualmente en muchos libros de texto, incluyendo Introduction to Algorithms de Cormen et al., [5] y forma la base de muchos otros algoritmos distribuidos para la coloración de grafos. [6]
Otras contribuciones de Uzi Vishkin y varios coautores incluyen algoritmos paralelos para clasificación de listas , ancestro común más bajo , árboles de expansión y componentes biconectados .
Este artículo de investigación cita 16 artículos escritos en coautoría con Vishkin
Cita 36 artículos escritos en coautoría con Vishkin
Este artículo de investigación cita 20 artículos escritos en coautoría con Vishkin
Cita 19 artículos escritos en coautoría con Vishkin