In this paper, we show how to use the GPU to parallelize a precise instruction scheduling algorithm that is based on Ant Colony Optimization (ACO). ACO is a nature-inspired intelligent-search technique that has been used to compute precise solutions to NP-hard problems in operations research (OR). Such intelligent-search techniques were not used in the past to solve NP-hard compiler optimization problems, because they require substantially more computation than the heuristic techniques used in production compilers. In this work, we show that parallelizing such a compute-intensive technique on the GPU makes using it in compilation reasonably practical. The register-pressure-aware instruction scheduling problem addressed in this work is a multi-objective optimization problem that is significantly more complex than the problems that were previously solved using parallel ACO on the GPU. We describe a number of techniques that we have developed to efficiently parallelize an ACO algorithm for solving this multi-objective optimization problem on the GPU. The target processor is also a GPU. Our experimental evaluation shows that parallel ACO-based scheduling on the GPU runs up to 27 times faster than sequential ACO-based scheduling on the CPU, and this leads to reducing the total compile time of the rocPRIM benchmarks by 21%. ACO-based scheduling improves the execution-speed of the compiled benchmarks by up to 74% relative to AMD's production scheduler. To the best of our knowledge, our work is the first successful attempt to parallelize a compiler optimization algorithm on the GPU.

This paper describes a new approach to register-pressure-aware instruction scheduling, using Ant Colony Optimization (ACO) . ACO is a nature-inspired optimization technique that researchers have successfully applied to NP-hard sequencing problems like the Traveling Salesman Problem (TSP) and its derivatives. In this work, we describe an ACO algorithm for solving the long-standing compiler optimization problem of balancing Instruction-Level Parallelism (ILP) and Register Pressure (RP) in pre-allocation instruction scheduling. Three different cost functions are studied for estimating RP during instruction scheduling. The proposed ACO algorithm is implemented in the LLVM open-source compiler, and its performance is evaluated experimentally on three different machines with three different instruction-set architectures: Intel x86, ARM, and AMD GPU. The proposed ACO algorithm is compared to an exact Branch-and-Bound (B&B) algorithm proposed in previous work. On x86 and ARM, both algorithms are evaluated relative to LLVM's generic scheduler, while on the AMD GPU, the algorithms are evaluated relative to AMD's production scheduler. The experimental results show that using SPECrate 2017 Floating Point, the proposed algorithm gives geometric-mean improvements of 1.13% and 1.25% in execution speed on x86 and ARM, respectively, relative to the LLVM scheduler. Using PlaidML on an AMD GPU, it gives a geometric-mean improvement of 7.14% in execution speed relative to the AMD scheduler. The proposed ACO algorithm gives approximately the same execution-time results as the B&B algorithm, with each algorithm outperforming the other on a substantial number of hard scheduling regions. ACO gives better results than B&B on many large instances that B&B times out on. Both ACO and B&B outperform the LLVM algorithm on the CPU and the AMD algorithm on the GPU.

QWOP is a popular Flash game in which a human player controls a sprinter in a simulated 100-meter dash. The game is notoriously difficult owing to its ragdoll physics engine, and the simultaneous movements that must be carefully coordinated to achieve forward progress. While previous researchers have evolved gaits using simulations similar to QWOP, we describe a software interface that connects directly to QWOP itself, incorporating a genetic algorithm to evolve actual QWOP gaits. Since QWOP has no API, ours detects graphical screen elements and uses them to build a fitness function. Two variable-length encoding schemes, that codify sequences of QWOP control commands that loop to form gaits, are tested. We then compare the performance of SGA, Genitor, and a Cellular Genetic Algorithm on this task. Using only the end score as the basis for fitness, the cellular algorithm is consistently able to evolve a successful scooting strategy similar to one most humans employ. The results confirm that steady-state GAs are preferred when the task is sensitive to small input variations. Although the limited feedback does not yet produce performance competitive with QWOP champions, it is the first autonomous software evolution of successful QWOP gaits.

