Pedro Tomás,

R – INESC-ID Lisboa


The increased complexity of Digital Signal Processing (DSP) algorithms demands for the development of more complex and more efficient hardware structures. The work presented describes the core components for the development of a tool capable of automatic generation of efficient hardware structures, therefore facilitating developers work. It comprises algorithms and techniques for i) balancing the paths in a graph, ii) scheduling of operations to functional units, iii) allocating registers and iv) generating the VHDL code. Results show that the developed techniques are capable of generating the hardware structure of typical DSP algorithms represented in data-flow graphs with over 2,000 nodes in around 200 ms, scaling to 80,000 nodes in about 214 s. Within the developed techniques, solving the scheduling problem is one of the most complex tasks: it is a NP-complete problem and directly influences the number of functional units and registers required. Therefore, experimental analysis was made on scheduling algorithms for time-constrained problems. Results show that simple list-based algorithms are more efficient in large problems than more complex algorithms: they run faster and tend to require less functional units.

This talk is a preparation for the defense of the master thesis entitled: “Algorithms and tools for automatic generation of DSP hardware structures”.


Date: 2006-Jan-10     Time: 14:00:00     Room: 336

For more information: