need a simple java code

High-performance processor design has recently taken two distinct approaches. One approach is to increase the execution rate by increasing the clock frequency of the processor or by reducing the execution latency of the operations. While this approach is important, much of its performance gain comes as a consequence of circuit and layout improvements and is beyond the scope of this research. The other approach is to directly exploit the instruction-level parallelism (ILP) in the program and to issue and execute multiple operations concurrently. This approach requires both compiler and microarchitecture support.

Traditional processor designs that issue and execute at most one operation per cycle are often called scalar designs. Static and dynamic scheduling techniques have been used to achieve better-than scalar performance by issuing and executing more than one operation per cycle. While Johnson[7] defines a superscalar processor as a design that achieves better-than scalar performance, popular usage of this term refers exclusively to those processors that use dynamic scheduling techniques. For clarity, we use instruction-level parallel processors to refer to the general class of processors that execute more than one operation per cycle of the computer both at the personal level, or the level of a small network of computers to do not require more of these types.

The primary static scheduling technique uses the compiler to determine sets of operations that have their source operands ready and have no dependencies within the set. These operations can then be scheduled within the same instruction subject only to hardware resource limits. Since each of the operations in an instruction is guaranteed by the compiler to be independent, the hardware is able to is- sue and execute these operations directly with no dynamic analysis. These multi-operation instructions are very long in comparison with traditional single-operation instructions and processors using this technique have been called Very Long Instruction Word (VLIW) processors.

The primary dynamic scheduling technique uses special hardware to analyze the instruction stream at execution time and to determine which operations in the instruction stream are independent of all preceding operations and have their source operands available. These operations can then be is- sued and executed concurrently. Processors using dynamic scheduling techniques have been called superscalar processors.

Both of these techniques have advantages and disadvantages and both have demonstrated significant problems that limit their achievable performance despite claims of strong peak performance. Statically scheduled processors require that the latencies of all operations be fixed and known in advance.

Literature Review

In this section we will explain the details of this technology to their importance.

Simulation framework and methodology

As an evaluation platform, we define a “universal” ILP microarchitecture that we use as to evaluate processor configurations using a range of dynamic analysis techniques to issue operations to function units. Based on a number of studies of available ILP [18, 8] we have defined a nominal architecture that ensures that our results are not significantly affected by the use of an unreasonably narrow or wide con- figuration. Using this nominal architecture we are able to vary a number of aspects in order to explore the effects of these changes on performance.

For the nominal architecture we use a configuration consisting of two of each kind of function unit—integer, floating point, load/store, and branch—for a total of eight function units. This configuration allows the support of a reasonable level of ILP as well as allowing the exploration of the performance impacts of double and half wide—four and sixteen function unit—versions to understand how these changes affect performance.

We make a further simplifying assumption that the cycle time for all processor configurations remains constant and is unaffected by the complexity of any dynamic analysis hardware. While this choice simplifies the experiment, it potentially complicated the data analysis—by not considering the complexity and cost of the analysis logic we are biasing the results in favor of processors using these techniques. We will revisit this bias in the conclusion and its impact on these results.

