Development and Analysis of a Global Compaction Technique of Microprograms.

The need for a better microprogramming tool has increased considerably as increased dem and and support of computer technology has brought about wide use of microprograms. The eventual goal of microprogramming tool development would be to make a high level microprogram language and a compiler to generate minimal-execution-time microcode for a variety of machines. In generating minimal-execution-time microcode, one aspect that differentiates microprogramming languages from macroprogramming languages is the need for compaction in highly horizontal microarchitecture. Among the proposed microprogram compaction methods, the trace scheduling is the most general and appears to give the fastest execution of compacted microcode. However, the growth of memory size by extensive copying of blocks can be enormous, exponential in the worst case, and the complicated bookkeeping stage of the trace scheduling has been an obstacle to implementation. A technique called beta compaction, based on trace scheduling, is proposed to mitigate the drawbacks of trace scheduling. Basically, it identifies the junction blocks (the blocks beginning with a join and ending with a conditional branch) as the major source of complication, and cut traces at those junction blocks. It achieves almost all the compaction of the trace scheduling except that which causes copying of blocks. Memory size after the beta compaction is usually smaller than the original. Even when the memory size grows in rare instances, it is bounded by O(n('2)) in the worst case. and the bookkeeping stage is very much simplified. The compacted microcode size variation as the source microcode changes is also very small. A loop-free version of both beta compaction and trace scheduling has been implemented. Comparison between the two was done using artificially synthesized microcodes and the above properties of the beta compaction was confirmed. A simple microprogrammable machine based on AM2900 components was designed and simulated with an interactive user-friendly interface. A realistic application program was written and h and -compiled into microcode. The microcode was executed on the simulator both before and after compaction, which demonstrated the applicability of the compaction technique and the correctness of the implementation.Ph.D.Computer scienceUniversity of Michiganhttp://deepblue.lib.umich.edu/bitstream/2027.42/160360/1/8502866.pd