Search

This papcr prcscnts a ncw global schcduling algorithm for automatic synthcsis of spccial-purposc microproccssors. Our goal is to achicvc maximal spccdup and minimal complcxity of thc control hardwarc in thc microprG ccssors. For a structurcd program dcscription, wc proposc scvcral intcrcsting propcrtics conccrning thc movcmcnt of opcrations among thc blocks. Bascd on thcsc propcrtics. a Global As Soon As Possiblc (GASAP) and a Global As Latc As Possihlc (GALAP) arc dcvclopcd to cxplorc thc global mobility of opcrations. Expcrimcnts show that thc proposcd approach achicvcs hcttcr rcsults ovcr thosc by thc cxisting algorithms.

Fisher's trace scheduling procedure for global compaction has proven to be able to produce significant reduction in execution time of compacted microcode, however extra space may be sometimes required during bookkeeping, and the efficacy of compaction of microprogram loop is lower than that of hand compaction. This paper introduces an improved trace scheduling compaction algorithm to mitigate the drawbacks mentioned above. The improved algorithm is based on a modified menu of moving microoperations, an improved trace scheduling algorithm, and a special loop compaction algorithm. Preliminary tests indicate that this global compaction algorithm gives shorter execution time and less space requirement in comparison with Fisher's algorithm.

Compacting microoperations of a microprogram into horizontal microinstructions require an efficient global compaction algorithm. This paper describes a global compaction algorithm which is more practical than some of the existing techniques based on Tree compaction, Trace scheduling and generalized data dependency graph. The algorithm uses a local compaction technique in which the microoperation priority function is dynamically modified.

Microcode compaction is the process of converting essentially vertical microcode into horizontal microcode for a given architecture. The conventional plan calls for a microcode compiler to generate vertical code for a given architecture and then use a compaction system to produce horizontal code, thereby greatly reducing the complexity of horizontal code generation.This paper attempts to extend the existing techniques used to perform the compaction process. Specifically, the procedure presented generalizes the "trace scheduling" method of [Fisher81] by using more global context information in compaction decisions. A number of definitions from classical compaction are generalized to encompass this expanded scope.Further, the paper presents two example classes of problem for which the new method outperforms the trace scheduling technique in terms of the execution time efficiency of the generated code. A number of unresolved questions are noted involving the class of global compaction procedures.