MAXIMUM PERFORMANCE PIPELINES WITH SWITCHABLE RESERVATION TABLES

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.