High speed virtual machine and compiler

Details High speed virtual machine and compiler High speed virtual machine and compiler

2003-03-31

2004-09-28

Chavis, John (Department: 2124)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

Reexamination Certificate

active

06799315

ABSTRACT:

BACKGROUND OF THE INVENTION
(1) Field of the Invention
The present invention relates to virtual machines and to virtual machine compilers. In particular, the invention relates to a technique for increasing the execution speed of virtual machines.
(2) Description of the Prior Art
Standard Virtual Machine
Virtual machines are used to have a same program executed by computers, such as personal computers and workstations, that include different types of CPU. Virtual machines are useful in the field of communications, especially on a network to which different types of computers are connected, since they can overcome the differences in CPU architecture between computers and so allow the efficient and high-speed use of shared resources. Note that in this specification, CPUs are called “real machines”.
A virtual machine is a virtual processor, which is to say, a processor achieved by executing software. A virtual machine decodes and executes executable programs (hereinafter referred to as “virtual machine programs” or “virtual machine instruction sequences”) that are sequences of instructions (hereinafter, “virtual machine instructions”) specific to the virtual machine. Virtual machines are normally realized by programs (hereinafter, “real machine programs” or “real machine instruction sequences” composed of instructions (hereinafter, “real machine instructions”) specific to a target real machine on which the virtual program is to be run. Maintaining a high execution speed is a central issue for virtual machines, so that many virtual machines have a stack architecture.
One example of conventional virtual machines are the JAVA (trademark) virtual machines developed by SUN MICROSYSTEMS, INC.
FIG. 1
is a block diagram showing a construction of a conventional virtual machine
4400
with a stack architecture, such as a JAVA virtual machine. The virtual machine
4400
comprises the instruction storing unit
4401
, the decoding unit
4402
, the executing unit
4410
, and the stack
4420
. The instruction storing unit
4401
stores a virtual machine program to be executed. The decoding unit
4402
reads and decodes a virtual machine instruction. The execution unit
4410
executes operations according to the decoded data produced by the decoding unit
4402
. The stack
4420
, which is a LIFO (last-in first-out) memory area, temporarily stores data used in the processing of the execution unit
4410
. In
FIG. 1
, solid lines show the data flows, while dotted lines show the control flows.
The decoding unit
4402
includes the decode table
4406
, the program counter (PC)
4404
, the instruction reading unit
4403
, and the search unit
4405
. The decode table
4406
stores data, such as jump addresses of microprograms (stored in the executing unit
4410
) that correspond to all of the virtual machine instructions that can be executed by the virtual machine
4400
with a stack architecture. The program counter (PC)
4404
holds the address of the next instruction to be read from the instruction storing unit
4401
. The instruction reading unit
4403
reads this next instruction. The search unit
4405
refers to the decode table
4406
to find a jump address corresponding to the read instruction and outputs the jump address to the execution unit
4410
. In this specification, a microprogram is a real machine program that corresponds to a virtual machine instruction.
The executing unit
4410
includes a microprogram storing unit
4411
and a stack pointer (SP)
4412
. The microprogram storing unit
4411
stores microprograms, which are real machine programs corresponding to virtual machine instructions, in advance at locations indicated by jump addresses. The stack pointer (SP)
4412
indicates the address at the top of the stack
4420
.
FIG. 2
is a table for describing the instruction set of the virtual machine
4400
. In
FIG. 2
, all of the virtual machine instructions that the virtual machine
4400
can decode and execute are shown in mnemonic form, along with the operation content of each instruction, changes in the content of the stack
4420
caused by each instruction, and the value of the SP
4412
after execution. In
FIG. 2
, the legend “s
0
” indicates the value at the top of the stack
4420
, while “s
1
” indicates the second highest value. As one example, the notation “sp←s
0
+s
1
” for the virtual machine instruction “Add” denotes that the value at the top of the stack is set equal to a sum of the top and second highest values of the stack before execution. The notation “sp←sp-
1
” denotes that the height of the stack decreases by one due to the execution of the “Add” instruction.
FIG. 3
shows the stored contents of the decode table
4406
shown in FIG.
1
. This decode table
4406
includes opcodes
4406
a
that indicate the operation types of virtual machine instructions, jump addresses
4406
b
which are the addresses of microprograms in the microprogram storing unit
4411
that correspond to these virtual machine instructions, and numbers of operands
4406
c
that show the number of operands in each virtual machine instruction. Here, each opcode is set as 1-byte long, and operands are counted in one-byte units. Virtual machine instructions, which may include only an opcode or only an operand, that are represented by a physical bit pattern are hereinafter referred to as “virtual machine code”.
FIGS. 4A-4D
show examples of the microprograms stored in the microprogram storing unit
4411
in FIG.
1
. The microprograms in
FIGS. 4A-4C
respectively correspond to the virtual machine instructions “Push”, “Add”, and “Mult”, while the microprogram in
FIG. 4D
shows a microprogram that forms the common latter part of each of the microprograms in
FIGS. 4A-4C
. This microprogram in
FIG. 4D
is a real machine program for jumping to the next virtual machine instruction. The operation contents of the real machine instructions in these microprograms are shown in FIG.
5
. The virtual machine
4400
itself is realized by a real machine that can decode and execute the real machine instructions shown in FIG.
5
. Note that the PC
4404
is physically realized by register #
2
(r
2
) of the real machine, and the SP
4423
by register #
3
(r
3
).
FIG. 6
is a flowchart showing the processing of decoding unit
4404
shown in FIG.
1
. The instruction reading unit
4403
is instructed by the execution unit
4410
via a signal line R to read the next instruction (steps
4502
-
4503
) and so reads the virtual machine instruction with the address stored in the PC
4404
from the instruction storage unit
4401
(steps
4504
-
4505
). Following this, search unit
4405
refers to the decode table
4406
to find a jump address and operands corresponding to the read virtual machine instruction, outputs the jump address and operands (if any) to the executing unit
4410
as decoded data (step
4506
), and gives the executing unit
4410
a “read end” notification via the signal line R (step
4507
). This “read end” notification marks the completion of decoding for one virtual machine instruction.
FIG. 7
is a flowchart showing the processing in step
4506
in detail. The search unit
4405
compares 1-byte of virtual machine code (the opcode) read by reading
4403
with one opcode
4406
a
in decode table
4406
at a time until a match is found (steps
4802
-
4807
). The search unit
4405
then reads the jump address
4406
b
and the number of operands
4406
c
corresponding to the matching opcode
4406
a
from the decode table
4406
. The search unit
4405
outputs the read jump address
4406
b
to the executing unit
4410
(step
4808
), has the instruction reading unit
4403
read as many operands as are indicated by the number of operands
4406
c
from the instruction storing unit
4401
, and outputs the operands to execution unit
4410
(steps
4809
-
4813
).
The flowcharts of
FIGS. 6 and 7
show the processing when decoded data sent from the decoding unit
4402
is directly transferred to the executing unit
4410
. The flowchart in
FIG. 8
shows the case when the decoded da

Affiliated with

Also associated with

Rating

High speed virtual machine and compiler does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with High speed virtual machine and compiler, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed virtual machine and compiler will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3239989