Two dimensional processor array with a reconfigurable bus system is at least as powerful as CRCW model

DOI10.1016/0020-0190(90)90182-WzbMath0703.68041MaRDI QIDQ916359

Gen-Huey Chen, Biing-Feng Wang

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexity; processor array; SIMD; reconfigurable bus; CRCW shared-memory computer; MIMD

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D15: Complexity of computation (including implicit computational complexity)

Related Items

Relating the power of the multiple associative computing (MASC) model to that of reconfigurable bus-based models, Simulations between two reconfigurable mesh models, Optimal simulation of multidimensional reconfigurable meshes by two- dimensional reconfigurable meshes, Fast algorithms for lowest common ancestors on a processor array with reconfigurable buses, Simulating the CRCW PRAM on reconfigurable networks, Sorting and computing convex hulls on processor arrays with reconfigurable bus systems, Multiple search problem on reconfigurable meshes, Simulating shared memory in real time: On the computation power of reconfigurable architectures, COLLAPSING THE HIERARCHY OF PARALLEL COMPUTATIONAL MODELS

Cites Work

• Constant time sorting on a processor array with a reconfigurable bus system
• Parallel computation and conflicts in memory access
• Efficient parallel convex hull algorithms
• Ultracomputers
• Bus automata and immediate languages