Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
1998-08-24
2002-08-06
Kim, Mathew (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S218000, C711S219000, C711S211000
Reexamination Certificate
active
06430666
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to memory systems in general, and specifically to memory systems incorporating linked lists.
BACKGROUND OF THE INVENTION
Often within a data processing system multiple processors and devices will access a common memory space. In such a case, it is necessary to coordinate the use and allocation of addresses within the common memory space so that each device addresses unique locations and avoids interference. For example, in a telecommunication switching system, such as an asynchronous transfer mode application (ATM), where multiple data ports share a the common memory space. One method of coordinating addresses involves the use of a linked list. The linked list is a copy of the common memory space, having a pointer associated with each memory address. Each device in the system has a list containing data to be stored in the data memory. The pointers indicate where the contents of the list are located in data memory.
The list pointers are compiled into a table, which may be maintained in software or in hardware. A list is typically designated as having a starting address, known as the “head” of the list, and an ending address, known as the “tail” of the list. The addresses between the head and tail are not necessarily sequential, and are typically spread throughout data memory. The list pointer then keeps track of all of the addresses that are contained within the list.
When the lists are implemented in hardware, control logic is used to update the list pointer, and to interface with the memory. Often this control logic will be some type of an application specific integrated circuit (ASIC) device which is specially designed and separate from the memory integrated circuit. ASIC solutions do not typically optimize access speed, and are expensive.
When designating addresses within a memory space it is desirable to use the entire memory space. Software implementations increase memory processing time, creating a problem in many faster memories. While it is desirable to implement these memory systems in hardware so as to increase the speed of memory access needed in fast memories, the linked list method may not always utilize all of the addresses within the memory.
There is a need for a linked list memory which provides the speed of a hardware implementation, while ensuring that all addresses within the main memory have been used.
REFERENCES:
patent: 4173783 (1979-11-01), Couleur et al
patent: 4949301 (1990-08-01), Joshi et al.
patent: 5101485 (1992-03-01), Perazzoli, Jr.
patent: 5125086 (1992-06-01), Perazzoli, Jr.
patent: 5481691 (1996-01-01), Day, III et al.
patent: 5493652 (1996-02-01), Koufopavlou et al.
patent: 5555339 (1996-09-01), Waldron et al.
patent: 5555399 (1996-09-01), Waldron et al.
patent: 5809560 (1998-09-01), Schneider
Anderson Matt
Chiu Joanna G.
Kim Mathew
Motorola Inc.
LandOfFree
Linked list memory and method therefor does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Linked list memory and method therefor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linked list memory and method therefor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2957775