A. Elamawy et Yc. Tseng, MAXIMUM PERFORMANCE PIPELINES WITH SWITCHABLE RESERVATION TABLES, I.E.E.E. transactions on computers, 44(8), 1995, pp. 1066-1069
We describe a new technique for achieving maximum performance in pipel
ines which allows task initiations to follow any arbitrary cycle provi
ded that the average time between initiations is less than or equal to
M, where M is the maximum number of reservations of any stage. This i
s not possible with the existing methods. The idea behind the proposed
scheme is to allow different initiations to follow different reservat
ion tables. This contrasts existing methods which require all initiati
ons in a cycle to follow the same reservation table. We describe an al
gorithm for systematic construction of the reservation tables for diff
erent initiations in any cycle whose performance does not exceed the t
heoretical upper bound on throughput. We formally prove that the algor
ithm is correct and that it will always succeed in constructing the ta
bles.