Browsing by Author "CHOU, HC"

Now showing 1 - 6 of 6

A BOUND ANALYSIS OF SCHEDULING INSTRUCTIONS ON PIPELINED PROCESSORS WITH A MAXIMAL DELAY OF ONE CYCLE
(1992-04-01)
CHOU, HC
;
CHUNG, CP
;
交大名義發表
;
資訊科學與工程研究所
;
National Chiao Tung University
In this paper we study the problem of scheduling a set of partially ordered instructions with a maximal pipeline delay of one cycle on m processors (or functional units). The ultimate criterion is to minimize the execution of time of the set of instructions. This problem is NP-hard, hence we analyze the worst case of a greedy schedule. since the optimal schedule of this problem is also greedy. Let w(g) and w(o) be the completion times of an arbitrary greedy schedule and the optimal schedule respectively. We find that the bound is w(g)/w(o) less-than-or-equal-to (2-1/2m).
AN OPTIMAL INSTRUCTION SCHEDULER FOR SUPERSCALAR PROCESSOR
(1995-03-01)
CHOU, HC
;
CHUNG, CP
;
交大名義發表
;
資訊科學與工程研究所
;
National Chiao Tung University
Performance in superscalar processing strongly depends on the compiler's ability to generate codes that can be executed by hardware in an optimal or near optimal order, Generating optimal code is an NP-complete problem. However, there is a need for highly optimized code, such as in superscalar or real-time systems, In this paper, an instruction scheduling scheme for optimizing a program trace is proposed. Optimized code can be arrived at without much redundant work, if some important features in code are well explored and utilized in scheduling. To formalize the task, two abstract models, one for a superscalar processor and the other for a program trace, are given, These two models reflect most of the characteristics of the scheduling problem. The interrelations between instructions and partial schedules are thoroughly studied, and dominance and equivalence relations on them are defined, These relations are then used to reduce the solution space and eventually help to produce optimal schedules. The results of experiments that show the promise of the proposed scheme are also presented.
DUAL-ALU CRISC ARCHITECTURE AND ITS COMPILING TECHNIQUE
(1991)
CHOU, HC
;
CHUNG, CP
;
CHENG, SC
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
As semiconductor technology advances, more devices can be accommodated in a single VLSI chip. The feasibility of putting multifunctional units in a chip is then worth studying. Such an approach, however, will face software and hardware difficulties (and also tradeoffs). CRISC is a 32-bit single-chip VLSI processor architecture achieving high performance by means of RISC and multiple functional unit approaches. Dual-ALUs are used to execute instructions concurrently for fine-grained parallelism. Up to three instructions can be executed simultaneously by CRISC. Here, CRISC architecture design considerations and instruction cache scheme are investigated. Final microarchitecture and its incorporated software technique to produce object code for fine-grained parallel execution are described; its upper bound performance is estimated by an architectural model. A preliminary evaluation of the CRISC is also conducted, showing most satisfying results.
MODELING OF SUPERSCALAR INSTRUCTION SCHEDULING AND ANALYSIS OF A HEURISTIC SCHEDULING ALGORITHM
(1993)
CHOU, HC
;
CHUNG, CP
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
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.
ON THE UPPER BOUND OF SCHEDULING INSTRUCTIONS ON PIPELINED PROCESSORS WITH DELAY
(1995-01-01)
CHOU, HC
;
CHUNG, CP
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
Several high performance microprocessor systems have been developed in recent years. Other than the fact that the system clocks were pushed to a higher rate than before, these systems were improved throughout by issuing more than one instruction within a cycle. Due to their increasingly complex pipeline structures as well as employment of multiple functional units, object codes of these systems are in general required to be reorganized in order to keep functional units busy and to avoid pipeline interlocks. Success of such a system design hence depends on not only how many hardware resources it provides, but primarily how efficiently these resources can be utilized. In this paper we analyze the worst case of applying a greedy method to schedule a set of instructions on m pipelined processors or functional units. Each instruction under discussion here will incur a delay of at most z cycles after it is issued to execute. The ultimate criterion is to minimize the completion time of the last completed instruction. The problem is NP-hard. Let w(g) be the length of an arbitrary greedy schedule on m processors, and w(o) be the length of an optimal schedule on m' processors. We prove that w(g)/w(o) less than or equal to (1+m'/m-1/((z+1)m)). The results of this research can serve as the basis for superscalar instruction scheduling as well as some other related fields, such as superscalar architecture designs.
OPTIMAL MULTIPROCESSOR TASK-SCHEDULING USING DOMINANCE AND EQUIVALENCE-RELATIONS
(1994-04-01)
CHOU, HC
;
CHUNG, CP
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
We propose an optimization scheme for unit-execution-time task scheduling on multiprocessors. In this scheme, dominance, semi-dominance, equivalence and semi-equivalence relations between tasks are first defined. The solution tree technique is adopted to keep track of the unfinished sub-schedules. We prove that when certain conditions are satisfied, a sub-schedule need not be explored further, since it cannot lead to a schedule better than some others. An algorithm that avoids generating such non-optimal schedules is presented. Then we conduct experiments to show the promise of our scheme in reducing solution space. Another advantage of this scheme is its extensibility. This scheme can easily be applied to other scheduling problems by simply adding additional constraints to the original definitions of the dominance, semi-dominance, equivalence and semi-equivalence relations.