DESIGN OF SPACE-OPTIMAL REGULAR ARRAYS FOR ALGORITHMS WITH LINEAR SCHEDULES

Abstract

The problem of designing space-optimal 2D regular arrays for N x N x N cubical mesh algorithms with linear schedule ai + bj + ck, 1 less than or equal to a less than or equal to b less than or equal to c, and N = nc, is studied. Three novel nonlinear processor allocation methods, each of which works by combining a partitioning technique (gcd-partition) with different nonlinear processor allocation procedures (traces), are proposed to handle different cases, In cases where a + b less than or equal to c, which are dealt with by the first processor allocation method, space-optimal designs can always be obtained in which the number of processing elements is equal to N-2/c. For other cases where a + b > c and either a = b and b = c, two other optimal processor allocation methods are proposed. Besides, the closed form expressions for the optimal number of processing elements are derived for these cases.