Performance analysis and hierarchical timing for DSP system synthesis

Improvements in computing resources have raised the possibility of spending significantly larger amounts of time on optimization of architectures and schedules for embedded system design than before. Existing design automation techniques are either deterministic (and hence fail to make use of increased time) or use general randomization techniques that may not be efficient at utilizing the time.; In this thesis, new techniques are proposed to increase the efficiency with which design optimizations can be studied, thus enabling larger portions of design space to be explored.; An adaptive approach to the problem of negative cycle detection in dynamic graphs is proposed. This technique is used to determine whether a given set of timing constraints is feasible. The dynamic nature of the graph often occurs in problems such as scheduling and performance analysis, and using an adaptive approach enables testing of more instances, thus increasing the potential design space coverage.; There are currently no hierarchical techniques to represent timing information in sequential systems. A model based on the concept of timing pairs is introduced and studied, that can compactly represent circuits for the purpose of analyzing their performance within the context of a larger system. An important extension of this model also allows timing representation for multirate systems that allows them to be treated similar to single rate systems for the purpose of performance analysis.; The problem of architecture synthesis requires the generation of both a suitable architecture and appropriate mapping and scheduling information of vertices. Some approaches based on deterministic search as well as evolutionary algorithms are studied for this problem. A new representation of schedules based on combining partial schedules is proposed for evolving building blocks in the system.*; *This dissertation includes a CD that is compound (contains both a paper copy and CD as part of the dissertation). The CD requires the following application: Adobe Acrobat.