Seminario: “Implementaciones multi-hilo de pilas y colas con semánticas relajadas”
21-OFecha: jueves 27 de enero de 2022 a las 11:00 hrs
Presenta: Dr. Armando Castañeda
Afiliación: Instituto de Matemáticas – UNAM
Resumen:
Por sus indudables y probados beneficios, la noción de linealizabilidad es la condición de consistencia más usada en la actualidad para identificar las implementaciones correctas de objetos concurrentes (e.g. pilas, colas, árboles, conjuntos) en sistemas multi-hilo. De forma intuitiva, una implementación linealizable da la ilusión al usuario de que las operaciones ocurren de forma secuencial, en algún orden que respeta en tiempo-real en el que ocurren las
invocaciones y respuestas a las operaciones. Desafortunadamente, se ha demostrado formalmente que para algunos tipos de objetos concurrentes, concretamente pilas y colas, toda implementación linealizable es costosa. Particularmente, cualquiera de estas implementaciones está forzada a usar costosos mecanismos de sincronización. Este resultado limita la escalabilidad de cualquier implementación para estos casos. Una forma de evitar este resultado negativo consiste en relajar la semántica de los objetos que queremos implementar. En esta plática veremos un tipo de relajación para pilas y colas que permite evitar los mencionados mecanismos de sincronización. Evaluaciones experimentales muestran que nuestras implementaciones se desempeñan bien para la solución en paralelo de algunos problemas sobre gráficas.
Semblanza:
El Dr. Armando Castañeda obtuvo el grado de Ingeniero en Sistemas Computacionales del Instituto Politécnico Nacional (IPN) en 2002, y los grados de Maestro y Doctor en Ciencias de la Computación de la Universidad Nacional Autónoma de México (UNAM) en 2007 y 2010 respectivamente. Entre 2011 y 2014, realizó estancias posdoctorales en el Institut National de Recherche en Informatique et en Automatique (INRIA) y en el Instituto Tecnológico Israelí (Technion). Actualmente es investigador de tiempo completo y definitivo del Instituto de Matemáticas de la UNAM.
Video del seminario: