COVERING CONDITIONS AND ALGORITHMS FOR THE SYNTHESIS OF SPEED-INDEPENDENT CIRCUITS

This paper presents theory and algorithms far the synthesis of standar d C-implementations of speed-independent circuits. These implementatio ns are block-level circuits which may consist of atomic gates to perfo rm complex functions in order to ensure hazard freedom. First, we pres ent Boolean covering conditions that guarantee that the standard C-imp lementations operate correctly. Then, we present two algorithms that p roduce optimal solutions to the covering problem. The first algorithm is always applicable, but does not complete on large circuits. The sec ond algorithm, motivated by our observation that our covering problem can often be solved with a single cube, finds the optimal single-cube solution when such a solution exists. When applicable, the second algo rithm is dramatically more efficient than the first, more general algo rithm. We present results for benchmark specifications which indicate that am single-cube algorithm is applicable on most benchmark circuits and reduces rim times by over an order of magnitude. The block-level circuits generated by our algorithms are a good starting paint for too ls that pet-form technology mapping to obtain gate-level speed-indepen dent circuits.