`The architectures that we studied share a common set of features. The memory system consists of split instruction and data caches, a pipelined bus, and a main memory system. The instruction cache is 32 kB with 128 B lines (4 instructions per line); the data cache is 32 kB with 64 B lines. Both are direct mapped. Memory is reached through a pipelined 64b bus using an 8 operation deep load/store queue. Branch prediction is performed using a 1024 entry direct-mapped counter-based history mechanism. Nominal function unit latencies are 1 cycle for integer operations and 2 cycles for floating point operations (8 and 15 cycles for floating point divide).

Around this common core we define five virtual architectures. One architecture has all operations completing in a single cycle and is used to represent a typical scalar processor instruction stream. The other four architectures are variations of the nominal architecture with the assumed/actual latency to the data cache scaled by multiples of 1 (the nominal architecture), 2, 4, and 8 times.

In order to explore the effects of the memory system on these architectures we use memory latencies of 4 cycles (approximating the effective latency when using a second level cache), 25 cycles (a nominal value for a moderate sys- tem), and 100 cycles (representing a system with a high- performance processor and a realistically slow main memory). To establish a measure of an upper bound on performance we also consider the case where the implementation has perfect branch prediction and perfect caches.

While the caches block on a miss (causing further references to stall until the miss is completed), this restriction only affects the relative cost of memory for the different applications. Non-blocking caches allow subsequent memory references to be serviced by the cache during miss processing and rely on the independence of memory references. Depending on the nature of the application’s memory reference pattern, the benefits of a non-blocking cache will vary with the worst case being equivalent to a blocking cache. Because the gain provided by non-blocking caches is pro- gram (and data) dependent, the performance for an architecture cannot be compared across the different benchmarks because each benchmark has different memory reference stream characteristics. However, the general characteristics of increasing memory latency still hold.

In order to see how performance varies with complexity, we vary the number of pending instructions analyzed in the hardware. In each cycle, there are a certain number of instructions available from which ready operations can be issued to function units—the greater the number of pending. Instructions, the greater the number of operations available for issue. This is analogous to varying the size of the instruction pool (reservation station, reorder buffer, etc.) in a superscalar processor.

We have simulated pending instruction window sizes from 1 to 64 pending instructions. These configurations cover the range from a simple in-order processor (with a window of 1 instruction) to a massively out-of-order processor (with a window of 64 instructions). Because the initial results have shown that the benefits from out-of-order issue rapidly saturate, we limit our results to architectures with window sizes up to 8 instructions. We use four benchmarks from the SPEC-92 benchmark suite (two integer, two floating point) to analyze the performance of the different configurations. These bench- marks were chosen because they give a range of integer and floating-point as well as loop-based and table-search control-flow patterns.

Results

We have generated and analyzed data from simulations using the configurations and benchmarks described in the previous section. These have shown us a number of interesting and sometimes surprising results. The first result is the dependence of the performance of the code schedule technique on the level of dynamic analysis performed by the hardware. The second result is that as the mismatch between processor and system performance increases (as is the case with processor performance improving at a faster rate than memory system performance), the benefits of dynamic analysis hardware are reduced so that all configurations yield similar performance.

A third result observed is that there is little benefit to increasing the number of function units beyond that assumed by the schedule. Simulations with double the number of function units showed only slight improvements over the nominal architecture. On the other hand, reducing the number of function units to a half of nominal resulted in performance comparable to a half-wide schedule configuration. There is little benefit in having a configuration that exploits.

More ILP than is available in the schedule (or program). The correspondence between the schedule (virtual architecture) and the actual machine (implementation architecture) is described by a qualitative matching value that has three basic values. When the

virtual and implementation machines agree we say that the schedule is well matched. Accordingly, a schedule that is not well matched is poorly matched and may be either under matched (when the virtual latencies are shorter than the implementation latencies) or overmatched (when the virtual latencies are longer than the implementation latencies). While it is possible to have some virtual latencies that are shorter and other virtual latencies that are longer than the implementation latencies, we have not considered these configurations and do not define any particular naming for these cases.

The matching value is important because it qualitatively describes the nature of the code stream as seen by the processor. An under matched schedule has operations scheduled before their source values become ready giving a densely packed schedule. A well-matched schedule has operations scheduled as their source values become available giving a schedule that matches the expected level of ILP in the schedule. An overmatched schedule has operations scheduled after their source values become available giving a sparsely packed schedule. This can be seen in table 2 which shows the operations per packet for the instruction streams for the benchmark 022.li.

The effects of these three kinds of matching can be seen in figure 2. In this figure, the x-axis is the number of instructions analyzed at any given time to issue computations to the function units (a value of 1 is effectively a statically scheduled VLIW architecture which stalls whenever a source or destination operand is not available as scheduled or used); the y-axis is the achieved performance in operations per cycle (the limit for performance is 8 operations—the number of operations in an instruction).

The data in figure 2 is for the benchmark 022.li with perfect caches and branch prediction (figure 5 shows the same data for all four benchmarks). By using perfect caches we are able to focus on the variations due to schedule matching. This figure shows the general behavior that is seen throughout our results. The performance of the under matched schedule increases dramatically up to the point that the number of dynamically analyzed instructions covers most of the implementation latency for the operations in the instruction stream; after this point the gain rapidly tops out. For an implementation with only a single dynamically analyzed instruction, any misscheduled operation will cause the processor to stall resulting in a performance loss. Since most operations are either 1 or 2

cycle latency operations, most of the gain is achieved by this point. The actual cross-over point will vary as the operation mix varies between programs. The well-matched schedule has flat performance over the range of dynamically analyzed instructions considered. With this schedule, all operations complete as scheduled. The overmatched schedules with scaled memory access latencies—the doubled and quadrupled cache latency schedules—also show flat performance but have lower achieved performance due to the poor schedule utilization.

It is instructive to look more closely at these results to understand the performance of the three scheduling classes. To do this we must examine the concepts of operation density and schedule efficiency. Operation density is a potential measure of program performance—the average number of operations per instruction packet. Program efficiency is a measure of how well the program ran in contrast to how well it should have run—the ratio of the scheduled execution time to the actual execution time. Neither operation density nor schedule efficiency alone is sufficient to compare performance values: while the operation density is a measure of the available ILP, a schedule may stall frequently resulting in poor overall performance; similarly, while a schedule

02468 Instruction packets analyzed Packed unit-latency schedule Nominal latency schedule Doubled cache latency schedule Quadrupled cache latency schedule

Figure 3. Schedule efficiency of 022.li (perfect cache and branch prediction) may run very efficiently, it may not utilize the exploitable ILP and again result in poor overall performance. However, the product of these two values yields program performance in terms of operations per cycle which is a useful measure- ment of performance between benchmarks, schedules, and configurations.

Table 2 shows the variations in the operation density for a range of schedules for 022.li. As can be seen, the operation density is greatest for the under matched schedule and decreases steadily from under matched to well matched to overmatched. Figure 3 shows the differences in the efficiency of the processor for the same schedules. We see that the well matched and overmatched schedules have perfect efficiency. This should come as no surprise since the caches are perfect and all operations complete at or before their scheduled time—there is no delay due to the schedule. In addition to having poor efficiency (due to the frequent stalls from the optimistic schedule), the under matched schedule requires a significant amount of analysis hardware to issue around the many delayed operations.

Next we examine the performance variations that occur in the presence of realistic memory latencies. Figure 4 shows the behavior of 052.alvinn as the memory sys- tem performance varies from a perfect cache to a latency of 100 cycles on a cache miss (figure 6 shows the same data for all four benchmarks). Just as in figure 2, the overmatched schedules show increasingly poor performance and are not shown here. Surprisingly, a memory latency of only 4 cycles to main memory shows that there is little benefit from the improved code density of the under matched schedule even in configurations with much dynamic analysis hard- ware.

3 Methodology & Conclusion

These results lead to one basic conclusion—in the presence of significant memory latencies there is little difference in performance across a wide range of simple and complex processors. With memory systems performing 100 times more slowly than high performance processors, this is a significant consideration. There is limited benefit from dynamic dynamic analysis hardware in some benchmarks (as seen by 052.alvinn in figure 4), yet the benefit rapidly diminishes to the point that it is not clear that the performance improvements are worth the complexity. The ability to sup- port two pending instructions gives a significant portion of the achievable benefit while limiting the complexity of the analysis hardware dramatically.

As was noted in earlier, we do not consider the complexity of the dynamic analysis logic and its cycle time impact. We need to consider both the assumption that the instruction stream consists of packets of independent operations as well as the assumption that the cycle time is fixed and unaffected by the number of outstanding instructions analyzed. What is the effect of this analysis hardware?

Dynamic analysis hardware that detects and schedules independent operations can produce no better performance than the compiler can with its static schedule—while compilers can look at the entire program, hardware has a very limited analysis window. Both the reduced quality of the schedule and the likely increase in cycle time combine to reduce overall performance.

Dynamic operation issue logic may affect the cycle time but may also result in improved performance by reordering around delayed operations—this reordering cannot be exploited by static scheduling. The effective performance impact of dynamic operation issue hardware is impossible to determine in the general case—although it is clear that the addition of this hardware will not reduce the cycle time! Again, any effect would be to reduce overall performance.

1. References:

[1] D.G.M.Amdahl.Validityofthesingleprocessorapproach to achieving large scale computing capabilities. In AFIPS Conference Proceedings 1967 Spring Joint Conference, vol- ume 30, pages 483–5, Washington, D.C., Apr. 1967. Thomp- son Books.

[2]P.BannonandJ.Keller.InternalarchitectureofAlpha21164 microprocessor. In Digest of Papers: COMPCON ’95, pages 79–87, Los Alamitos, 1995. IEEE Computer Society, IEEE Computer Society Press.

[3] D. Christie. Developing the AMD-K5 architecture. IEEE Micro, 16(2):16–26, Apr. 1996.

[4] N.B.Gaddis,J.R.Butler,A.Kumar,andW.J.Queen.A56- entry instruction-reorder buffer. In 1996 IEEE International Solid-State Circuits Conference. Digest of Technical Papers, ISSCC, pages 212–3, New York, Feb. 1996. IEEE.

[5] D. Hunt. Advanced performance features of the 64-bit PA- 8000. In Digest of Papers: COMPCON ’95, pages 123–8, Los Alamitos, 1995. IEEE Computer Society, IEEE Com- puter Society Press.