EFFICIENT PROCESSOR ASSIGNMENT ALGORITHMS AND LOOP TRANSFORMATIONS FOR EXECUTING NESTED PARALLEL LOOPS ON MULTIPROCESSORS

An important issue for the efficient use of multiprocessor systems is the assignment of parallel processors to nested parallel loops. It is desirable for a processor assignment algorithm to be fast and always generate an optimal processor assignment. In this paper, we propose two efficient algorithms to decide the optimal number of processors assigned to each individual loop. Efficient parallel counterparts of these two algorithms are also presented. These algorithms not only always generate an optimal processor assignment, but also are much faster than the existing optimal algorithm in the literature. Next, we try to improve the performance of parallel execution by transforming a nested parallel loop into a semantically equivalent one. Three loop transformations are investigated. The effect of these transformations on processor assignment is discussed. Experiments are conducted to show the advantage of applying these transformations. It is observed that, in most cases, the parallel execution time is improved after applying these transformations.