A branching linear programming approach for the mapping of systems of n-dimensional affine recurrences onto k-dimensional systolic arrays

摘要

We propose a method to map algorithms represented by systmes of n-dimensional affine recurrence equations onto k-dimensional systolic arrays (1 <= k <= n). The mapping involves two parts. First, an allocation is chosen which linearly maps the operations of the algorithm onto the processors of a k-dimensional regular and synchronous array. The problem of finding a corresponding optimal or at least "nearly-optimal" affine timing function is tackled by a branching linear programming approach. Second, as the resultant array may exhibit broadcasting of data, the delicate problem of localization of broadcasting is solved by an extension of the branching linear programming approach. A numerical test example shows the applicability to practical examples.