A process for the determination of addresses in variable length addressing

ABSTRACT

An algorithm is presented for the assignment of instruction addresses and formats under the following conditions: (1) the length of the instruction varies as a function of the distance of the instruction from its target; (2) there exists an optimality criterion which implies some preferential choices subject to the addressing constraints. This may be, for example, achieving the smallest number of long instructions, in which case the total code length is minimized, or minimizing the assigned address of a specified point in the program. The algorithm is suitable for arbitrary program structure and a choice of optimization criteria.

REFERENCES

• 1: Donald L. Richards, How to keep the addresses short, Communications of the ACM, v.14 n.5, p.346-349, May 1971 [doi>10.1145/362588.362596]
• 2: Frieder, G., and Saal, H.J. On the determination of addresses in variable length addressing. Report 9, IBM Israel Scientific Center, Haifa, Israel, 1974.
• 3: Balas, E., and Padberg, M. On the set covering problem. Op. Res. 20, 6 (June 1972), 1152-1161.
• 4: Ronald D. Koncal , Harvey M. Salkin, Set Covering by an All Integer Algorithm: Computational Experience, Journal of the ACM (JACM), v.20 n.2, p.189-193, April 1973 [doi>10.1145/321752.321753]
• 5: Christofides, N. Zero-one programming using non-binary tree search. Computer J. 14, 4 (Apr. 1971), 418-421.
• 6: Saal, H.J., and Shustek, L.J. On measuring computer systems by microprogramming. State of the Art Report on Microprogramming and System Architecture, INFOTECH, Maidenhead, Berkshire, England, 1975.

INDEX TERMS

Keywords:
assembler, paging, varible length addressing