| Popis: |
The problem of designing space-optimal 2D regular arrays for N/spl times/N/spl times/N cubical mesh algorithms with linear schedule ai+bj+ck, 1/spl les/a/spl les/b/spl les/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/spl les/c, which are dealt with by the first processor allocation method, space-optimal designs can always he obtained in which the number of processing elements is equal to N/sup 2c. 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. > |
