Effective Partitioning of Static Global Buses for Small Processor Arrays
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
This paper shows an effective partitioning of static global row/column buses for tightly coupled 2D mesh-connected small processor arrays (“mesh”, for short). With additional O(n/m (n/m + log m)) time slowdown, it enables the mesh of size m×m with static row/column buses to simulate the mesh of the larger size n×n with reconfigurable row/column buses (m ≤ n). This means that if a problem can be solved in O(T) time by the mesh of size n×n with reconfigurable buses, then the same problem can be solved in O(T n/m (n/m + log m)) time on the mesh of a smaller size m×m without a reconfigurable function. This time-cost is optimal when the relation n ≥ m log m holds (e.g., m = n^(1-ε) for ε > 0).
Abstract
This paper shows an effective partitioning of static global row/column buses for tightly coupled 2D mesh-connected small processor arrays (“mesh”, for short). With additional O(n/m (n/m + log m)) time slowdown, it enables the mesh of size m×m with static row/column buses to simulate the mesh of the larger size n×n with reconfigurable row/column buses (m ≤ n). This means that if a problem can be solved in O(T) time by the mesh of size n×n with reconfigurable buses, then the same problem can be solved in O(T n/m (n/m + log m)) time on the mesh of a smaller size m×m without a reconfigurable function. This time-cost is optimal when the relation n ≥ m log m holds (e.g., m = n^(1-ε) for ε > 0).
참고문헌 (13)
- V. K. Prasanna-Kumar, "Array processor with multiple broadcasting", J. of Parallel Distributed Computing, 4, pp.173~190 (1987)
- T. Maeba, "Semigroup computations on a processor array with partitioned buses", IEICE Trans. A, J80-A(2), pp.410~413 (1997)
- R. Miller, "Meshes with reconfigurable buses", Proc. of the fifth MIT Conference on Advanced Research in VLSI, pp.163~178 (1988)
- B. Wang, "Constant time algorithms for the transitive closure and some related graph problems on processor arrays with reconfigurable bus systems", IEEE Trans. Parallel and Distributed Systems, 1(4), pp.500~507 (1990)
- T. Maeba, "Algorithms for finding maximum and selecting median on a processor array with separable global buses", IEICE Trans. A, J72-A(6), pp.950~958 (1989)
- M. J. Serrano, "Optimal architectures and algorithms for mesh-connected parallel computers with separable row", column buses, 1993, pp.4(10), 1073~1080
- S. Matsumae, "Simulating a mesh with separable buses", Transactions of Information Processing Society of Japan, 40(10), pp.3706~3714 (1999)
- R. Vaidyanathan, "Dynamic Reconfiguration", pp.2004, Kluwer Academic
- T. Maeba, "An influence of propagation delays on the computing performance in a processor array with separable buses", IEICE Trans. A, J78-A(4), pp.523~526 (1995)
- S. Matsumae, "Polylogarithmic time simulation of reconfigurable row", column buses by static buses, 2010, ~
- S. Matsumae, "Tight bounds on the simulation of meshes with dynamically reconfigurable row", column buses by meshes with statically partitioned buses, 2006, pp.66(10), 1338~1346
- Y. Ben-Asher, "Efficient self-simulation algorithms for reconfigurable arrays", J. of Parallel and Distributed Computing, 30(1), pp.1~22 (1995)
- S. Matsumae, "Simulation algorithms among enhanced mesh models", IEICE Transactions on Information and Systems, E82-D(10), pp.1324~1337 (1999)