Optimization of n-base typed arithmetic expressions

Details Optimization of n-base typed arithmetic expressions Optimization of n-base typed arithmetic expressions

2001-11-01

2004-02-03

Chavis, John (Department: 2124)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S151000, C708S498000, C708S551000, C708S553000

Reexamination Certificate

active

06687898

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer systems. More particularly, the present invention relates to the optimization of n-base typed arithmetic expressions.
2. Background
Preparation of a computer program is illustrated in FIG.
1
. The user writes programs in a high-level programming language
10
. The programs written in the high-level program language
10
are compiled into a low-level machine language
12
, which can be executed by the targeted machine. For example, programs written in the high-level Java™ programming language are compiled into low level bytecode instructions. The bytecode instructions are the machine language for a Java™ Virtual Machine. The Java™ Virtual Machine Specification is described in Lindholm et al., “The Java™ Virtual Machine Specification”, 1999, Addison Wesley, Second Edition.
Typical high-level programming languages support arithmetic expressions. Arithmetic expressions are defined by an arithmetic operator that operates on one or more operands. Operators typically supported include addition, subtraction, multiplication, division, remainder, negate, shift, bitwise OR, bitwise AND and bitwise exclusive OR. Intermediate values are the results of one or more arithmetic operations.
High-level languages also typically support multiple or n-base integral types and arithmetic operations are overloaded. Overloading allows operators to accept operands having mixed types. For example, the Java™ programming language supports four base integral types: byte, short, int and long. These types support 8-, 16-, 32- and 64-bit values, respectively. Operators such as the “+” operator may accept operands of any of these integral types. The three examples below illustrate overloading the “+” operator for operations on operands having mixed base types.
int a, b;
a+b;
short a, b;
a+b;
byte a, b;
a+b;
This overloading is typically performed by widening values to a wider base type and then performing the arithmetic operation. For example, C and Java™ compilers typically widen values of type byte and short to type int. In the Java™ language, type int is always 32 bits. Thus, 16-bit values of type short and 8-bit values of type byte are widened to the 32-bit type int before performing the arithmetic operation. In the Java™ language, the following byte code is generated for each of the three examples listed above:
iload a
iload b
iadd
The iload instructions loads any of the 8, 16 or 32-bit variables and puts a 32-bit operand on the stack. The iadd instruction pops two 32-bit operands off the stack, adds them and puts the 32-bit result back on the stack.
Unlike Java™, some high-level languages define only the relationship between the integral types, and not the size of each type. For example, one C compiler vendor may define the bit sizes of types byte, short and int to be 8, 16 and 32 bits, respectively. However, another C compiler vender may define the sizes of the same types to be 16, 32 and 64 bits, respectively. Yet another compiler may define the bit sizes to be 16, 32 and 32 bits, respectively. In all cases, the relationship between the sizes of each type is maintained (number of values represented by type byte<number of values represented by type short, number of values represented by type short<number values represented by type int), but the actual number of bits used to represent each type may differ. Like Java™, however, C performs arithmetic operations in the size of the int type defined by each particular compiler. This requires widening values having a smaller base type to type int.
This type widening approach reduces the number of machine instructions, thus reducing the complexity of the target machine. However, this type widening typically requires more computational stack space. For example, adding two 16-bit values of type short after they have been widened to the 32-bit type uses the same amount of stack space as adding two 32-bit values of type int, as illustrated in
FIGS. 2A and 2B
.
Turning now to
FIG. 2A
, a flow diagram that illustrates stack usage when adding two 16-bit values of type short in the Java™ language is illustrated. At reference numeral
20
, the first 16-bit operand is loaded and pushed onto the operand stack. The operand stack at this point is illustrated by reference numeral
30
. At reference numeral
22
, the first 16-bit operand is expanded to 32 bits. At reference numeral
24
, the second 16-bit operand is loaded and pushed onto the operand stack. At reference numeral
26
, the second 16-bit operand is expanded to 32 bits. At this point, the operand stack occupies 4×16=64 bits. At reference numeral
28
, the two 32-bit operands are added using a 32-bit add operator.
Turning now to
FIG. 3A
, a flow diagram that illustrates stack usage when adding two 32-bit values of type int is presented. At reference numeral
40
, the first 32-bit operand is loaded and pushed onto the operand stack. The operand stack is illustrated by FIG.
3
B. At reference numeral
42
, the second 32-bit operand is loaded and pushed onto the operand stack. At reference numeral
44
, the two 32-bit operands are added using a 32-bit add operator. Thus, in both the 16-bit add and the 32-bit add examples above, two 32-bit operands are pushed onto the stack before being popped off the stack and added using a 32-bit add operation.
During the course of program execution, the stack size may vary in size due to factors such as the level of nested procedure calls, the complexity of computed expressions and the number of locally declared variables. On resource-constrained devices such as smart cards, there is typically insufficient memory available to perform such computations where type widening takes place.
Resource-constrained devices are generally considered to be those that are relatively restricted in memory and/or computing power or speed, as compared to typical desktop computers and the like. By way of example, other resource-constrained devices include cellular telephones, boundary scan devices, field programmable devices, personal digital assistants (PDAs) and pagers and other miniature or small footprint devices.
Smart cards, also known as intelligent portable data-carrying cards, generally are made of plastic or metal and have an electronic chip that includes an embedded microprocessor or microcontroller to execute programs and memory to store programs and data. Such devices, which can be about the size of a credit card, have computer chips with 8-bit or 16-bit architectures. Additionally, these devices typically have limited memory capacity. For example, some smart cards have less than one kilo-byte (1K) of random access memory (RAM) as well as limited read only memory (ROM), and/or non-volatile memory such as electrically erasable programmable read only memory (EEPROM).
Furthermore, smart cards with 8-bit or 16-bit architectures typically have built-in 8-bit or 16-bit arithmetic operations, respectively. As such, smart cards can typically perform 8-bit or 16-bit operations more efficiently than 32-bit operations. Performing 32-bit operations on data that has been widened to 32-bits is especially inefficient. Thus, the limited architecture and memory of resource-constrained devices such as smart cards make it impractical or impossible to execute programs where the values have been widened to a larger integral type.
The Java™ Virtual Machine instruction set defines an arithmetic instruction set to handle values of integral types byte, short and int. Variables of type byte and short are widened to the integral type int during compilation. By contrast, the Java Card™ (the smart card that supports the Java™ programming language) Virtual Machine defines a separate instruction set to handle variables of type byte and short, in addition to the instruction set to handle variables of integral type int. Most Java Card™ applications operate on data values of type short or byte.
There is an increasing trend in the computer industry to support high-level computer la

Affiliated with

Also associated with

Rating

Optimization of n-base typed arithmetic expressions does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Optimization of n-base typed arithmetic expressions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization of n-base typed arithmetic expressions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3279046