Research On High Level Synthesis Method For VLSI

The high-speed and complexity of chip design put forward new challenges to thefundamental theories and design methods of VLSI (Very Large Scale Integration).SoC (system on chip), based onthe technology of VDSM (very deep submicron),nanometer and IP (intelligent property) core reuse, is the main development trend ofVLSI. However it is difficult for traditional design methods to handle such problems.Therefore many new design techniques have emerged, such as efficient high levelsynthesis, verification technology and series of key technologies brought about bynanometer technology. Among them, high level synthesis (HLS) bridges systembehaviors and system architectures. HLS can shorten time of design, layout andverification. There is huge optimization space of power dissipation at the stage ofHLS; however the optimization space of power dissipation is smaller at the stage ofphysical design. Scheduling, allocation and multi-voltages low power design of HLSare studied in this paper. The major contributions are as follows:1) The high level scheduling methods based on the combination of geneticalgorithm and ant algorithm with latency constraints and resource constraints areproposed. After an abundant investigation of the capabilities of genetic algorithm andant algorithm to solve high level scheduling independently, the coding scheme,crosstalk operator, mutation operator, evolution function of genetic algorithm and thepheromone updating rules of ant algorithm are presented. And the dynamic switchingconditions of genetic algorithm and ant algorithm are also explored: when thesub-generation evolution ratio is less than the min sub-generation evolution ratio setbeforehand or the iteration times exceed the given maximum iteration times ofgenetic algorithm, genetic algorithm terminates and switches to ant algorithm. Theinitial pheromone distribution of ant algorithm can be generated by theoptimizational solutions of genetic algorithm, thus many blind searches in the earlystage of ant algorithm for deficiency of pheromone can be avoided, and the algorithmefficiency can also be improved greatly. Experimental results indicate that, the resource constrained scheduling method in this paper can reduce scheduling lengthand the latency constrained scheduling method in this paper can reduce the totalresource numbers, compared with genetic algorithm and ant algorithm.2) A new polynomial model K*TDG is presented after an intensive study on thecharacteristic of complex high level data flow, which is suitable for complex highlevel data flow decomposition and design space exploration. First, the arc weights ofTDG are redefined according to the relationship between the parameters of complexdata flow polynomial. Then two basic operations of K*TDG are discussed: additionand multiplication. The new model K*TDG makes the best of model TDG fully, andovercomes the disadvantages of TDG as well. On this basis, a complex data flowdecomposition method is proposed by applying the Simplify function and Factorfunction in Maple. A cost function regarding area and critical path delay is defined inthis process in order to move the decomposition to a more optimal direction. In orderto reduce the algorithm complexity further, a grouping strategy based on the degreesof component polynomials is proposed. The search space is transformed from thewhole space into the local one that share the same degree with the K*TDG branch ineach iteration. Experimental results indicate that the method in this paper can reducesearch space greatly on the precondition of keeping area and delaying approximateoptimal.3) A high level low power multi-voltages design method based on network flow isdeveloped. A new system power dissipation model isdefined, in which function unitpower, interconnection power and voltages converting power are taken intoconsideration. Single voltage high level synthesis methods run first, and thenmulti-voltages local adjustments are done iteratively on the single voltage high levelsynthesis results. Only when one operation node can be allocated to the componentwhich has the same voltage cluster with its previous operation nodes or successoroperation nodes, can the adjustment be executed. In the following, the network flowsub-graph needed to adjust is extracted from the previous network flow graph andthe min-cost max-flow incremental algorithm is run on it. At last, the topologystructure used in this paper is discussed. A gated filler value computation algorithm is proposed at last to further reduce the power dissipation of spurious switchingactivity. Experimental results indicate that, the interconnection power, voltageconverting power and total power can be optimized greatly by using the methods.