Susumu Matsumae, Journal of Information Processing Systems Vol. 7, No. 1, pp. 85-92, Mar. 2011  

10.3745/JIPS.2011.7.1.085
Keywords: Processor Array, Dynamically Reconfigurable Bus, Statically Partitioned Bus, Scaling-Simulation, Polylogarithmic Time Simulation
Fulltext: PDF

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 = n1-¥å for ¥å> 0).

Statistics
Cite this article