MODELING OF SUPERSCALAR INSTRUCTION SCHEDULING AND ANALYSIS OF A HEURISTIC SCHEDULING ALGORITHM
檔案
- A1993LZ68700001.pdf (901.1 KB, Adobe PDF)
日期
1993
類型
系所
期刊名稱
BIT
卷期與頁次
第 33 卷第 3 期,頁 354–371
ISSN
0006-3835
語言
英文
摘要
The problem of superscalar instruction scheduling is studied and an analysis of a heuristic scheduling algorithm is presented. First, a superscalar architecture is characterized by k, the number of types of functional units employed, m(i), the number of type i functional units, P(ij), the jth functional unit of type i, and z, the maximal number of delay cycles incurred by the execution of instructions. A program trace to be scheduled is modeled by a directed acyclic graph with delay on precedence relations. These two models reflect most of the flavor of the superscalar instruction scheduling problem. A heuristic scheduling algorithm called the ECG-algorithm is designed by compiling two scheduling guidelines. The performance of the ECG-algorithm is evaluated through worst-case analysis. Letting w(ECG) denote the length of an ECG-schedule and w(opt) the length of an optimal schedule, we established the bound w(ECG)/w(opt) less-than-or-equal-to k + 1 - 2/[max {m(i)}(z + 1)], which is smaller than other known bounds.