电子料做女学 University of Electroe Scioncad TechofChina 986 Chapter 2 Iteration Bound Dr.Ling National Key Lab of Science and Technology on Communication
Chapter 2 Iteration Bound Dr. Ling National Key Lab of Science and Technology on Communication
2.1 Introduction /96 What is the maximum sample,operation frequency? The iteration bound is a characteristic of the representation of an algorithm in the form of a data flow graph(DFG); Different representation of the same algorithm may lead to different iteration bounds. It is not possible to achieve an iteration period less than the iteration bound even when infinite processors are available. 2021年2月 2
2021年2月 2 2.1 Introduction What is the maximum sample, operation frequency? The iteration bound is a characteristic of the representation of an algorithm in the form of a data flow graph (DFG); Different representation of the same algorithm may lead to different iteration bounds. It is not possible to achieve an iteration period less than the iteration bound even when infinite processors are available
2.2 Data-flow graph 966 y(n)=ay(n-1)+x(n) (2) Inter-iteration A D x(n) y(n).1 M Intra-iteration (4) Intra-iteration and inter-iteration The precedence constraint is an intra-iteration precedence constraint if the edge has zero delays. The precedence constraint is an inter-iteration precedence constraint if the edge has one or more delays. 2021年2月 3
2021年2月 3 2.2 Data-flow graph y(n) ay(n 1) x(n) X + x(n) y(n) a Z-1 A M D 1 (4) (2) Intra-iteration and inter-iteration The precedence constraint is an intra-iteration precedence constraint if the edge has zero delays. The precedence constraint is an inter-iteration precedence constraint if the edge has one or more delays. Intra-iteration Inter-iteration
Critical path /96 The critical path of a DFG is defined to be the path with the longest computation time among d2 all paths that contain 4 zero delay. d3 The computation time of the critical path is the d4 minimum computation time for one iteration of (2 the DFG. 2021年2月 4
2021年2月 4 Critical path D 1 D D D 3 2 4 5 6 (1) (1) (2) (2) (2) (1) d1 d4 d3 d2 The critical path of a DFG is defined to be the path with the longest computation time among all paths that contain zero delay. The computation time of the critical path is the minimum computation time for one iteration of the DFG
2.3 Loop bound 966 Nonrecursive DFG and recursive DFG Intra-iteration (2) (4) 2D Inter-iteration A0→B0→A1→B1→A2→B2→.. 2021年2月 5
2021年2月 5 2.3 Loop bound Nonrecursive DFG and recursive DFG (2) A B (4) 2D Intra-iteration Inter-iteration A B A B A B 0 0 1 1 2 2 ...