STACK ORGANIZATION: REGISTER STACK, MEMORY STACK; INSTRUCTION....

STACK ORGANIZATION:

The computers which use Stack-based CPU Organization are based on a data structure called stack. The stack is a list of data words. It uses the Last-in First-Out (LIFO) Operations.Stack pointer (SP): A register that holds the address of the top item in the stack. SP always points at the top item in the stack.

STACK IMPLEMENTATION:

In digital Computer, stack can be used in two ways:

·       Registers can be put into a stack, i.e. “REGISTER STACK”.

·       Memory can be used as a stack, i.e. “MEMORY STACK”.

 

REGISTER STACK:

          A stack can be placed in a portion of a large memory or it can be organized as a collection of a finite number of memory words or registers. Figure 3 shows the organization of a 64-word register stack. The stack pointer register SP contains a binary number whose value is equal to the address of the word that is currently on top of the stack. Three items are placed in the stack: A, B, and C, in that order. Item C is on top of the stack so that the content of SP is now 3.

MEMORY STACK:

            Memory with Program Data and Stack Segments. A Position of memory is used as a stack with a processor register as a stack pointer.

If SP reaches 0, the stack is full of items, so FULL is set to L this condition is reached if the top item prior to the last push was in location 63 and, after incrementing SP, the last item is stored in location 0.

Once an item is stored in location 0, there are no more empty registers in the stack. If an item is written in the stack, obviously the stack cannot be empty, so EMPTY is cleared to 0.A new item is deleted from the stack if the stack is not empty (if EMPTY = 0). The pop operation consists of the following sequence of micro operations:

DR ← M [SP] Read item from the top of stack

SP ← SP - 1 Decrement stack pointer

If (SP = 0) then (EMTY ← 1) Check if stack is empty

FULL ← 0    Mark the stack not full 

• The top item is read from the stack into DR. The stack pointer is then decremented. If its value reaches zero, the stack is empty, so EMTY is set to 1.

The stack pointer SP points at the top of the stack. The three registers are connected to a common address bus, and either one can provide an address for memory.
PC is used during the fetch phase to read an instruction. AR is used during the execute phase to read an operand.

SP is used to push or pop items into or the stack. As shown in Fig. 2, the initial value of SP is 4001 and the stack grows with decreasing addresses.

Thus the first item stored in the stack is at address 4000, the second item is stored at address 3999, and the last address that can be used for the stack is 3000.No provisions are available for stack limit checks.

We assume that the items in the stack communicate with a data register DR. A new item is inserted with the push operation as follows:

SP ← SP - 1
M[SP] ← DR

The stack pointer is decremented so that it points at the address of the next word. A memory write operation inserts the word from DR into the top of the stack. A new item is deleted with a pop operation as follows:

DR ← M[SP]
SP ← SP + 1

The top item is read from the stack into DR. The stack pointer is then incremented to point at the next item in the stack.

Most computers do not provide hardware to check for stack overflow (full stack) or underflow (empty stack).

The stack limits can be checked by using two processor registers: one to hold the upper limit (3000 in this case), and the other to hold the lower limit (4001 in this case).

After a push operation, SP is compared with the upper-limit register and after a pop operation, SP is compared with the lower-limit register.

The two micro operations needed for either the push or pop are (1) an access to memory through SP, and (2) updating SP. Which of the two micro operations is done first and whether SP is updated by incrementing or decrementing depends on the organization of the stack.

In Fig.2 the stack grows by decreasing the memory address. The stack may be constructed to grow by increasing the memory address as in Fig. 1.
In such a case, SP is incremented for the push operation and decremented for the pop operation. A stack may be constructed so that SP points at the next empty location above the top of the stack.
In this case the sequence of micro operations must be interchanged. A stack pointer is loaded with an initial value. This initial value must be the bottom address of an assigned stack in memory. Henceforth, SP is automatically decremented or incremented with every push or pop operation.

The advantage of a memory stack is that the CPU can refer to it without having to specify an address, since the address is always available and automatically updated in the stack pointer.

STACK OPERATIONS 

The main two operations that are performed on the operators of the stack are Push and Pop. These two operations are performed from one end only.

1.     Push –
This operation results in inserting one operand at the top of the stack and it decrease the stack pointer register. The format of the PUSH instruction is:

PUSH

It inserts the data word at specified address to the top of the stack. It can be implemented as:

//decrement SP by 1

SP <-- SP - 1

//store the content of specified memory address

//into SP; i.e., at top of stack

SP <-- (memory address)

2.     Pop –
This operation results in deleting one operand from the top of the stack and it increase the stack pointer register. The format of the POP instruction is:

      POP

It deletes the data word at the top of the stack to the specified address. It can be implemented as:

//transfer the content of SP (i.e., at top most data)

//into specified memory location                  

(Memory address) <-- SP

 

//increment SP by 1

SP <-- SP + 1 

 

EVALUATION OF ARITHMETIC EXPRESSIONS:

The stack organization is very effective in evaluating arithmetic expressions. Expressions are usually represented in what is known as Infix notation, in which each operator is written between two operands (i.e., A + B). With this notation, we must distinguish between (A + B)*C and A + (B * C) by using either parentheses or some operator-precedence convention. 

CONCLUSION:

Stack is a memory region within the program/process. This part of the memory gets allocated when a process is created. We use Stack for storing temporary data such as local variables of some function, environment variables which helps us to transition between the functions, etc.

A stack can be placed in a portion of a large memory or it can be organized as a collection of a finite number of memory words or registers. Memory with Program Data and Stack Segments. A Position of memory is used as a stack with a processor register as a stack pointer.

The implementation of a stack in the CPU is done by assigning a portion of memory to a stack operation and using a processor register as a stack pointer.

                                                                                                               REFERENCES:

Computerarchitecturebook#MCAhttps://www.geeksforgeeks.org/introduction-of-stack-based-cpuorganization/#:~:text=The%20computers%20which%20use%20Stack,a%20list%20of%20data%20words.&text=A%20register%20is%20used%20to,are%20performed%20on%20stack%20data.  http://www.eazynotes.com/pages/computer-system-architecture/stack-organization.html    https://upscfever.com/upsc-fever/en/gatecse/en-gatecse-chp159.html