[Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14]

Journal of Inforamtion Science and Engineering, Vol.14 No.1, pp.53-78 (March 1998)
Compiler Techniques for Minimizing Link Contention
of Linear-Constant Communication on k-ary n-cubes+

Chien-Min Wang, Yomin Hou* and Chiu-Yu Ku
Institute of Information Science
Academia Sinica
Taipei, Taiwan 115, R.O.C.
* Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.

In this paper, we address the problem of minimizing link contention of linear-constant communication on wormhole-routed k-ary n-cubes. Our research reveals that, for dimension-ordered routing algorithms, the degree of link contention of a linear-constant communication can be quite large. To solve this problem, we propose an alternative approach which applies processor mapping at compile-time. In the compiler approach, the communications to be performed in a parallel program can be detected by compilers automatically or can be specified by programmers. According to the given communications, processors are logically rearranged so that the new communications can be efficiently realized on the k-ary n-cube network. It is proved that, for any set of m linear-constant communications, m k - 1, there exists a processor mapping such that the new communications have minimum link contention. Several computer simulations have been conducted, and the results clearly show the advantage of the proposed approach.

Keywords: k-ary n-cubes, linear-constant communication, link contention, processor mapping, wormhole routing

Received July 11, 1997; revised December 10, 1997.
Comunicated by PeiZong Lee.
+ This work was supported by National Science Concil, Republic of China, Under Graml NSC86-2213-E-001-006.