Analytics
CPU
Betweenness Centrality
Bipart
Breadth-first Search
Clustering
Connected Components
GMetis
Independent Set
k-Core
k-Truss
Max Cardinality Bipartite Matching
Matrix Completion
Minimum Spanning Tree
PageRank
Points-To Analysis
Preflow-Push
Single-Source Shortest Path
Triangle Counting
GPU
Breadth-First Search
Connected Components
Maximal Independent Set
Minimum Spanning Tree
Pagerank
Points-To Analysis
Single-Source Shortest Paths
Matrix Completion
Triangle Counting
Distributed
Betweenness Centrality
Breadth-first Search
Connected Components
k-Core
Matrix Completion
PageRank
Single-Source Shortest Path
Triangle Counting

Maximal Independent Set

Problem Description

This benchmark computes maximal independent set in an unweighted graph.

Algorithm

This code has been generated using IrGL compiler. IrGL produces CUDA code and automatically adds a few optimizations to the CUDA code. For more information on the implementation and these optimizations please read this paper.

Performance

Graph	Time (ms)
USA-road-d.CTR	3
USA-road-d.W	13
USA-road-d.USA	56
orkut	922
livejournal	235
indochina	387

The above performance is observed on a 1733.500 Mhz GeForce GTX 1080 6000 with 8119 MB of main memory.