Circular address register

Details Circular address register Circular address register

1999-12-17

2004-08-24

Tran, Denise (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C711S220000, C711S201000, C711S218000, C711S219000

Reexamination Certificate

active

06782447

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of computer and programming systems, and in particular to the programming of systems that employ circular lists or iteratively process multiple-word operands.
2. Description of Related Art
Circular lists are often used to implement First-In, First-Out (FIFO) buffers. The FIFO model represents a list of items wherein new items are added to the top of the list, and old items are removed from the bottom of the list. In effect, the FIFO is structured as a list of L data items; when a data item is added to the list, it is given the next available address of L+1; when a data item is removed from the list, the address of each data item remaining in the list is decremented by one. The moving of each remaining data item down in the list each time a data item is removed from the list, however, is inefficient. Instead, the defined “bottom” of the list is moved up by one each time a data item is removed. The logical address of each data-item in the list is defined by its distance from this defined bottom of the list, rather than by its physical location in the continually growing list. Even though the “removed” data items may remain in the physical locations below the “bottom” of the list, they are no longer within the logical address space of the list, and are no longer considered to be a part of the list of L items. As would be evident to one of ordinary skill in the art, the continued advancement of the physical location used for each added data item, without a corresponding physical relocation of each data item to lower physical locations as data items are removed, will eventually exhaust the physical resources used to contain these data items.
A circular list is embodied as N contiguous physical memory locations, and a corresponding controlling mechanism that adds new data items to the list, starting at the beginning of the physical memory locations, and continuing to each next available physical location until the end of the contiguous locations is reached. When the next data item arrives after reaching the end of the contiguous locations, this next data item is placed at the beginning of the contiguous locations, replacing the prior data item that was stored at the beginning of the contiguous locations. Each next data item is placed into each next physical location, replacing the data items previously stored at each next physical location, until the end of the contiguous locations is again exceeded, at which point the next data item is placed at the beginning of the contiguous locations. This process continues ad infinitum without consuming more than the N contiguous physical memory locations at any time. Note, however, that the prior data items that are being replaced by the next data items must have been data items that were conceptually “removed” from the list. That is, at no time can the logical length of the list, L, exceed the physical length of the contiguous locations N. In a typical embodiment, the controlling mechanism maintains a pointer to the logical “bottom” of the list, and updates it accordingly as each data item is removed from the list, and also maintains a pointer to the logical “top” of the list, and updates it accordingly as each data item is added to the list. The controlling mechanism also inhibits the addition of a new data item when the “top” of the list becomes coincident with the “bottom” of the list, and waits for the “bottom” of the list to be advanced (by a removal of the oldest item in the list) before placing the new data item into the list.
Typically, multiple programming instructions are required to control the incrementing and decrementing of a pointer that is associated with a circular list. The instructions must test whether the pointer has gone beyond the upper or lower bounds of the physically contiguous memory locations, and adjust the pointer accordingly to provide the circular addressing effect.
BRIEF SUMMARY OF THE INVENTION
It is an object of this invention to provide a device that facilitates the use of circular lists. It is a further object of this invention to ease the task of programming a device to facilitate the use of circular lists. It is a further object of this invention to ease the task of programming a device to facilitate the use of multiple-word data items by modeling the multiple-word data items as circular addressing process.
These objects and others are achieved by providing a device and corresponding programming instructions that facilitate a circular addressing process. The device is configured to provide an address output that is constrained to lie within specified bounds. When a “circular increment” or “circular decrement” instruction is executed that would cause the address to exceed a bound, the address is reset to the other bound. In a preferred embodiment, the programming instruction also sets condition flags that indicate when the address is at each bound. By providing these “bounds” flags in conjunction with the circular addressing operation, multiple-word data items can be processed efficiently. A base-address of N contiguous words in a memory is loaded into the circular register, and a circular addressing instruction is used to access each word of the N contiguous words in sequence; a bounds flag is set when the last word of the multi-word data item is accessed. This bounds flag may thus be used to signal the end of processing of N words of a multi-word data item, and can be used to trigger a load of a next multi-word data item, or to trigger a next operation on the current data-item, and so on. Other condition flags are also provided to facilitate the processing of multi-word data-items.


REFERENCES:
patent: 4202035 (1980-05-01), Lane
patent: 4809156 (1989-02-01), Taber
patent: 4908748 (1990-03-01), Pathak et al.
patent: 5032986 (1991-07-01), Pathak et al.
patent: 5623621 (1997-04-01), Garde
patent: 5649146 (1997-07-01), Riou
patent: 5659698 (1997-08-01), Weng et al.
patent: 5659700 (1997-08-01), Chen et al.
patent: 5983333 (1999-11-01), Kolagotla
“Circular Addressing Circuitry for Accessing Computer Storage”, IBM Technical Disclosure Bulletin, vol. 20, No. 2, Jul. 1977, pp. 871-872.

Affiliated with

Also associated with

Rating

Circular address register does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Circular address register, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circular address register will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3283889