In conventional compilation, register allocation—the mapping of program variables to the registers of the target architecture—plays an important role in the performance of application code. In particular, for load/store architectures, good register allocation is exceedingly important as all operands to instructions, in this type of architecture, must be contained within the register set.

Typical processors selected as the core unit or core processor for an embedded system closely resemble the load/store or RISC-type of architecture, and, thus, conventional register allocation techniques are applicable in the generation of code for an embedded processor. However, architectural features of the core processor, features designed to reduce core size/cost and/or are specific to the target application area for improved performance—such as disjoint register files and/or requirements that operands to particular instructions reside in specialized registers—complicate the register allocation process. This, coupled with the time-sensitive nature of typical embedded applications necessitates high-quality register allocation.

Loops are the main source of parallelism in applications. The issue of finding an optimal register allocation to loops has been an open issue for some time. In this case optimal refers to the minimization of spills from registers to memory. In this paper we address this issue and present an optimal, but exponential algorithm which allocates registers to loop bodies such that the spill code is minimal. We also show heuristic modifications to the algorithm which perform in practice as well as the exponential approach. Finally, we examine this algorithm's feasibility in production compilers.

In this paper we present a new transformation for the scheduling of memory accessing operations in High-Level Synthesis. This transformation is suited to memory-intensive applications with synthesized designs containing a secondary store accessed by explicit instructions. Such memory-intensive behaviors are commonly observed in video compression, image convolution, hydro-dynamics and mechatronics. Our transformation removes load instructions which become redundant during the transformation of loops. The advantage of this reduction is the decrease of secondary memory bandwidth demands. Our experiments on benchmarks from several application areas show that a significant reduction in the number of memory loads is obtainable.

One of the challenging tasks in code generation for embedded systems is register assignment. When more live variables than registers exist, some variables will necessarily be accessed from data memory. Because loops are typically executed many times and are often time-critical, good register assignment in loops is exceedingly important as accessing data memory can degrade performance. The issue of finding an optimal register assignment to loops has been open for some time. In this paper, we present a technique for optimal (i.e., spill minimizing) register assignment to loops. First, we present a technique for register assignment to processor cores which are characterized by a consolidated register file. Then, we extend the technique to include architecture styles which are characterized by the partitioning of registers into multiple register files and/or a combination of general - and special - purpose registers. Experimental results demonstrate that, while the optimal algorithm may be computationally prohibitive, heuristic versions obtain results with performance better than that of an existing graph coloring approach.

Loops are the main source of parallelism in applications. The issue of finding an optimal register allocation to loops has been an open issue for some time. In this case optimal refers to the minimization of spills from registers to memory. In this paper we address this issue and present an optimal, but exponential algorithm which allocates registers to loop bodies such that the spill code is minimal. We also show heuristic modifications to the algorithm that performs as well as the exponential approach on typical loops from scientific code. Finally, we examine this algorithm's feasibility in production compilers.

Previously Percolation Based Synthesis (PBS) was proposed as a new approach to the task of scheduling in High-Level Synthesis and demonstrated favorable results. PBS is an adaptation of well-founded compiler techniques with several desirable properties (e.g. flexibility, completeness and optimality). However, the granularity of the PBS scheduler is at the functional unit level. Schedules generated at this level do not necessarily represent the best obtainable performance as they do not exploit the lower level aspects of the functional units. By scheduling at a lower level more efficient and effective schedules can be generated by utilizing the lower level information. This lower-level granularity is termed the ultra fine-grain level and the resources at this level correspond to the hardware components that are sequenced via the control unit during each clock (sub-) cycle. Therefore the schedules produced with this technique are suitable for control unit construction. The resulting impact is that it allows the ultra fine-grain code scheduler to apply parallelization techniques in the presence of low-level constraints and to utilize the underlying architecture in novel ways. In this paper we discuss the enhancement of PBS which allows the exploitation of the ultra fine-grain level. While it may seem that, due to the finer granularity, code size might increase beyond manageability, our experiments have shown that on the standard benchmark set, this was not a prohibitive factor. In fact, the increase in run-time of the code scheduler is within acceptable limits for the resultant increase in parallelism. Further, although the scheduling of this ultra fine-grain code could potentially cause simultaneous register file accesses to increase-an undesirable side-effect as building register files with a large number of ports is not currently practical-our experiments indicate that for the benchmarks studied the maximum number of simultaneous RF accesses can actually decrease.

This paper presents a new technique for the problem of allocating and assigning registers to variables in loops. Traditionally, cyclic variables (variables written in the current iteration and read in subsequent iterations) are split at the loop boundary and treated as separate variables during register allocation and assignment. When these split variables are not assigned to the same register, register copy operations are necessary to match the register usages at the beginning and end of a loop iteration. Register copy operations, which are inherently overhead operations, have an adverse impact on the quality of the final design both in area (extra hardware—registers, busses—may be necessary) and in performance (register copy operations lengthen the schedule). Therefore, it is desirable to eliminate these spurious copy operations. In this paper, we describe a novel technique that incorporates loop unrolling into an assignment algorithm so that cyclic variables are used directly in subsequent iterations without requiring additional register copy operations, and also without requiring more registers than that used by the left-edge algorithm. We conducted experiments on some core numerical and image algorithms and observed optimal allocation.

One of the most promising approaches for high speed networks for integrated service applications is fast packet switching, or ATM (Asynchronous Transfer Mode). ATM can be characterized by very high speed transmission links and simple, hard wired protocols within a network. To match the transmission speed of the network links, and to minimize the overhead due to the processing of network protocols, the switching of cells is done in hardware switching fabrics in ATM networks.

A number of designs has been proposed for implementing ATM switches. While many differences exist among the proposals, the vast majority of them is based on self-routing multi-stage interconnection networks. This is because of the desirable features of multi-stage interconnection networks such as self-routing capability and suitability for VLSI implementation.

Existing ATM switch architectures can be classified into two major classes: blocking switches, where blockings of cells may occur within a switch when more than one cell contends for the same internal link, and non-blocking switches, where no internal blocking occurs. A large number of techniques has also been proposed to improve the performance of blocking and nonblocking switches. In this paper, we present an extensive survey of the existing proposals for ATM switch architectures, focusing on their performance issues.

The efficient execution of Java programs presents a challenge to hardware and software designers alike. The difficulty however lies with the Java bytecodes. Their model of a simplistic, platform-independent stack machine is well-suited for portability, though at the expense of execution speed. Various approaches are being proposed to increase the speed of Java bytecode programs, including: (1) on-the-fly compilation to native code (also known as JIT or "just-in-time" compilation); (2) traditional ("ahead-of-time") compilation of bytecodes to some higher-level intermediate form and then to native code; and (3) translation of bytecodes to a higher-level language and then use of an existing compiler to produce native code. Speedups on the order of 50 over standard bytecode interpretation have been claimed.

All of these approaches rely upon bytecode analysis (of varying sophistication) to extract information about the program, which is then used to optimize the native code during the translation process. However, extracting information from a bytecode representation is expensive, and in general does not collect all the information originally available at the source-level.

In this paper we propose an optimization approach based on bytecode annotations. The bytecodes are annotated during the original source code to bytecode translation, allowing both traditional interpretation by a JVM and aggressive optimization by an annotation-aware bytecode compiler. Annotations do not hinder portability nor compatibility, while preserving optimization information that is (1) expensive to recompute and (2) sometimes impossible to recompute. Preliminary results yield bytecode with C-like performance using JIT technology.