Author(s)

Tzung-Shi Chen & Jang-Ping Sheu

Abstract

Partitioning and mapping nested loops on multicomputer Tzung-Shi Chen* & Jang-Ping Sheu% ^Department of Information Management, Chang Jung University, Taiwan ^Department of Computer Science and Information Engineering, National Central University, Taiwan Abstract Minimizing interprocessor communication is the key to a parallelized pro- gram running on multicomputers. This paper addresses a compilation tech- nique to achieve the goal of generating an efficient parallelized code with both reducing the incurred communication cost and preserving parallelism. First, we transform a nested loop into a transformed structure with sup- porting an evaluation function to evaluate these transformed structures to obtain a certain parallelized code with less parallel executing time. Next, a mapping strategy is proposed to map the transformed structure onto hy- percubes to be executed in parallel in a way with workload balance and low communication cost over processors. 1 Introduction

Keywords