Sparse Data Structures for Weighted Bipartite Matching

50 %
50 %
Information about Sparse Data Structures for Weighted Bipartite Matching
Technology

Published on November 1, 2008

Author: jasonriedy

Source: slideshare.net

Description

A stab at optimizing the inner loop for auctiion-based, sparse bipartite matching.

Sparse Data Structures for Weighted Bipartite Matching E. Jason Riedy Dr. James Demmel (. . . and thanks to the BeBOP group) SIAM Workshop on Combinatorial Scientific Computing 2004

Use Sparse Matrix Optimizations... Take a fixed, simple algorithm: Auction alg. for matchings Repeated iterations over a sparse graph. What’s expensive, and is there anything we can do about it? Take an idea from optimizing sparse matrix-vector products. A little speed-up in some cases, but there are more ideas available...

Where’s the Time Going? Auction algorithm: Iterative, greedy algorithm bipartite matching: 1. An unmatched row i finds a “most profitable” column j π(i) = maxj b(i, j) − p(i) 2. Row i places a bid for column j. Bid price raised until j is no longer the best choice. (Min. increment µ) 3. Highest bid gets the matching (i, j).

Time linear in entries examined... Number of entries examined is problem-dependent. 4.5 4 3.5 3 time (s) 2.5 2 1.5 1 0.5 0 0 5e+06 1e+07 1.5e+07 2e+07 2.5e+07 3e+07 number of entries examined

Expensive Inner Loop! 1.3 GHz Itanium 2 10 8 6 4 2 0 100 150 200 250 300 350 400 450 cycles per entry

Verifying... Using kcachegrind (N.Nethercote and J.Weidendorfer) and valgrind (J. Seward).

And Locating... No obvious culprits in the instructions...

And Locating... But considering cache effects!

Auction’s Inner Loop Price Index Entry value = entry - price save largest...

Auction’s Inner Loop Same accesses as sparse matrix-vector multiplication! Price Index Entry y += a(i,j) * x(j)

Performance Through Blocking? (Images swiped from Berkeley’s BeBOP group.)

Performance Through Blocking? (Images swiped from Berkeley’s BeBOP group.)

Performance Through Blocking? More entries, but 1.5× performance on Pentium 3! (Images swiped from Berkeley’s BeBOP group.)

Blocking Speeds Some Matches Finite element matrix from Vavasis (in UF collection):

Blocking Speeds Some Matches

Blocking Speeds Some Matches

Observations A blocked graph data structure may provide additional performance if: you iterate over whole rows, the graph / matrix has runs of columns, and you’re willing to use an automated tuning system. Maximizing the runs: linear arrangement. Hard, but there may be cheap heuristics. Only worth-while if you’re performing many iterations. (For mat-vec, often > 50 computations of Ax.)

Add a comment

Related presentations

Related pages

Sparse Data Structures for Weighted Bipartite Matching

Sparse Data Structures for Weighted Bipartite Matching E. Jason Riedy∗ Dr. James Demmel UC Berkeley October 31, 2003 1 Introduction Inspired by the ...
Read more

Sparse Data Structures for Weighted Bipartite Matching ...

Sparse Data Structures for Weighted Bipartite Matching E. Jason Riedy∗ Dr. James Demmel UC Berkeley October 31, 2003 1 Introduction Inspired by the ...
Read more

Sparse Data Structures for Weighted Bipartite Matching

Sparse Data Structures for Weighted Bipartite Matching E. Jason Riedy Dr. James Demmel (... and thanks to the BeBOP group) SIAM Workshop on Combinatorial ...
Read more

LNCS 3503 - Fast Algorithms for Weighted Bipartite Matching

Fast Algorithms for Weighted Bipartite Matching ... ings between the two structures, one has to solve a weighted ... This was improved for sparse ...
Read more

Matching (graph theory) - Wikipedia, the free encyclopedia

Finding a maximum bipartite matching ... for sparse graphs, ~ ... A maximum weighted bipartite matching ...
Read more

Weighted Bipartite Matching in Matrix Multiplication Time ...

In this paper we consider the problem of finding maximum weighted matchings in bipartite ... Weighted Bipartite Matching in Matrix ... Data Structures, ...
Read more

Parallel ½-approx Weighted Matching Algorithm

A Parallel ½-approx Weighted Matching Algorithm ... –Nonbipartite / Bipartite –Weighted / Unweighted w S T 3. ... •Vertex-oriented data structures ...
Read more

ALGORITHMS FOR VERTEX-WEIGHTED MATCHING IN GRAPHS

VERTEX-WEIGHTED MATCHING IN GRAPHS ... 2 Power of data structures. ... A bipartite graph G, (b) a matching M
Read more

Vertex-Weighted Matching in Two-Directional Orthogonal Ray ...

Vertex-Weighted Matching in Two-Directional ... rithm for left-weighted convex bipartite matching ... topic of augmented BST data structures, ...
Read more