Intelligent multiple stack management unit

• US 6,006,323 A
• Filed: 05/20/1998
• Issued: 12/21/1999
• Est. Priority Date: 05/20/1998
• Status: Expired due to Term

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Shang, Shi-Sheng, Ma, Ruey-Liang
• Primary Examiner(s): Treat, William M.
• Application Number:
  US09/082,368
• Time in Patent Office: 580 Days
• Field of Search: 712/202
• US Class Current: 712/202
• CPC Class Codes: G06F 9/30101 Special purpose registers
• CPC Class Codes: G06F 9/30134 Register stacks; shift registers
• CPC Class Codes: G06F 9/4484 Executing subprograms

Abstract

A stack management unit for a processing system that manages multiple stacks and corresponding stack pointer data as a frame stack. The stack management unit utilizes a combination of a primary stack and a secondary stack as the frame stack. A background spill/fill detect unit determines when an overflow/underflow of the primary stack occurs. In response to an overflow/underflow condition, the background spill/fill detect unit controls the transfer of a frame portion between the primary stack and the secondary stack without halting the processing system.

Claims

1. A stack management unit comprising:

a plurality of register stacks organized as a frame stack and configured to store a corresponding plurality of frame portions and a corresponding plurality of stack pointer data, wherein said plurality of frame portions together comprise a frame and each of said plurality of stack pointer data indicate a position of a corresponding one of said frame portions in said plurality of stack registers;

a stack pointer register configured to store said plurality of stack pointer data during a call operation to said frame stack and a return operation from said frame stack; and

a control unit configured to control the storage of said frame in said frame stack and the storage of said plurality of stack pointer data in said stack pointer register during said call operation, and configured to retrieve said frame from said frame stack using said plurality of stack pointer data stored in said stack pointer register during said return operation.

2. The stack management unit of claim 1, wherein said frame is one of a plurality of frames, wherein said frame stack is configured to store said plurality of frames, each one of said plurality of frames having a plurality of frame portions and a corresponding plurality of stack pointer data, wherein each one of said plurality of register stacks is configured to store one of each said plurality of frame portions for each of said plurality of frames, and wherein said stack pointer register is configured to store the plurality of stack pointer data corresponding to a top most frame of said plurality of frames during said call and return operations.

3. The stack management unit of claim 2, wherein said frame stack is configured such that the number of said plurality of frame portions for each of said plurality of frames is the same.

4. The stack management unit of claim 1, wherein said frame stack is configured such that the size of each of said plurality of frame portions is determined by the size of each of a corresponding plurality of elements stored in each of said plurality of frame portions.

5. The stack management unit of claim 1, wherein a first one of said plurality of stack pointer data indicates the end of a corresponding first one of said plurality of frame portions and said first one of said plurality of frame portions is a data frame portion, and wherein a second one of said plurality of stack pointer data indicates the beginning of a corresponding second one of said plurality of frame portions and said second one of said plurality of frame portions is other than a data frame portion.

6. The stack management unit of claim 2, wherein a first one of said plurality of stack pointer data for each of said plurality of frames indicates the end of a corresponding first one of said plurality of frame portions, said corresponding first one of said plurality of frame portions is a data frame portion, and said first one of said plurality of stack pointer data for each of said plurality of frames indicates the top of each of said plurality of frames, and wherein a second one of said stack pointer data indicates the beginning of a corresponding second one of said plurality of frame portions and said corresponding second one of said plurality of frame portions is other than a data frame portion.

7. The stack management unit of claim 5, wherein said frame stack is configured to store said first one of said plurality of stack pointer data and said first corresponding one of said frame portions after storing the other ones of said plurality of stack pointer data and frame portions.

8. The stack management unit of claim 5, wherein said first one of said plurality of frame portions is comprised of one or more data elements, wherein said control unit is configured to access said first one of said plurality of frame portions during a return operation by removing one of said one or more data elements at the end of said first one of said plurality of frame portions and configured to change said first one of said plurality of stack pointer data to indicate a next data element of said first one of said plurality of frame portions, and wherein said control unit is configured to access said first one of said plurality of frame portions during a call operation by appending a new data element to the end of said first one of said plurality of frame portions and configured to change said first one of said plurality of stack pointer data to indicate the end of said new data element.

9. The stack management unit of claim 5, wherein said control unit is configured to access said second one of said plurality of frame portions during call and return operations utilizing said second one of said plurality of stack pointer data and an offset value for a particular non-data element that is being accessed.

10. A stack management unit comprising:

a plurality of register stacks organized as a frame stack and configured to store a plurality of frames, each one of said plurality of frames having a plurality of frame portions, wherein each one of said plurality of register stacks is configured to store one of said plurality of frame portions for each of said plurality of frames, wherein said frame stack is configured as a primary stack and a secondary stack, and wherein each of said frame portions is comprised of a number of elements; and

