Det har funnits ett betydande intresse för parallell graf bearbetning på grund av behovet av att snabbt analysera de stora grafer som finns tillgängliga idag. Många grafkoder har utformats för distribuerat minne eller externt minne. Men idag även den största allmänt tillgängliga real-world grafen ( Hyperlink Web graf med över 3,5 miljarder hörn och 128 miljarder kanter) kan passa i minnet av en enda vara multicore server. Ändå, de flesta experimentella arbeten i litteraturen rapporterar resultat på mycket mindre grafer, och de för Hyperlink grafen använder distribuerat eller externt minne. Därför är det naturligt att fråga om vi effektivt kan lösa en bred klass av grafproblem på denna graf i minnet. Detta dokument visar att teoretiskt effektiva parallella grafalgoritmer kan skalas till de största offentligt tillgängliga graferna med hjälp av en enda maskin med en terabyte RAM, bearbeta dem på några minuter. Vi ger implementationer av teoretiskt effektiva parallella algoritmer för 13 viktiga grafproblem. Vi presenterar också de optimeringar och tekniker som vi använde i våra implementationer, vilket var avgörande för att vi snabbt skulle kunna bearbeta dessa stora grafer. Vi visar att drifttiderna för våra implementeringar överträffar befintliga toppmoderna implementeringar på de största verkliga graferna. För många av de problem som vi överväger är detta första gången de har lösts på grafer i denna skala. Vi tillhandahåller en offentligt tillgänglig referenssvit som innehåller våra implementeringar. 1 Dessa maskiner är ungefär lika stora som en arbetsstation och kan enkelt hyras i molnet (t.ex. på Amazon EC2).
Vi granskar befintliga parallella grafalgoritm riktmärken i den fullständiga versionen av vårt dokument REF.
Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
{'venue': "SPAA '18", 'journal': None, 'mag_field_of_study': ['Computer Science']}