Search

This paper presents an instruction scheduling algorithm for clustered very long instruction words (VLIW) architectures. It exploits a path-dividing-based technique to decide a more appropriate processing order of instructions, and utilizes a more global view to generate the scheduling result by simultaneously considering the influence of both data dependence relations between instructions and distribution of instructions among clusters. The algorithm is composed of two stages. The first stage virtually schedules all the instructions based on the path-dividing technique. The cluster virtually assigned in the first stage is delivered to the second stage. While the cycle virtually scheduled in the first stage is only used in this stage for the purpose of taking into account the implications between cluster assignment and cycle scheduling. The second stage performs actual scheduling according to the cluster assignment decisions made in the first stage and generates final scheduling results. The proposed algorithm is implemented and evaluated with benchmarks extracted from UTDSP and MediaBench. Results show that the improvement is impressive. Besides producing a large reduction in energy consumption, the algorithm can also make a remarkably performance speed-up. The average energy consumption ranges from 28.1% (4-Clusters) to 37.3% (8-Clusters). And the average speed-up ranges from 29.9% (4-Clusters) to 39.1% (8-Clusters).

With technology scaled to nanometer-scale, leakage energy consumption is accounting for a greater proportion than ever, especially for very long instruction word (VLIW) architectures with a large number of functional units (FUs). The growing energy consumption leads to an increase in chip temperature, which again brings an exponential growth in leakage current, and consequently leakage energy. However, few studies consider both leakage energy and temperature reduction during the compiling on VLIW architectures. In this paper, a leakage- and temperature-aware design flow is presented to assist the compiling of instruction-level VLIW scheduling. And two scheduling algorithms are proposed for the design flow. First, the leakage-aware rescheduling algorithm is proposed for leakage energy reduction by concentrating operations to fewer FUs and shutting more FUs down. Then, the temperature-aware workload balance algorithm is presented to reduce peak temperature by balancing the concentrated workloads among homogenous FUs. It is proved that the proposed two algorithms can reduce the leakage energy and peak temperature without performance loss. Experimental results demonstrate that the peak temperature is reduced by 15.27% and 12.84% for FU groups with three and two FUs and the leakage energy is reduced by 78.14% and 30.31% on average compared with the communication scheduling and list algorithm, respectively.

Very long instruction word (VLIW) refers to a computer architecture and algorithms that take advantage of large amounts of instruction level parallelism (ILP). Joseph A. (Josh) Fisher, a former Yale professor and a Hewlett-Packard Senior Fellow, introduced VLIW architecture in the early 1980s. The insights underlying Fisher's invention of VLIW came to him when he was a graduate student at New York University's Courant Institute in the late 1970s. He was microcoding a clone of the Control Data Corporation (CDC) 6600 computer. To maximize the performance of the clone, called PUMA, he used a standard trick of writing microcode with many concurrent operations. In doing so, he realized he could get even more concurrency and performance by moving operations speculatively above branches. His study of this motion, and how it violated the laws of computer architecture of the day, led to his invention of the trace scheduling compiler algorithm. He wrote his Ph.D. thesis about trace scheduling. He later became a professor at Yale University, where he started the Extremely Long Instruction (ELI) project, which developed the architecture for the trace scheduling compiler.

This paper presents a system in which the already executing user code is continually and automatically reoptimized in the background, using dynamically collected execution profiles as a guide. Whenever a new code image has been constructed in the background in this manner, it is hot-swapped in place of the previously executing one. Control is then transferred to the new code and construction of yet another code image is initiated in the background. Two new runtime optimization techniques have been implemented in the context of this system: object layout adaptation and dynamic trace scheduling. The former technique constantly improves the storage layout of dynamically allocated data structures to improve data cache locality. The latter increases the instruction-level parallelism by continually adapting the instruction schedule to predominantly executed program paths. The empirical results presented in this paper make a case in favor of continuous optimization, but also indicate some of the pitfalls and current shortcomings of continuous optimization. If not applied judiciously, the costs of dynamic optimizations outweigh their benefit in many situations so that no break-even point is ever reached. In favorable circumstances, however, speed-ups of over 96 percent have been observed. It appears as if the main beneficiaries of continuous optimization are shared libraries in specific application domains which, at different times, can be optimized in the context of the currently dominant client application.

In this paper I introduced the term VLIW. VLIW was motivated by a compiler technique, and, for many readers, this paper was their introduction to "region scheduling" as well. I had put forward the first region scheduling algorithm, called trace scheduling, a few years before. Since region scheduling is a compiler technique, it is of interest to fewer people, but it enables superscalars and VLIWs with lots of instruction-level parallelism (ILP). Because I could see the power of region scheduling, I first began to think about VLIWs. I was fortunate in that this allowed me to coin the term instruction-level parallelism, and to work out a lot of the original details and terminology of ILP, before many others believed it was important.

