標題: MODELING OF SUPERSCALAR INSTRUCTION SCHEDULING AND ANALYSIS OF A HEURISTIC SCHEDULING ALGORITHM
作者: CHOU, HC
CHUNG, CP
資訊科學與工程研究所
Institute of Computer Science and Engineering
關鍵字: SCHEDULING;PARALLEL PROCESSING;HEURISTIC METHODS;WORST-CASE ANALYSIS
公開日期: 1993
摘要: 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.
URI: http://hdl.handle.net/11536/3191
http://dx.doi.org/10.1007/BF01990519
ISSN: 0006-3835
DOI: 10.1007/BF01990519
期刊: BIT
Volume: 33
Issue: 3
起始頁: 354
結束頁: 371
Appears in Collections:Articles


Files in This Item:

  1. A1993LZ68700001.pdf