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

    On the Architectural Requirements for Efficient Execution of Graph Algorithms

    Thumbnail
    View/Open
    GT-CSE-06-04.pdf (409.6Kb)
    Date
    2006-02-25
    Author
    Bader, David A.
    Cong, Guojing
    Metadata
    Show full item record
    Abstract
    Combinatorial problems such as those from graph theory pose serious challenges for parallel machines due to non-contiguous, concurrent accesses to global data structures with low degrees of locality. The hierarchical memory systems of symmetric multiprocessor (SMP) clusters optimize for local, contiguous memory accesses, and so are inefficient platforms for such algorithms. Few parallel graph algorithms outperform their best sequential implementation on SMP clusters due to long memory latencies and high synchronization costs. In this paper, we consider the performance and scalability of two graph algorithms, list ranking and connected components, on two classes of shared-memory computers: symmetric multiprocessors such as the Sun Enterprise servers and multithreaded architectures (MTA) such as the Cray MTA-2. While previous studies have shown that parallel graph algorithms can speedup on SMPs, the systems' reliance on cache microprocessors limits performance. The MTA's latency tolerant processors and hardware support for fine-grain synchronization makes performance a function of parallelism. Since parallel graph algorithms have an abundance of parallelism, they perform and scale significantly better on the MTA. We describe and give a performance model for each architecture. We analyze the performance of the two algorithms and discuss how the features of each architecture affects algorithm development, ease of programming, performance, and scalability.
    URI
    http://hdl.handle.net/1853/14383
    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