EVOLUTIONARY SYNTHESIS OF COMPLEX DIGITAL CIRCUITS

The research presented in this thesis focuses on the field of evolutionary optimization of complex combinational circuits. The work begins with a study of the existing conventional and nonconventional approaches to the optimization of combinational circuits. Features and issues connected with the internal circuit representations commonly used by present synthesis tools. Boolean networks and their scalability were discussed. Attention was also paid to the evolutionary synthesis, with focus on the CGP (Cartesian Genetic Programming).

A new approach to the evolutionary optimization of combinational circuits was proposed. By extracting a sub-circuit containing a suitable number of gates of the original circuit and by optimizing this sub-circuit by the CGP, it was possible to reduce the number of gates of the circuit significantly more than by optimizing the whole circuit by the CGP. For the extraction phase, three methods were proposed. The first method is based on the cut computing algorithm. This method was able to reduce the number of gates of every benchmark circuit and it overcame the results of the globally working CGP in majority of cases. The second method is based on the windowing algorithm. This allows to expand the sub-circuit selection with the gates in the output direction of the root node of the selection and not only with the gates in its input direction. This method significantly improved the results obtained by using the cut-based method. It also overcame the issue of the cut-based method with selecting the sub-circuit near the primary inputs of the circuit and thus creating a selection too small for a subsequent optimization. The third method is based on the reconvergent-paths selection algorithm. The existence of a reconvergent-path in the sub-circuit increases the probability of presence of don't care nodes and thus the higher efficiency of the optimization. Also, an evolutionary optimization method targeting the non-uniform delay on the sub-circuit's inputs. By using this method, it is possible to extract and optimize a sub-circuit without an influence on the delay of the whole circuit.

By applying the principle of local evolutionary optimization, a significantly better gate reduction of the circuits was achieved then by applying the CGP optimization on whole cir- cuits. However, it is important to choose the sub-circuit's root node carefuly with respect to its position in the circuit. Also, it is necessary to set the parameters of evolution, extraction and the whole optimization process carefully (e.g. the number of gates in each sub-circuit, number of CGP generations and number of sub-circuits that should be optimized).

Evolutionary algorithms, CGP, synthesis, optimization, combinational circuits, delay.