# Graph500

El Graph500 és una classificació dels supercomputadors, centrats en les càrregues intensives. El projecte es va anunciar a la Conferència Internacional de Supercomputació el juny de 2010. La primera llista es va publicar a la Conferència de Supercomputació ACM / IEEE el novembre de 2010. Les noves versions de la llista es publiquen dues vegades a l'any. La mètrica de rendiment principal utilitzada per classificar els superordinadors és GTEPS (arestes travessades per giga per segon).
Richard Murphy, de Sandia, diu que "L'objectiu del Graph500 és promoure la consciència sobre problemes complexos de dades", en lloc de centrar-se en punts de referència ("Benchmarks") d'ordinadors com HPL (High Performance Linpack), en què es basa TOP500.
Malgrat el seu nom, hi havia diversos centenars de sistemes en la qualificació, que van créixer fins a 174 el juny de 2014.
L'algorisme i la implementació que va guanyar el campionat es publica en el document titulat "Extreme scale wideth-first search on supercomputers".
També hi ha una llista Green Graph 500, que utilitza la mateixa mètrica de rendiment, però classifica segons el rendiment per watt, com Green 500 funciona amb TOP500 (HPL).

## Benchmark

El benchmark utilitzat en Graph500 dona una gran importància al subsistema de comunicació del sistema, en comptes de valorar el punt flotant de precisió doble. Està basat en l'algorisme de cerca en amplada en un gran graf no dirigit (seguint el model del graf de Kronecker amb grau mitjà de 16). Hi ha tres kernels de còmput en el benchmark: el primer kernel genera el graf i ho comprèn en estructures disperses CSR o CSC (del anglès, Compressed Sparse Row/Column); el segon kernel realitza una cerca BFS en paral·lel d'un cert nombre de vèrtexs aleatoris (64 iteracions de cerca per execució); el tercer kernel executa la cerca dels camins més curts des d'un node d'origen a tots els altres nodes del graf (SSSP). Sis possibles mides de graf són definits: toy (226 nodes; 17 GB de RAM), mini (229; 137 GB), small (232; 1.1 TB), medium (236; 17.6 TB), large (239; 140 TB), huge (242; 1.1 PB de RAM).
La implementació de referència del benchmark conté diverses versions:
* sèrie a alt nivell en GNU Octave
* sèrie a baix nivell en C
* una versió en paral·lel de C utilitzant OpenMP
* dues versions per Cray-XMT
* una versió bàsica a MPI (amb funcions de MPI-1)
* una versió optimitzada de MPI (amb comunicacions unilaterals de MPI-2)

### Passos del Benchmark

* Genera una llista d'arestes.
* Construeix un graf a partir de la llista d'arestes (cronometrat, kernel 1).
* Mostra de forma aleatòria 64 nodes amb grau mínim d'u, sense comptar bucles.
* Per cada clau de cerca:
** Calcula l'array pare (cronometrat, kernel 2)
** Comprova que l'array pare sigui un arbre de cerca BFS correcte per l'arbre donat.
* Per cada clau de cerca:
** Calcula l'array pare i l'array de distància (cronometrat, kernel 3).
** Valida que l'array pare/vector de distàncies, el qual es un arbre de cerca SSSP amb els camins més curts, sigui correcte per a l'arbre de cerca donat.
* Calcula i retorna la informació relativa al rendiment.

### Kernel 1 - Construcció del graf

El primer kernel pot transformar la llista d'arestes en qualsevol de les estructures de dades que s'utilitzin en la resta de kernels, com podria un graf dispers. Encara que el graf es pot representar de qualsevol manera, no pot ser modificat per un kernel o entre d'altres. Es pot reservar espai a l'estructura de dades per marca o bloquejar. Cada kernel té accés exclusiu a qualsevol espai de marcatge o bloqueig i se li permet (només) modificar aquest espai.
El procés de construcció de l'estructura de dades a partir del conjunt de tuples ha de ser cronometrat.
Les claus de cerca s'han de mostrar aleatòriament dels vèrtexs del graf. Per evitar trivialitats, només es mostraran aquells que tinguin com a mínim grau u. Si hi ha menys de 64 nodes, s'executaran menys de 64 cerques.

