We present two new results of importance in code generation for and synthesis of synchronously scheduled parallel processor arrays and multicluster VLIWs. The first is a new practical method for constructing a linear schedule for the iterations of a loop nest that schedules precisely one iteration per cycle on each of a prescribed set of processors. While this problem goes back to the era in which systolic computation was in vogue, it has defied practical solution until now. We provide a closed form solution that enables the enumeration of all such schedules. The second result is a new technique that reduces the cost of code or hardware whose function is to control the flow of data and predicate operations, and to generate memory addresses. The key idea is that by using the mathematical structure of any of the conflict-free schedules we construct, a very shallow recurrence can be developed to inexpensively update these quantities.

Designing compilers for Explicitly Parallel Instruction Computing (EPIC.) architectures presents challenges substantially different from those encountered in designing compilers for traditional sequential architectures. These challenges are addressed not only by employing new optimizations that are specific to EPIC, but also by employing new ways to architect compilers. EPIC architectures provide features that allow compilers to take a proactive role in exploiting instruction level parallelism. Compiler technology is intimately intertwined with the target processor architecture, and compiler architects must solve new analysis and optimization problems to achieve the highest levels of performance. When complex optimizations are uniformly applied to large applications, the resulting slow compile speeds are unacceptable. Demanding requirements to produce high-quality code at high compile speed shapes the fundamental structure of EPIC compilers.

The PICO-N system automatically synthesizes embedded nonprogrammable accelerators to be used as co-processors for functions expressed as loop nests in C. The output is synthesizable VHDL that defines the accelerator at the register transfer level (RTL). The system generates a synchronous array of customized VLIW (very-long instruction word) processors, their controller local memory, and interfaces. The system also modifies the user's application software to make use of the generated accelerator. The user indicates the throughput to be achieved by specifying the number of processors and their initiation interval. In experimental comparisons, PICO-N designs are slightly more costly than hand-designed accelerators with the same performance.

Automated design tools must understand and exploit the hierarchical structure of large design spaces.We have developed a general methodology for decomposing system design spaces into smaller component design spaces, followed by component-level evaluation, filtering, recomposition and system-level evaluation.This methodology greatly reduces the time and cost of design space exploration, since the typical number of system-level evaluations is greatly reduced.This paper describes the application of our decomposition methodology in the context of PICO.PICO is a design space exploration system that automatically generates embedded designs consisting of a stylized processor, hardware accelerator and a cache hierarchy, each customized to a benchmark.First, PICO splits the specified system design space into smaller design spaces, one for each of the components, viz.processor, accelerator and data/instruction/unified caches.PICO further partitions each component design space into predicated design spaces, so that all designs in a predicated design space satisfy a specified predicate.PICO uses component-level evaluations to identify the performance-cost optimal component-level Pareto designs in each predicated design space.PICO generates all compositions of Pareto designs from compatible predicated design spaces and uses a system-level evaluation to identify the Pareto designs at the system level.For reasonable design spaces, PICO reduces the design exploration time by over four orders of magnitude compared to an exhaustive approach.

No abstract available.

We describe a new, practical, constructive method for solving the well-known conflict-free scheduling problem for the locally sequential, globally parallel (LSGP) case of processor array synthesis. First, we provide a closed form solution that enables the enumeration of all conflict-free schedules. Then, we discuss the reduction of the cost of hardware whose function is to control the flow of data, enable or disable functional units, and generate memory addresses. We present a new technique for controlling the complexity of these housekeeping functions in a processor array. Both of these techniques have been incorporated into a software system for the automatic synthesis of hardware accelerators developed by HP Labs.

PICO is a fully automated system for designing the architecture and the microarchitecture of VLIW and EPIC processors. A serious concern with this class of processors, due to their very long instructions, is their code size. One focus of this paper is to describe a series of code size minimization techniques used within PICO, some of which are applied during the automatic design of the instruction format, while others are applied during program assembly. The design of a retargetable assembler to support these techniques also poses certain novel challenges, which constitute the second focus of this paper. Contrary to widely held perceptions, we demonstrate that it is entirely possible to design VLIW and EPIC processors that are capable of issuing large numbers of operational per cycle, but whose code size is only moderately larger than that for a sequential CISC processor.

