AN EVOLUTIONARY TECHNIQUE FOR LOCAL MICROCODE COMPACTION

In this paper we present a variant of the simulated evolution techniqu e for local microcode compaction. Simulated evolution is a general opt imization method based on an analogy with the natural selection proces s in biological evolution. The proposed technique combines simulated e volution with list scheduling, in which simulated evolution is used to determine suitable priorities which lead to a good solution by applyi ng list scheduling as a decoding heuristic. The proposed technique is an effective method that yields good results without problem-specific parameter tuning on test problems of very different sizes and structur es. This is achieved by establishing a reasonable balance between expl oration of the search space and exploitation of good solutions round i n an acceptable CPU time. We demonstrate the effectiveness of our tech nique by comparing it with the existing microcode compaction technique s for randomly generated data dependency graphs. The proposed scheme o ffers considerable improvement in the number of microinstructions comp ared with the existing techniques with comparable CPU time.