Article

Free access

An approach to optimization of horizontal microprograms

Authors:

M. Tsuchiya,

M. J. Gonzalez, Jr.Authors Info & Claims

MICRO 7: Conference record of the 7th annual workshop on Microprogramming

Pages 85 - 90

https://doi.org/10.1145/800118.803846

Published: 30 September 1974 Publication History

PDF eReader

Abstract

Detection of concurrently executable microoperations is an important consideration for effective horizontal microprogramming. Since it is highly machine-dependent and requires knowledge of highly intricate features of a machine, only limited effort has been made so far to derive an algorithm for detection of microprogram parallelism to enable optimization of horizontal microprograms.

In this paper, problems involved in optimization of horizontal microprograms are described. Existing techniques are applied to detect microprogram parallelism in a sequential source microprogram to allow subsequent optimization of the microprogram in a horizontal format. An algorithm for optimization of horizontal microprograms is derived. An upper bound for microprogram execution time is determined. The results derived in this paper are very general so that they are applicable to any machine with a horizontal microinstruction format (including a vertical format which is a special case of a horizontal format). An example is given to illustrate the algorithm.

References

[1]

Schwartz, S. J., "An Algorithm for Minimizing Read Only Memories for Machine Control," 1968 IEEE 10th Annual Symp. on Switching and Automata Theory.

Google Scholar

[2]

Grasseli, A. and Montanari, U., "On the Minimization of Read Only Memories in Microprogrammed Digital Computer," IEEE-TC, Vol. C-19, pp. 1111-1114, November, 1970.

Google Scholar

[3]

Das, S. R., Banerji, D. K., and Chattopadhyay, A., "On Control Memory Minimization in Microprogrammed Digital Computers," IEEE-TC, Vol. C-22, pp. 845-848, September, 1973.

Google Scholar

[4]

Montangero, C., "An Approach to the Optimal Specification of Read-Only Memories in Microprogrammed Digital Computers," IEEE-TC, Vol. C-23, pp. 375-389, April, 1974.

Google Scholar

[5]

Allen, F. E., "Program Optimization," Annual Review in Automatic Programming, Vol. 5, New York: Pergamon, pp. 239-307.

Google Scholar

[6]

Kleir, R. L. and Ramamoorthy, C. V., "Optimization Strategies for Microprograms," IEEE-TC, Vol. C-20, pp. 783-794, July, 1971.

Google Scholar

[7]

Ramamoorthy, C. V. and Tsuchiya, M., "A High-Level Language for Horizontal Microprogramming," IEEE-TC, Vol. C-23, No. 8, August, 1974.

Google Scholar

[8]

Hu, T. C., "Parallel sequencing and assembly line problems," Oper. Res., 9,6, 841-848, November, 1961.

Digital Library

Google Scholar

[9]

Coffman, E. G., Jr. and R. L. Graham, "Optimal Scheduling Strategies for two-processor system," Acta Informatica, 1, 3, pp. 200-213, 1972.

Digital Library

Google Scholar

[10]

Ramamoorthy, C. V., K. M. Chandy, and M. J. Gonzalez, "Optimal scheduling and strategies in a multiprocessor system," IEEE-TC, Vol. C-21, 2, pp. 137-146, February, 1972.

Google Scholar

[11]

Ramamoorthy, C. V. and M. J. Gonzalez, "A survey of techniques for recognizing parallel processable streams in computer programs," Proc. FJCC, 1-15, 1969.

Google Scholar

[12]

Graham, R. L. and M. R. Gorey, "Bounds on scheduling arth limited resources," Fourth Symposium Operating System Principles, 104-111, October, 1973.

Digital Library

Google Scholar

Cited By

View all

Rau BFisher J(1993)Instruction-level parallel processingThe Journal of Supercomputing10.1007/BF012051817:1-2(9-50)Online publication date: 1-May-1993
https://dl.acm.org/doi/10.1007/BF01205181
Das SNayak APapachristou CAllan V(1990)A survey on bit dimension optimization strategies of microprogramsProceedings of the 23rd annual workshop and symposium on Microprogramming and microarchitecture10.5555/255237.255295(281-291)Online publication date: 30-Nov-1990
https://dl.acm.org/doi/10.5555/255237.255295
Das SNayak A(1990)A survey on bit dimension optimization strategies of microprograms[1990] Proceedings of the 23rd Annual Workshop and Symposium@m_MICRO 23: Microprogramming and Microarchitecture10.1109/MICRO.1990.151455(281-291)Online publication date: 1990
https://doi.org/10.1109/MICRO.1990.151455
Show More Cited By

