1. Introduction2. Fundamental Formulations2.1. Uniform Recurrence Equations2.2. Linear Schedule2.3. Uniform Affine Schedule2.4. Affine Schedule3. Multidimensional Schedule3.1. The Computability of UREs3.2. Calculating Multidimensional Schedule3.3. Multidimensional Affine Schedule4. Scheduling Real Applications4.1. Convolution4.1.1. First Dependence RelationshipLinear and uniform affine schedulingAffine scheduling4.1.2. Another Dependence Relationship4.2. Selection Sort4.2.1. Uniform Affine Schedule4.2.2. Affine Schedule4.2.3. Multi-dimensional Schedule4.3. 2D FIR Filter4.3.1. Affine Schedule4.4. A Complex System of UREs4.4.1. Multidimensional Schedule of URE14.4.2. Multidimensional Affine Schedule of URE15. ConclusionECE 734 Final ProjectOn the Time Scheduling Problem ofUniform Recurrence EquationsChin, Tai-Lin and Lin, Wei-YangMay 14, 2004Content1. INTRODUCTION..........................................................................................................................32. FUNDAMENTAL FORMULATIONS.........................................................................................32.1. UNIFORM RECURRENCE EQUATIONS.......................................................................................32.2. LINEAR SCHEDULE..................................................................................................................42.3. UNIFORM AFFINE SCHEDULE..................................................................................................62.4. AFFINE SCHEDULE..................................................................................................................73. MULTIDIMENSIONAL SCHEDULE.........................................................................................83.1. THE COMPUTABILITY OF URES..............................................................................................83.2. CALCULATING MULTIDIMENSIONAL SCHEDULE...................................................................103.3. MULTIDIMENSIONAL AFFINE SCHEDULE...............................................................................114. SCHEDULING REAL APPLICATIONS..................................................................................134.1. CONVOLUTION......................................................................................................................134.1.1. First Dependence Relationship.......................................................................................144.1.2. Another Dependence Relationship..................................................................................164.2. SELECTION SORT...................................................................................................................184.2.1. Uniform Affine Schedule..................................................................................................184.2.2. Affine Schedule................................................................................................................194.2.3. Multi-dimensional Schedule............................................................................................194.3. 2D FIR FILTER......................................................................................................................214.3.1. Affine Schedule................................................................................................................214.4. A COMPLEX SYSTEM OF URES.............................................................................................224.4.1. Multidimensional Schedule of URE1...............................................................................234.4.2. Multidimensional Affine Schedule of URE1....................................................................265. Conclusion.....................................................................................................................................281. IntroductionTime scheduling is a very important issue on parallel computing applications. Itserves an important role in the design of parallel processor arrays and parallelcompilers. Recently, a large number of applications such as digital signal processing,computer graphics, computer vision, weather forecasting, and virtual reality need highspeed computing capabilities to process their massive computational tasks. As aresult, high performance computing will become one of the most crucial issues ofcomputer technology in the near future. In this report, we focus on the timescheduling problem of Uniform Recurrence Equations[1]. We first study the affineschedule[7] and multidimensional schedule[8], and then, based on these twoscheduling methods, formulate a more efficient scheduling method named multi-dimensional affine schedule to solve more complex systems of uniform recurrenceequations. All these scheduling problems are formulated as linear programs. Finally acomplex example of uniform recurrence equation is illustrated. The quality of thedifferent scheduling methods can be explored.2. Fundamental FormulationsIn this section, we define the Uniform Recurrence Equations and someterminologies. Afterward, we will study three effective time scheduling methodsbased on hyperplanes including linear schedule, uniform affine schedule, and affineschedule.2.1. Uniform Recurrence EquationsMany algorithms are comprised of a set of uniform dependence computationswhich can be arranged on an n dimensional lattice. The data dependencies can berepresented by dependence vectors. If a vector between any two lattice points is equalto one of the dependence vectors, the computations on one of the lattice points woulddepend on the results of the other regardless of the positions of the two lattice pointsin the iteration space. We call this relationship uniform relation. The UniformRecurrence Equations are formally defined as follows.Def 1. Uniform Recurrence Equation(URE)[1]: Zn is all the lattice points in ndimensional space. S is a subset of Zn. Any lattice point in S can berepresented as an n dimensional integer vector. In the space S, we candefine the URE as follows.v p f v p d v p d v p di i i i i i i ik k( ) ( ( ), ( ),..., ( )) 1 1 2 2where i m i i i m pk 1 2 1 21 2, ... ; , ... , ... ; S vi is the data variable where i m1 2,
View Full Document
Unlocking...