Soporte para estructuras de datos dinámicas en máquinas de memoria distribuida

La compilación para máquinas de memoria distribuida ha sido un área de investigación muy activa en los últimos años. Gran parte de este trabajo se ha concentrado en programas que utilizan arreglos como sus estructuras de datos primarias. Hasta la fecha, se ha hecho poco trabajo para abordar el problema de soportar programas que utilizan estructuras de datos dinámicas basadas en punteros. Las técnicas desarrolladas para soportar la ejecución SPMD de programas basados en arreglos se basan en el hecho de que los arreglos están definidos estáticamente y son directamente direccionables. Las estructuras de datos recursivas no tienen estas propiedades, por lo que deben desarrollarse nuevas técnicas. En este artículo, describimos un modelo de ejecución para soportar programas que utilizan estructuras de datos dinámicas basadas en punteros. Este modelo utiliza un mecanismo simple para migrar un hilo de control basado en la disposición de los datos asignados en el heap e introduce paralelismo utilizando una técnica basada en futuros y creación perezosa de tareas. Nuestro objetivo es explotar este modelo de ejecución utilizando análisis de compilador y técnicas de paralelización automática. Hemos implementado un sistema prototipo, al que llamamos Olden, que se ejecuta en el Intel iPSC/860 y en el Thinking Machines CM-5. Discutimos nuestra implementación e informamos sobre experimentos con cinco puntos de referencia.