While control speculation is highly effective for generating good schedules in out-of-order processors, it is less effective for in-order processors because compilers have trouble scheduling in the presence of unbiased branches, even when those branches are highly predictable. In this paper, we demonstrate a novel architectural branch decomposition that separates the prediction and deconvergence point of a branch from its resolution, which enables the compiler to profitably schedule across predictable, but unbiased branches. We show that the hardware support for this branch architecture is a trivial extension of existing systems and describe a simple code transformation for exploiting this architectural support. As architectural changes are required, this technique is most compelling for a dynamic binary translation-based system like Project Denver.

Indirect branches have historically been a challenge for microarchitectures and code generators alike. The recent steady increase in indirect branch predictability has translated into continual performance improvements especially for Out-of-Order processors which benefit more readily from improvements in branch prediction. In contrast, in-order processors which rely on code generators for performance are still challenged by indirect branches; they are a frequent source of issue stalls and the large number of indirect branch targets and unbiased nature of indirect branches complicate the use of traditional branch handling techniques like assert conversion and predication.

In this paper, we set out to study the performance advantages of an Out-of-Order (OOO) processor relative to in-order processors with similar execution resources. In particular, we try to tease apart the performance contributions from two sources: the improved sched- ules enabled by OOO hardware speculation support and its ability to generate different schedules on different occurrences of the same instructions based on operand and functional unit availability. We find that the ability to express good static schedules achieves the bulk of the speedup resulting from OOO. Specifically, of the 53% speedup achieved by OOO relative to a similarly provisioned in- order machine, we find that 88% of that speedup can be achieved by using a single "best" static schedule as suggested by observing an OOO schedule of the code. We discuss the ISA mechanisms that would be required to express these static schedules. Furthermore, we find that the benefits of dynamism largely come from two kinds of events that influence the application's critical path: load instructions that miss in the cache only part of the time and branch mispredictions. We find that much of the benefit of OOO dynamism can be achieved by the potentially simpler task of addressing these two behaviors directly.

The well-known shift to parallelism in CPUs is often associated with multicores. However another trend is equally salient: the increasing parallelism in per-core single-instruction multiple-date (SIMD) vector units. Intel's SSE and IBM's VMX (compatible to AltiVec) both offer 4-way (single precision) floating point, but the recent Intel instruction sets AVX and Larrabee (LRB) offer 8-way and 16-way, respectively. Compilation and optimization for vector extensions is hard, and often the achievable speed-up by using vectorizing compilers is small compared to hand-optimization using intrinsic function interfaces. Unfortunately, the complexity of these intrinsics interfaces increases considerably with the vector length, making hand-optimization a nightmare. In this paper, we present a peephole-based vectorization system that takes as input the vector instruction semantics and outputs a library of basic data reorganization blocks such as small transpositions and perfect shuffles that are needed in a variety of high performance computing applications. We evaluate the system by generating the blocks needed by the program generator Spiral for vectorized fast Fourier transforms (FFTs). With the generated FFTs we achieve a vectorization speed-up of 5.5--6.5 for 8-way AVX and 10--12.5 for 16-way LRB. For the latter instruction counts are used since no timing information is available. The combination of the proposed system and Spiral thus automates the production of high performance FFTs for current and future vector architectures.

Mainstream video games are increasingly benefiting from more sophisticated adversarial artificial intelligences. The quality of these synthetic opponents is becoming a significant competitive advantage that was once exclusively reserved for graphics. This new generation of synthetic opponent relies on dynamic planning systems such as STRIPS to realize realistic and challenging adversarial behavior. Such systems have been embraced by game developers as they provide for transparent representation of agent state and behavior, have low CPU utilization and are available in toolkit form. Concurrently, the dramatic proliferation of parallel computational units in modern hardware architectures is also facilitating the use of connectionist models of artificial intelligence in gaming. However, significant barriers such as neural network training set generation and turnaround time for neural network development have inhibited widespread adoption of such techniques. To overcome these barriers, we present an infrastructure that automates neural network development through the use of a genetic algorithm to evolve the behavioral training set of an adversarial artificial intelligence. The infrastructure uses an existing game, Wolfenstein 3D, as a simulation environment. We compare the effectiveness of the neural network generated by this system against a manually constructed neural network and the original game AI. All three models are pitted against human players

One way to address the continuing performance problem of high-level domain-specific languages, such as Octave or Matlab, is to compile them to a relatively lower level language for which good compilers are available. As a first step in this direction, specializing the high-level operations in the source, based on operand types, leads to significant gains. However, simple translation of the high-level operations to the underlying libraries can often miss important opportunities to improve performance. This paper presents a global algorithm to select functions from a target library, utilizing the semantics of the operations as well as the platform-specific performance characteristics of the library. Making use of the library properties, the simple and easy-to-implement selection algorithm, is able to achieve as much as three times performance improvement for certain linear algebra kernels, over a straight mapping of operations, which are compiled to the vendor-tuned BLAS.