### Kernel 2 – Breadth-First Search

La cerca del primer en amplada del graf començarà amb un únic node d'origen i, per fases, trobarà i etiquetarà als seus veïns. Després als veïns dels seus veïns, fins a completar la cerca. El resultat d'efectuar l'algorisme BFS reflectirà el rendiment d'una arquitectura en executar threads concurrents, cadascun de poca concurrència de memòria i alta densitat de referència de memòria. També l'eficiència quan la ruta d'execució de cada fil depèn dels efectes secundaris asíncrons d'altres i la capacitat de carregar dinàmicament unitats de treball de mida imprevisible.

### Kernel 3 - SSSP

El càlcul del camins més curts (SSSP) trobarà la distància més curta per un node donat a tots els altres vèrtexs del graf. Aquest kernel ampliarà el benchmark amb proves addicionals i accés a dades per vèrtex. Molts, però no tots els algoritmes de SSSP, són similars als de BFS i pateixen problemes similars de hot-spotting i referències a memòria duplicades.

### Criteri d'avaluació

En ordre aproximat d'importància, els objectius del benchmark són:
* Adherència adequada a la intenció de la especificació del benchmark.
* Mida màxima del problema per a una determinada màquina.
* Temps d'execució mínim per a una determinada mida del problema
Objectius menys importants:
* Mida mínima del codi (sense incloure el codi de validació).
* Temps de desenvolupament mínim.
* Manteniment màxim.
* Extensibilitat màxima.

## Classificació i rankings

Graph500 té diferents tipus de subclassificacions de supercomputadors a més de la classificació general. Tot ells tenen en compte els TEPS (Traversed edges per second) que es realitzen a la màquina a l'aplicar el Benchmark.

### Resultats Complets

Aquesta és la classificació general del Graph500. Premia al supercomputador amb més TEPS a l'aplicar Benckmark.
Consta d'un total de 248 entrades.
Top 5 November 2019 Complete Results :
| Posició | Màquina | Venedor | País | Localització | Nº Nodes | Nº Cores | Memòria | GTEPS | C_Time |
| 1 | K computer | Fujitsu | Japó | Kobe Hyogo | 82.944 | 663.552 | 1.327.100 GiB | 31302,4 | 609,395 segons |
| 2 | Sunway TaihuLight | NRCPC | Xina | Wuxi | 40.768 | 10.599.680 | 1.304.580 GiB | 23755,7 | 961,455 segons |
| 3 | DOE/NNSA/LLNL Sequoia | IBM | EEUU | Livermore CA | 98.304 | 1.572.864 | 1.572.860 GiB | 23751 | 368,7 segons |
| 4 | DOE/SC/Argonne National Laboratory Mira | IBM | EEUU | Chicago IL | 49.152 | 786.432 | 786.432 GiB | 14982 | 259,8 segons |
| 5 | SuperMUC-NG | Lenovo | Alemanya | Garching | 4.096 | 196.608 | 393.216 GiB | 6279,47 | 1547,10 segons |

### BFS

A la subclassificació BFS es classifica als superordinadors per la quantitat de TEPS que realitzen a l'aplicar el Kernel 2 del Benchmark (la cerca en profunditat (BFS)).
Aquesta és la subclassificació més participada del Graph500 amb un total del 291 entrades.
TOP 5 November 2019 BFS :
| Posició | Màquina | Venedor | País | Localització | Nº Nodes | Nº Cores | Memòria | GTEPS | C_Time |
| 1 | Sunway TaihuLight | NRCPC | Xina | Wuxi | 40,768 | 10.599.680 | 1.304.580 GiB | 23.755,7 | 961,455 segons |
| 2 | BlueGene/Q Power BQC 16C 1.60 GHz | IBM | EEUU | Livermore CA | 98.304 | 1.572.864 | 1.572.860 GiB | 23.751 | 368,7 segons |
| 3 | DOE/SC/Argonne National Laboratory Mira | IBM | EEUU | Chicago IL | 49.152 | 786.432 | 786.432 GiB | 14.982 | 259,8 segons |
| 4 | OLCF-Summit (CPU -Only) | IBM | EEUU | Oak Ridge TN | 2.048 | 86.016 | 1.048.576 GiB | 7.665,7 | 370,647 segons |
| 5 | SuperMUC-NG | Lenovo | Alemanya | Garching | 4.096 | 196.608 | 393.216 GiB | 6279,47 | 1547,10 segons |

