Thomas Messi Nguelé - DSLs for Social Network Analysis on Multi-core Architecture

08:00
Saturday
15
Sep
2018
Organized by: 
Thomas Messi Nguelé
Speaker: 
Thomas Messi Nguelé
Detailed information: 

Jury :

  • Examinateurs : 
    • Pr Daniel AKUME  (Université de Buéa)
    • Pr Roger ATSA ETOUNDI  (Université de Yaoundé 1) 
  • Co-Directeurs : 
    • Pr Jean-Francois MEHAUT  (Université de Grenoble Alpes) 
    • Pr Maurice TCHUENTE  (Université de Yaoundé 1) 
  • Rapporteurs : 
    • Pr Emmanuel VIENNET  (Université de Paris Nord)  
    • Pr  Clémentin TAYOU  (Université de Dschang)

 

Abstract: 

A complex network is a set of entities in a relationship, modeled by a graph where nodes represent entities and edges between nodes represent relationships. Graph algorithms have inherent characteristics, including data-driven computations and poor locality. These characteristics expose graph algorithms to several challenges, because most well studied (parallel) abstractions and implementation are not suitable for them. The main question in this thesis is how to develop graph analysis applications that are both --easy to write (implementation challenge), -- and efficient (performance challenge)? We answer this question with parallelism (parallel DSLs) and also with knowledge that we have on complex networks (complex networks properties such as community structure and heterogeneity of node degree). 
The first contribution of this thesis shows the exploitation of community structure in order to design community-aware graph ordering for cache misses reduction. We proposed NumBaCo and compared it with Gorder and Rabbit (which appeared in the literature at the same period NumBaCo was proposed). This comparison allowed to design Cn-order, another heuristic that combines advantages of the three algorithms (Gorder, Rabbit and NumBaCo) to solve the problem of complex-network ordering for cache misses reduction. Experimental results with one thread on Core2, Numa4 and Numa24 (with Pagerank and livejournal for example) showed that Cn-order uses well the advantages of the other orders and outperforms them. 
The second contribution of this thesis considered the case of multiple threads applications. In that case, cache misses reduction was not sufficient to ensure execution time reduction; one should also take into account load balancing among threads. In that way, heterogeneity of node degree was used in order to design Deg-scheduling, a heuristic to solve degree-aware scheduling problem. Deg-scheduling was combined to Cn-order, NumBaCo, Rabbit, and Gorder to form respectively Comm-deg-scheduling, Numb-deg-scheduling, Rab-deg-scheduling and Gor-deg-scheduling. Experimental results with many threads on Numa4 showed that Degree-aware scheduling heuristics (Comm-deg-scheduling, Numb-deg-scheduling, Rab-deg-scheduling and Gor-deg-scheduling) outperform their homologous graph ordering heuristics (Cn-order, NumBaCo, Rabbit, and Gorder) when they are compared two by two. 
The last contribution was the integration of graph ordering heuristics and degree-aware scheduling heuristics in graph DSLs and particularly Galois and Green-Marl DSLs. We showed that with Green-Marl, performances are increased by both graph ordering heuristics and degree-aware scheduling heuristics (time was reduced by 35% due to heuristics). But with Galois, performances are increased only with graph ordering heuristics (time was reduced by 48% due to heuristics). 
In perspective, instead of using complex networks properties to design heuristics, one can imagine to use machine learning. Another perspective concerns the theoretical aspect of this thesis. We showed that graph ordering for cache misses reduction and degree-aware scheduling for load balancing problems are NP-complete. We provided heuristics to solve them. But we didn't show how far these heuristics are to the optimal solutions. It is good to know it in the future.