Cada vez más rápido

  • Juan Felipe Ramos
  • Juan Sebastián Gómez
  • Nicolás Cardozo
Palabras clave: Algoritmos, Paralelismo, Consultas en Rango, Descomposición de raíz cuadrada

Resumen

El diseño de algoritmos es fundamental para la construcción de artefactos de software que son correctos y eficientes. La importancia de los algoritmos se ha visto resaltada en los últimos años, donde debido a los requerimientos de procesamiento de altos volúmenes de datos en dominios como la inteligencia artificial o el procesamiento en la nube con arquitecturas de BigData. Ya no es suficiente diseñar algoritmos con tiempos de complejidad teórica óptimos. Además, estos algoritmos deben optimizar al máximo el tiempo de ejecución de los procesos. Para responder a esta necesidad, la programación paralela se ha enfocado en el desarrollo de algoritmos que pueden ejecutar múltiples tareas de forma simultánea, cada una en una unidad de procesamiento distinta. En este trabajo, presentamos la forma de mejorar el tiempo de ejecución de algoritmos óptimos aplicando técnicas de paralelismo a los algoritmos para aprovechar al máximo las capacidades de multi-procesamiento de las máquinas modernas. Para hacer concreto este proceso, utilizamos el método de descomposición de raíz cuadrada sobre grandes volúmenes de datos. Los resultados obtenidos de nuestro experimento muestran una mejora de hasta 1.9x sobre la versión secuencial del algoritmo, confirmando los resultados teóricos del diseño del algoritmo.

Publicado
2021-12-13