Code scheduling to exploit instruction level parallelism (ILP) is a critical problem in compiler optimization research in light of the increased use of long-instruction-word machines. Unfortunately optimum scheduling is computationally intractable, and one must resort to carefully crafted heuristics in practice. If the scope of application of a scheduling heuristic is limited to basic blocks, considerable performance loss may be incurred at block boundaries. To overcome this obstacle, basic blocks can be coalesced across branches to form larger regions such as super blocks. In the literature, these regions are typically scheduled using algorithms that are either oblivious to profile information (under the assumption that the process of forming the region has fully utilized the profile information), or use the profile information as an addendum to classical scheduling techniques. We believe that even for the simple case of linear code regions such as super blocks, additional performance improvement can be gained by utilizing the profile information in scheduling as well. We propose a general paradigm for converting any profile-insensitive list scheduler to a profile-sensitive scheduler. Our technique is developed via a theoretical analysis of a simplified abstract model of the general problem of profile-driven scheduling over any acyclic code region, yielding a scoring measure for ranking branch instructions.

As the amount of instruction-level parallelism required to fully utilize VLIW and superscalar processors increases, compilers must perform increasingly more aggressive analysis, optimization, parallelization and scheduling on the input programs. Traditionally, compilers have been built assuming functions as the unit of compilation. In this framework, function boundaries tend to hide valuable optimization opportunities from the compiler. Function inlining may be applied to assemble strongly coupled functions into the same compilation unit at the cost of very large function bodies. This paper introduces a new technique, called region-based compilation, where the compiler is allowed to repartition the program into more desirable compilation units. Region-based compilation allows the compiler to control problem size while exposing inter-procedural optimization and code motion opportunities.

Module scheduling is a framework within which a wide variety of algorithms and heuristics may be defined for software pipelining innermost loops. This paper presents a practical algorithm, iterative module scheduling, that is capable of dealing with realistic machine models. This paper also characterizes the algorithm in terms of the quality of the generated schedules as well the computational expense incurred.

Presents a model of coarse grain dataflow execution. The authors present one top down and two bottom up methods for generation of multithreaded code, and evaluate their effectiveness. The bottom up techniques start from a fine-grain dataflow graph and coalesce this into coarse-grain clusters. The top down technique generates clusters directly from the intermediate data dependence graph used for compiler optimizations. The authors discuss the relevant phases in the compilation process. They compare the effectiveness of the strategies by measuring the total number of clusters executed, the total number of instructions executed, cluster size, and number of matches per cluster. It turns out that the top down method generates more efficient code, and larger clusters. However the number of matches per cluster is larger for the top down method, which could incur higher cluster synchronization costs.>

Instruction-level parallelism in a single stream of code for non-numerical applications has been the subject of many recent researches. This work extends the analysis to symbolic applications described with logic programming. In particular, the authors analyze the effects on performance of speculative execution, memory alias disambiguation, renaming and flow prediction. The obtained results indicate that one can reach a sustained parallelism of 4 (comparable with imperative languages), with the proper optimizations. The authors also show a comparison between static and dynamic scheduled approaches, outlining the conditions under which a dynamic solution can reach substantial improvements over a static one. In this way, they point out some important optimizations and parameters of a dynamic scheduling approach, indicating a guideline for future architectural implementations.>

In this paper we present a set of isomorphic control transformations that allow the compiler to apply local scheduling techniques to acyclic subgraphs of the control flow graph. Thus, the code motion complexities of global scheduling are eliminated. This approach relies on a new technique, Reverse If-Conversion (RIC), that transforms scheduled If-Converted code back to the control flow graph representation. This paper presents the predicate internal representation, the algorithms for RIC, and the correctness of RIC. In addition, the scheduling issues are addressed and an application to software pipelining is presented.

Speculative execution is an important source of parallelism for VLIW and superscalar processors. A serious challenge with compiler-controlled speculative execution is to efficiently handle exceptions for speculative instructions. In this article, a set of architectural features and compile-time scheduling support collectively referred to assentinel schedulingis introduced. Sentinel scheduling provides an effective framework for both compiler-controlled speculative execution and exception handling. All program exceptions are accurately detected and reported in a timely manner with sentinel scheduling. Recovery from exceptions is also ensured with the model. Experimental results show the effectiveness of sentinel scheduling for exploiting instruction-level parallelism and overhead associated with exception handling.

