[ca] El camp de recerca de les xarxes neuronals aplicades a grafs (GNN) ha experimentat un creixement explosiu en els darrers anys. Aquesta és una conseqüència de la seva capacitat única per gestionar dades en forma de graf, una estructura de dades molt comuna que s'aplica àmpliament a innombrables indústries, des de la sanitat fins als sistemes de recomanació. Malgrat la popularitat, encara hi ha alguns aspectes que no s'han desenvolupat tant com d'altres. Un dels casos és la recerca de maneres més eficients de computar-los. Aquest problema pateix d'una complexitat important, a causa de la flexibilitat dels grafs per adaptar-se a una àmplia gamma de problemes. Les dissimilaritats estructurals entre diferents grafs dificulten el disseny d'un algorisme eficient amb una bona generalització. Juntament amb això, també hi ha la qüestió de la quantitat considerable de multiplicacions de matrius esparses que afecten negativament a l'eficiència. S'han proposat diversos nous algorismes d'acceleració, inclosos els enfocats al software, hardware i el hardware-software. Hi ha acceleradors que es basen a representar el graf d'entrada d'una forma més adequada per al hardware per tal d'aconseguir l'acceleració. Altres utilitzen un esquema diferent per calcular el graf per aprofitar diferents plataformes hardware. En aquesta tesi suggerim dues hipòtesis. A la llum del fet que no tots els acceleradors funcionen bé per a tots els grafs, la nostra primera hipòtesi és que no hi ha cap accelerador que funcioni bé per a tots els grafs. La segona hipòtesi és que, donada una caracterització adequada del graf, podem predir quin pot ser el millor accelerador entre una selecció d'ells. Per donar una resposta a ambdues hipòtesis, comparem dues alternatives de càlcul GNN: deep graph library (DGL) com a model de referència i TC-GNN com a accelerador de software per a GNN. La comparació es fa a través d'un conjunt de grafs tan ampli i complet com sigui possible, que contingui grafs de moltes estructures diferents. Amb tal de complir aquest objectiu, utilitzem un generador de graf sintètic, GraphLaxy, del nostre grup de recerca. Usarem tots els grafs sintètics per enregistrar el temps que triga DGL i TC-GNN. Amb aquestes dades, entrenem un model per predir el temps d'execució d'ambdues alternatives en funció de les característiques dels grafs d'entrada. Després de tots els experiments, hem descobert que, en general, TC-GNN té un millor rendiment que DGL, especialment per a gràfics petits, mentre que DGL supera en grafs grans i ultra esparsos.

[en] The research field of Graph Neural Networks (GNNs) has been experimenting an explosive growth in the recent years. This is a consequence of their unique capability to manage graph data, a highly common data structure which is widely applied across innumerable industries ranging from healthcare to recommendation systems. Despite the popularity, there are still some aspects which have not been developed as much as others. One of the cases is the research on more efficient ways of computing. This problem suffers from a significant complexity, due to the flexibility of graph for adapting a wide range of problems. The structural dissimilarities between different graphs makes it difficult to design an efficient computing algorithm with good generalization. Along with that, there is also the problem of the considerable amount of sparse matrix multiplications which impact negatively on efficiency. Several new acceleration algorithms have been proposed, including software, hardware and hardware-software co-design approaches. There are accelerators which rely on represent the input graph in a more suitable form for hardware in order to get the speedup. Others use a different schema of computing the graph for taking advantage of different hardware platforms. In this thesis, we propose two hypotheses. In light of the fact that not all accelerators work well for all graphs, our first assumption is that there is no accelerator that works well for all graphs.The second hypothesis follows that, given a proper graph characterization, we can predict which can be the best accelerator among selection of them. Towards providing an answer to both hypotheses, we compare two GNN computing alternatives: deep graph library (DGL) as a baseline library and TC-GNN as a software accelerator for GNNs. The comparison is done over a wide and comprehensive graph dataset which contains graphs of many different structures. To that end, we use a synthetic graph generator, GraphLaxy, from our research group. We train all the graphs with synthetic data and record the time taken by DGL and TC-GNN. With this data, we train a model to predict the runtime of both alternatives based on the input graph characteristics. After all experiments, we have discovered that in general TC-GNN has better performance than DGL, especially for small graphs, while DGL outperforms in large and ultra-sparse graphs.