The AntMinerGPU algorithm uses a directed acyclic graph (DAG) as the representation of solution space. The construction graph, Gc (V , E ), is generated in such a way that the vertices represent the set of all possible solution components and the existence of some edge E _ij represents the ability to select solution component j after having selected i . With this configuration, a path through Gc can be taken as a solution to the target problem, and good solutions can be found by exploiting the collectively intelligent behaviors of ant colonies that allow them to find optimal paths through an environment.

In the case of rule-based classification, the construction graph is generated in such a way that it captures the dimensionality of the feature space of the data to be classified. That is, the construction graph is created by generating one node group for each variable in the training dataset. These node groups are shown as vertical rectangles in Figure 22.4 . Each group contains nodes representing all possible values that the respective variable may possess.

Nominal variables are represented by one node group, containing a node for each value the variable may possess, as well as an additional node representing “does not matter.” This “dummy” node can be selected by the ants and signifies that the variable has no bearing on the class that is predicted by the rule. An ant visiting vertex k in the group representing nominal variable i will add the term (Variable _i = Value _k ) to its candidate rule.

The AntMinerGPU algorithm also allows for ordinal variables to be used in the data mining process. For this type of variable, we allow for the selection of terms that can specify a range of values. That is, we allow for terms such as (Variable _i >= Value _k ) and (Variable _i <= Value _l ). To realize this, ordinal variables are represented by two node groups that represent a lower and upper bound that can be placed on the given variable in candidate classification rules. V 2 in Figure 22.4 is an example of this structure.

The movements of ants through the construction graph are restricted by requiring that each variable appear at most once in the final classification rule. This is accomplished by using directed edges in the construction graph. In the case of nodes representing ordinal variables, the choice of paths is also restricted such that rules that lead to logically unsatisfiable conditions cannot be produced. Specifically, we wish to avoid the situation where a rule specifies (Variable _i <= x ) AND (Variable _i >= y ) where y > x . To prevent this, we simply remove edges from the construction graph that would allow for this type of path (note that node n _{2, 2} does not connect to node n _{2, 1} ).

In the solution construction phase, a set of m ant agents generates candidate classification rules from a finite set of terms (represented by the vertices of GC ). Solution construction for each ant begins with an empty partial classification rule, R _p = Ø. At each construction step, R _p is extended by adding an available term to the partial classification rule. This is achieved as ant agents repeatedly move from some node i to some node j in the construction graph, appending the term represented by j to R _p , and continuing in this fashion until reaching the end node. The choice of term to add to R _p from the set of feasible terms is a probabilistic choice with the probability of selecting term j after having selected term i given by: where τ _i,j is the pheromone associated with edge E _i,j , and η is the heuristic value of term j (α and β being parameters that weight the relative influence of τ and η ). As mentioned, pheromone levels reflect the quality of classification rules produced when other ants traversed the edge, and these pheromones are used to attract ants toward potentially rich areas in the construction graph. The heuristic value of j (η _j ) indicates the importance of node j in final solutions. This value is supplied by a problem-dependent function and is derived from a priori knowledge of the problem. The reader is referred to [6] for a description of the heuristic value used by the AntMiner class of algorithms.

An ant will select a term to add to its candidate classification rule with a probability that is proportional to the amount of pheromone on the edge leading to it. The objective of pheromone updating is to increase the pheromone levels on paths associated with good solutions (by reinforcement) and to decrease pheromone levels on paths associated with bad solutions (by evaporation). Reinforcing the pheromone levels on edges that comprise “good” solutions attracts ants in later iterations to similar areas of solution space (which are likely to contain other good, if not better, solutions). Evaporation is the process whereby pheromone levels on all graph edges are diminished over time. This allows for trails that were reinforced earlier in the exploration phase, and that may represent suboptimal solutions, to be slowly “forgotten.”

The MAX-MIN Ant System on which AntMinerGPU is based specifies a few requirements for pheromone levels. Before the first exploration of the construction graph by ant agents, all edges are initialized with a pheromone level equal to the parameter τ _max . This allows for a more complete exploration of solution space in the early iterations of the algorithm because all edges appear equally attractive with respect to pheromone level.

Pheromone updating is achieved in two phases, evaporation and reinforcement. First, pheromone evaporation is applied to all edges in the construction graph. In this phase, all pheromone levels are multiplied by an evaporation factor (ϱ ) that normally lies in the range between 0.8 and 0.99. The pheromone levels on all edges are bounded to a minimum value (τ _min ) such that edges are prevented from having such a small amount of pheromone on them that they become unexplored altogether.

