This paper presents a new algorithm fur exact estimation of the minimum memory size required by programs dealing with array computations. Based on parametric partitioning of the iteration space and Formalized live var...
详细信息
This paper presents a new algorithm fur exact estimation of the minimum memory size required by programs dealing with array computations. Based on parametric partitioning of the iteration space and Formalized live variable analysis, our algorithm transforms the minimum memory size estimation into an equivalent problem: integer point counting fur intersection/union of mappings of parameterized polytopes. A heuristics was then proposed to solve the counting problem. Experimental results show that the algorithm achieves the exactness traditionally associated with totally unrolling loops while exploiting educed computation complexity by preserving the original loop structure.
Using a directed acyclic graph (dag) model of algorithms, we solve a problem related to precedence-constrained multiprocessor schedules for array computations: Given a sequence of dags and linear schedules parametrize...
详细信息
Using a directed acyclic graph (dag) model of algorithms, we solve a problem related to precedence-constrained multiprocessor schedules for array computations: Given a sequence of dags and linear schedules parametrized by n, compute a lower bound on the number of processors required by the schedule as a function of n. In our formulation, the number of tasks that are scheduled for execution during any fixed time step is the number of non-negative integer solutions dn to a set of parametric linear Diophantine equations. We present an algorithm based on generating functions for constructing a formula for these numbers dn. The algorithm has been implemented as a Mathematica program. Example runs and the symbolic formulas for processor lower bounds automatically produced by the algorithm for Matrix-Vector Product, Triangular Matrix Product, and Gaussian Elimination problems are presented. Our approach actually solves the following more general problem: Given an arbitrary r× s integral matrix A and r-dimensiona...
暂无评论