HitGraph: Hochleistungs-Grafverarbeitungsrahmen auf FPGA

Dieses Papier präsentiert HitGraph, ein FPGA-Rahmenwerk zur Beschleunigung der Grafverarbeitung basierend auf dem edge-zentrierten Paradigma. HitGraph nimmt einen edge-zentrierten Grafikalgorithmus und Hardware-Ressourcenbeschränkungen auf, bestimmt die Entwurfsparameter und generiert dann ein Register Transfer Level (RTL) FPGA-Design. Dies macht das Entwerfen von Beschleunigern für verschiedene Grafikanalysen transparent und benutzerfreundlich, indem es die internen Details des Entwurfsprozesses für den Beschleuniger maskiert. HitGraph ermöglicht eine erhöhte Datenwiederverwendung und Parallelität durch neuartige algorithmische Optimierungen, einschließlich (1) eines optimierten Datenlayouts, das nicht-sequenzielle externe Speicherzugriffe reduziert, (2) eines effizienten Aktualisierungszusammenführungs- und Filterschemas zur Reduzierung der Datenkommunikation zwischen dem FPGA und dem externen Speicher, und (3) eines Partitionsüberspringungsschemas zur Reduzierung redundanter Kantendurchquerungen für nichtstationäre Grafikalgorithmen. Basierend auf unserer Entwurfsmethodologie beschleunigen wir Sparse Matrix Vector Multiplication (SpMV), PageRank (PR), Single Source Shortest Path (SSSP) und Weakly Connected Component (WCC). Experimentelle Ergebnisse zeigen, dass HitGraph eine hohe Durchsatzrate von 2076 Millionen durchquerten Kanten pro Sekunde (MTEPS) für SpMV, 2225 MTEPS für PR, 2916 MTEPS für SSSP und 3493 MTEPS für WCC aufrechterhält. Im Vergleich zu hochoptimierten Multi-Core-Implementierungen erreicht HitGraph bis zu 37,9-fachen Speedup. Im Vergleich zu modernen FPGA-Rahmenwerken erzielt HitGraph bis zu 50,7-fache Durchsatzverbesserung.