DOC PREVIEW
UW-Madison ECE 734 - Digital Filter Design Space Exploration Tools

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1. Introduction2. Features Implemented2.1 Visualization2.2 High Level Input Format2.3 Critical Path Calculation2.4 Iteration Bound Calculation2.5 Retiming2.5.1 Retiming Algorithm for Clock Period Minimization2.5.2 Retiming Algorithm for Register Minimization2.5.3 A Design Example2.6 Unfolding2.7 Folding2.7.1 The Implemented Folding Algorithm2.7.2 A Design Example3. Future Work4. Conclusion5. Acknowledgement6. ReferencesDigital Filter Design Space Exploration ToolsEric Hill & Lixin SuECE 734: Professor HuMay 13, 2004Digital Filter Design Space Exploration ToolsEric Hill & Lixin SuECE 734 Final Project Report1. IntroductionOur choice of topic for this course project was primarily motivated by two factors. First,over the course of this semester we have learned about numerous differenttransformations that can be applied to FIR and IIR filters. The majority of thesetransformations (unfolding, retiming, lookahead, etc…) are used to accomplish differentgoals. These goals include shorter sample periods, low power consumption, and lowhardware cost. Additionally, all of these goals are in general interdependent on oneanother. Consequently, a large design space exists, and automatic design tools are neededto efficiently develop digital filters.The second reason we chose this particular project concerns the representations of filtersused by existing design tools. The majority of current design tools perform optimizationson dependence graph (DG) representations of FIR and IIR filters. These DGs aretypically modeled using matrix-based representations. While matrix-based forms areconvenient for performing transformations, they are a very cumbersome input format. Ahigh level input format for these filters, such as an equation-oriented or high levelprogramming language representation would make these tools more accessible to a largergroup of people.With these factors in mind, we decided to implement a design toolkit which wouldaddress some of the aforementioned issues. At the outset of this project, we had severalgeneral goals in mind. First, we wanted this toolkit to enable rapid tradeoff analysis, thuslowering total design time. Also, we wanted our toolkit to have an open-ended design, sothat new features could be easily added. In addition, we were particularly concernedabout the usability of our tool. In order to make this tool as user-friendly as possible, wewanted as high level an input format as possible. Also, we believed a graphicalrepresentation of the intermediate and final filter designs would be very beneficial.2. Features Implemented2.1 VisualizationIn order to improve the usability of our tool, we utilized existing graph drawing softwarein order to produce visual representations of filter designs. The Graphviz softwarepackage, developed by AT&T Research Laboratories was used to obtain these visualrepresentations [2]. Given a sequence of edges, this package produces a visualembedding of the described graph. Graphviz uses several graph layout algorithms whosegoal is to produce visual representations which are humanly readable. Figure 1 shows anexample of a graph pictured in our textbook along with the visual representation given byGraphviz.Figure 1. Graph Representation.While the nodes in the representation generated by Graphviz are not in the exact samespots as the graph from the textbook, it is relatively easy to verify that the graphs areidentical. In order to use this graph drawing software, our tool generates output files in aformat readable by Graphviz.2.2 High Level Input FormatOne of our initial goals at the outset of this project was to have a high level format thatmade this tool accessible to a wide range of users. While this tool was primarilydebugged using hand generated adjacency matrices as input, support for an equation-based format was also developed. Since this tool is used for optimization rather thansimulation of filters, the delays associated with filter coefficients are more important thanthe actual coefficient values. Given a set of filter coefficients and their associated delays,our tool automatically generates a corresponding DG representation. Figure 2 shows anx+ x+dd2dexample of this process for an FIR filter. While the resulting filter is far from optimized,it represents a valid starting point from which repeated transformations may be applied.Figure 2. Automatic DG Synthesis.2.3 Critical Path CalculationThe critical path is an important design parameter for both FIR and IIR filterimplementations. In order to calculate critical paths, exhaustive search methods wereused. The approach we used to do this was to calculate the longest zero-delay pathbetween every possible pair of nodes, and keep the absolute longest path as the criticalpath. This algorithm has )(2nO computational complexity, where n is the number ofnodes in the DG. For a digital filter, n is typically small, so the efficiency of thealgorithm is not of paramount concern.2.4 Iteration Bound CalculationThe iteration bound is an important optimization parameter for IIR filter design. It has afundamental limit on how fast the IIR filter can run. Our software provides twoalgorithms to calculate the iteration bound. Both algorithms rely on loop detection andthe calculation of the ratio between the loop computation time and the number of delaysfor each loop. The largest ratio is the iteration bound of the IIR filter. The loop that hasthe largest ratio provides a fundamental limit on the filter performance.The first algorithm to find loops is an exhaustive search. Its computational complexity is)(3nO. The reasoning behind this algorithm is that IIR filters don’t have a large numberof nodes, probably at most tens of nodes. Therefore, the absolute computation time ofthis algorithm is relatively small even though the algorithm itself is not very efficient.The second algorithm we implemented to find loops is Lengauer and Tarjan’s dominatoralgorithm [5]. It is a very popular algorithm in compilers to efficiently identify loopssince it has a low computational complexity of))log(( nnO. To understand thisalgorithm, we need to


View Full Document

UW-Madison ECE 734 - Digital Filter Design Space Exploration Tools

Documents in this Course
Load more
Download Digital Filter Design Space Exploration Tools
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Digital Filter Design Space Exploration Tools and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Digital Filter Design Space Exploration Tools 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?