Electrical computers and digital processing systems: processing – Architecture based instruction processing – Stack based computer
Reexamination Certificate
1999-06-28
2001-10-09
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: processing
Architecture based instruction processing
Stack based computer
C712S200000, C712S217000, C712S228000, C712S248000, C712S231000, C711S110000, C711S125000, C711S132000
Reexamination Certificate
active
06301651
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a stack machine, and more particularly, to a method and apparatus for folding a plurality of instructions.
2. Description of the related Art
Please refer to FIG.
1
.
FIG. 1
is a functional block diagram of a stack machine
10
. The prior art of a stack machine is disclosed in Bulman, D. M., “Stack Computers: An Introduction,” IEEE Computer, Vol. 10, No. 5, May 1977, p. 18~28. The prior art of a pipeline machine is disclosed in Harold S. Stone, “High-Performance Computer Architecture,” Addison-Wesley Publishing Company, 1987, p.102~115. We can learn from the related art of the above materials that the modern stack machine
10
could comprise:
an instruction cache
41
for storing a plurality of instructions,
an instruction ring buffer
42
for storing a predetermined number of the instructions,
an operation code checker (sizer)
44
for determining the size of each instruction in the instruction ring buffer
42
based on an operation code, and obtaining indicators of the operation code and operands of the instruction for identifying the operation code and the operands such that indicators of operation codes are 1 and that of operands are 0,
a program controller
60
for controlling access or shift of the instructions stored in the instruction cache
41
or the instruction ring buffer
42
according to the indicators of the instructions generated in the operation code checker
44
,
a decoder
52
for decoding each of the operation codes according to its instruction format, and outputting a control signal
109
for providing an execution unit
54
with an executable function such as addition, subtraction, multiplication, division and shifting,
an address generation unit
55
for generating a source address
105
and a destination address
107
, an executable instruction buffer
58
for storing the source address
105
, the destination address
107
, and the control signal
109
, and
an execution unit
54
for receiving the control signal
109
, source address
105
and destination address
107
from the executable instruction buffer
58
, and executing the control signal
109
such as addition, subtraction, multiplication, division and shifting by reading and storing data through a local variable register
18
, operand stack
12
or constant register
16
according to the source and destination addresses
105
,
107
.
Please refer to FIG.
2
.
FIG. 2
is an operation flow of the stack machine
10
. Instructions can be classified into three basic types by the viewpoint of the present invention. They are producer (P)
14
, operator (O)
20
, and consumer (C)
22
. Assuming three instructions in the sequence of type P, O, C are to be executed and the instruction of type O has to be stored into the operand stack
12
after execution, operations of the three instructions are as follows:
Step 1: accessing data from a source such as the constant register
16
or local variable register
18
and storing it to top of the operand stack (TOS)
12
according to the producer
14
because data are accessed through the operand stack
12
in a first in last out manner;
Step 2: reading the data from the top of the operand stack
12
(TOS);
Step 3: having the execution unit
54
use the operator
20
to execute the data to obtain an executed data;
Step 4: storing the executed data to the top of the operand stack (TOS)
12
;
Step 5: accessing the executed data from the top of the stack (TOS)
12
and storing it to the local variable register
18
according to the consumer
22
.
The above steps show that data have to be accessed through the operand stack
12
. This is called data dependency and it causes the waste of operation time.
A related art method of speeding up operations of instructions is disclosed in U.S. Pat. No. 5,214,763. This method utilizes a super scalar technique to perform operations of instructions by using a plurality of function units. Although the instructions are operated at the same time, the problem of data dependency still persists. Moreover, the use of the function units will make operations of the instructions very complicated.
SUMMARY OF THE INVENTION
It is therefore a primary objective of the present invention to provide a method and an apparatus for folding a plurality of instructions to solve the above mentioned problems.
The apparatus comprises a folding instruction buffer, an operation folder, a folding length checker, a temporary folded instruction buffer, a source address generation unit, and a destination address generation unit.
The folding instruction buffer is used for storing operation codes, operands and their indicators of a predetermined number of instructions to be folded, the indicators are used for identifying the operation codes and the operands such that indicators of operation codes are 1 and that of operands are 0.
The operation folder is used for receiving the operation codes of the instructions, and checking if two consecutive instructions are foldable according to a POC folding rule and a position storage rule by checking if a destination of a preceding instruction and a source of a following instruction are the same, and a destination data length of the preceding instruction and a source data length of the following instruction are the same. If the two consecutive instructions are not foldable, the operation folder will output the operation code, source and destination of the preceding instruction. If the two consecutive instructions are foldable, the operation folder will check POC types of the two instructions according to the POC folding rule so as to generate a folding number signal. The operation folder will also generate a source and a destination of a combined temporary command according to the position storage rule, and select a primary operation code according to the POC types of the instructions and the folding number signal.
The folding length checker is used for receiving the indicators of the operation codes and operands corresponding to the instructions in the folding instruction buffer, and checking the folding number signal transmitted from the operation folder for the number of foldable instructions.
The temporary folded instruction buffer is used for receiving a source, a destination, operands corresponding to the operation codes, and a primary operation code of a folded instruction from the operation folder.
The source address generation unit is used for receiving the source from the temporary folded instruction buffer and a base address corresponding to the source. If the instructions contain operands corresponding to their operation codes, operands corresponding to the source will be combined to form a source address.
The destination address generation unit is used for receiving the destination from the temporary folded instruction buffer and a base address corresponding to the destination. If the instructions contain operands corresponding to their operation codes, operands corresponding to the destination will be combined to form a destination address.
It is an advantage of the present invention that the apparatus can fold a plurality of instructions for enhancing operation efficiency of a stack machine.
REFERENCES:
patent: 6125439 (2000-09-01), Tremblay et al.
patent: 6148391 (2000-11-01), Petrick
patent: 6237086 (2001-05-01), Koppala et al.
Bulman, D.M. “Stack Computers: An Introduction”, IEEE Computer Magazine, vol. 10, No. 5, May 1997, pp. 18-28.
Harold S. Stone, “High-Performance Computer Architecture”, Addison-Wesley Publishing Company, 1987, pp. 102-115.
Chang Lung-Chung
Chung Chung-Ping
Kao Min-Fu
Ton Lee-Ren
Hsu Winston
Industrial Technology Research Institute
Pan Daniel H.
LandOfFree
Method and apparatus for folding a plurality of instructions does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for folding a plurality of instructions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for folding a plurality of instructions will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2602856