Ejecución paralela de algoritmos incrementales aleatorizados

Abstract

Hoy en día es cada vez más fácil tener acceso a un supercomputador. Sin embargo sólo los programadores expertos, con un elevado conocimiento del problema a paralelizar y de la arquitectura de la máquina en que se desea ejecutar el programa, son capaces de diseñar algoritmos que se ejecuten en paralelo eficientemente. En este trabajo presentamos una técnica de paralelización automática que, con un mínimo esfuerzo de imple-mentación, permite ejecutar código secuencial en paralelo en una máquina de memoria compartida con varios procesadores. Se mostrará que, en el contexto de la Geometría Computacional, los algoritmos incrementales aleatorizados son claros candidatos a beneficiarse de esta técnica. Se presentan resultados experimentales para el cálculo de la envolvente convexa y del menor círculo contenedor de nubes de puntos en 2D, que muestran aceleraciones significativas en la ejecución paralela de bucles frente a su versión secuencial.