The process of pheromone reinforcement occurs after evaporation. This phase begins by evaluating the quality of each ant agent's candidate solution with respect to some quantitative fitness function. The MAX-MIN Ant System indicates that only the path representing the iteration-best solution be reinforced with an amount of pheromone proportional to the quality of that solution [8] . To realize this, an amount of pheromone is added to all edges of the iteration-best solution equal to the quantitative measure of quality of that solution. The maximum amount of pheromone on an any given edge is bounded by the parameter τ _max .

To capture the structure of the construction graph, we implement two structs, Node and Link . The output of the host-side initialization code is two arrays, d_nodes and d_links , each a 1-D array containing all Node and Link structs generated to represent the construction graph for the input dataset.

Node structs keep track of which edges emanate from each node in order to allow ants to identify which edges are available to them during each stage of solution construction. The Node struct contains two int values, allowing a Node to be read as a single 64-bit chunk. This also alleviates alignment issues as Node structs can be neatly packed in memory and accesses can be coalesced.

The important information pertaining to edges (pheromone level, heuristic value of terminal node, and probability of traversal) are stored as float values in three separate arrays (d_pheromone , d_heuristic , and d_probability ). Keeping these values separate allows kernels that may need some combination of them to fetch them individually. Additionally, separating this data as such allows Link structs to only contain 4 int values, allowing them to be aligned neatly in memory. Because there are a number of kernel functions that operate over all links, the d_pheromone , d_heuristic , and d_probability arrays are padded so that their sizes are a multiple of 512 elements. In this way, we can avoid the overhead of checking to see if threads are working within the bounds of the array, and a number of threads equal to the number of links in the padded array can always be safely invoked.

In addition to reading in training data and generating the corresponding construction graph, host-side code also generates an array of the training data itself because this will be needed by the evaluateTours and calculateHeuristic kernels to compute the quality of candidate solutions and heuristic values of nodes, respectively. Because training data is static, we are able to leverage the performance benefits of caching by binding the training data to a 1-D texture and accessing the data through texture fetch calls. The use of texture caching will be discussed in the following subsections in the context of particular kernel functions.

This very simple kernel function initializes the pheromone level on all edges in the construction graph to the value supplied by the parameter tMax . The initializePheromones kernel is passed a pointer to the padded array of pheromone levels, d_pheromone , and the parameter tMax . Because adjacent threads store tMax to adjacent memory locations, very strong memory coalescing is achieved by this kernel.

The heuristic value of a node in the construction graph attempts to capture the importance of that node's value for its variable in classification rules. The heuristic value of a given node is given in Equation 22.2 . We use the notation | condition | to refer to the number of elements in the set of all data points that satisfy condition .

Equation 22.2 is realized by the kernel calculateHeuristic in the following way. We pass calculateHeuristic pointers to the array of links, d_links , and training data, d_translatedData . Each Link in d_links specifies the node to which the link connects.

calculateHeuristic is invoked with a number of threads equal to the size of d_links arranged in a 1-D grid of 1-D blocks. A thread identifies which link it is responsible for based on its position in the grid. Each thread then iterates over the training data in d_translatedData and calculates the heuristic value of the node to which its edge connects to, recording this value in the d_heuristic array in the location of the link it is working with.

As detailed earlier in this chapter, the solution-generation process carried out by ant agents is probabilistic. That is, when located on a given node, an ant will elect to traverse a connected edge with some probability as given by Eq. 22.1 . The task of the calculateProbabilities kernel is to precompute edge probabilities. This requires computing the product of the amount of pheromone on an edge and the heuristic value of the node to which the edge connects, divided by the sum of this value computed for all edges emanating from the source node.

The abstraction we make in this kernel is between nodes and blocks. Each node in the construction graph is allocated a block of threads where each thread calculates the probability for an edge emanating from its block's node.

The calculateProbabilities kernel is actually quite simple. Each thread identifies which node it is working with based on its block's index in the grid. Then, based on its index within the block, each thread calculates the product of the amount of pheromone and heuristic value associated with its link, retrieving these values from the d_pheromone and d_heuristic arrays, respectively. The resultant value is then stored in a shared memory array. Once all threads calculate this value for their respective link, each thread sums these values from shared memory, storing the result in a register. All threads then divide the value it calculated for its link by the sum, storing the result in the d_probability array located in global memory. Abbreviated source code for the calculateProbabilities kernel is offered below.

