Computational Power of Memory-Based Parallel Computation Models with Communication

Yasuhiko TAKENAGA  Shuzo YAJIMA  

IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.1   pp.89-94
Publication Date: 1992/01/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Theoretical Foundations of Computing)
parallel computation model,  computational power,  hypercube network,  functional memory,  memory-based parallel computation,  

Full Text: PDF(534.5KB)>>
Buy this Article

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.