Advanced systolic APP designs

The best area-time tradeoff for solving an instance of the APP of size n seems to be 5n units of time and cells hence the area-time product is 5n. Among the architectures that achieve this tradeoff, the one of Kung-Lo-Lewis [23] has the smallest period P — n (the solution of a new instance of the APP can begin every n steps). Rote [35] has shown that 5n units of time is asymptotically optimal under the hypothesis that no coefficient a(j is duplicated in the array. Note that the architecture of Delosme [14] requires 4n time-steps and 5n /4 cells hence the area-time product is 5n for this architecture, too. 

Benaini, Robert, and Tourancheau [4] showed how to decrease the area-time product by a factor of two they introduce a 2-D toroidal array of only rP/2 processors that can solve any instance of the APP in 5n time-steps. The main 

In latency-limited applications, the important criterion is the execution time T. This is in contrast to the real-time signal and data processing applications, where the period P is more important. Solutions for the latter category are the focus of chapters 5 and 6. In this chapter, the latency-limited case will be addressed. Even though a large part of the underlying theory can be shared, important distinctions will be pointed out. 

Following Cappello [6], we have the following two definitions for space-time minimality  

Definition 3.1 A schedule is time-minimal when the number of time-steps is equal to the length of a longest path in the dependence graph (which is clearly the minimal time needed to achieve the computation). 

---