OPTIMUM AND HEURISTIC TRANSFORMATION TECHNIQUES FOR SIMULTANEOUS-OPTIMIZATION OF LATENCY AND THROUGHPUT

Although throughput alone can be arbitrarily improved for several clas ses of systems using previously published techniques, none of those ap proaches are effective when latency constraints, which are increasingl y important in embedded DSP systems, are considered. After formally es tablishing the relationship between latency and throughput in general computation, we explore the effect of pipelining on latency, and estab lish necessary and sufficient conditions under which pipelining does n ot alter latency. Many systems are either linear, or have subsystems t hat are linear. For such cases we have used a state-space based approa ch that treats various transformations in an integrated fashion, and a nswers analytically whether it is possible to simultaneously meet any given combination of constraints on latency and throughput. The analyt ic approach is constructive in nature, and produces a complete impleme ntation when feasibility conditions are fulfilled. We also present a s uboptimal but hardware efficient heuristic approach for the special ca se of initially-relaxed single-input single-output linear time-invaria nt computations. A novel software platform consisting of a high-level synthesis system coupled to a symbolic algebra system was used to impl ement the proposed algorithm transformations. Instead of optimizing to improve throughput and latency, our transformations can also be used to increase the implementation efficiency while achieving the same lat ency and throughput as the original design.