Efficient Parallel Algorithms on the Network Model

Abstract

We develop efficient parallel algorithms for several fundamental problems on the hypercube, the shuffle-exchange, the cube-connected cycles and the butterfly. Those problems are related to load balancing, packet routing list ranking, graph theory and VLSI routing. Load balancing, sorting routing problems have been studied heavily on various parallel models. There are some optimal algorithms for these problems on few networks. We introduce a new simple and efficient algorithm for load balancing on our networks, and show that load balancing requires more time on our bounded-degree networks than on the weak hypercube. Keywords: Integers, Routing, PRAM(Parallel Random Access Machine).

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1990
Accession Number
ADA227144

Entities

People

  • Kwan W. Ryu

Organizations

  • University of Maryland

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Computer Science
  • Computers
  • Computing System Architectures
  • Data Transmission
  • Decomposition
  • Diameters
  • Electrical Engineering
  • Graph Theory
  • Parallel Computing
  • Parallel Processing
  • Theoretical Computer Science
  • Topology
  • Two Dimensional
  • Universities
  • Very Large Scale Integration

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.