Electrical computers and digital processing systems: processing – Processing control – Processing sequence control
Reexamination Certificate
1998-09-30
2001-07-17
Hjerpe, Richard (Department: 2674)
Electrical computers and digital processing systems: processing
Processing control
Processing sequence control
C712S247000, C712S243000, C712S210000
Reexamination Certificate
active
06263429
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to embedded microprocessors. More particularly, the present invention relates to a microcode based compression technique for use with embedded microprocessors.
BACKGROUND OF THE INVENTION
Today it is quite common for everyday devices and systems to incorporate computer technology. Personal digital assistants, pagers with integrated data and message services, smart phones, television remote controls, automotive engine controllers, and the like all rely upon microprocessors and/or microcontrollers to perform numerous and varied functions. These microprocessors and/or microcontrollers are commonly referred to as embedded processors. In most of these devices, the embedded processor executes a predefined, stored program.
As demands for more powerful, smaller, lighter, less expensive, and/or more energy efficient devices has risen, system designers have been tasked with packing more features into ever smaller components. These features are commonly controlled by a program (an instruction code) contained within an embedded processor. Since the size of the program used in embedded processors has quickly become a significant constraint on the miniaturization of electronic devices, reducing the program size has become a primary goal of system designers. A reduced code size often results in a reduction of a device's cost, size, weight, and/or power consumption. Additionally, as the profit margin on semiconductor devices (“chips”) erodes, designers may be tasked with providing more devices per a given wafer area. Thus, miniaturization is today a primary goal of system designers.
Numerous approaches have been proposed for reducing the length of a program used in an embedded processor. One approach was proposed in 1996 by Peter L. Bird and Trevor N. Mudge in their paper, “An Instruction Stream Compression Technique” (hereafter “Bird and Mudge”). In their approach, Bird and Mudge analyze a program for patterns of frequently used sequences of instructions. This analysis is performed for all sequences within basic instruction blocks. A basic instruction block is a sequence of instructions within a program in which no jumps exist. For purposes of this description, “jumps” in a program shall refer to any deviation in the sequential processing of a sequence of lines of code including branches, conditional branches, sub-routines, and the like. The basic instruction block is always entered at the top of the sequence and exited only at the bottom of the sequence. Since jumps commonly occur in programs, basic instruction blocks may not be prevalent in a given program. Additionally, since basic instruction blocks are often quite short, the number of available patterns in a given program are often reduced. Hence the utility of the Bird and Mudge approach is often quite limited.
Additionally, under the Bird and Mudge approach, after the program is analyzed and patterns of basic instruction blocks identified, those patterns with the highest frequency of occurrence are assigned an opcode and are stored in Read Only Memory (ROM). The opcode is then placed in a directory which identifies the specific location in memory of the associated instruction sequence. The program
100
is then reassembled and consists of original lines of code
110
interleaved with opcodes
112
, as shown in FIG.
1
.
During an instruction fetch cycle, the decoder within a Central Processing Unit (CPU) checks the line of code of the incoming instruction. If no opcode
112
exists, the line of code is an uncompressed instruction which is executed in the regular manner. If an opcode
112
exists, the opcode
112
references the memory location at which the actual code sequence resides. The actual code sequence is then recalled from memory and executed.
In order to keep track of the location of the compressed instructions corresponding to an opcode, Bird and Mudge utilize a look-up table
114
, wherein the opcode
112
identifies the location of the first instruction of the compressed sequence in the look-up table
114
. The look-up table
114
also provides the location in memory
116
of the second instruction (if one should exist) of the compressed sequence and the number of remaining instructions
118
, as shown in FIG.
1
. For example, when the embedded processor encounters opcode three
120
during an instruction processing cycle, the embedded processor proceeds to the opcode three location
122
in the look-up table
114
. The embedded processor executes the first instruction
124
associated with opcode three
120
and then proceeds to the memory location
128
of the second instruction (in this example, memory address 07002). Upon executing a second instruction
129
, the processor proceeds in sequential order through memory
130
until the number of instructions
126
indicated in the look-up table
114
have been executed (in this case four instructions). The processor then resumes normal instruction processing in the original program code (thus, in this example the processor returns to the third instruction
136
).
While the Bird and Mudge approach is effective, it has numerous disadvantages. First, this approach requires that space on the chip be allocated to track the number of instructions associated with an opcode, and the number of instructions executed or which remain to be executed. Thus, some sort of counter must be included in the processor (or the processor's normal routines interrupted to keep track of the instruction count). Additionally, the second table requires the allocation of additional space on the chip. Thus, this approach requires more space, more power, and inhibits miniaturization.
Another disadvantage of the Bird and Mudge approach is that it only works for instruction sequences that are contained within a basic instruction block (i.e., this approach does not work for instruction sequences which contain jumps). Since many programs have numerous jumps and conditional branches, the application of Bird and Mudge is often extremely limited. Additionally, the Bird and Mudge approach can not be used with arguments (wherein an argument is a portion of an instruction which references another value). Designers prefer a sequence of instructions which correspond to a given code word, where the instructions can be parameterized. Ideally, the arguments in a sequence of instructions can be suitably replaced such that the instructions can be flexibly configured to function with specific variables. For example, a sequence of instructions in an aircraft's embedded processor which utilizes the wind speed to determine the desired landing speed is preferably parameterizable such that the value of the wind speed may be suitably inserted into any calculations which require wind speed.
In summary, Bird and Mudge unnecessarily allocates memory to hold the needed tables and does not allow for jumps, parameterization, or the like. Thus, Bird and Mudge do not disclose a desirable approach.
Another approach for reducing the size of the instruction set in embedded processors was proposed in 1997 by Darko Kirovski, Johnson Kin, and William H. Mangione-Smith in their paper, “Procedure Based Program Compression” (hereafter, “KKMS”). In the KKMS approach, the entire program is compressed. At run time, decompression of the entire program is
10
accomplished in real-time, i.e., each procedure is decompressed by the processor as needed. Each procedure is compressed as an entity (including jumps and arguments contained within a given procedure) and stored in a dedicated region of Random Access Memory (RAM). Inter-procedure calls and global references are stored in a software cache which is accessed via a Directory Service. As procedures are needed by the processor for a given operation, the Directory Service is consulted, and a linking tool is utilized to identify the location of the desired procedure and where to return after the procedure has been implemented. The procedure is then called into a pcache (i.e., a cache of volatile memory commonly provided on the p
Conexant Systems Inc.
Hjerpe Richard
Monestine Mackly
Snell & Wilmer L.L.P.
LandOfFree
Dynamic microcode for embedded processors does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic microcode for embedded processors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic microcode for embedded processors will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2504296