Combined logic function for address limit checking

Details Combined logic function for address limit checking Combined logic function for address limit checking

2002-06-14

2004-12-28

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Address formation

Slip control, misaligning, boundary alignment

C711S220000

Reexamination Certificate

active

06836835

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to central processing units in computer systems. In particular, it relates to a method and a respective hardware implementation of an add operation and a subtract operation.
Although the present invention has a quite general scope which covers in general method and system for adding and subtracting operands with improved performance and area-optimized implementations it will be next discussed in relation to a specific field of use, namely that of address limit checking. In this particular situation an address A must be checked if it lies within a given zone of the main memory of a computer.
This typical situation is depicted in FIG.
1
. Address A is obtained in prior art by adding the base
20
and an offset
22
and comparing the add result, both, with the zone start address
24
a
and the zone end-address
24
b.
If address A is within the zone i defined by said start-and end-addresses
24
a
and b the operation of a program may, for example, be regularly continued and otherwise some prior art exception handling may occur.
Such kind of address limit check operations are often occurred in modern computer systems because the main memory storage size is increased more and more which opens up a variety of operational features, as, for example, to operate on the same central processing unit a first operating system in a first zone and a second operating system in a second memory zone, and loading the respective application programs for being run simultaneously. In such situations most of memory addresses which are issued by any of the executing units must be checked in the above mentioned sense in order to make sure that the application programs may run properly.
In
FIG. 1
the memory is partitioned into several zones, indexed by i which is each limited by a start-address and end-address. Thus, multiple zones may be present.
Each zone can begin at a certain ‘higher level’ boundary, e.g. 1 Mbyte boundary, and can be expanded up to, e.g., 2 GByte, see FIG.
1
. All accesses to a certain zone have then to be checked to stay within the zone. Thus, the more frequent such accesses are the more urgently logic functions are required to efficiently check if address A is greater than zone start (ZS)
24
a
and if it is smaller than zone end (ZE)
24
b.
As the address A is generated by adding an offset value to a base register value the complete logical function is a 2-operand add operation followed by an adequate compare operation with the zone boundaries. Said compare operation is usually done by subtracting the zone boundary from the add result. This is a very timing critical path within a computer system as the clock cycle is normally adjusted to a 2-operand addition within the ALU. Thus, in prior art this is done sequentially in time.
Some details concerning said prior art approach are next introduced with reference to
FIGS. 2 and 3
. For the following discussion and disclosure it is assumed without any restriction that the addresses have a width of 64 bits.
Base address
20
and Offset address
22
(
FIG. 1
) are byte addresses of 64 bit length, whereas the zone start ZS and zone end ZE usually point to boundaries of e.g. 64 KByte, or even to higher level boundaries as e.g., 1 or 2 Gbyte as mentioned before. The relevant parts of the ZE, ZS addresses are therefore by 16 bits (in case of 64 kByte boundary) shorter. This is illustrated in
FIG. 2
where the not relevant part
25
of the zone boundary beyond bit
47
is shown filled with ‘0’ digits (zeros).
In prior art, the above mentioned limit check function was done as it is schematically depicted in
FIG. 3
, by first adding base and offset with a 2-port adder
30
, and second, by performing a greater or smaller compare of bit
0
to bit
47
from the adder result with the value of ZS and ZE, respectively. Therefore, two further, separate logic circuits
32
,
34
are used in prior art which begin to work after the add result is present on the output of the 2-port adder
30
.
As a person skilled in the art may appreciate two major disadvantages result therefrom:
There is a remarkable performance loss because the compare circuit
32
or
34
have to wait until the add result is present from circuit
30
, and
The area consumption required for implementing the compare circuits
32
and
34
is quite large in regard of the quite similar tasks both circuits have to do. Indeed, they are similar in nature because both compare circuits
32
,
34
work according to the same principle, i.e. subtracting an operand from another one.
SUMMARY OF THE INVENTION
It is thus an object of the present invention to provide a method and system for an improved add and subtract operation.
According to the broadest aspect of the invention a method is provided for performing an add operation with two add operands, and a subtract operation with a third operand, of which a less significant part (
25
) of its binary (1/0) representation exclusively consists of zeros (0), and the subtract operation involves the result of said add operation. It is characterized by the steps of:
a. preferably using a 2-port adder for adding a less significant part of the add operands the bit length of which corresponds to the respective more significant part of said third operand, for generating a carry-out bit using a first carry network,
b. in a first step of a 3-port operation concurrently to the above step a) adding a respective more significant part
51
53
of the add operands for bit wise generating sum bits and carry bits preferably in a full adder stage,
c. in a second step of the 3-port operation performing said subtract operation by bit wise operating a second carry network
with respective bits of the more significant part
55
of said third operand,
with respective ones of said sum bits
56
,
with said carry out bit
54
of said less
significant part add operation, and
with the carry-out bits
58
of said more significant part add operation.
Thus, a general approach is disclosed which applications include mathematical add/subtract operations, amongst the address operations which are actually focused by the disclosed concepts.
By the disclosed combination of said add and compare operations a solution is disclosed which is faster than prior art because of the early start of the 3-port subtract operation which can be done before the add operation is completed. Moreover, the 3-port operation and the 2-port add operation is basically started in parallel which accelerates operation.
Further, the timing of the carry-out of the 2-port operation can be adjusted to be active when needed in 3 port operation part:
The carry-out of carrynet
1
takes longer than the fulladder stage of the 3-port operation. Considering
FIG. 6
, the carry-out of carrynet
1
seems to be needed directly after the sum and carry bits of the 3 port stage are available. Actually, the control bit takes the position of the carry-in. The carry-out of carrynet
1
can then be faced in at the latest possible point of the
2
. part of the 3 port operation, FIG.
4
. Thus, a lot of parallel work can be done while the carry-out is generated.
Further, when said first and said second operands are base, and offset address operands, and said third operand is a zone start or zone end address of a storage means, and in particular of a physical memory means, which is divided into one or more of said zones, and the disclosed method further comprises the step of evaluating the carry-out of the second carry network for checking if the address given by said add result of add operands is within the address zone defined by said zone start and zone end addresses, then, the particular preferential use of the disclosed method is found, i.e., address arithmetic, and in particular address limit checking is enabled with the third operand being a higher level boundary in memory, e.g., a Megabyte boundary having 20 least significant bits as trailing or leading (architecture-dependent) zeros, respectively. In those cases an efficient address limit checking is provided by th

Affiliated with

Also associated with

Rating

Combined logic function for address limit checking does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Combined logic function for address limit checking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combined logic function for address limit checking will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3297668