Method of carrying out computer operations

Details Method of carrying out computer operations Method of carrying out computer operations

1998-07-27

2001-04-03

Powell, Mark R. (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000

Reexamination Certificate

active

06212678

ABSTRACT:

BACKGROUND AND SUMMARY OF THE INVENTION
The present invention relates to a method of carrying out stack based computer operations and to a computer for carrying out such operations.
Computer software is usually written in a high-level language such as C or Pascal, and compiled into the object code of the particular computer processor on which it will be executed. In some cases, however, code is compiled into an intermediate representation (intermediate code), sometimes referred to as ‘Pseudo-Code’ or ‘P-Code’, which is independent of any particular processor architecture. This intermediate code is then interpreted by a program (known as a Virtual Machine), which runs on the target processor. A well-known example of such a system is the Java™ language and intermediate representation, where the high level source code is compiled into one-byte virtual instructions (some of which have further operand bytes), which can then be interpreted by a Java Byte Code interpreter. For more efficient execution, a variant of this scheme involves a ‘Just-In-Time Compiler’, which translates sequences of pseudo-code into real machine code just before executing it.
It is common for the intermediate representation to be defined in terms of a stack-based architecture for the data which is being manipulated. In such a system, of which Java Byte Code is an example, all arithmetic operations act on the operands currently at the top of the stack. For example, to add two numbers together, the following steps would be taken:
1. Push the first number on to the stack.
2. Push the second number on to the stack (just above the first number).
3. Execute the ‘add’ instruction, which pops the top two elements from the stack, adds them together, and pushes the result back on to the stack.
This is illustrated, for the case where the first number is 12 and the second number is 7, in FIG.
1
. The stack is usually implemented in memory, with a processor register acting as a stack pointer and pointing at the current top of the stack. Pushing an element on to the stack then involves writing a value to the memory location pointed to by the stack pointer, and incrementing the stack pointer (assuming an upwards-growing stack). Popping an element from the stack involves decrementing the stack pointer (again assuming an upwards-growing stack), and reading the element then pointed to by the stack pointer.
Although such a virtual machine can easily be implemented using any standard computer processor, it has a major disadvantage for modern high-performance processor architectures commonly known as Reduced Instruction Set Computers (RISC). These processors are designed to take advantage of the fact that operations on registers can be executed much more quickly than operations which need to read and write data from relatively slow main memory. They thus have many registers (typically 32), and their instruction sets are optimised for executing code which is able to keep data in registers as much as possible. This conflicts with the stack-based pseudo-code architecture described above, which is based on the assumption that data will be addressable in memory in a stack form.
Although it is possible to design a simple scheme where, by convention, the first few elements of the stack are held in registers, such a scheme if implemented with a fixed mapping of registers to stack position would be very inefficient. For example, consider a processor with 32 registers (denoted r
0
to r
31
). The pseudo-code interpreter could easily be designed in such a way that eight of those registers were used to hold the first eight elements of the stack, with any further elements being spilled out to memory. For example, r
24
might always represent the first or top element on the stack, r
25
the second, and so on, up to r
31
which would represent the eighth or bottom element. If the stack contained more than eight elements, the ninth and subsequent elements would have be held in memory. This would mean that code implementing the ‘add’ pseudo-instruction could then act directly on registers, since the top two elements of the stack would always be held in registers r
24
and r
25
. However, such an implementation would not be practical, since in order to push a new element on to the stack, it would be necessary to copy the whole contents of the stack down one position in order to maintain the fixed mapping whereby r
24
always represented the first element, and similarly to pop an element from the stack the whole stack would need to be copied up one position.
The present invention seeks to avoid this conflict and improve the performance of virtual machines interpreting stack-based pseudo-code by ensuring that data remains in registers as much as possible, without normally needing to copy data when pushing and popping elements.
According to a first aspect, the invention is a method of carrying out computer operations on a computer including a processor and a series of registers, the method comprising:
the construction of a series of program sections, each program sections comprising an interpreter program which runs on the processor and interprets intermediate code, each program sections constructed to consider the series of registers as all or part of a stack for holding operands and each program sections arranged to consider a different one of the series of registers to be at the top of the stack;
switching from one program sections to another whereby, when an operand is pushed by a virtual machine into the register which it considers to be at the top of the stack, a subsequent virtual machine in the series is selected which considers a different register to be at the top of the stack, and when an operand is popped by a program sections from the register which it considers to be at the top of the stack, a previous program sections in the series is selected which considers a different register to be at the top of the stack.
This invention can be implemented so as to operate very quickly but with the use of only a small amount of extra memory used in constructing the virtual machines. Known solutions are either very quick but use a lot of memory, or use little memory and are slow.
Normally, all of the virtual machines consider the series of registers to be in the same sequence, but each considers a different register to be at the top of the stack. Switching between virtual machines therefore has the effect of moving the stack up and down without having to copy the whole contents of the stack up or down the registers. Also, where more than one operand is pushed or popped, it would be normal to switch up and down the series of virtual machines by the same number of times as operands are pushed or popped. Thus, if two operands are pushed, the virtual machines are switched twice to the virtual machine two away from the original one.
In certain circumstances, the virtual machines are constructed to be identical in every respect, other than the register it considers to be at the top of the stack. The virtual machines are constructed by writing the intermediate code interpreter programs to the computer memory.
In a preferred embodiment, there are the same number of registers as virtual machines, and each virtual machine considers a different one of the registers to be at the top of the stack.
In some circumstances, more operands are pushed onto the stack than there are registers. If this occurs, the method of operation spills one or more of the operands from the stack into memory, and these operands may be retrieved later, if required. It is preferred to spill one or more of the operands at the bottom of the stack to memory since these are least likely to be used again immediately. It is also preferred to spill more than one operand to memory, and preferably between 25 and 50 percent of the operands held in the registers. This means that were the next operation of the computer to be to push another operand onto the stack, it will not have to spill operands to memory again straight away.
The interpreter can operate to convert all of the instructions into

Affiliated with

Also associated with

Rating

Method of carrying out computer operations 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 of carrying out computer operations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of carrying out computer operations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2508379