Application of genetic algorithm to high-level circuit synthesis

Abstract

Self-recovery Micro-rollback Synthesis (SMS) has currently become an important issue in the high-level circuit synthesis. The problem of SMS combines the problem of functional unit scheduling and assignment with the problem of cheekpoint insertion and microprogram optimization. It has been shown that these problems are NP-complete. The most studied problem is the functional units scheduling and assignment. Several heuristic techniques, including as soon as possible (ASAP), as last as possible (ALAP), integer programming, spring elasticity model, graph-based mobility model, and genetic algorithm, are proposed. However, few studies are on the self-recovery microrollback synthesis and the technique of solution space searching by genetic algorithm is not attempted. In this thesis, we study the feasibility of genetic algorithm to the problem of SMS constrained only on the number of functional units, number of control steps, number of checkpoints and the functional unit areas.