Tesis "Estrategias de Cómputo Paralelo en Multi/Many-Cores para el Procesamiento Eficiente de Redes Complejas"
Alumno: Alberto García Robledo
Asesor: Dr. Arturo Díaz Pérez, Dr. Guillermo Benito Morales Luna
Sinodales: Dr. Abel Sánchez, Dr. Francisco Javier Zaragoza Martínez, Dr. Eduardo Arturo Rodríguez Tello, Dr. Víctor Jesús Sosa Sosa
Resumen:
La Ciencia de Redes es un nuevo campo dedicado al estudio de redes complejas: modelos gráficos de fenómenos físicos, biológicos y tecnológicos grandes. Para procesar redes complejas, procesadores de propósito general (CPUs) pueden ser combinados con procesadores gráficos (GPUs) en un enfoque conocido como cómputo heterogéneo. Un problema fundamental es decidir cómo dividir una gráfica para distribuirla entre el CPU y el GPU. Por un lado, el rendimiento de nuevas plataformas heterogéneas síncronas paralelas (BSP) depende de la reducción del tiempo de procesamiento de las particiones. Por otra parte, la estructura de redes complejas provee información útil que puede ser explotada para una variedad de propósitos.
Para resolver eficientemente problemas en redes complejas del presente y del futuro, es necesario diseñar nuevos algoritmos que (1) exploten la estructura de grafos a través de métricas estructurales; y (2) que adopten un enfoque heterogéneo que combine el poder de cómputo de CPUs y GPUs. La presente tesis documenta nuevos algoritmos para redes complejas que explotan la topología de la red, con aplicaciones en cómputo heterogéneo. A lo largo del documento se describen: (1) un enfoque basado en redes para el análisis de datos no etiquetados, (2) el diseño de un proceso de engrosamiento de gráficas que conserva propiedades no redundantes de redes complejas, y (3) el diseño de algoritmos de particionamiento que explotan la topología de las redes para balanceo de carga. Al final, se estudia el rendimiento de una plataforma BSP existente que utiliza los algoritmos propuestos para el recorrido de redes reales y sintéticas grandes.
----------------------------------------------------------------------------------------------------------------------------
Networks Science is a new field devoted to the study of complex networks: graphical models of large physical, biological, technological, and sociological phenomena. To process real-world networks, CPU's can be combined with Graphics Processing Units (GPU's), in an approach known as heterogeneous computing. A fundamental problem is to decide how to partition the graph to distribute it between the CPU and the GPU. On the one hand, the performance of new Bulk Synchronous Parallel (BSP) heterogeneous platforms depends on minimizing the computation time of partitions. On the other hand, the structure of complex networks provides insights that can be measured and exploited for a variety of purposes.
To efficiently solve a variety of problems in complex networks of the present and future, it is necessary to design novel algorithms that: (1) exploit the structure of graphs by means of topological metrics; and (2) adopt a heterogeneous approach that combines the computing power of multi/many-core architectures. This thesis presents new topology-aware algorithms for complex networks with applications in graph heterogeneous computing. Throughout this document, there are described: (1) an application of a network-based approach for unlabeled data analysis, (2) the design of a complex network coarsening process that preserves non-redundant structural properties, and (3) the design of topology-aware partitioning algorithms for load-balancing. The performance of an existing BSP-based heterogeneous computing platform is studied by exploiting the proposed algorithms when traversing large real-world and synthetic graphs.