By adding some functions to memories, highly parallel computation may be realized. We have proposed memory-based parallel computation models, which uses a new functional memory as a SIMD type parallel computation engine. In this paper, we consider models with communication between the words of the functional memory. The memory-based parallel computation model consists of a random access machine and a functional memory. On the functional memory, it is possible to access multiple words in parallel according to the partial match with their memory addresses. The cube-FRAM model, which we propose in this paper, has a hypercube network on the functional memory. We prove that PSPACE is accelerated to polynomial time on the model. We think that the operations on each word of the functional memory are, in a sense, the essential ones for SIMD type parallel computation to realize the computational power.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Yasuhiko TAKENAGA, Shuzo YAJIMA, "Computational Power of Memory-Based Parallel Computation Models with Communication" in IEICE TRANSACTIONS on Information,
vol. E75-D, no. 1, pp. 89-94, January 1992, doi: .
Abstract: By adding some functions to memories, highly parallel computation may be realized. We have proposed memory-based parallel computation models, which uses a new functional memory as a SIMD type parallel computation engine. In this paper, we consider models with communication between the words of the functional memory. The memory-based parallel computation model consists of a random access machine and a functional memory. On the functional memory, it is possible to access multiple words in parallel according to the partial match with their memory addresses. The cube-FRAM model, which we propose in this paper, has a hypercube network on the functional memory. We prove that PSPACE is accelerated to polynomial time on the model. We think that the operations on each word of the functional memory are, in a sense, the essential ones for SIMD type parallel computation to realize the computational power.
URL: https://global.ieice.org/en_transactions/information/10.1587/e75-d_1_89/_p
Copy
@ARTICLE{e75-d_1_89,
author={Yasuhiko TAKENAGA, Shuzo YAJIMA, },
journal={IEICE TRANSACTIONS on Information},
title={Computational Power of Memory-Based Parallel Computation Models with Communication},
year={1992},
volume={E75-D},
number={1},
pages={89-94},
abstract={By adding some functions to memories, highly parallel computation may be realized. We have proposed memory-based parallel computation models, which uses a new functional memory as a SIMD type parallel computation engine. In this paper, we consider models with communication between the words of the functional memory. The memory-based parallel computation model consists of a random access machine and a functional memory. On the functional memory, it is possible to access multiple words in parallel according to the partial match with their memory addresses. The cube-FRAM model, which we propose in this paper, has a hypercube network on the functional memory. We prove that PSPACE is accelerated to polynomial time on the model. We think that the operations on each word of the functional memory are, in a sense, the essential ones for SIMD type parallel computation to realize the computational power.},
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - Computational Power of Memory-Based Parallel Computation Models with Communication
T2 - IEICE TRANSACTIONS on Information
SP - 89
EP - 94
AU - Yasuhiko TAKENAGA
AU - Shuzo YAJIMA
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E75-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 1992
AB - By adding some functions to memories, highly parallel computation may be realized. We have proposed memory-based parallel computation models, which uses a new functional memory as a SIMD type parallel computation engine. In this paper, we consider models with communication between the words of the functional memory. The memory-based parallel computation model consists of a random access machine and a functional memory. On the functional memory, it is possible to access multiple words in parallel according to the partial match with their memory addresses. The cube-FRAM model, which we propose in this paper, has a hypercube network on the functional memory. We prove that PSPACE is accelerated to polynomial time on the model. We think that the operations on each word of the functional memory are, in a sense, the essential ones for SIMD type parallel computation to realize the computational power.
ER -