Proportionally growing stack in a linear memory array

Details Proportionally growing stack in a linear memory array Proportionally growing stack in a linear memory array

2000-09-21

2003-09-30

McLean-Mayo, Kimberly (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Memory configuring

C711S154000

Reexamination Certificate

active

06629228

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The present invention is related generally to an improved data processing system and, more particularly, to an improved first in last out data structure within a memory array.
2. Description of Related Art
A stack or First In Last Out (FILO) data structure is used in many computer applications. Often multiple stacks are needed in a single application and they are added as needed, because initially it is not known how many stacks will be needed. Memory in computer systems is commonly arranged as a linear array, with an application having some segment of this linear array that it will use to place multiple stacks. The way stacks are traditionally implemented is with a base and head pointer.
In a typical case, two stacks are placed at opposite ends of the memory array. One stack grows to the right and the other stack grows to the left. Each stack may grow until it hits the opposite stack coming from the opposite direction (which is referred to as a collision).
The arrangement with two stack growing toward one another from opposite ends of the array is efficient if both the stacks grow at the same rate. That is, all memory within the memory array will be consumed before a collision. However, if a third stack is needed, a problem may arise. If all three stacks grow at the same rate, the third stack grows in one direction, and the third stack is placed in the middle of the first two stacks, then the third stack will tend to collide with one of the other two stacks, before the other of the other two stacks has used all its space. The third stack could be offset in location from the center in an effort to anticipate this problem, but if the three stacks do not grow at the same rate, then the selected offset location of the third stack may not help.
In one of the related applications, these problems are addressed by one or more bidirectionally growing stacks. In another of the related applications, these problems are further addressed in stacks which are split into more than one part. Both of these inventions are useful for addressing the problems, as described, which arise in managing the space in a linear memory array, including allocation of the space. However, a need exists for a method or apparatus to manage memory having other features, which relate to aspects of these problems in a different way, and which may provide even greater adaptability in certain circumstances, particularly circumstances involving uncertain variation in growth rate of stacks.
SUMMARY OF THE INVENTION
The present invention addresses this need as follows. A storage area, with a first and second end, is provided for storing data elements. The data elements are stored in a first stack, also having a first and second end. Space in the storage area for the first stack includes a first space proximate the first end of the first stack, and a second space proximate the second end of the first stack. The storing of one of the data elements in the first stack includes selecting between storing in the first space or the second space, responsive to the relative sizes of the two spaces.
In another aspect, data elements are stored in the storage area in a second stack. Space available in the storage area for data elements of the second stack includes the above mentioned first and second spaces, that is, the space proximate the first end of the first stack, and the space proximate the second end of the first stack. Storing in the second stack includes selecting between storing in the first or second space, responsive to the relative sizes of the two spaces.


REFERENCES:
patent: 6006323 (1999-12-01), Ma et al.
patent: 6138210 (2000-10-01), Tremblay et al.
Li, A Bidirectional Multiple Stack Algorithm, Dec. 1999, IEEE.*
Chien, A Dynamic Strategy for Multiple Stacks Manipulation, IEEE, Dec. 1991*
Lin, “Modified Multiple Stack Algorithm for Decoding Convolutional Codes”, IEEE, vol. 4; No. 4; Aug. 1997.*
Korsh et al., “A Multiple Stack Manipulation Procedure,” Nov. '83, pp 27-29, plus one page w/ ltr.
Knuth, “The Art of Computer Programming,” 2d ed., vol. 1, pp240-248.
Garwick, “Data Storage in Compilers,” Bit 4, 1964, pp 137-140.
Yeh et al., Dynamic Initial Allocation and Local Reallocation Procedures for Multiple Stacks, Communications of the ACM, Feb. '86, pp 30-39.

Affiliated with

Also associated with

Rating

Proportionally growing stack in a linear memory array does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Proportionally growing stack in a linear memory array, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Proportionally growing stack in a linear memory array will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3039289