UPPER BOUND ANALYSIS OF SCHEDULING ARBITRARY-DELAY INSTRUCTIONS ON TYPED PIPELINED PROCESSORS

作     者：HONG-CHICH CHOU CHUNG-PING CHUNG 

作者机构：Institute of Computer Science and Information Engineering National Chiao Tung University Taiwan Republic of China 

出 版 物：《International Journal of High Speed Computing》 

年 卷 期：1992年第4卷第4期

页      面：301-312页

主　　题：Instruction scheduling algorithm analysis NP-completeness superscalar architecture compiler greedy algorithm 

摘      要：In this paper we study the problem of schedule upper bound of a set of different types and partially ordered instructions with a maximal pipeline delay of z cycles, where z is an arbitrary integer, on k types of pipelined processors (or functional units). The goal of this scheduling is to minimize execution time for these instructions. This problem is NP-hard, so we analyze the worst case of any greedy schedule, since the optimal schedule of this problem can always be transformed into a greedy form. Let w g and w 0 be the completion times of an arbitrary greedy schedule and the optimal schedule, respectively. With each type containing m i processors, for 1 ≤ i ≤ k, we establish a bound that w g /w 0 ≤ (k + 1 − 1/(z + 1)* max{m i }) and show also that this bound is best possible.