We consider the resource-constrained scheduling of loops with inter-iteration dependencies. A loop is modeled as a data flow graph (DFG), where edges are labeled with the number of iterations between dependencies. We design a novel and flexible technique, called rotation scheduling, for scheduling cyclic DFGs using loop pipelining. The rotation technique repeatedly transforms a schedule to a more compact schedule. We provide a theoretical basis for the operations based on retiming. We propose two heuristics to perform rotation scheduling, and give experimental results showing that they have very good performance.

We present a programming language called TCEL (Time-Constrained Event Language), whose semantics are based on time-constrained relationships between observable events. Such a semantics infers only those timing constraints necessary to achieve real-time correctness, without overconstraining the system. Moreover, an optimizing compiler can exploit this looser semantics to help tune the code, so that its worst-case execution time is consistent with its real-time requirements. In this paper we describe such a transformation system, which works in two phases. First, the TCEL source code is translated into an intermediate representation. Then an instruction-scheduling algorithm rearranges selected unobservable operations and synthesizes tasks guaranteed to respect the original event-based constraints. >

Detecting independent operations is a prime objective for computers that are capable of issuing and executing multiple operations simultaneously. The number of instructions that are simultaneously examined for detecting those that are independent is the scope of concurrency detection. The authors present an analytical model for predicting the performance impact of varying the scope of concurrency detection as a function of available resources, such as number of pipelines in a superscalar architecture. The model developed can show where a performance bottleneck might be: insufficient resources to exploit discovered parallelism, insufficient instruction stream parallelism, or insufficient scope of concurrency detection. The cost associated with speculative execution is examined via a set of probability distributions that characterize the inherent parallelism in the instruction stream. These results were derived using traces from a Multiflow TRACE SCHEDULING compacting FORTRAN 77 and C compilers. The experiments provide misprediction delay estimates for 11 common application-level benchmarks under scope constraints, assuming speculative, out-of-order execution and run time scheduling. The throughput prediction of the analytical model is shown to be close to the measured static throughput of the compiler output. >

Region scheduling, a technique applicable to both fine-grain and coarse-grain parallelism, uses a program representation that divides a program into regions consisting of source and intermediate level statements and permits the expression of both data and control dependencies. Guided by estimates of the parallelism present in regions, the region scheduler redistributes code, thus providing opportunities for parallelism in those regions containing insufficient parallelism compared to the capabilities of the executing architecture. The program representation and the transformations are applicable to both structured and unstructured programs, making region scheduling useful for a wide range of applications. The results of experiments conducted using the technique in the generation of code for a reconfigurable long instruction word architecture are presented. The advantages of region scheduling over trace scheduling are discussed. >

Clustered organizations are becoming a common trend in the design of VLIW architectures. In this work we propose a novel modulo scheduling approach for such architectures. The proposed technique performs the cluster assignment and the instruction scheduling in a single pass, which is shown to be more effective than doing first the assignment and later the scheduling. We also show that loop unrolling significantly enhances the performance of the proposed scheduler especially when the communication channel among clusters is the main performance bottleneck. By selectively unrolling some loops, we can obtain the best performance with the minimum increase in code size. Performance evaluation for the SPECfp95 shows that the clustered architecture achieves about the same IPC (Instructions Per Cycle) as a unified architecture with the same resources. Moreover when the cycle time is taken into account, a 4-cluster configurations is 3.6 times faster than the unified architecture.

Microcode compaction is the conversion of sequential microcode into efficient parallel (horizontal) microcode. Local compaction techniques are those whose domain is basic blocks of code, while global methods attack code with a general flow control. Compilation of high-level microcode languages into efficient horizontal microcode and good hand coding probably both require effective global compaction techniques.

The PQCC experience reveals that—contrary to common practice and belief—retargetability and a high level of optimization are not incompatible.

An overview of and survey solutions to the problem of instruction scheduling for pipelined computers are provided. The author demonstrated that dynamic instruction scheduling can provide performance improvements not possible with static scheduling alone. He describes a high-performance computer, the Astronautics ZS-1, which uses novel methods for implementing dynamic scheduling and which can outperform computers using similar-speed technologies that rely solely on state-of-the-art static scheduling techniques. >

Long instruction word architectures, such as attached scientific processors and horizontally microcoded CPU's, are a popular means of obtaining code speedup via fine-grained parallelism. The falling cost of hardware holds out the hope of using these architectures for much more parallelism. But this hope has been diminished by experiments measuring how much parallelism is available in the code to start with. These experiments implied that even if we had infinite hardware, long instruction word architectures could not provide a speedup of more than a factor of 2 or 3 on real programs.