Read more
Excerpt from The Optimization of Horizontal Microcode Within and Beyond Basic Blocks: An Application of Processor Scheduling With Resources
Microprogram optimization is the rearrangement of micro code written vertically, with one operation issued per step, into legal horizontal microinstructions, in which several Operations are issued each instruction cycle. The rearrange ment is to be done in a way that approximately minimizes the running time of the code.
We identify this problem with the problem of processor scheduling with resource constraints. As a result of this identification, the problem of Optimizing basic blocks of microcode can be seen to be np - complete; however, we are able to use approximate methods for basic blocks which have good records in other, similar, scheduling environments. We use a method of scheduling called priority list scheduling in which the tasks are ordered according to some evaluation function, and then schedules are found by repeated scans of the list. Several evaluation functions are shown to perform very well on large samples of various classes of random data - precedence graphs with characteristics similar to those derived from microprograms. An evaluation function we produced is sensitive to both the data - precedence graph and the resource constraints; it performed best of those tested, though the differences among the four best functions, while statistically significant, were small.
About the Publisher
Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com
This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.
