.png){kind=icon}
.png){kind=icon}
Return
Constant time graph algorithms on the reconfigurable multiple bus machine
.png){kind=icon}
PRE
AI
DOI：10.1006/jpdc.1997.1385.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The reconfigurable multiple bus machine (RMBM) is a model of parallel computation based on reconfigurable buses, Unlike other reconfigurable bus-based models such as the reconfigurable mesh (R-Mesh), the RMBM separates the functions of processors and switches, In this paper, we present constant time RMBM algorithms for a number of fundamental graph problems. These algorithms are more efficient, in terms of processors, than corresponding R-Mesh algorithms, Also presented is a novel range reduction technique for a constant time simulation of each step of a Priority CRCW RMBM on a Common or Collision CRCW RMBM, This simulation incurs only a factor of O(P-epsilon) increase in the number of processors and buses, where epsilon > 0 is any constant and P is the number of processors in the simulated Priority CRCW RMBM, This method may be of independent interest. The algorithms presented in this paper demonstrate the potential for fast and processor-efficient computation available in the ability of a reconfigurable bus-based model to separate the functions of processors and switches. (C) 1991 Academic Press.
Keywords:
ARRAYS
SIMULATION
MESHES
POWER
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K
Organization
No organization information available