Stack Organization in Computer Architecture

YASH PAL,

Stack Organization in Computer Architecture – The stack is a portion of read/write memory that is used for temporary storage during the execution of a program.

For the application programs, the internal memory of the microprocessor (registers) is not sufficient to store the intermediate results. These intermediate results can be stored temporarily on the stack and can be used again when required.

The stack follows the LIFO (Last-In-First-Out) concept. The data inserted last will be taken out first. This type of input/output manner is called the Last-In First-Out manner. When the data is written on the stack, the operation is called the PUSH operation. Similarly, when the data is read from the stack, the operation is called the POP operation.

The stack is generally initialised at the highest available memory location. The beginning of the stack is defined by loading the address in the Stack Pointer (SP). The stack pointer is a register which indicates the top of the stack.

Top of the stack means the data which is recently stored can be retrieved first. The figure below shows the stack architecture in the memory. The memory unit is divided into program, data and stack segments.

Stack Organization

Stack organization is useful for storing the temporarily result of program and can be used while when required. also stack organization is used for evaluation or arithmetic expressions. Stack architecture is used to store data while stack operations are use for insertion/read and deletion of data from stack.

Stack Architecture

As defined earlier, the stack is a portion of large memory that is used for temporary storage during the execution of a program. It can be architecture as a collection of a finite number of memory registers. The figure below shows the stack architecture of a 32-word register stack. The stack contains 32 registers with addresses from 0 to 31, as shown in the image below.

The above figure shows the stack architecture with four registers: (i) FULL, (ii) EMPTY, (iii) SP and (iv) DR. The beginning of the stack is defined by the address stored in the stack pointer (SP). In a 32-word stack, the stack pointer contains 5 bits because 25-32. Since SP has only 5 bits, it can not exceed a number greater than 31 (111112).

The register FULL is a one-bit register. It is set to 1 when the stack is full. Similarly, EMPTY is a one-bit register and is set to 1 when the stack is empty. DR is a data register that holds the binary data to be written into or read out of the stack.

Stack Operations

There are two basic operations that are related to the stack. These operations are the insertion and deletion of data from the stack. The operation of insertion is called the PUSH operation, whereas deletion (retrieve) is called the POP operation. These operations are simulated by incrementing or decrementing the stack pointer.

PUSH Operation

This operation is a memory write operation which inserts the data from DR into the top of the stack. SP (Stack Pointer) points to the top of the stack, and M[SP] denotes the data that is stored in memory (stack in this case) pointed by Stack Pointer (SP).

Initially, assume the stack is empty; therefore EMPTY register is set, and SP contains 0 address. Since the stack is empty FULL register is reset. New data is inserted with a push operation. For push operation, the stack pointer is incremented first, so that it points to the next-higher memory location to insert the data. Memory write operation then stores the data from DR to the top of the stack pointed by SP.

If the stack pointer, SP, reaches 0, the stack is full, so the FULL register is set, and the EMPTY register is reset. Now, no more push operation is possible with the stack.

The following sequence of micro operations explains the PUSH operation.

SP ← SP + 1;increment stack pointer
M[SP] ← DR;write data into stack from DR
If (SP = = 0) thencheck if stack is full
(FULL ← 1);Mark stack is full
EMPTY ← 0;Mark stack is not empty.

POP Operation

This operation is a memory read operation which retrieves the data from the stack into the DR (data register). This operation is performed by decrementing the stack pointer register. The stack pointer points to the top of the stack.

The POP operation starts with the memory reading operation from the top of the stack and stores that data into the data register DR. Then, after the stack pointer is decremented. If its value reaches to 0, the stack is empty, so the EMPTY register is set, and the FULL register is reset.

The following sequence of microoperations shows the POP operation.

DR ← M [SP];Read data from top of stack
SP ← SP-1;Decrement stack pointer
If (SP = 0) thencheck if stack is empty
(EMPTY ← 1);Mark stack is empty
FULL ← 0;Mark stack is not full.
  1. Note: I. In the above stack architecture, the data at address 0 is the last data in the stack, whereas the first data is stored at address 1.
  2. 2. An erroneous operation will result if the stack is pushed when FULL = 1 or popped when EMPTY = 1.

Reverse Polish Notation (RPN)

The stack organisation is very useful for evaluating arithmetic expressions. The common mathematical method of writing arithmetic expressions imposes difficulties when evaluated by digital systems. There are three types of representation for the arithmetic expressions.

  1. Infix Notation
  2. Prefix Notation or Polish Notation
  3. Postfix Notation or Reverse Polish Notation

Infix Notation

Commonly, arithmetic expressions are written in infix notation. In this notation, each operator is written between the operands. For example addition of two operands A and B is written like.

A + B

The addition operation (+) is written between the operands A and B.

Prefix Notation

The Polish mathematician Lukasriewiez developed the prefix notation representation of arithmetic expressions. Therefore, it is also known as Polish notation. In this notation, the operator is placed before the operands. For example addition of two operands A and B is written like.

+ AB

The addition operator (+) is written before the operands A and B.

Postfix Notation

    The postfix notation, referred to as Reverse Polish Notation (RPN), places the operator after the operands. For example addition of two operands A and B is represented as follows:

    AB +

    The addition operator (+) is placed after the operands A and B. The reverse Polish notation is in a form which is suitable for stack manipulation.

    Conversion from Infix to Postfix Notation

    The conversion from infix (Polish) notation to postfix (reverse Polish) notation must take into consideration the operational hierarchy adopted for infix notation. This hierarchy instructs that first perform all arithmetic inside inner parentheses, then inside outer parentheses, and do multiplication and division before addition and subtraction operations.

    Regardless of the complexity of an expression, no parentheses are required when using reverse Polish notation. The advantage of this notation is that an expression in this form is easily evaluated using a stack.

    RPN Stack Evaluation

    An expression in postfix (reverse Polish) notation is scanned from left to right. For each operand or operator, read follows the following rules:

    1. If the operand is a variable or constant, push it into the stack.
    1. For the operator, pop the top two data from the stack and perform the operator. Now push the result into the stack.

    When the complete expression is scanned, the final result will be at the top of the stack. The basic limitation of postfix notation is that it is less common than other types of architectures and has more difficult programming for many common applications.

    Computer System Architecture engineering subjects