Fast Maximal Independent Set Algorithm for GPUs

a high quality and fast maximal independent n.w
1 / 62
Embed
Share

"Explore a high-quality and fast maximal independent set algorithm designed for GPUs by Martin Burtscher and Sindhu Devale. Learn about the importance of maximal independent sets, parallel algorithms, optimizations, and more."

  • GPU Algorithm
  • Independent Set
  • Parallel Computing
  • Graph Theory
rayaanacharya
kort_iel Follow

Uploaded on | 1 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. A High-Quality and Fast Maximal Independent Set Algorithm for GPUs Martin Burtscher and Sindhu Devale Department of Computer Science

  2. Overview Introduction Serial and parallel algorithms Our parallel algorithm Optimizations Results Summary A High-Quality and Fast MIS Algorithm 2

  3. Maximal Independent Set Maximal independent set (MIS) Subset of vertices of undirected graph Vertices in subset are independent (not adjacent) Subset is maximal (all other vertices are adjacent) Not unique a b c d e f Largest possible MIS Maximum independent set NP-hard to compute g h i A High-Quality and Fast MIS Algorithm 3

  4. Importance of MIS Building block of many parallel graph algorithms Graph coloring a Maximal matching 2-satisfiability b c d e f Maximal set packing g Odd set cover problem etc. h i A High-Quality and Fast MIS Algorithm 4

  5. Importance of MIS (cont.) Parallelization of complex computations Supports arbitrary and dynamically changing conflicts 1. Build graph (vertices = computations, edges = conflicts) 2. Compute MIS 3. Run computations in MIS in parallel (w/o locks or atomics) 4. Repeat if necessary E.g., Delaunay mesh refinement Approach is only useful if MIS can be computed quickly in parallel and benefits from large sets A High-Quality and Fast MIS Algorithm 5

  6. Highlights ECL-MIS algorithm for massively-parallel devices Fastest MIS runtimes on modern GPUs Randomized permutation selection function Largest set sizes among many MIS algorithms New optimizations Enhance performance and reduce memory footprint A High-Quality and Fast MIS Algorithm 6

  7. Serial Algorithm A High-Quality and Fast MIS Algorithm 7

  8. Serial Algorithm Repeating steps Visit unvisited vertex Add vertex to set if no graph neighbors in set a b c d e f Example Start with empty set g h i Set = {} A High-Quality and Fast MIS Algorithm 8

  9. Serial Algorithm Repeating steps Visit unvisited vertex Add vertex to set if no graph neighbors in set a b c d e f Example a has no neighbor in set Add vertex a g h i Set = {a} A High-Quality and Fast MIS Algorithm 9

  10. Serial Algorithm Repeating steps Visit unvisited vertex Add vertex to set if no graph neighbors in set a b c d e f Example b has neighbor in set Discard vertex b g h i Set = {a} A High-Quality and Fast MIS Algorithm 10

  11. Serial Algorithm Repeating steps Visit unvisited vertex Add vertex to set if no graph neighbors in set a b c d e f Example c has neighbor in set Discard vertex c g h i Set = {a} A High-Quality and Fast MIS Algorithm 11

  12. Serial Algorithm Repeating steps Visit unvisited vertex Add vertex to set if no graph neighbors in set a b c d e f Example d has neighbor in set Discard vertex d g h i Set = {a} A High-Quality and Fast MIS Algorithm 12

  13. Serial Algorithm Repeating steps Visit unvisited vertex Add vertex to set if no graph neighbors in set a b c d e f Example e has no neighbor in set Add vertex e g h i Set = {a, e} A High-Quality and Fast MIS Algorithm 13

  14. Serial Algorithm Repeating steps Visit unvisited vertex Add vertex to set if no graph neighbors in set a b c d e f Example f has neighbor in set Discard vertex f g h i Set = {a, e} A High-Quality and Fast MIS Algorithm 14

  15. Serial Algorithm Repeating steps Visit unvisited vertex Add vertex to set if no graph neighbors in set a b c d e f Example g has neighbor in set Discard vertex g g h i Set = {a, e} A High-Quality and Fast MIS Algorithm 15

  16. Serial Algorithm Repeating steps Visit unvisited vertex Add vertex to set if no graph neighbors in set a b c d e f Example h has no neighbor in set Add vertex h g h i Set = {a, e, h} A High-Quality and Fast MIS Algorithm 16

  17. Serial Algorithm Repeating steps Visit unvisited vertex Add vertex to set if no graph neighbors in set a b c d e f Example i has neighbor in set Discard vertex i g h i MIS = {a, e, h} A High-Quality and Fast MIS Algorithm 17

  18. Lubys Random-Priority Parallel MIS Algorithm A High-Quality and Fast MIS Algorithm 18

  19. Random-Priority Algorithm (Luby) Repeating steps Assign random priorities Add vertices with highest local priority to set Remove their neighbors from graph a b c d e f g Set = {} h i A High-Quality and Fast MIS Algorithm 19

  20. Random-Priority Algorithm (Luby) Repeating steps Assign random priorities Add vertices with highest local priority to set Remove their neighbors from graph a5 b7 c1 d4 e6 f3 g4 Set = {} h3 i2 A High-Quality and Fast MIS Algorithm 20

  21. Random-Priority Algorithm (Luby) Repeating steps Assign random priorities Add vertices with highest local priority to set Remove their neighbors from graph a5 b7 c1 d4 e6 f3 g4 Set = {b, e} h3 i2 A High-Quality and Fast MIS Algorithm 21

  22. Random-Priority Algorithm (Luby) Repeating steps Assign random priorities Add vertices with highest local priority to set Remove their neighbors from graph a b c d e f g Set = {b, e} h i A High-Quality and Fast MIS Algorithm 22

  23. Random-Priority Algorithm (Luby) Repeating steps Assign random priorities Add vertices with highest local priority to set Remove their neighbors from graph a b c9 d e f g Set = {b, e} h5 i6 A High-Quality and Fast MIS Algorithm 23

  24. Random-Priority Algorithm (Luby) Repeating steps Assign random priorities Add vertices with highest local priority to set Remove their neighbors from graph a b c9 d e f g Set = {b, c, e, i} h5 i6 A High-Quality and Fast MIS Algorithm 24

  25. Random-Priority Algorithm (Luby) Repeating steps Assign random priorities Add vertices with highest local priority to set Remove their neighbors from graph a b c d e f g MIS = {b, c, e, i} h i A High-Quality and Fast MIS Algorithm 25

  26. Random-Permutation Parallel MIS Algorithm A High-Quality and Fast MIS Algorithm 26

  27. Random-Permutation Algorithm Initialization Assign random priorities Repeating steps Add vertices with highest local priority to set Remove neighbors and their edges from graph a b c d e f g h i Set = {} A High-Quality and Fast MIS Algorithm 27

  28. Random-Permutation Algorithm Initialization Assign random priorities Repeating steps Add vertices with highest local priority to set Remove neighbors and their edges from graph a5 b7 c1 d4 e6 f3 g4 h3 i2 Set = {} A High-Quality and Fast MIS Algorithm 28

  29. Random-Permutation Algorithm Initialization Assign random priorities Repeating steps Add vertices with highest local priority to set Remove neighbors and their edges from graph a5 b7 c1 d4 e6 f3 g4 h3 i2 Set = {b, e} A High-Quality and Fast MIS Algorithm 29

  30. Random-Permutation Algorithm Initialization Assign random priorities Repeating steps Add vertices with highest local priority to set Remove neighbors and their edges from graph a5 b7 c1 d4 e6 f3 g4 h3 i2 Set = {b, e} A High-Quality and Fast MIS Algorithm 30

  31. Random-Permutation Algorithm Initialization Assign random priorities Repeating steps Add vertices with highest local priority to set Remove neighbors and their edges from graph a5 b7 c1 d4 e6 f3 g4 h3 i2 Set = {b, c, e, h} A High-Quality and Fast MIS Algorithm 31

  32. Random-Permutation Algorithm Initialization Assign random priorities Repeating steps Add vertices with highest local priority to set Remove neighbors and their edges from graph a5 b7 c1 d4 e6 f3 g4 h3 i2 MIS = {b, c, e, h} A High-Quality and Fast MIS Algorithm 32

  33. Lubys Random-Selection Parallel MIS Algorithm A High-Quality and Fast MIS Algorithm 33

  34. Random-Selection Algorithm (Luby) Repeating steps Mark vertices with probability 0.5/degree Add marked vertices to set if no marked neighbors Remove their neighbors from graph a b c d e f g h i Set = {} A High-Quality and Fast MIS Algorithm 34

  35. Random-Selection Algorithm (Luby) Repeating steps Mark vertices with probability 0.5/degree Add marked vertices to set if no marked neighbors Remove their neighbors from graph ao bi co di eo fo go hi ii Set = {} A High-Quality and Fast MIS Algorithm 35

  36. Random-Selection Algorithm (Luby) Repeating steps Mark vertices with probability 0.5/degree Add marked vertices to set if no marked neighbors Remove their neighbors from graph ao bi co di eo fo go hi ii Set = {b, d} A High-Quality and Fast MIS Algorithm 36

  37. Random-Selection Algorithm (Luby) Repeating steps Mark vertices with probability 0.5/degree(v) Add marked vertices to set if no marked neighbors Remove their neighbors from graph a b c d e f g h i Set = {b, d} A High-Quality and Fast MIS Algorithm 37

  38. Random-Selection Algorithm (Luby) Repeating steps Mark vertices with probability 0.5/degree Add marked vertices to set if no marked neighbors Remove their neighbors from graph a b ci d e fi g ho ii Set = {b, d} A High-Quality and Fast MIS Algorithm 38

  39. Random-Selection Algorithm (Luby) Repeating steps Mark vertices with probability 0.5/degree Add marked vertices to set if no marked neighbors Remove their neighbors from graph a b ci d e fi g ho ii Set = {b, c, d, f, i} A High-Quality and Fast MIS Algorithm 39

  40. Random-Selection Algorithm (Luby) Repeating steps Mark vertices with probability 0.5/degree Add marked vertices to set if no marked neighbors Remove their neighbors from graph a b c d e f g h i MIS = {b, c, d, f, i} A High-Quality and Fast MIS Algorithm 40

  41. ECL-MIS Our Permutation-Selection Parallel MIS Algorithm A High-Quality and Fast MIS Algorithm 41

  42. Our Permutation-Selection Algorithm Initialization Assign priorities ~ 1/deg Randomize within level Repeating steps Add vertices with highest local priority to set Remove their neighbors from graph a b c d e f g h i Set = {} A High-Quality and Fast MIS Algorithm 42

  43. Our Permutation-Selection Algorithm Initialization Assign priorities ~ 1/deg Randomize within level Repeating steps Add vertices with highest local priority to set Remove their neighbors from graph a65 b87 c82 d76 e74 f73 g35 h89 i81 Set = {} A High-Quality and Fast MIS Algorithm 43

  44. Our Permutation-Selection Algorithm Initialization Assign priorities ~ 1/deg Randomize within level Repeating steps Add vertices with highest local priority to set Remove their neighbors from graph a65 b87 c82 d76 e74 f73 g35 h89 i81 Set = {} A High-Quality and Fast MIS Algorithm 44

  45. Our Permutation-Selection Algorithm Initialization Assign priorities ~ 1/deg Randomize within level Repeating steps Add vertices with highest local priority to set Remove their neighbors from graph a65 b87 c82 d76 e74 f73 g35 h89 i81 Set = {b, c, d, h} A High-Quality and Fast MIS Algorithm 45

  46. Our Permutation-Selection Algorithm Initialization Assign priorities ~ 1/deg Randomize within level Repeating steps Add vertices with highest local priority to set Remove their neighbors from graph a65 b87 c82 d76 e74 f73 g35 h89 i81 Set = {b, c, d, h} A High-Quality and Fast MIS Algorithm 46

  47. Our Permutation-Selection Algorithm Initialization Assign priorities ~ 1/deg Randomize within level Repeating steps Add vertices with highest local priority to set Remove their neighbors from graph a65 b87 c82 d76 e74 f73 g35 h89 i81 Set = {b, c, d, f, h} A High-Quality and Fast MIS Algorithm 47

  48. Our Permutation-Selection Algorithm Initialization Assign priorities ~ 1/deg Randomize within level Repeating steps Add vertices with highest local priority to set Remove their neighbors from graph a b c d e f g h i MIS = {b, c, d, f, h} A High-Quality and Fast MIS Algorithm 48

  49. ECL-MIS Features Single initialization Requires less work (faster) Enables asynchronous implementation (faster) Permutation-selection function Boosts set size (higher-quality result) Requires only a few bits (lower memory footprint) Combined priority and status information Reduces storage (lower memory footprint) Minimizes memory accesses (faster) A High-Quality and Fast MIS Algorithm 49

  50. Permutation-Selection Function Requirements Has to work for all graphs Needs to be proportional to 1/degree Do not know highest degree (but know average) Our solution priority(v) = avg_degree / (avg_degree + degree*(v)) Degree* includes random fraction (e.g., 3.xyz) Scaled to small integer (e.g., a byte) A High-Quality and Fast MIS Algorithm 50

Related


No related presentations.

More Related Content