JPH01126729A - Stack storage device - Google Patents

Abstract

PURPOSE:To efficiently execute stack operation by realizing the stack operation with a stack base counter, which designates the base of a high speed memory, and a stack top counter to designate a memory address for push/pop operation. CONSTITUTION:The push operation in an initial condition is realized by addressing the contents of a stack TOP counter (ST)30 through a line 301, a selector 11 and a line 111 and writing the contents of a data register to the 00-address of a high speed memory and the ST30 is 1-added after this writing. This value is given through the line 301, a selector 71 and a line 711 to a coinciding circuit 70. For the other input of the coinciding circuit 70, a value to be subtracted only by 1 is inputted from a stack base counter (SB)40. When the coinciding circuit 70 detects coincidence, the both values of the ST30 and the SB40 are '00' and this shows a condition that the entry of the high speed memory 10 is wholly used. When the push operation is executed in such a condition, a save processing is executed to sweep out the contents of the high speed memory 10 to an external memory 20.

Description

[Detailed Description of the Invention] (Industrial Application Field) The present invention efficiently realizes the stack function in a computer with less hardware, thereby increasing processing speed and making it possible to use complex application programs in a wide range of applications. It is for.

(Prior Art) The stack function is a function that temporarily saves the state during computer operation and returns to the saved state when other related operations are completed, and has been frequently used since ancient times. This is a basic function. In general, a stack must be constructed so that it can hold a logically infinite number of entries by stacking multiple states one after another. However, in reality, it is difficult to realize all of this with hardware due to quantitative limitations of hardware. Efforts to solve this problem are complex and have traditionally been realized using software and microprograms.

(Problems to be Solved by the Invention) Stack operations occur very frequently, and the efficiency with which they are realized greatly affects system efficiency. Efficiency is particularly important in the execution of languages such as LISP and PROLOG that include stack operations as a basic mechanism of the programming language itself. In order to create a state in which an infinite number of logical states can be stored, software and firmware have conventionally been implemented as a basic function of a system, but this has had many problems in terms of efficiency and the limits of system resources. Therefore, many inventions have been made in the past, but when they are implemented using hardware support, the amount of hardware tends to increase in response to complex operations.

More specifically, detection of the timing for swapping between two memory hierarchies and the efficiency of the actual swapping operation are major problems.

) An object of the present invention is to provide a stack storage device that solves these problems.

(Means for Solving the Problems) The present invention includes a high-speed memory for storing power-of-two entries used as a stack, an external memory for saving stack contents, a stack top counter, and a stack top counter.・A base counter, a subtracter A that generates an output by subtracting the contents of the two types of counters by 1, a subtracter B that generates an output by subtracting the contents of the stack base counter by 1, and the two types of counters described above. and a match circuit that compares the contents of the counter and the outputs of the subtracter A and the subtracter B to detect a match, and the stack base counter is counted up/down by a carry to the top and a down by one digit signal. It consists of a block counter,
In a stack push operation, when the coincidence circuit detects that all the entries in the memory are filled, the contents of the high-speed memory are saved in the external memory until the state of the block counter is changed, and the stack pop operation is performed. When the matching circuit detects that the contents of the memory are all empty, the data group is always stored at the top of the stack by returning to the faster memory than the external memory 1 until the state of the block counter is changed. The stack memory is characterized in that the high-speed memory stores the following information.

(Function) The stack function retains the state at a certain point in time, then successively retains the state at subsequent points in time, and when accessed, outputs the most recently held state (Last In First Out).
This is realized using memory (LIFO memory). At Uni, the former is called a button operation, and the latter is called a pop operation. Logically, the button operation should be performed an infinite number of times, but there is a limit to the amount of hardware available. In order to efficiently perform stack operations, a small amount of fast but expensive memory is combined with a slow but cheap memory that can be increased in capacity.

In other words, since the most recently bushed state has the highest possibility of being accessed, it is desirable to store it in the fastest possible memory. Here, the push operation to the fast memory continues, and when the fast memory is overflowed, the oldest state is flushed to the slow memory,
High speed memory must be cleared for subsequent bush operations. The timing of this content replacement and speeding up of the replacement process are important.

The stack memory of the present invention realizes stack operations by a stack base counter pointing to the base of the high speed memory and a stack top counter pointing to the address of the memory for push/pop operations, and also detects whether the high speed memory overflows. This is to detect by hardware whether or not the content is present, and to realize a high-speed content replacement operation.

(Example) Hereinafter, an example of the stack memory of the present invention will be described in detail using the drawings.

FIG. 1 is a block diagram showing one embodiment of the present invention. In the figure, 10 is a high-speed memory that stores entries of powers of 2 used as a stack, 20 is an external memory, and 30
is a stack top counter (abbreviated as ST), 40 is a stack base counter (abbreviated as SB), 50 is a subtracter A, 60 is a subtracter B, 70 is a coincidence circuit, 80 is a block counter, 11, 51, 71 .72 is a selector.

For simplicity, an example will be described in which the number of entries (addresses) in the high-speed memory 10 is four. In the initial state, both 5T30 and 5B40 are set to "00" and the contents of the block counter 80 are cleared to zero.

