.png){kind=icon}
返回
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}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
ARRAYS
SIMULATION
MESHES
POWER
期刊
IF:
4
论文数:
3.8K
被引数:
4.8K
机构
暂无机构信息
引用论文
.png){kind=icon}
分享收藏
查看更多内容