Effective Partitioning of Static Global Buses for Small Processor Arrays

다국어 초록 (Multilingual 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{\times}m$ with static row/column buses to simulate the mesh of the larger size $n{\times}n$ with reconfigurable row/column buses ($m{\leq}n$). This means that if a problem can be solved in O(T) time by the mesh of size $n{\times}n$ with reconfigurable buses, then the same problem can be solved in O(Tn/m (n/m + log m)) time on the mesh of a smaller size $m{\times}m$ without a reconfigurable function. This time-cost is optimal when the relation $n{\geq}m$ log m holds (e.g., m = $n^{1-\varepsilon}$ for $\varepsilon$ > 0).

참고문헌 (Reference)

1 S. Matsumae, "Tight bounds on the simulation of meshes with dynamically reconfigurable row/column buses by meshes with statically partitioned buses" 66 (66): 1338-1346, 2006

2 S. Matsumae, "Simulation algorithms among enhanced mesh models" E82-D (E82-D): 1324-1337, 1999

3 S. Matsumae, "Simulating a mesh with separable buses" 40 (40): 3706-3714, 1999

4 T. Maeba, "Semigroup computations on a processor array with partitioned buses" J80-A (J80-A): 410-413, 1997

5 S. Matsumae, "Polylogarithmic time simulation of reconfigurable row/column buses by static buses" 2010

6 M. J. Serrano, "Optimal architectures and algorithms for mesh-connected parallel computers with separable row/column buses" 4 (4): 1073-1080, 1993

7 R. Miller, "Meshes with reconfigurable buses" 163-178, 1988

8 Y. Ben-Asher, "Efficient self-simulation algorithms for reconfigurable arrays" 30 (30): 1-22, 1995

9 R. Vaidyanathan, "Dynamic Reconfiguration" Kluwer Academic/Plenum Publishers 2004

10 B. Wang, "Constant time algorithms for the transitive closure and some related graph problems on processor arrays with reconfigurable bus systems" 1 (1): 500-507, 1990

11 V. K. Prasanna-Kumar, "Array processor with multiple broadcasting" 4 : 173-190, 1987

12 T. Maeba, "An influence of propagation delays on the computing performance in a processor array with separable buses" J78-A (J78-A): 523-526, 1995

13 T. Maeba, "Algorithms for finding maximum and selecting median on a processor array with separable global buses" J72-A (J72-A): 950-958, 1989