Design and Implementation of Stack Pointer

Overview

The stack pointer is supposed to take in a two bit input and produce a 3 bit address and a stack full bit as an output. The 2 bit input (S1 and S0) and their correspondence to the operation of the stack pointer are shown in the table below. For a block diagram of the stack pointer please refer to the figure below.

S1	S0	Instruction Mapping
0	0	Clear
0	1	Hold
1	0	Push
1	1	Pop

Block Diagram

[Stack Pointer Overview]

As a convention for the stack pointer, it was decided to use speculative prediction and have two pointers. One pointer points to the next push location (output of the positive edge register) and the pop pointer (address flowing from the decrementor to the third mux). This assures that the word lines will be valid once the S1 and S0 inputs comes since the third mux can choose one of these address pointers.

It was also decided that a stack access should only take one clock cycle and hence, the stack pointer had to supply a valid address on the high part of the clock and the read or write operation to occur on the low part of the clock. The following sections discuss when the inputs become valid; what happens in the stack pointer given one of the four different possible inputs (clear, hold, push and pop); and some timing considerations.

Input Data Validity

The input data S1 and S0 will be valid a little after the clock edge. This is because of the delay from the outside inputs to propagate through the ROM which supplies S1 and S0.

Clear

On a clear, the second mux (that is the one with S1 as a selector) chooses the 4 bit input on the 0 selector side. This input is an AND of S0 and the current pointer which results in an output of 0 (since S0 is 0), thus resetting the counter to zero on the next clock edge.

Note that clearing is an operation that does no memory accesses such that it is not important what the pointer to the memory is at the time of a clear. The pointer just needs to be set to zero on the next clock edge.

Hold

Similar to the clear, there is really no memory access on a hold and it should just be assured that the address pointers do not change. This is assured by the third second mux selecting the 0 input which for this case is just the current output of the positive edge register AND'ed with S0=1.

Push

When a push instruction comes, the push pointer has to flow through to the stack memory and be valid on the low part of the clock. This is done by the third mux which lets the output of the positive register (push pointer) through. The presence of the negative edge register at the end will be discussed later in the timing considerations.

Since a push is made, the pointers needs to be changed to point to the next memory location for the next push. This is done by the combinational logic to the left of the positive edge register. Keeping in mind that S1=0 and S1=1, it can be easily seen that the incrementor output will pass through as the input to the positive edge register which will be latched at the next clock edge.

Pop

On a pop instruction, the pop pointer should be let through to the stack memory. This is done by the third mux through the negative edge register. And similar to the push instructions, the pointer will be updated by the combinational logic to the right of the positive edge register.

Timing Considerations

Since the write operation of the stack memory will be on the low edge of the clock and possible flowing through a little to the next clock cycle, the word lines should be assured to be valid a little after the the clock cycle. Thus, this explains the presence of the negative edge register which will hold the address lines valid until the next falling edge. A graph representing the timing diagram is shown below.

[Stack Timing]

Comments to benleong@mit.edu or mike_sy@mit.edu or sclee@mit.edu
Last updated 11/21/96.