an overflow/underflow detector configured to detect a total number of elements stored in said primary stack and to produce a spill signal if the total number of elements stored in said primary stack exceeds an overflow limitation value, and configured to produce a fill signal if the total number of elements stored in said primary stack is less than an underflow limitation value, wherein said frame stack is configured to move a predetermined number of elements from said primary stack to said secondary stack in response to a received spill signal, and wherein said frame stack is configured to move said predetermined number of elements from said secondary stack to said primary stack in response to a received fill signal.

11. The stack management unit of claim 10, wherein said overflow/underflow detector further comprises:

a limitation table configured to output an overflow limitation signal and an underflow limitation signal; and

a comparator configured to receive a top of primary stack (TOS) signal indicating an end location of a last stored element in said primary stack, configured to receive a bottom of primary stack (BOS) signal indicating a beginning location of a first stored element in said primary stack, configured to receive said overflow and underflow limitations signals, and configured to produce said spill and fill signals in response to said received signals.

12. The stack management unit of claim 11, wherein said comparator further comprises:

a TOS register configured to store said TOS signal;

a BOS register configured to store said BOS signal; and

a subtractor configured to receive said TOS signal and said BOS signal respectively from said TOS and said BOS registers in response to an access operation to and from said frame stack, and configured to produce a usage signal indicative of the total number of elements stored in said primary stack, wherein said comparator is configured to compare said usage signal to said overflow limitation signal and said underflow limitation signal to respectively produce said spill and fill signals.

13. A stack management unit comprising:

a plurality of register stacks organized as a frame stack and configured to store a plurality of frames, each one of said plurality of frames having a plurality of frame portions and a corresponding plurality of stack pointer data for indicating where said plurality of frame portions are located in said plurality of register stacks, wherein each one of a first subset of said plurality of register stacks is configured to store one of said plurality of frame portions for each of said plurality of frames and one of a second subset of said plurality of register stacks is configured to store said corresponding plurality of stack pointer data for each of said plurality of frames;

a stack pointer register configured to store the plurality of stack pointer data corresponding to a top most frame of said plurality of frames during an access operation of said frame stack; and

a control unit configured to control storage of said top most frame in said frame stack and storage of the corresponding plurality of stack pointer data in said plurality of stack pointer registers during a call operation to said frame stack, and configured to retrieve said top most frame in said frame stack using the corresponding plurality of stack pointer data stored in said plurality of stack pointer registers during a return operation from said frame stack.

14. The stack management unit of claim 13, wherein a first one of said plurality of stack pointer data for each one of said plurality of frames indicates the end of a corresponding first one of said plurality of frame portions and said first one of said plurality of frame portions is a data frame portion, and wherein a second one of said plurality of stack pointer data for each one of said plurality of frames indicates the beginning of a corresponding second one of said plurality of frame portions and said second one of said plurality of frame portions is other than a data frame portion.

15. The stack management unit of claim 14, wherein for each one of said plurality of frames, said control unit is configured to store said first one of said plurality of stack pointer data and said first one of said frame portions after storing other ones of said plurality of stack pointer data and frame portions.

16. The stack management unit of claim 15, wherein during said call operation said control unit is configured to determine said first one of said plurality of stack pointer data of said top most frame by adding an offset to said first one of said plurality of stack pointer data of a next top most frame of said plurality of frames, wherein said offset represents the size of said first one of said frame portions for said top most frame, and wherein during said return operation said control unit is configured to retrieve said top most frame from said frame stack.

17. The stack management unit of claim 13, wherein each of said frame portions is comprised of a number of elements and wherein said frame stack is comprised of:

a primary stack; and

a secondary stack, wherein said primary stack is configured to transmit a predetermined number of elements of a bottom most frame of said plurality of frames stored in said primary stack to said secondary stack if an overflow condition occurs in said primary stack, and wherein said primary stack is configured to receive said predetermined number of elements of a top most frame of said plurality of frames stored in said secondary stack if an underflow condition occurs in said primary stack.

18. A method of managing a stack comprising the steps of:

configuring a plurality of register stacks as a frame stack having a primary stack and a secondary stack;

storing in each one of said plurality of register stacks one of a plurality of frame portions for each one of a plurality of frames, wherein each of said frame portions is comprised of a number of elements;

moving a predetermined number of elements from said primary stack to said secondary stack if a total number of elements stored in said primary stack exceeds an overflow limitation value; and

moving said predetermined number of elements from said secondary stack to said primary stack if said total number of elements stored in said primary stack is less than an underflow limitation value.

19. The method of claim 18, comprising the step of comparing a beginning location of a first stored word in said primary stack to an end location of a last stored word in said primary stack to determine said total number of words in said primary stack.