The Terrain-Based Memetic Algorithm (TBMA) is a diffusion MA in which the local search (LS) behavior depends on the topological distribution of memetic material over a grid (terrain). In TBMA, the spreading of meme values -- such as LS step sizes -- emulates cultural differences which often arise in sparse populations. In this paper, adaptive capabilities of TBMAs are investigated by meme diffusion: individuals are allowed to move in the terrain and/or to affect their environment, by either following more effective memes or by transmitting successful meme values to nearby cells. In this regard, four TBMA versions are proposed and evaluated on three image vector quantizer design instances. The TBMAs are compared with K-Means and a Cellular MA. The results strongly indicate that utilizing dynamically adaptive meme evolution produces the best solutions using fewer fitness evaluations for this application.

We observe the effects of a variety of splitting strategies for partitioning the input domain in a self-splitting modular neural network applied to the two-spiral classification problem, and assisted by a special-purpose visualization tool. The observations motivate the development of an improved strategy, consisting of a series of binary splits along the boundaries of trained areas, and a particular weight initialization strategy. The work is leading to fewer networks and better generalization for this application, when backpropagation is used.

We describe and implement a visualization tool for a self-splitting neural network (SSNN). The SSNN is a modular neural network that partitions the input domain during training through the identification of solved chunks and a divide-and-conquer strategy. The visualization tool shows a 2D projection of the input domain as partitioning proceeds, highlighting the boundaries of trained regions. Greyscale can be used to contrast the ranges of outputs so that generalization can be visually assessed. The tool is useful for illustrating how the SSNN works and for comparing different learning and splitting strategies.

An extremely simple technique for training the weights of a feedforward multilayer neural network is described and tested The method, dubbed ldquoneighbor annealingrdquo is a simple random walk through weight space with a gradually decreasing step size. The approach is compared against backpropagation and particle swarm optimization on a variety of training tasks. Neighbor annealing is shown to perform as well or better on the test suite, and is also shown to have pragmatic advantages.

A modular neural network works by dividing the input domain into segments, assigning a separate neural network to each sub-domain. This paper introduces the self-splitting modular neural network, in which the partitioning of the input domain occurs during training. It works by first attempting to solve a problem with a single network. If that fails, it finds the largest chunk of the input domain that was successfully solved, and sets that aside. The remaining unsolved portion(s) of the input domain are then recursively solved according to the same strategy. Using standard backpropagation, several large problems are shown to be solved quickly and with excellent generalization, with very little tuning, using this divide-and-conquer approach.

A genetic algorithm is used to solve a class of maze pathfinding problems. In particular, we find a complete set of paths directing an agent from any position in the maze towards a single goal. To this end, we define a sparse direction map, wherein the maze is divided into sectors, each of which contains a direction indicator. Maps are evolved using a simple genetic algorithm. The fitness function samples the efficacy of the map from random starting points, this estimating the likelihood that agents find the goal. The framework was effective in evolving successful maps for three different mazes of varying size and complexity, resulting in interesting and lifelike agent behavior suitable for games, but not always the shortest paths.

A genetic algorithm is used to find solutions to the standard 8/spl times/8 knight's tour problem, and its performance is compared against standard depth-first search with backtracking. The binary encoding is described, along with a simple repair technique which can be used to extend tours that have reached impasse. The repair method is powerful enough on its own to find complete tours, given randomly generated bitstrings. But when used in conjunction with a genetic algorithm, considerably more solutions are found. Depth-first search is shown to find more solutions under certain conditions, but the genetic algorithm finds solutions more consistently for arbitrary initial conditions.

We describe and implement a visualization tool applet for a Terrain-based genetic algorithm (TBGA). The TBGA is a self-tuning version of the cellular genetic algorithm (CGA), wherein various combinations of parameter values appear in different physical locations of the population. The TBGA is useful for solving optimization problems as well as for finding good CGA parameter values. By tallying the number of times a new best individual is found for each location in the population, the applet illustrates the progress of evolution as a gradually evolving terrain map showing effective locations as having increasing altitude. We contrast two methods for using the TBGA to determine good parameter settings. The tool can also help educate users unfamiliar with the TBGA and how it works.