TITLE

A Decomposition Algorithm for the All-Pairs Shortest Path Problem on Massively Parallel Computer Architectures

AUTHOR(S)
Habbal, Mayiz B.; Koutsopoulos, Haris N.; Lerman, Steven R.
PUB. DATE
November 1994
SOURCE
Transportation Science;Nov94, Vol. 28 Issue 4, p273
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
Network optimization on parallel computer architectures has attracted significant interest in recent years. In this paper, we examine the solution of the shortest path problem on massively parallel architectures. We propose a network decomposition strategy that is amenable to parallel implementation and suggest efficient data structures and mappings of the data to the processors that facilitate the solution of the problem. We discuss computational results for the solution of networks of various sizes on the Connection Machine CM-2¹ (a representative massively parallel architecture) and compare the performance of the algorithm to the performance of serial algorithms implemented on the CRAY X-MP² supercomputer and VAXstation 3100.³ We also present an "idealized" analysis of the algorithm and draw conclusions on properties of decomposition strategies that optimize its performance.
ACCESSION #
4454295

 

Related Articles

  • MONTGOMERY AND RNS FOR RSA HARDWARE IMPLEMENTATION. MANOCHEHRI, Kooroush; POURMOZAFARI, SAADAT; SADEGHIAN, Babak // Computing & Informatics;2010, Vol. 29 Issue 5, p849 

    There are many architectures for RSA hardware implementation which improve its performance. Two main methods for this purpose are Montgomery and RNS. These are fast methods to convert plaintext to ciphertext in RSA algorithm with hardware implementation. RNS is faster than Montgomery but it uses...

  • Practical Considerations for Wireless Sensor Network Algorithms. Halkes, Gertjan; Langendoen, Koen // Wireless Sensor Network;Jun2010, Vol. 2 Issue 6, p441 

    Many researchers from different backgrounds have found interesting research challenges that arise from the physical constraints and envisaged applications in Wireless Sensor Networks (WSNs). The WSN community that has formed over the years is divided into two sub-communities: the systems...

  • Missing Data Estimation using Principle Component Analysis and Autoassociative Neural Networks. Mistry, Jaisheel; Nelwamondo, Fulufhelo V.; Marwala, Tshilidzi // Journal of Systemics, Cybernetics & Informatics;2009, Vol. 7 Issue 3, p72 

    Three new methods are used for estimating missing data in a database using Neural Networks, Principal Component Analysis and Genetic Algorithms are presented. The proposed methods are tested on a set of data obtained from the South African Antenatal Survey. The data is a collection of...

  • Architecture.  // Network Dictionary;2007, p41 

    A definition of the term "Architecture" is presented. In the context of networking, it refers to the overall structure, topology, protocols and framework of a network. Based on the entry, the architecture of the network affects the capabilities and limitations of the network.

  • Security Analysis and Modelling Framework for Critical Infrastructure Systems. Pye, Graeme; Warren, Matthew // Proceedings of the European Conference on Information Warfare & ;2009, p198 

    The provision and delivery of many of the services that modern society enjoys are the result of ubiquitous critical infrastructure systems that permeate across many sectors of the Australian community. Moreover, the integration of technological enhancements and networking interconnections...

  • Comparison study between IPV4 & IPV6. Ali, Amer Nizar Abu // International Journal of Computer Science Issues (IJCSI);May2012, Vol. 9 Issue 3, p314 

    Nowadays IPv6 over IPv4 tunnels are widely used to form the global IPv6 Internet. This paper demonstrates the two tunnels and show when to immigrate from IPv4 to IPV6.Then the risks of immigration are discussed,

  • SOA's Tipping Point. McKean, Kevin // InfoWorld;3/7/2005, Vol. 27 Issue 10, p4 

    This article suggests that service-oriented architecture (SOA) may be the next big trend in information technology (IT) as of march 2005. A search of LexisNexis shows only three such mentions from 1999, but 67 in 2001, and more than 3,000 last year--a proverbial hockey stick growth. To learn...

  • Never-Say-Die Network Services. Venezia, Paul // InfoWorld;6/6/2005, Vol. 27 Issue 23, p26 

    Evaluates the Infoblox-100 DNS and DHCP network device available in the U.S. Key features; Advantages and disadvantages; Cost.

  • Virtual Subnet.  // Network Dictionary;2007, p516 

    A definition of the term "Virtual Subnet" is presented. It refers to a logical grouping of devices that share a common Layer 3 subnet.

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics