QPR: Quantisierung von PageRank mit kohärenten Shared Memory Beschleunigern

Graphalgorithmen erfordern oft feinkörnigen, zufälligen Zugriff auf erheblich große Datenstrukturen. Frühere Arbeiten zur FPGA-basierten Beschleunigung erforderten erhebliche Vorverarbeitung und Umstrukturierung, um die Speicherzugriffs-Patterns in ein Streaming-Format zu transformieren, das für die Hardware von FPGAs geeigneter ist. Mit dem Aufkommen von cache-kohärenten Shared Memory-Schnittstellen wie CAPI können Designer nun einfacher mit der natürlichen In-Memory-Organisation der Daten arbeiten. Dieses Papier stellt einen vertex-zentrierten Shared-Memory-Beschleuniger für den PageRank-Algorithmus vor, der für hohe Leistung optimiert ist und effektiv kohärente Caching auf der FPGA-Hardware nutzt. Das vorgeschlagene Design erreicht bis zu 14,9-fache Geschwindigkeit durch selektives Cachen von Graphdaten für den Beschleuniger unter Berücksichtigung von Lokalität und Wiederverwendung im Vergleich zur naiven Verwendung des Shared Address Space-Zugriffs und ausschließlich DRAM. Wir stellen außerdem die PageRank-Quantisierung vor, eine innovative Technik zur Darstellung von Page-Ranks mit 32-Bit quantisierten Festpunktwerten. Dieser Ansatz ist bis zu 1,5-fach schneller als 64-Bit Festpunkt und hält gleichzeitig die Präzision innerhalb eines tolerierbaren Fehlerbereichs. Infolgedessen erhalten wir sowohl die Hardware-Skalierbarkeit der Festpunktrepräsentation als auch die Cache-Leistung von 32-Bit Gleitkommazahlen.