Some Experiments in Local Microcode Compaction for Horizontal Machines
Davidson, Landskov, Shriver et al. · IEEE Transactions on Computers · 1981
Microcode compaction is an essential tool for the compilation of high-level language microprograms into microinstructions with parallel microoperations. The purpose of the research reported in this paper is to compare four microcode compaction methods reported in the literature: first-come first-served, critical path, branch and bound, and list scheduling. In order to do this a complete, machine independent method of representing the microoperations of real machines had to be developed; and the compaction algorithms had to be recast to use this representation. The compaction algorithms were then implemented and tested on microcode produced by a compiler for a high-level microprogramming language. The results of these experiments were that for all cases examined the first-come first-served and list scheduling algorithms produced microcode compacted into a minimal number of microinstructions in time that was a polynomial function of order two of the number of input microoperations.
Cited by 240 works. doi:10.1109/tc.1981.1675826
Authors
References
- A comparison of list schedules for parallel processing systems
- A survey of techniques for recognizing parallel processable streams in computer programs
- Parallel operation in the control data 6600
- Local Microcode Compaction Techniques
- Optimization of horizontal microcode within and beyond basic blocks: an application of processor scheduling with resources
- Methods of compacting microprograms
- A High-Level Language for Horizontal Microprogramming
- Optimization Strategies for Microprograms
- The Identification of Maximal Parallelism in Straight-Line Microprograms
- Microcode compaction