Reorganización de matrices en algoritmos de barrido radial sobre Modelos Digitales del Terreno

Abstract

Es muy frecuente, en los sistemas de información geográfica que trabajan con modelos digitales del terreno, el uso de algoritmos de barrido radial para el estudio de variables asociadas a parámetros cuya magnitud decrece con el cuadrado de la distancia, como las señales de radio, las ondas de sonido, o la propia visión humana. Sin embargo, dichos algoritmos están asociados a un acceso a las matrices de datos que, en la mayoría de los casos, aun siendo regular, derivan en un mal aprovechamiento de la localidad de la memoria. En este trabajo se muestra cómo la completa reorganización previa de las matrices de datos, en función de la dirección radial que corresponde, produce una considerable mejora del rendimiento, especialmente en algoritmos de elevada intensidad computacional. Sirva como ejemplo el cálculo de cuencas visuales totales, que es utilizada en este trabajo como caso de estudio. Por otra parte, la reestructuración matricial propuesta abre la puerta al uso intensivo de GPUs en muchos algoritmos para los que nunca se han considerado, por su irregularidad y baja eficiencia.