### SSSP

A la classificació SSSP es classifica als superordinadors per la quantitat de TEPS que realitzen a l'aplicar el Kernel 3 del Benchmark (la cerca dels camins més curts des del node origen a tots els punts del graf (SSP)).
Aquesta subclassificació del Graph500 només compte amb 24 entrades. És la menys participada de totes.
Top 5 November 2019 SSSP :
| Posició | Màquina | Venedor | País | Localització | Nº Nodes | Nº Cores | Memòria | GTEPS | C_Time |
| 1 | SuperMUC-NG | Lenovo | Alemanya | Garching | 4.096 | 196.608 | 393.216 GiB | 1053,93 | 310,72 segons |
| 2 | NERSC Cori - 1024 haswell partition | Cray | EEUU | DOE/SC/LBN/NERSC | 1.024 | 32.768 | 133.376 GiB | 558,833 | 446,475 segons |
| 3 | Nurion | Cray | Corea | Daejeon | 1.024 | 65.536 | 98.304 GiB | 337,239 | 858 segons |
| 4 | NERSC Cori - 512 KNL partition | Cray | EEUU | DOE/SC/LBN/NERSC | 512 | 32.768 | 57.344 GiB | 229,188 | 1188 segons |
| 5 | Undisclosed Cray XE6 | Cray | EEUU | University | 512 | 16.384 | Unknown | 134,173 | 400,206 segons |

### GreenGraph500

En aquesta classificació tornem a classificar als computadors segons la quantitat de TEPS que realitzen a l'aplicar el Kernel 2, però en aquest cas, dividits entre els Watts que consumeix la màquina.
Aquesta classificació va aparèixer per primer cop l'any 2013, a l'edició de juny.
Dins del GreenGraph500 trobem dues classificacions més:

#### BIG DATA

Té un total de 40 entrades.
November 2019 Green: BIG DATA :
| Posició | MTEPS/W | Màquina | GTEPS | Nª Nodes | Nº Cores | Potència | Posició al Graph500 |
| 1 | 282,70 | High Throughput Computer | 34,49 | 1 | 40 | 122 W | 81 |
| 2 | 177,45 | IBM Power8+ Tesla P100 | 41,70 | 1 | 66 | 235 W | 77 |
| 3 | 165,97 | High Throughput Computer | 22,24 | 1 | 40 | 134 W | Null |
| 4 | 163,96 | High Throughput Computer | 21,97 | 1 | 40 | 134 W | Null |
| 5 | 112,41 | PowerfullServer | 16,30 | 1 | 18 | 145 W | 92 |

#### SMALL DATA

Té un total de 45 entrades.
November 2019 Green: SMALL DATA :
| Posició | MTEPS/W | Màquina | GTEPS | Nº Nodes | Nº Cores | Potència | Posició al Graph500 |
| 1 | 1830,31 | High Throughput Computer(+GPU) | 237,94 | 1 | 58 | 130 W | 42 |
| 2 | 1400,19 | Graph-WICIL-Node0 | 79,531 | 1 | 18 | 56,8 W | 67 |
| 3 | 1165,71 | IBM POWER8+ Tesla P100 | 240 | 1 | 66 | 175 W | 45 |
| 4 | 815,68 | TitanX_forsite | 132,14 | 1 | 28 | 162 W | 55 |
| 5 | 597,86 | Xeon(R) Gold 5118+Tesla P100 | 131,53 | 1 | 24 | 220 W | 56 |

