High-speed top-of-stack scheme for VLSI processor
Makoto Hasegawa, Yoshiharu Shigei · ACM SIGARCH Computer Architecture News · 1985
The Top-Of-Stack(TOS) register is a high-speed storage which hold the top portion of the frequently used stack entries.We propose a Cut-Back-K algorithm, a sophisticated algorithm for TOS register management, to speed up the stack operation.The performance of this algorithm is analyzed with random-walk model.The effective stack access time with this algorithm can be as fast as the inherent access time of the TOS register in appropriate configurations.The inherent access time of TOSregister formed by on-chip shift register is proportional to O(1)~O(log N) for N cells.On the other hand, N elements arrav of dual-ports register takes O(N 27k) minimum access delay (k:some constant) .