https://scholars.lib.ntu.edu.tw/handle/123456789/488303
標題: | Two-Dimensional Processor Array with a Reconfigurable Bus System is at Least as Powerful as CRCW Model. | 作者: | Wang, Biing-Feng GEN-HUEY CHEN |
關鍵字: | Computational complexity; CRCW shared-memory computer; MIMD; processor array; reconfigurable bus; SIMD | 公開日期: | 1990 | 卷: | 36 | 期: | 1 | 起(迄)頁: | 31-36 | 來源出版物: | Inf. Process. Lett. | 摘要: | The power of a computation model usually indicates how fast a problem can be solved under that model. The CRCW shared-memory computer has been considered the most powerful computation model. Recently, the two-dimensional processor array with a reconfigurable bus system (such as the reconfigurable mesh and the polymorphic-torus network) has been proposed for solving many problems efficiently. Since the structure of the two-dimensional processor array with a reconfigurable bus system is regular, it is suitable for VLSI implementation. In this paper, we show that the two-dimensional processor array with a reconfigurable bus system is at least as powerful as the CRCW shared-memory computer. To say more concretely, we show that if a problem can be solved in O(f(n)) time on the CRCW shared-memory computer, it can also be solved in O(f(n)) time on the two-dimensional processor array with a reconfigurable bus system. Also, the proof suggests a general method to convert algorithms designed on the former into algorithms on the latter. © 1990. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-0025507830&doi=10.1016%2f0020-0190%2890%2990182-W&partnerID=40&md5=1fbdbbbba3b7cb5faadcb16ae3a883b3 | DOI: | 10.1016/0020-0190(90)90182-W | SDG/關鍵字: | Computer Programming--Algorithms; Concurrent Read Concurrent Write; Reconfigurable Bus; Shared Memory Computers; Computer Systems, Digital |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。