Search

Since its introduction by Joseph A. Fisher in 1979, trace scheduling has influenced much of the work on compile-time ILP (Instruction Level Parallelism) transformations. Initially developed for use in microcode compaction, it quickly became the main technique for machine-level compile-time parallelism exploitation. Although it has been used since the 1980s in many state-of-the-art compilers (e.g., Intel, Fujitsu, HP), a rigorous theory of trace scheduling is still lacking in the existing literature. This is reflected in the ad hoc way compensation code is inserted after a trace compaction, in the total absence of any attempts to measure the size of that compensation code, and so on. The aim of this article is to create a mathematical theory of the foundation of trace scheduling. We give a clear algorithm showing how to insert compensation code after a trace is replaced with its schedule, and then prove that the resulting program is indeed equivalent to the original program. We derive an upper bound on the size of that compensation code, and show that this bound can be actually attained. We also give a very simple proof that the trace scheduling algorithm always terminates. [ABSTRACT FROM AUTHOR]

Embedded block coding with optimized truncation (EBCOT) employed in the JPEG2000 standard accounts for the majority of the processing time, because the EBCOT is full of bit operations that cannot be implemented efficiently in software. The block coder consists of a bit-plane coder (BPC) followed by a binary arithmetic coder (BAC), where the most up-to-date BPC architectures are capable of producing symbols at a much higher rate than the conventional BACs can handle. This letter proposes a novel pipelined BAC architecture that can encode input symbols at a much higher rate than the conventional BAC architectures. The proposed architecture can significantly reduce the critical path delay and can achieve a throughput of 400Msymbols/s. The critical path delay synthesized with 0.18μm CMOS technology is 2.42 ns, which is almost half of the delay taken in conventional BAC architectures. [ABSTRACT FROM AUTHOR]

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 work$ 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. [ABSTRACT FROM AUTHOR]

In developing compiler techniques for programs targeted for parallel execution, it is imperative that a program representation be utilized that not only facilitates the detection and scheduling of parallelism but also easily enables program transformations that increase opportunities for parallelism. These requirements are the driving force behind region scheduling, a technique applicable to both fine grain and coarse grain parallelism. This technique employs a program representation that divides a program into regions consisting of source and intermediate level statements and enables 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, another technique for transforming and detecting fine grain parallelism in programs, are discussed. [ABSTRACT FROM AUTHOR]

Advances in memory and circuit technologies make custom microarchitectures a cost-effective approach to architectures designed to support high-performance applications such as image processing and synthesis. However, the vertical migration of complex application code into horizontal microcode makes traditional methods of handwritten and hand-optimized microcode with primitive assembly languages impractical. Higher level languages that permit abstraction from low-level timing and concurrency details are a major step toward alleviating the problem. This approach is feasible only if compilers for these languages exist that can produce high-quality microcode and that can be targeted to new machines with modest effort and high reliability. In this paper we overview the distinctive aspects of the Horizon retargetable microcode compiler that facilitate the production of highly optimized microcode and the targeting of the compiler to specific machines. [ABSTRACT FROM AUTHOR]

The Multiflow compiler uses the trace scheduling algorithm to find and exploit instruction-level parallelism beyond basic blocks. The compiler generates code for VLIW computers that issue up to 28 operations each cycle and maintain more than 50 operations in flight. At Multiflow the compiler generated code for eight different target machine architectures and compiled over 50 million lines of Fortran and C applications and systems code. The requirement of finding large amounts of parallelism in ordinary programs, the trace scheduling algorithm, and the many unique features of the Multiflow hardware placed novel demands on the compiler. New techniques in instruction scheduling, register allocation, memory-bank management, and intermediate-code optimizations were developed, as were refinements to reduce the overhead of trace scheduling. This article describes the Multiflow compiler and reports on the Multiflow practice and experience with compiling for instruction-level parallelism beyond basic blocks. [ABSTRACT FROM AUTHOR]