Speculative execution is an important source of parallelism for VLIW and superscalar processors. A serious challenge with compiler-controlled speculative execution is to accurately detect and report all program execution errors at the time of occurrence. In this paper, a set of architectural features and compile-time scheduling support referred to as sentinel scheduling is introduced. Sentinel scheduling provides an effective framework for compiler-controlled speculative execution that accurately detects and reports all exceptions. Sentinel scheduling also supports speculative execution of store instructions by providing a store buffer which allows probationary entries. Experimental results show that sentinel scheduling is highly effective for a wide range of VLIW and superscalar processors.

Software pipelining is an important instruction scheduling technique for efficiently overlapping successive iterations of loops and executing them in parallel. This paper studies the task of register allocation for software pipelined loops, both with and without hardware features that are specifically aimed at supporting software pipelines. Register allocation for software pipelines presents certain novel problems leading to unconventional solutions, especially in the presence of hardware support. This paper formulates these novel problems and presents a number of alternative solution strategies. These alternatives are comprehensively tested against over one thousand loops to determine the best register allocation strategy, both with and without the hardware support for software pipelining.

Interleaved memories are often used to provide the high bandwidth needed by multi- processors and high performance uniprocessors. The manner in which memory locations are distributed across the memory modules has a significant influence on whether, and for which types of reference patterns, the full bandwidth of the memory system is achieved. The most common interleaved memory architecture is the sequentially interleaved memory in which successive memory locations are assigned to successive memory modules. Although such an architecture is the simplest to implement and provides good performance with strides that are odd integers, it can degrade badly in the face of even strides, especially strides that are a power of two. This happens because all the memory references are concentrated on a subset of the memory modules. Pseudo-

Horizontal architectures, such as the CDC Advanced Flexible Processor [I] and the FPS APi20-B [2}, consist of a number of resources that can operate in parallel, each of which is controlled by a field in the wide instruction word. Such architectures have been developed to perform high speed scientific computations at a modest cost: Figure 1 displays those characteristics of horizontal architectures that are germane to the issues discussed in this paper. The simultaneous requirements of high performance and low cost lead to an architecture consisting of multiple pipelined processing elements (PEs) such as adders and multipliers, a memory (which for scheduling purposes may be viewed as yet another PE with two operations: a READ and a WRITE), and an interconnect which ties them all together. The interconnect allows the result of one operation to be directly routed to another PE as one of the inputs for an operation that is to be performed there. The required memory bandwidth is reduced since temporary values need not be written to and read from the memory. The final aspect of horizontal processors that is of interest is that their program memories emit wide instructions which synchronously specify the actions of the multiple and possibly dissimilar PEs. The program memory is sequenced by a conventional sequencer that assumes sequential flow of control unless a branch is explicitly specified.

A horizontal architecture consists of a number of resources that can operate in parallel, each of which is controlled by a field in the wide instruction word. Such architectures offer the potential for high performance scientific computing at a modest cost. If this potential performance is to be realized, the multiple resources of a horizontal processor must be scheduled effectively. The scheduling task for conventional horizontal processors is quite complex and the construction of highly optimizing compilers for them is a difficult and expensive project. The polycyclic architecture is a horizontal architecture with architectural support for the scheduling task. The complexity of scheduling conventional horizontal processors and the ease of scheduling polycyclic processors is demonstrated by means of an example.

An approximate analysis is performed of an often studied model of an interleaved memory, multiprocessor system consisting of M memory modules and N processors. A closed-form solution is obtained and the one approximation used is found to result in negligible error. This solution is about an order of magnitude more accurate than the best previous result.

One of the major factors influencing the performance of an interleaved memory system is the behavior of the request sequence, but this is normally ignored. This paper examines this issue. Using trace driven simulations it is shown that the commonly used assumption, that each request is independently and equally likely to be to any module, is not valid. The duality of memory interference with paging behavior is noted and this suggests the use of the least-recently used stack model to model program behavior. Simulations indicate that this model is reasonably accurate. An accurate, though approximate, expression for the bandwidth is derived based upon this model.

Alternative approaches to the interconnection problem on multilayer boards are studied and evaluated with respect to their desirability and feasability. A brief review of the current methodology is included to highlight those aspects of the current approach that might be improved upon. The conclusion is that a more integrated approach to interconnection on multilayer boards is essential to deriving the maximum benefit from the additional degrees of freedom afforded by a multilayer board. Various such integrated approaches are proposed.