• 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.

    Designing Irregular Parallel Algorithms With Mutual Exclusion and Lock-free Protocols

    Thumbnail
    View/Open
    GT-CSE-06-02.pdf (860.4Kb)
    Date
    2006-02-25
    Author
    Cong, Guojing
    Bader, David A.
    Metadata
    Show full item record
    Abstract
    Irregular parallel algorithms pose a significant challenge for achieving high performance because of the difficulty predicting memory access patterns or execution paths. Within an irregular application, fine-grained synchronization is one technique for managing the coordination of work; but in practice the actual performance for irregular problems depends on the input, the access pattern to shared data structures, the relative speed of processors, and the hardware support of synchronization primitives. In this paper, we focus on lock-free and mutual exclusion protocols for handling fine- grained synchronization. Mutual exclusion and lock-free protocols have received a fair amount of attention in coordinating accesses to shared data structures from concurrent processes. Mutual exclusion offers a simple programming abstraction, while lock-free data structures provide better fault tolerance and eliminate problems associated with critical sections such as priority inversion and deadlock. These synchronization protocols, however, are seldom used in parallel algorithm designs, especially for algorithms under the SPMD paradigm, as their implementations are highly hardware dependent and their costs are hard to characterize. Using graph-theoretic algorithms for illustrative purposes, we show experimental results on two shared-memory multiprocessors, the IBM pSeries 570 and the Sun Enterprise 4500, that irregular parallel algorithms with efficient fine-grained synchronization may yield good performance.
    URI
    http://hdl.handle.net/1853/14378
    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