In anticipation of the emergence of multimedia applications as an important workload, microprocessor companies have augmented their instruction-set architectures with short vector extensions, thus adding basic vector hardware to state-of-the-art superscalar processors. Although a vector architecture may be a good match for multimedia applications, there is growing evidence that the control logic for increasingly complex superscalar processors is difficult to implement, Rather than combining a complex superscalar core with short wide vector hardware, we propose using a much simpler processor design that is similar to traditional vector computers with long vectors and simple control logic for instruction issue. Such a design would use the bulk of its transistors and die area for datapath and registers, and thus lessen the time required to design, implement, and verify control. In this paper we present data that quantifies this trading of control transistors for datapath and register transistors. We demonstrate that a 2-way, in-order vector processor with a vector length of 64 and a vector width of 8 requires no more die area, and possibly significantly less area, than a 4-way, out-of-order superscalar processor with short vector extensions. Furthermore, we show that the simple long vector processor is, on average, 2.7 times faster executing multimedia applications than the superscalar processor; and 1.6 times faster than one with short vector extensions. To explain the reasons for the higher performance, we analyze execution time in terms of dynamic operation count and cycles per operation (CPO). A vector processor executes fewer operations by using vector instructions to stripmine a loop. Moreover, a long vector processor achieves a lower CPO by effectively using parallelism at both the operation and the instruction levels. Thus by reducing both terms of the CPO equation, the simple long vector processor achieves greater performance.

Increasingly wider superscalar processors are experiencing diminishing performance returns while requiring larger portions of die area dedicated to control rather than datapath. As an alternative to using these processors to exploit parallelism effectively, we are investigating the viability of using single-chip vector microprocessors. This paper presents some initial results of our investigation where we compare the performance and cost of vector microprocessors to that of aggressive, out-of-order superscalar microprocessors. On the performance side, we show that vector processors are able to execute a highly parallel, integer-based application 1.5-7.3 times faster than superscalar processors can by exploiting parallelism more effectively. This ability stems from the use of vector instructions. Vector instructions exploit parallelism across loop iterations by implicitly re-scheduling operations and temporally localizing the parallelism. Vector instructions also reduce instruction bandwidth by more than an order of magnitude because they express an abundance of parallelism in a compact encoding. On the cost side we show that, to achieve these performance gains, highly parallel, integer-based vector microprocessors are no more costly to implement than existing in-order and out-of-order superscalar microprocessors. One reason for this is that the organization of a vector register file provides tremendous bandwidth without incurring a large area penalty. A second reason is that the control logic for issuing vector instructions is relatively simple. Both the performance gains and cost savings are possible because vector processors rely on a vectorizing compiler, rather than hardware, to detect parallelism and to express it in a compact form to the hardware. These initial results suggest that transferring this functionality to the compiler offers a tremendous performance/cost benefit.

Over the past decade, digital signal processors (DSPs) have emerged as the processors of choice for implementing embedded applications in high-volume consumer products. Through their use of specialized hardware features and small chip areas, DSPs provide the high performance necessary for embedded applications at the low costs demanded by the high-volume consumer market. One feature commonly found in DSPs is the use of dual data-memory banks to double the memory system's bandwidth. When coupled with high-order data interleaving, dual memory banks provide the same bandwidth as more costly memory organizations such as a dual-ported memory. However, making effective use of dual memory banks remains difficult, especially for high-level language (HLL) DSP compilers.In this paper, we describe two algorithms --- compaction-based (CB) data partitioning and partial data duplication --- that we developed as part of our research into the effective exploitation of dual data-memory banks in HLL DSP compilers. We show that CB partitioning is an effective technique for exploiting dual data-memory banks, and that partial data duplication can augment CB partitioning in improving execution performance. Our results show that CB partitioning improves the performance of our kernel benchmarks by 13%-40% and the performance of our application benchmarks by 3%-15%. For one of the application benchmarks, partial data duplication boosts performance from 3% to 34%.

Software pipelining is an aggressive scheduling technique that generates efficient code for loops and is particularly effective for VLIW architectures. Few software pipelining algorithms, however, are able to efficiently schedule loops that contain conditional branches. We have developed an algorithm we call All Paths Pipelining (APP) that addresses this shortcoming of software pipelining. APP is designed to achieve optimal or near-optimal performance for any run of iterations while providing efficient code for transitioning between runs. A run is the execution of consecutive iterations that all execute the same path through a loop. APP accomplishes this by using techniques from modulo scheduling and kernel recognition algorithms, the two main approaches for software pipelining loops. We have implemented the APP algorithm in our research compiler and have evaluated its performance by executing its generated code on a VLIW instruction-set simulator. For a processor with five heterogeneous functional units, APP is able to add another 1% to 23% increase in performance over basic software pipelining by effectively pipelining loops with conditional branches.

Current DSP architectures are designed to enhance the execution of computationally-intensive, kernel-like loops. Their peculiar architectural features are often difficult for high-level language compilers to exploit. Moreover, their tightly-encoded instruction sets usually restrict the exploitation of instruction-level parallelism beyond a few instances. The quality of compiler-generated code is therefore poor when compared to hand-coded assembly language. We argue for an application-driven approach to designing flexible DSP architectures and effective compilers. We show that the run-time behavior and architectural characteristics of DSP kernels are different from those of DSP applications. We also show that when given a sufficiently flexible target architecture, a compiler is capable of effectively exploiting instances of instruction-level parallelism and DSP-specific architectural features. Finally, we show that a suitable DSP architecture is one that provides the functionality to support digital signal processing requirements, and the flexibility that enables a compiler to generate efficient code.>

The authors study partitioned video register files, where multiple vector registers are connected by a pair of buses to a set of functional units. Although less costly to implement, this alternative organization places some restrictions on accessing vector registers, thus potentially degrading processor performance. To circumvent this restrictive access, the authors develop a heuristic algorithm for assigning vector registers in a partitioned vector register file. By compiling a set of benchmarks with the proposed assignment algorithm, the authors generated data showing that the performance of this alternative register organization is comparable to that of a traditional one. Moreover, the data show that eight pairs of buses are adequate for a Cray Y-MP vector processor. If each pair of buses services two vector registers, for a total of 16, the algorithm successfully assigns 94% of the benchmark loops. Using 32 vector registers raises this percentage to 97%.>