Optimization of a Data Dependence Graph for the Local Microcode Compaction Problem. Part 1: Problem Statement

A traditional approach to solving the problem of local compaction of a horizontal microcode is described. In accordance with this approach any linear segment of the source microcode is made to correspond to a unique data dependence graph. A notion of the data exchange between the microoperations is introduced. Based on this notion, a model is developed that demonstrates that a given linear segment is, generally, associated with a set of semantically equivalent data dependence graphs, which differ from one another by the order of the execution of the exchanges on shared static resources. An optimization combinatorial problem on the permutation of the exchanges of a linear segment is formulated. Conditions for the existence of an admissible solution are studied, and a method for finding it is developed. A new space of solutions for the local compaction problem is obtained through the use of a new data dependence graph, which is, in a sense, better than the original one.