'Ontwikkelen' is hier het belangrijke woord, aangezien het onderzoek betrekking heeft op het aanscherpen van algoritmen op synthetische datasets in plaats van op echte big data.
"Grafieken worden veel gebruikt om objecten uit de echte wereld weer te geven en te analyseren in veel domeinen, zoals sociale netwerken, business intelligence, biologie en neurowetenschappen", aldus Kaist. “Bij het ontwikkelen en testen van algoritmen voor een grootschalige grafiek wordt meestal een synthetische grafiek gebruikt in plaats van een echte grafiek. Dit komt doordat het delen en gebruiken van grootschalige echte grafieken zeer beperkt is omdat ze eigendom zijn of praktisch onmogelijk te verzamelen zijn. "
Conventioneel, volgens Kaist, wordt het ontwikkelen en testen van grafiekalgoritmen gedaan via de volgende tweestapsbenadering:
Stap één genereert een synthetische grafiek en slaat deze op schijven op. De grafiek wordt meestal gegenereerd door ofwel parametergebaseerde generatie of door het opschalen van grafieken - de eerste extraheert een klein aantal parameters die enkele eigenschappen van een gegeven echte grafiek kunnen vastleggen en genereert de synthetische grafiek met de parameters, de laatste schaalt een grafiek op. gegeven echte grafiek naar een grotere om de eigenschappen van de originele echte grafiek zoveel mogelijk te behouden.
Stap twee laadt de opgeslagen grafiek in het hoofdgeheugen van een grafiekverwerkingsengine, zoals Apache GraphX, en voert een bepaald grafiekalgoritme uit op de motor. "Omdat de grafiek te groot is om in het hoofdgeheugen van een enkele computer te passen, draait de grafiekengine meestal op een cluster van enkele tientallen of honderden computers", zei Kaist, "daarom zijn de kosten van de conventionele tweestapsbenadering hoog. . "
Het Koreaanse team genereert en slaat geen grootschalige synthetische grafiek op.
In plaats daarvan laadt het de eerste kleine echte grafiek in het hoofdgeheugen. Vervolgens, met behulp van een techniek genaamd T-GPS (grafiekverwerkingssimulatie op triljoen schaal), confronteerde het grafiekalgoritme met de kleine echte grafiek alsof de grootschalige synthetische grafiek die uit de echte grafiek zou moeten worden gegenereerd in het hoofdgeheugen bestaat, zei Kaist. , eraan toevoegend dat nadat het algoritme is voltooid, T-GPS hetzelfde resultaat retourneert als de conventionele tweestapsbenadering.
"Het belangrijkste idee van T-GPS is het genereren van alleen het deel van de synthetische grafiek waartoe het algoritme direct toegang moet hebben, en het aanpassen van de grafische verwerkingsengine om het direct gegenereerde deel te herkennen als het daadwerkelijk gegenereerde deel van de synthetische grafiek. ”Zei Kaist.
T-GPS verwerkte een grafiek van een biljoen randen op één computer, terwijl de conventionele tweestapsbenadering een cluster van elf computers met dezelfde specificatie nodig had om een grafiek van een miljard randen te verwerken. T-GPS had geen netwerktoegang nodig en was tot 43 keer sneller dan de conventionele benadering, die aanzienlijke communicatieoverheadkosten met zich meebrengt.
Het werk werd gepresenteerd op de IEEE ICDE 2021-conferentie als 'Trillion-scale Graph Processing Simulation gebaseerd op Top-Down Graph Upscaling'.