Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Optimal Microcode Address Assignment

IP.com Disclosure Number: IPCOM000037060D
Original Publication Date: 1989-Nov-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 7 page(s) / 167K

Publishing Venue

IBM

Related People

Ditlow, GS: AUTHOR

Abstract

In many VLSI microprocessors, instructions are decoded and then executed under microprogram control. Given Instructions {I0 ,I1 ,..., Im-1 }; Lengths {L0 ,L1 ,..., Lm-1 }of the microprograms for each instruction; A microcode ROS of 2h words; Microcode addresses {A0 ,A1 ,A2 ,..., A h }. the problem is to find an optimal mapping f:{I0 ,I1 ,...Im-1 }T {A0 ,A1 ,.., A h } under the constraints Si Li & 2h each microcode address Ai is used, at most, once; when instruction Ii with length Li maps into address Aj ,then addresses {Aj, Aj+1 ,..., Aj+Li-1 }are reserved for Ii and are not available for assignment to any other instruction.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 49% of the total text.

Page 1 of 7

Optimal Microcode Address Assignment

In many VLSI microprocessors, instructions are decoded and then executed under microprogram control. Given Instructions {I0 ,I1 ,..., Im-1 };

Lengths {L0 ,L1 ,..., Lm-1 }of the microprograms

for each instruction;

A microcode ROS of 2h words;

Microcode addresses {A0 ,A1 ,A2 ,..., A h }.

the problem is to find an optimal mapping

f:{I0 ,I1 ,...Im-1 }T {A0 ,A1 ,.., A h }

under the constraints

Si Li & 2h

each microcode address Ai is used, at most, once;

when instruction Ii with length Li maps into

address Aj ,then addresses {Aj, Aj+1 ,..., Aj+Li-1

}are reserved for Ii and are not available for

assignment to any other instruction.

An algorithm is presented for optimally mapping an instruction Ii into microcode addresses Aj . When the realization is a PLA, an optimal mapping is one which minimizes the delay through the PLA.

INSTRUCTION MAPPING: Instruction decode is conveniently represented in tabular PLA form. The inputs of the PLA are opcodes {Op0 ,Op1 ,Op2 ,...} and control signals {C0 ,C1 ,C2 ,...}. The rows of the PLA are product terms {P0 ,P1 ,P2 ,...}. A product term Pi is the conjunction of a subset of the true and complement of the input signals {Op "- ,Op, C - ,C}. The outputs are the addresses Ai ,each of which in binary form is h bits wide.

An instruction Ii consists of a set of product terms. Since each instruction maps into a single address Aj ,the mapping from product terms to addresses is not unique, i.e., several product terms can map into the same address. DELAY CONSIDERATIONS

The delay through a PLA consists of three parts: (1) decoder delay, (2) AND- array delay, and (3) OR-array delay. Of these, the delay through the OR-array is the largest. The OR-array comprises the addresses Ai . The jth bit in the binary expansion of Ai is defined as Aij . When Aij = 1, a pulldown device exists in the jth column of the OR-array. The major contribution to the OR-array delay is the device delay because of the large diffusion device capacitance.

Under these assumptions, each (Aij = 1) is modeled as 1-unit of delay. The problem then is to minimize the number of 1's in the OR-array such that the maximum number of 1's in any column is minimized. M = max{S i Aij

minimize M by finding an optimal mapping

f:{I0 I1 ,...Im-1} T {A0, A1, ...A h }

2 -1

1

Page 2 of 7

From a microcode point of view, this means assign instructions Ii to microcode addresses Aj so that the delay through the PLA OR-array is minimized.

ALGORITHM: Address Sets: Assume the microcode is implemented in a ROS with 2h words. The microcode addresses with exactly one 1-bit in the binary expansion is the ordered set a1 = {A1, A2, A4, ...}. Similarly, a2 are those addresses with exactly two 1-bits in them, i.e., a2 = {A3, A5, A6, ...}. In general, ai = {Aj ¯ i = S(1's Aj}. Note that a0 = {A0 }is not used since this location is typically a reserved location. Address Ordering

To minimize the number of 1-bits when assigning instruction Ii to a...