Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Integer linear programming for microprograms register allocation
Luque E., Ripoll A. Information Processing Letters19 (2):81-85,1984.Type:Article
Date Reviewed: Mar 1 1985

The high cost of main memory access makes the register allocation problem especially important in microprogramming. This paper presents a technique for reducing microprogram run time by inserting main memory loads and stores based on an analysis of the dynamic behavior of the program. The authors present, but do not derive, a formula for time saved by doing a specific sequence of loads and stores, given a set of variables used by the program and a control flow graph of the program. They state that the time saved can be maximized by integer linear programming techniques, using implicit enumeration.

One would have to do considerably more search before deciding to use the techniques outlined in this short paper. First, data on the dynamic performance of a microprogram are often not available. Second, no mention is made of the complexity of the solution to the integer programming problem, very important because of the large control flow graphs produced by a compiler. Therefore, I doubt the practicality of the technique as stated. However, the paper is a contribution to the theory of storage allocation required for microprogramming language compilers.

Reviewer:  S. Davidson Review #: CR108912
Bookmark and Share
 
Optimization (B.1.4 ... )
 
 
Integer Programming (G.1.6 ... )
 
 
Linear Programming (G.1.6 ... )
 
 
Control Structure Performance Analysis And Design Aids (B.1.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Optimization": Date
An algorithm for local compaction of horizontal microprograms
Rao S., Majumdar A. Information Processing Letters 20(1): 29-33, 1985. Type: Article
Sep 1 1985
Algorithms for optimization
Kochenderfer M., Wheeler T., The MIT Press, Cambridge, MA, 2019.  520, Type: Book (978-0-262039-42-0)
Apr 27 2021

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy