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).Performance Evaluation of Graph500 on Large-Scale Distributed Environment // IEEE IISWC 2011, Austin, TX; presentation
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 ResultsPosicióMàquinaVenedorPaísLocalitzacióNº NodesNº CoresMemòriaGTEPSC_Time1K computerFujitsuJapóKobe Hyogo82.944663.5521.327.100 GiB31302,4609,395 segons2Sunway TaihuLightNRCPCXinaWuxi40.76810.599.6801.304.580 GiB23755,7961,455 segons3DOE/NNSA/LLNL SequoiaIBMEEUULivermore CA98.3041.572.8641.572.860 GiB23751368,7 segons4DOE/SC/Argonne National Laboratory MiraIBMEEUUChicago IL49.152786.432786.432 GiB14982259,8 segons5SuperMUC-NGLenovoAlemanyaGarching4.096196.608393.216 GiB6279,471547,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 BFSPosicióMàquinaVenedorPaísLocalitzacióNº NodesNº CoresMemòriaGTEPSC_Time1Sunway TaihuLightNRCPCXinaWuxi40,76810.599.6801.304.580 GiB23.755,7961,455 segons2BlueGene/Q Power BQC 16C 1.60 GHzIBMEEUULivermore CA98.3041.572.8641.572.860 GiB23.751368,7 segons3DOE/SC/Argonne National Laboratory MiraIBMEEUUChicago IL49.152786.432786.432 GiB14.982259,8 segons4OLCF-Summit (CPU -Only)IBMEEUUOak Ridge TN2.04886.0161.048.576 GiB7.665,7370,647 segons5SuperMUC-NGLenovoAlemanyaGarching4.096196.608393.216 GiB6279,471547,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 SSSPPosicióMàquinaVenedorPaísLocalitzacióNº NodesNº CoresMemòriaGTEPSC_Time1SuperMUC-NGLenovoAlemanyaGarching4.096196.608393.216 GiB1053,93310,72 segons2NERSC Cori - 1024 haswell partitionCrayEEUUDOE/SC/LBN/NERSC1.02432.768133.376 GiB558,833 446,475 segons3NurionCrayCoreaDaejeon1.02465.53698.304 GiB337,239 858 segons4NERSC Cori - 512 KNL partitionCrayEEUUDOE/SC/LBN/NERSC51232.76857.344 GiB229,1881188 segons5Undisclosed Cray XE6CrayEEUUUniversity51216.384Unknown134,173400,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 DATAPosicióMTEPS/WMàquinaGTEPSNª NodesNº CoresPotènciaPosició al Graph5001282,70High Throughput Computer34,49140122 W812177,45IBM Power8+ Tesla P10041,70166235 W773165,97High Throughput Computer22,24140134 WNull4163,96High Throughput Computer21,97140134 WNull5112,41PowerfullServer16,30118145 W92
SMALL DATA Té un total de 45 entrades. + November 2019 Green: SMALL DATAPosicióMTEPS/WMàquinaGTEPSNº NodesNº CoresPotènciaPosició al Graph50011830,31High Throughput Computer(+GPU)237,94158130 W4221400,19Graph-WICIL-Node079,53111856,8 W6731165,71IBM POWER8+ Tesla P100240166175 W454815,68TitanX_forsite132,14128162 W555597,86Xeon(R) Gold 5118+Tesla P100131,53124220 W56
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 2010PosicióMàquinaVenedorTipusIndret d'instal·lacióNombre de
nodesNombre de
coresImplemen- tacióEscalaGTEPS1IntrepidIBMBlueGeneArgonne National
Laboratory819232000Optimitzada367.08672FranklinCrayXT4NERSC9544Optimitzada325.604933cougarxmtCrayXMTPacific Northwest
National Laboratory128Optimitzada291.30997 El computador que va quedar primer amb l'algoritme Breadth First Search, BFS, algoritme de cerca 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 DATARANKMTEPS/WSITEMACHINEGRAPH500 RANKSCALEGTEPSNODESPOWER16.72Tokyo Institute of TechnologyTSUBAME KFC473244.019100326552.7 Watts25.41Forschungszentrum Juelich (FZJ)JUQUEEN3385848.000000163841081340 Watts34.42Argonne National LaboratoryDOE/SC/Argonne National Laboratory Mira24014328.00000049152324430 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 DATARANKMTEPS/WSITEMACHINEGRAPH500 RANKSCALEGTEPSNODESPOWER1153.17Yuichiro YasuiGraphCREST-Xperia-A-SO-04E143200.47763313.1184 Watts2129.63Tokyo Institute of TechnologyGraphCREST-NEXUS7-2013141200.53471314.1248 Watts373.57University of Tsukubakitty6582517.2070001233.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 2017PosicióPosició prèviaMàquinaVenedorTipusNETWORKIndret d'instal·lacióLocalitzacióPaísAnyAplicacióÚsNombre de NODESNombre de CORESMemòriaImple- mentacióEscalaGTEPSC_TYPEPOWER1novaCray XE6 systemCrayBlueGeneMPPUniversitatUniversitatEUAUniversitatRecerca8192newreference +heavy32768Optimitzada3112.88 GTEPS27.502novaUniversitat de Notre Dame clusterDellXT4clústerUniversitat de Notre DameUniversitat de Notre DameEUA2016UniversitatRecerca128newreference