MODELING OF SUPERSCALAR INSTRUCTION SCHEDULING AND ANALYSIS OF A HEURISTIC SCHEDULING ALGORITHM

檔案

日期

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.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

CHOU, H., & CHUNG, C. (1993). MODELING OF SUPERSCALAR INSTRUCTION SCHEDULING AND ANALYSIS OF A HEURISTIC SCHEDULING ALGORITHM. BIT, 33(3), 354–371. https://doi.org/10.1007/BF01990519

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/3191