## Història

El projecte va ser anunciat en la Conferència Internacional de Supercomputació en juny de 2010 i va sortir més tard al Novembre del mateix any en el ACM/IEEE Supercomputing Conference amb el propòsit de veure quin era el supercomputador amb millor rendiment.
Graph 500 BFS Novembre 2010 :
| Posició | Màquina | Venedor | Tipus | Indret d'instal·lació | Nombre de nodes | Nombre de cores | Implemen- tació | Escala | GTEPS |
| 1 | Intrepid | IBM | BlueGene | Argonne National Laboratory | 8192 | 32000 | Optimitzada | 36 | 7.0867 |
| 2 | Franklin | Cray | XT4 | NERSC | 9544 | | Optimitzada | 32 | 5.60493 |
| 3 | cougarxmt | Cray | XMT | Pacific Northwest National Laboratory | 128 | | Optimitzada | 29 | 1.30997 |
El computador que va quedar primer amb l'algoritme Breadth First Search, BFS, algoritme de busqueda no informada en la qual recorres tot un graf visitant tots els veïns d'un node. Va ser l'Intrepid d'IBM. Està instal·lada en el laboratori de Lawrence Livermore, EE. UU. i es dedica principalment l'emmagatzemament i transmissió de dades entre diversos sistemes informàtics.
Al Novembre 2013 va aparèixer el primer Green Graph500 per classificar el top500 de supercomputadors amb millor eficiència d'energia mesurat el Limpack flops per watt. Hi ha dues classificacions: Big data i small data.
Green graph 500 Novembre 2013 BIG DATA :
| RANK | MTEPS/W | SITE | MACHINE | GRAPH500 RANK | SCALE | GTEPS | NODES | POWER |
| 1 | 6.72 | Tokyo Institute of Technology | TSUBAME KFC | 47 | 32 | 44.019100 | 32 | 6552.7 Watts |
| 2 | 5.41 | Forschungszentrum Juelich (FZJ) | JUQUEEN | 3 | 38 | 5848.000000 | 16384 | 1081340 Watts |
| 3 | 4.42 | Argonne National Laboratory | DOE/SC/Argonne National Laboratory Mira | 2 | 40 | 14328.000000 | 49152 | 324430 Watts |
En el Big Data va quedar primer la TSUBAME KFC que opera en el Tokyo Institute of Technology.
Green graph 500 Novembre 2013 SMALL DATA :
| RANK | MTEPS/W | SITE | MACHINE | GRAPH500 RANK | SCALE | GTEPS | NODES | POWER |
| 1 | 153.17 | Yuichiro Yasui | GraphCREST-Xperia-A-SO-04E | 143 | 20 | 0.477633 | 1 | 3.1184 Watts |
| 2 | 129.63 | Tokyo Institute of Technology | GraphCREST-NEXUS7-2013 | 141 | 20 | 0.534713 | 1 | 4.1248 Watts |
| 3 | 73.57 | University of Tsukuba | kitty6 | 58 | 25 | 17.207000 | 1 | 233.894 Watts |
El millor va ser el GraphCREST-Xperia-A-SO-04E situat en Yuichiro Yasui.
Al Novembre del 2017 es va fer el primer graph500 amb l'algoritme SSSP, en el qual consisteix en troba el camí més curt en un graf, l'algoritme més conegut és el de Dijkstra que consisteix en anar visitant els nodes amb menys cost i trobar dels diferents recorreguts el més òptim.
Graph 500 SSSP Novembre 2017 :
| Posició | Posició prèvia | Màquina | Venedor | Tipus | NETWORK | Indret d'instal·lació | Localització | País | Any | Aplicació | Ús | Nombre de NODES | Nombre de CORES | Memòria | Imple- mentació | Escala | GTEPS | C_TYPE | POWER |
| 1 | nova | Cray XE6 system | Cray | BlueGene | MPP | Universitat | Universitat | EUA | | Universitat | Recerca | 8192 | newreference +heavy | 32768 | Optimitzada | 31 | 12.88 GTEPS | 27.5 | 0 |
| 2 | nova | Universitat de Notre Dame cluster | Dell | XT4 | Cluster | Universitat de Notre Dame | Universitat de Notre Dame | EUA | 2016 | Universitat | Recerca | 128 | newreference +heavy | 2048 | Optimitzada | 27 | 0.656085 GTEPS | 60.0327 | |
| 3 | nova | Alkindi27-CPU | Dell | XMT | Commodity Machine / Intel Xeon E5-2695 v3 (2 Sockets 28 cores 56 hardware threads) | Universitat de British Columbia | Vancouver BC | Canadà | 2015 | Universitat | Recerca | 56 | Custom | 256 | Optimitzada | 27 | 0.1972 GTEPS | 102.35 | 0 |
El supercomputador amb millor rendiment va ser la Cray XE6 system de Cray de tipus MMP. Una versió actualitzada del CrayXT6, es fa servir per promoure una topologia de xarxes entre els nodes.
Veient totes les classificacions, podem arribar a la conclusió de que hi ha hagut molta rivalitat durant els diferents anys.
En el ranking de l'algoritme d'SSSP, les dues primeres classificacions va ser millor el Cray XE6 system dels EE. UU. Però a partir de la següent fins al dia d'avui no tenen el millor. En el Novembre del 2018 fins al 2019 va ser el millor el SuperMUC-NG d'Alemanya. En el ranking de l'algoritme BFS va haver-hi molta rivalitat entre IBM dels Estats Units i Fujitsu del Japó fins al Novembre del 2019 que la K computer de Fujitsu ja no era dels millors i va ser millor, superant els Estats Units, la Sunway TaihuLight de la companyia xinesa NRCPC. Per acabar, en el Green Graph 500 va dominar sempre el supercomputador japonès GraphCREST-SandybridgeEP-2.4GHz fins al Novembre del 2017 que va aparèixer la IBM Power8+ Tesla P100 dels Estats Units.

