RESOURCE-CONSTRAINED SCHEDULING OF PARTITIONED ALGORITHMS ON PROCESSOR ARRAYS

We deal with the problem of partitioning and mapping uniform loop nest s onto physical processor arrays. Resource constraints are taken into account: not only do we assume a limited number of available processor s, but we also assume that the communication capabilities of the physi cal processors are restricted (in particular, the number of communicat ion links in each direction is bounded). This paper is motivated by th e recent work of Chou and Kung and of Thiele. Our main contributions a re a new formulation of the complex optimization problem to be solved in terms of a single integer linear programming problem, as well as op timal scheduling algorithms and complexity results in the case of Line ar processor arrays.