Browsing by Author "CHUNG, CP"

Now showing 1 - 11 of 11

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).
ADOPTABILITY AND EFFECTIVENESS OF MICROCODE COMPACTION ALGORITHMS IN SUPERSCALAR PROCESSING
(1992-05-01)
SHIAU, YH
;
CHUNG, CP
;
交大名義發表
;
資訊科學與工程研究所
;
National Chiao Tung University
Superscalar processing is a technique to improve uniprocessor performance by exploiting instruction-level parallelism to issue and execute more than one instruction per clock cycle. To achieve high performance, the instruction sequence must be arranged so that the maximum instruction-level parallelism and hence the minimum execution time are achieved. Microcode compaction is an essential task in the compilation of high-level language programs into microprograms. Four algorithms are widely used in microcode compaction: the first-come-first-served algorithm, critical path algorithm, branch and bound algorithm, and list scheduling algorithm. The objective of this research is to study the adaptability and effectiveness, and to modify the four algorithms so that they can be applied to the instruction scheduling in a basic block of superscalar processor systems to minimize the execution time of a program. Experiments are conducted to examine the adaptability and effectiveness of each algorithm.
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.
ANALYZING CACHE PERFORMANCE ON MULTI-STREAM EXECUTION PROCESSOR
(1993)
LIN, CZ
;
TSENG, CC
;
CHUNG, CP
;
資訊工程學系
;
Department of Computer Science
BENCHMARKING AND ANALYSIS OF SUPERSCALAR ARCHITECTURE
(1994-03-01)
SHIAU, YH
;
CHUNG, CP
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
Superscalar processing can improve the performance of a single CPU beyond that of traditional RISC machines by exploiting instruction-level parallelism. It is the objective of this study to design a superscalar system which will best exploit a given program's instruction-level parallelism. Three different architectural models, XPCB, XXPB, and X4P2, are used as vehicles in evaluating system performance and the degree of utilization of each individual functional unit. The XPCB model is used as a preliminary model to analyze the loading breakdowns of the various function types. It was found that the performance improvement of the XPCB model relative to a single-instruction stream model is only about 4.3 percent. In addition, the fixed-point operations are in great demand, and dominate the behavior as well as performance of the processor. Two enhanced models, the XXPB and the X4P2, are suggested to improve on the performance of the XPCB model by distributing fixed-point, and even floating-point operation loads among multiple functional units of the same type(s). Simulations show that the XXPB and X4P2 models can improve the performance of the sequential model by 50.8 and 61.6 percent, respectively.
BENCHMARKING AND ANALYSIS OF SUPERSCALAR ARCHITECTURE
(1994-03-01)
SHIAU, YH
;
CHUNG, CP
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
Superscalar processing can improve the performance of a single CPU beyond that of traditional RISC machines by exploiting instruction-level parallelism. It is the objective of this study to design a superscalar system which will best exploit a given program's instruction-level parallelism. Three different architectural models, XPCB, XXPB, and X4P2, are used as vehicles in evaluating system performance and the degree of utilization of each individual functional unit. The XPCB model is used as a preliminary model to analyze the loading breakdowns of the various function types. It was found that the performance improvement of the XPCB model relative to a single-instruction stream model is only about 4.3 percent. In addition, the fixed-point operations are in great demand, and dominate the behavior as well as performance of the processor. Two enhanced models, the XXPB and the X4P2, are suggested to improve on the performance of the XPCB model by distributing fixed-point, and even floating-point operation loads among multiple functional units of the same type(s). Simulations show that the XXPB and X4P2 models can improve the performance of the sequential model by 50.8 and 61.6 percent, respectively.
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.
REACHING APPROXIMATE AGREEMENT ON HYPERCUBE
(1993-07-01)
CHENG, RL
;
CHUNG, CP
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
The interactive convergence algorithm has been used for reaching agreement in systems with multiple procesors. This algorithm must utilize a broadcast mechanism regardless of the underlying architecture. This paper proposes an appropriate algorithm, the local interactive convergence algorithm, for reaching an approximate agreement on systems with high locality. The hypercube is one such system, and it is used as a vehicle for studying the algorithm. This algorithm requires only local information with simple computation. Convergence rate analysis shows that the local interactive convergence algorithm is able to achieve an approximate agreement in a predetermined rate.