## Referències

* 1 2 The Exascale Report. «The Case for the Graph 500 – Really Fast or Really Productive? Pick One». Inside HPC, 15-03-2012.
* ↑ «Archived copy». Arxivat de l'original el 2014-06-28. [Consulta: 26 juny 2014].
* ↑ Ueno, Koji; Suzumura, Toyotaro; Maruyama, Naoya; Fujisawa, Katsuki; Matsuoka, Satoshi. «Extreme scale breadth-first search on supercomputers». A: 2016 IEEE International Conference on Big Data (Big Data), 2016, p. 1040–1047. DOI 10.1109/BigData.2016.7840705. ISBN 978-1-4673-9005-7.
* ↑ Performance Evaluation of Graph500 on Large-Scale Distributed Environment // IEEE IISWC 2011, Austin, TX; presentation
* ↑ «Graph500: адекватный рейтинг» (en rus). Open Systems #1 2011.
* ↑ Ueno, K.; Suzumura, T.; Maruyama, N.; Fujisawa, K.; Matsuoka, S. «Extreme scale breadth-first search on supercomputers». 2016 IEEE International Conference on Big Data (Big Data), 01-12-2016, pàg. 1040–1047. DOI: 10.1109/BigData.2016.7840705.
* ↑ «Benchmark Specification | Graph 500» (en anglès americà). [Consulta: 2 abril 2020].
* ↑ «Complete Results | Graph 500» (en anglès americà). [Consulta: 1r abril 2020].
* ↑ «novembre 2019 BFS | Graph 500» (en anglès americà). [Consulta: 1r abril 2020].
* ↑ «novembre 2019 SSSP | Graph 500» (en anglès americà). [Consulta: 1r abril 2020].
* 1 2 «novembre 2019 Green | Graph 500» (en anglès americà). [Consulta: 1r abril 2020].

## Vegeu també

* TOP500

## Enllaços externs

* Graph500 - Lloc web oficial
* https://es.qwe.wiki/wiki/Graph500
* http://micaminomaster.com.co/grafo-algoritmo/historia-teoria-grafos/