Browse Prior Art Database

A Preliminary Evaluation of_ Trace Scheduling for Global Microcode Compaction

IP.com Disclosure Number: IPCOM000128183D
Original Publication Date: 1982-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 3 page(s) / 17K

Publishing Venue

Software Patent Institute

Related People

Ralph Grishman: AUTHOR [+4]

Abstract

Fisher [1] recently described a new, relatively complex procedure for global microcode compaction which he calls "trace scheduling". To evaluate the efficacy of this algorithm, we have implemented it and tested it on several microcode sequences.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 41% of the total text.

Page 1 of 3

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Preliminary Evaluation of_ Trace Scheduling for Global Microcode Compaction

by Ralph Grishman and Su Bogong

May 1982 Report T?o. 043 * on leave from Tsina I?ua University, Beijing Fisher [1] recently described a new, relatively complex procedure for global microcode compaction which he calls "trace scheduling". To evaluate the efficacy of this algorithm, we have implemented it and tested it on several microcode sequences.

* THE PROBLEM

To take advantage of the parallelism inherent in a horizontally microprogrammed machine, it is necessary to convert sequential microcode into equivalent parallel microcode. This task is called microprogram compaction or optimization. Because the task often involes interweaving logically separate code sequences, it is a tedious and error-prone operation. As a result, there has been considerable research over the past few years on automating this process.

Most of this research has focussed on local compaction -- the compaction of individual basic: blocks [2]. However, because basic blocks in microcode are typically rather short, efficiencies approaching those of hand-written microcode can be achieved only by a. procedure which is willing to move micro-operations from one basic block to another -- global compaction.

TRACE SCHEDULING

Earlier procedures for global microcode compaction have been based on a menu of rules for moving micro-operations from one basic block to another [3]. Such procedures can involve extensive tree searches (trying alternative sequences of microcode motions) and hence be very costly.

Fisher has proposed trace scheduling as an alternative approach. In essence, trace scheduling begins by identifying the most frequently traversed path through a section of microcode. A local compaction procedure is applied to this path, scheduling branch micro-operations just like other micro-operations (within data precedence constraints). Because arithmetic micro-operations may be moved relative to branches, a bookkeeping phase is required after compaction to "fix up" the microcode, so that it is equivalent to the original (this primarily involves ' inserting duplicates of moved micro-operations into paths which enter or leave the main path). The procedure -is then repeated on the main path through the code which remains uncompacted. If the code contains loops, the procedure will be first applied recursively to compact each loop.

IMPLEMENTATION

We have implemented most of the procedures described in Fisher [1], including the Schedule and BookkeeD routines, and all of the subroutines they invoke; the extensions needed for scheduling code with loops* and for handling equal edges in the data precedence graph. We

New York University Page 1 Dec 31, 1982

Page 2 of 3

A Preliminary Evaluation of_ Trace Scheduling for Global Microcode Compaction

have not automated the Picctrace algorithm, which selects the next path to schedule; instead, we...