We are now witnessing a proliferation of integrated circuit solutions to several signal processing and related problems. This has motivated the evolution of High Level Synthesis (HLS) where the objective is to obtain an efficient register-transfer level (RTL) realization of a target system from its behavioural specification. An important aspect of HLS is the Data Path Synthesis (DPS) problem, which concerns the construction of optimal data paths of the target system. In this work we examine the complexity of several DPS problems and propose solutions to them. The overall objectives of this work are characterization of the complexity of the synthesis problem and proposing solutions to major tasks involved in DPS. We have, in general, considered the hardness of the problem in question and also the hardness of its approximation schemes. We have found that several interconnect optimization problems, like port assignment of multi-port memories, register-interconnect optimization and allocation and binding, are NP-hard and their relative approximations are also NP-hard. A few scheduling problems, on the other hand, can be solved optimally in polynomial time. List scheduling sometimes guarantees a 2-approximate solution under some conditions. A number of scheduling problems and their constant approximations are also NP-hard. To the best of our knowledge the complexity of relative approximation of many scheduling problems, of interest in DPS, is open.
We have proposed solutions to some individual interconnection oriented sub-problems of data path synthesis and solution to the entire DPS problem. We have made use of heuristic techniques, controlled search and genetic algorithms as problem solving tools. The individual sub-problems are register-interconnect optimization (RIO), memory-interconnect optimization (MIO) and port assignment (PA) of dual and triple port memories. For RIO and MIO we use heuristic techniques, whereas the PA problems are solved using genetic algorithms. For the entire DPS problem we have adopted an approach based on a design space exploration (DSE). Instead of finding a single design from a given behavioural specification, we seek to find a set of competitive designs which satisfy the specification. We have proposed a two phase solution to the entire synthesis problem. In the first phase we find a set of competitive schedules through design space exploration, based on controlled search and heuristic methods. We have also developed a genetic list scheduling technique to work with our DSE technique. In the second phase we find the data paths for each of these schedules through allocation and binding using a genetic algorithm approach.
Keywords: VLSI Design, Data Path Synthesis, Algorithms, Complexity Analysis, Genetic Algorithms, Design Space Exploration, Interconnect Optimization, Memory, Port Assignment.