How To Keep the Addresses Short

An algorithm is presented for minimizing the
sum of the lengths of the blocks of coding produced 
by an assembler or compiler when (1) the length of
each computer instruction is assumed to be either 
"long" or "short" ("long," if the memory location addressed
is more than a predetermined distance from 
the current location; "short," otherwise), and (2)
there are blocks of instructions whose beginnings 
(origins) are separated by prespecified amounts. For example,
some computers permit either 8-bit addressing 
(interpreted relative to the location counter) or full
16-bit addressing of all of memory.  When assembling 
or compiling two or more blocks of instructions which
have many mutual references in such a computer, 
there is no simple iterative procedure for keeping
as many of the addresses short as possible.  This 
paper demonstrates that a wide class of problems of
this type can be formulated as covering problems 
solvable by means of elementary arithmetic operations
on the column vectors of a ternary matrix.

CACM May, 1971

Richards, D. L.

addressing, assembler, covering problem, integer
programming, variable-length addressing

4.11 4.12 4.21 5.41

CA710505 JB February 3, 1978  2:40 PM

2194	5	2194
2194	5	2194
2194	5	2194
2858	5	2194
3110	5	2194
2194	6	2194
2194	6	2194
2629	6	2194
2858	6	2194