Index Terms

An approach to optimization of horizontal microprograms
1. Hardware
  1. Electronic design automation
    1. Logic synthesis
      1. Circuit optimization
  2. Hardware validation
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

On storage optimization of horizontal microprograms
MICRO 7: Conference record of the 7th annual workshop on Microprogramming

The storage requirement of a horizontal microprogram can be reduced by optimal packing of micro-operations into micro-instructions. The purpose of this paper is to examine micro-instruction generation for horizontally microprogrammable computers in ...
Toward Optimization of Horizontal Microprograms

Detection of concurrently executable microoperations is an important consideration for effective horizontal microprogramming. Since it is highly machine-dependent and requires knowledge of highly intricate features of a machine, only limited effort has ...
Execution time (and memory) optimization in microprograms
MICRO 7: Supplement to the conference record of the 7th annual workshop on Microprogramming

Availability of dynamically writable control memories for microprogramming motivates researchers in the design of appropriate languages. Certain processors allow simultaneous activation of several microoperations. Exploitation of parallelism existing in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

MICRO 7: Conference record of the 7th annual workshop on Microprogramming

September 1974

322 pages

ISBN:9781450374217

DOI:10.1145/800118

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 September 1974

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 484 of 2,242 submissions, 22%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
192
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)7

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Rau BFisher J(1993)Instruction-level parallel processingThe Journal of Supercomputing10.1007/BF012051817:1-2(9-50)Online publication date: 1-May-1993
https://dl.acm.org/doi/10.1007/BF01205181
Das SNayak APapachristou CAllan V(1990)A survey on bit dimension optimization strategies of microprogramsProceedings of the 23rd annual workshop and symposium on Microprogramming and microarchitecture10.5555/255237.255295(281-291)Online publication date: 30-Nov-1990
https://dl.acm.org/doi/10.5555/255237.255295
Das SNayak A(1990)A survey on bit dimension optimization strategies of microprograms[1990] Proceedings of the 23rd Annual Workshop and Symposium@m_MICRO 23: Microprogramming and Microarchitecture10.1109/MICRO.1990.151455(281-291)Online publication date: 1990
https://doi.org/10.1109/MICRO.1990.151455
Bhasker JSamad T(1988)Compacting MIMOLA microcodeACM SIGMICRO Newsletter10.1145/62197.6220619:1-2(40-44)Online publication date: 1-Jun-1988
https://dl.acm.org/doi/10.1145/62197.62206
Bhasker JSamad TJohnson G(1987)Compacting MIMOLA microcodeProceedings of the 20th annual workshop on Microprogramming10.1145/255305.255323(97-105)Online publication date: 1-Dec-1987
https://dl.acm.org/doi/10.1145/255305.255323
Mueller RDuda MO'Haire SCarter MMueller R(1984)A survey of resource allocation methods in optimizing microcode compilersProceedings of the 17th annual workshop on Microprogramming10.1145/800016.808237(285-295)Online publication date: 1-Dec-1984
https://dl.acm.org/doi/10.1145/800016.808237
Atkins RCarter MMueller R(1984)Improved instruction formation in the exhaustive local microcode compaction algorithmProceedings of the 17th annual workshop on Microprogramming10.1145/800016.808220(105-111)Online publication date: 1-Dec-1984
https://dl.acm.org/doi/10.1145/800016.808220
Mueller RDuda MO'Haire S(1984)A survey of resource allocation methods in optimizing microcode compilersACM SIGMICRO Newsletter10.1145/384281.80823715:4(285-295)Online publication date: 1-Dec-1984
https://dl.acm.org/doi/10.1145/384281.808237
Atkins R(1984)Improved instruction formation in the exhaustive local microcode compaction algorithmACM SIGMICRO Newsletter10.1145/384281.80822015:4(105-111)Online publication date: 1-Dec-1984
https://dl.acm.org/doi/10.1145/384281.808220
Henry SMueller RAndrews M(1983)Local and global microcode compaction using reduction operatorsACM SIGMICRO Newsletter10.1145/1096419.109642514:4(34-43)Online publication date: 1-Dec-1983
https://dl.acm.org/doi/10.1145/1096419.1096425
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

On storage optimization of horizontal microprograms

Toward Optimization of Horizontal Microprograms

Execution time (and memory) optimization in microprograms