(Bush operation) When a push button operation is performed, each selector is set to the following state. That is, the input of selector 11 is line 3
01, the line 301 is selected as the input to the selector 71, and the line 601 is selected as the input to the selector 72. The button operation in the initial state is such that the contents of 5T30 are addressed via line 301, selector 11, and line 111, and the contents of 5T30 are addressed to “00” of high-speed memory 10.
This is achieved by writing the contents of a data register (not shown) to the address, and 5T30 is incremented by 1 after this writing is completed.In other words, the output of 5T30 becomes RQlt+ at the end of writing, and is ready for the next bushing operation. A preparation is made. This value is given as one input of the matching circuit 70 via line 301, selector 71 and line 711. The other input of the -number circuit 70 is the value 5B40 minus 1, i.e. '11''. - Since the several circuits do not detect a match at this point, no further operation occurs.

When the bushing operation is subsequently performed, the same operation as described above is executed until the coincidence circuit 70 detects a coincidence.

(Saving process) 5T30 and 5B4 when the matching circuit 70 detects a match
Both values of 0 are "oo'", indicating that all entries in the high-speed memory 10 are used. If a push button operation is performed in this state, it will be necessary to perform a save process to flush out the contents of the high-speed memory 10 to the external memory 20. The states of each selector at this time are as follows. That is, line 401 is selected as the input to selector 11, line 301 is selected as input to selector 51, line 501 is selected as input to selector 71, and line 401 is selected as input to selector 72. From then on high speed memory 1
0 is saved to the external memory 20. First, 5
The contents of B40 are given as an address to the high-speed memory 10, and after the contents of address "oo'" are transferred to the external memory 20, the value of 5B40 is incremented by one. The output of the most significant digit of 5B40 is provided to block counter 80 via line 402 and is counted up when a carry occurs.

The above operation is performed until this block counter 80 is updated. In other words, half the amount of high-speed memory 10 is saved.

The content of 5B40 at the time when the saving of the final entry is completed is "10". Therefore, the subsequent stack base becomes the top position of the second half of the high speed memory 10.

From this state, further push operations are performed, and when the high-speed memory 10 becomes full again, the content of the block counter 80 is not 0, so the latter half of the high-speed memory 10 is evacuated, and the stack base is updated to address "oo" again. . The end of the subsequent return process is when the contents of the block counter 80 are updated by the most significant carry of 5B40.

(Pop operation) The state of each selector when a pop operation is performed is as follows. That is, the input of the selector 11 is the line 50
1. The line 301 is selected as the input to the selector 51, the line 501 is selected as the input to the selector 71, and the line 401 is selected as the input to the selector 72. Since 5T30 indicates the address of the high speed memory 10 to be bushed next, the subtracter 50 reads the previous address by 1 in the pop operation. When this reading is completed, 5T30 is subtracted by 1. - 5B for the number circuit 70
A value of 40 and a value obtained by subtracting 1 from the value of 5T30 are input. The pop operation is realized by repeating the above operation until the minus number circuit 70 detects a match.

(Return Process) The states of each selector when the return process is performed are as follows. That is, the input of the selector 11 is the line 501
, the line 401 is selected as the input to the selector 51, the line 301 is selected as the input to the selector 71, and the line 601 is selected as the input to the selector 72. During the pop operation, the matching circuit 70 detects a match when the content of 5B30 is '01' and the content of 8B40 is '00'. Immediately after this, 5T30 is ROO
ll, and if a pop operation is performed at this point, address &11111 is accessed. Here, if it is detected that the save process was previously performed because the contents of the block counter 80 are not '0', the restore process must be performed.
It is performed to the address "11'" which is 1 subtracted from 0,
When the reading is completed, the value of 5B40 is subtracted by 1. This operation is repeated until the block counter 80 is updated by the most significant carry of 8B40.

This operation restores half the contents of high speed memory 10 to high speed memory 1o.

The contents of the embodiment have all been explained through the explanation of the four types of operations described above.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing one embodiment of the present invention. In the figure, 10 is a high-speed memory that stores entries of powers of 2 used as a stack, 2o is an external memory,
30 is a stack top counter (abbreviated as ST); 4
0 is the stack base counter (abbreviated as 'SB), 5
0 is subtracter A, 60 is subtracter B, 70 is matching circuit, 80
is a block counter, and 11, 51, 71.72 are selectors. Juzo Iizuka, Director of the Agency of Industrial Science and Technology

Claims (1)

[Claims] A high-speed memory for storing power-of-2 entries used as a stack, an external memory for saving the stack contents, a stack top counter, a stack base counter, and the contents of the two types of counters are subtracted by 1. a subtracter A that generates an output that is obtained by subtracting the contents of the stack base counter by 1; a subtracter B that generates an output that is obtained by subtracting the contents of the stack base counter by 1; and the contents of the two types of counters and the outputs of the subtracter A and the subtracter B. and a flip-flop that is counted up/down by a carry/down signal to the top of the stack base counter, and in a stack push operation, the memory is When it is detected that all the entries in the block counter are filled, the contents of the high-speed memory are saved to the external memory until the state of the block counter is changed, and the contents of the memory are saved by the matching circuit in a stack pop operation. When it is detected that the block counter is completely empty, the data group at the top of the stack is always held in the high-speed memory by returning from the external memory to the high-speed memory until the state of the block counter is changed. Stack storage device.