It should be noted that the calculateProbabilities kernel is usually invoked with a relatively small number of threads per block. Thus, the occupancy of the calculateProbabilities kernel is usually small. However, this abstraction of graph structure to grid organization is the most natural and has been selected here.

Exploration of the construction graph by the population of ant agents is carried out by the runGeneration kernel. The runGeneration kernel illustrates one of the most challenging aspects of ACO for GPGPU computing, namely, the probabilistic path selection process. Because each ant may take a different path through the construction graph and because these paths are impossible to predict, little can be done to ensure orderly memory transactions and concurrency.

The runGeneration kernel is passed a pointer to d_nodes , d_probability , and an array of random number seeds, d_random . It is invoked with a number of threads equal to the number of ants in the system, arranged into a 1-D grid of 1-D blocks. Each thread calculates which ant it represents based on its position in the grid.

All threads enter a loop for a number of iterations equal to the number of node groups in the construction graph. In each pass of the loop, a new link is added to each ant's tour. Threads generate a new random number based on their seeds and a simple Park-Miller pseudorandom number generator. This pseudorandom number is then used in a roulette-wheel selection process to probabilistically select an edge to traverse. When an ant selects an edge to traverse, it adds the index of the edge it traverses to an array in global memory that records the paths of all ants in the generation.

The evaporizePheromone kernel is very similar to the initializePheromone kernel in that a simple function is being applied to all values in the d_pheromone array. In this case, the kernel must read in each value from d_pheromone , multiply it by a supplied parameter, and store the result back to d_pheromone . As in initializePheromone , adjacent threads in evaporizePheromone read and write values to adjacent memory locations and, therefore, strong memory coalescing is achieved in this kernel as well. The source code for this kernel is provided here. It should be noted that the array d_pLevels contains the values of parameters <tau>_min and <tau>_max in locations 0 and 1, respectively.

Solution evaluation is the most costly portion of the AntMinerGPU algorithm. This phase necessitates comparing each ant's tour to the entirety of the training dataset to identify how many training data points each ant's tour accurately describes. Thus, this kernel requires a very large amount of memory transactions because each training data point must be analyzed.

The implementation strategy we have adopted here is depicted in Figure 22.7 . The abstraction we make is between ants and blocks. That is, the threads of one block are collectively responsible for evaluating the respective ant's tour against all training data points. Each block contains a number of helper threads equal to the number of data points, m , in the training dataset (or the maximum number of threads per block if m is greater than this value).

The heart of the evaluateTours kernel is a for-loop that iterates over each term in the block's candidate classification rule. For each term, the helper thread must determine whether its training data point is accurately described by its ant's candidate classification rule. By storing the training dataset in column major form, consecutive helper threads access consecutive memory locations. Because of the spatial locality exhibited by this access pattern, we have found that texture caching provides performance benefits. In fact, testing reveals an average texture cache hit rate of ∼40% in the evaluateTours kernel and running time of this kernel is reduced by nearly 25%.

Recall that the goal of the evaluateTours kernel is to determine how many training data points are described by each ant's rule. In our implementation strategy, we use an atomic add operation on a shared memory location to accumulate this value across all helper threads. That is, once each helper thread evaluates whether or not the ant's tour accurately predicts its designated data point, the helper thread will increment the shared memory accumulator atomically. Although this method implies some degree of serialization will occur, we have found the performance impact to be small compared with other approaches.

After the result of each helper thread is recorded, a thread will select a new data point to consider if m is greater than the maximum number of threads allowed per block. Here is abbreviated source code for this kernel function.

AntMinerGPU deposits pheromone only on the best path of all ants in a generation. Therefore, the quality of each ant's path must be considered to determine which ant generated the “best” solution. This is accomplished by a kernel function that copies the quality of each ant's tour into shared memory and then applies a reduction to determine which ant generated the best quality tour. Once the iteration-best ant has been identified, a number of threads equal to the number of node groups in the construction graph adds an amount of pheromone to the links in the iteration-best ant's tour.

Once a predefined number of iterations pass with no improvement to the global-best solution, the global-best rule is outputted, and data points described by that rule must be removed from the training dataset. To accomplish this, we invoke the kernel flagCoveredCases with a number of threads equal to the number of training data points. Each thread checks to see if the global-best solution describes the data point it is responsible for. If so, the class of that data point is set to −1, indicating that the data point has been covered. The internal workings of this kernel are very similar to that of the evaluateTours kernel.