• Login
    View Item 
    •   SMARTech Home
    • College of Computing (CoC)
    • School of Computational Science and Engineering (CSE)
    • School of Computational Science and Engineering Technical Reports
    • View Item
    •   SMARTech Home
    • College of Computing (CoC)
    • School of Computational Science and Engineering (CSE)
    • School of Computational Science and Engineering Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    A Cache-Aware Parallel Implementation of the Push-Relabel Network Flow Algorithm and Experimental Evaluation of the Gap Relabeling Heuristic

    Thumbnail
    View/Open
    GT-CSE-06-05.pdf (202.4Kb)
    Date
    2006-02-25
    Author
    Bader, David A.
    Sachdeva, Vipin
    Metadata
    Show full item record
    Abstract
    The maximum flow problem is a combinatorial problem of significant importance in a wide variety of research and commercial applications. It has been extensively studied and implemented over the past 40 years. The push-relabel method has been shown to be superior to other methods, both in theoretical bounds and in experimental implementations. Our study discusses the implementation of the push-relabel network flow algorithm on present-day symmetric multiprocessors (SMP's) with large shared memories. The maximum flow problem is an irregular graph problem and requires frequent fine-grained locking of edges and vertices. Over a decade ago, Anderson and Setubal implemented Goldberg's push-relabel algorithm for shared memory parallel computers; however, modern systems differ significantly from those targeted by their implementation in that SMP's today have deep memory hierarchies and different performance costs for synchronization and fine-grained locking. Besides our new cache-aware implementation of Goldberg's parallel algorithm for modern shared-memory parallel computers, our main new contribution is the first parallel implementation and analysis of the gap relabeling heuristic that runs from 2.1 to 4.3 times faster for sparse graphs.
    URI
    http://hdl.handle.net/1853/14384
    Collections
    • College of Computing Technical Reports [506]
    • School of Computational Science and Engineering Technical Reports [37]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology