A binary classification task is the one that given ln -dimensional examples and their corresponding labels with and Y = {−1, 1}, constructs a classifier that predicts the binary label y ∈ {−1, 1} of a new unseen example The binary classifier is obtained by solving the following regularization problem: The introduction of slack variables ξ _i allows classifying nonseparable data and leads to the Primal form: The Dual form, which is derived from the Primal, has simpler constraints to be solved: where is the kernel function. Common kernel functions are shown in Table 20.1 . The Dual form (Eq. 20.3 ) is a quadratic programming optimization problem, and solving it defines the classification function: where b is an unregularized bias term. Geometrically, obtaining corresponds to finding the maximum margin hyperplane. Figure 20.1 (left) illustrates the geometrical interpretation of the binary SVM classifier, and Figure 20.1 (right) shows the introduction of slack variables when data is not separable. The samples on the margin (α _i > 0) are called the support vectors (SVs).

Classical approaches construct the multiclass classifier as the combination of N independent binary classification tasks. Binary tasks are defined in the output code matrix R of size M × N , where M is the number of classes, N is the number of tasks, and R _ij ∈ {−1, 0, 1}. Each column in matrix R represents how multiclass labels are mapped to binary labels for each specific binary task. There are three common types of output codes:

Figure 20.2 (left) illustrates the hyperplanes generated from the resolution of a multiclass SVM problem using AVA output codes, while Figure 20.2 (right) represents the result using OVA output codes.

Then each is trained separately with where k = 1 … N . The outputs of trained binary classifiers along with the output codes R _yk and a user-specified loss function V are used to calculate the multiclass label that best agrees with the binary predictions:

In order to construct the set of N binary classifiers we need to solve N quadratic programming (QP) optimization programs on the same set of kernel evaluations K , but with different binary labels: subject to: and We will use the sequential minimal optimization (SMO) algorithm. SMO solves large-scale QP optimization problems by choosing the smallest optimization problem at every step, which involves only two Lagrange multipliers . For two Lagrange multipliers the QP problem can be solved analytically without the need of numerical QP solvers. At each iteration, the two Lagrange multipliers are used to obtain the updated function values The SMO algorithm can be directly decomposed into iterations of Map and Reduce primitives, which have been proven to be very useful extracting parallelism on machine-learning algorithms [6] and [7] . Different QP programs will have different convergence rates, and the algorithm finishes when the last QP program has converged. Early convergence of some of the QP programs allows binary tasks that are lagging to find a larger number of stream processors available. These are the key steps of the algorithm:

The core of the algorithm is illustrated in Figure 20.3 . In the next subsections we include additional details for each step.

The Map step updates the values of the classifier function based on the variation of the two Lagrange multipliers, and the corresponding kernel evaluations: with i = 1, …, l , k = 1, …, N . The initialization values for the first iteration of the SMO algorithm are . Figure 20.4 presents the code of the kernel function that executes the Map step. The function takes the following arguments: (1) Input arrays: the function values d_f , the binary labels d_y , K matrix rows d_k and the variation of the Lagrange multipliers d_delta_a . (2) Indices: the indices of the global locations of the two Lagrange multipliers (d_Iup_global, d_Ilow_global ) and the indices of the cached rows that store the required kernel evaluations (d_Iup_cache, d_Ilow_cache ). (3.) Other parameters: An array pointing to the non-converged binary tasks d_active and the number of training samples in the dataset ntraining . The Map kernel is launched on a 2-D grid where the blocks along the x dimension select specific subsets of the training samples, and the y dimension specifies the binary task to work on.

The Reduce step finds the indices and of the Lagrange multipliers that need to be optimized in each iteration and calculates the new values for and This step interleaves host and device segments. The calculation of the indices is as follows:

The indices are obtained by filtering Eq. 20.7 and reducing Eq. 20.8 the array. The Local Reduce is carried out on the device and the Global Reduce is performed by the host. Figure 20.5 shows the Local Reduce kernel function utilized to obtain the Lagrange multiplier using min and argmin reductions. The kernel function for the multiplier is analogous, but using max and argmax operations instead.

Both kernel functions take similar arguments: (1) Input arrays: the binary labels d_y , the current Lagrange multiplier values d_a , the function values d_f . (2) Output arrays: the value and index of the locally reduced Lagrange multiplier (d_Bup_local,d_Iup_local) for the min reduction and (d_Blow_local, d_Ilow_local) for the max reduction. (3) Other parameters: an array pointing to the regularization parameter values d_c , an array pointing to the nonconverged binary tasks d_active , and the number of training samples in the dataset ntraining . The parallel reduction is carried out using a shared memory array, extern__shared__ float reducearray[] . The length of this array is specified at kernel launch time. The first half of the array is used to store the reduced values and the second half for the indices. Both reduce kernels are launched on a 2-D grid in which the blocks along the x dimension select specific subsets of the training samples, and the y dimension specifies the binary task to work on.

After the Local Reduce has been performed in the device, the host finalizes the reduction by finding the global minimum and global maximum with their corresponding indices, which indicate the Lagrange multipliers to be optimized. These two indices per binary task, and also point to the rows of the Gram matrix K that will be required in order to calculate the new values of the Lagrange multipliers. A host-controlled LRU (Least Recently Used) cache indicates whether these rows have been previously calculated and are kept in the device memory. A cache hit simply returns the memory location of the required row, whereas a cache miss invokes the CUBLAS sgemv routine to calculate the new row and returns its location. In any case, the required 2 N rows will be in memory before the Lagrange multipliers are updated. The fact that different binary tasks may require the same rows of the Gram matrix K increases the cache hit rate.

Using the values of these rows of the K matrix, we obtain the new values of the Lagrange multipliers: where . Because all the information required to update the Lagrange multipliers resides on the device memory and the Lagrange multipliers themselves will be required by the Map task to be on the device memory as well, are calculated on the device using the kernel function in Figure 20.6 .

The Update kernel function takes the following arguments: (1) Input arrays: K matrix rows d_k , the binary labels d_y , the function values d_f . (2) Output arrays: the Lagrange multiplier values d_a , the variation of the Lagrange multipliers d_delta_a . (3) Indices: the indices of the global locations of the two Lagrange multipliers (d_Iup_global, d_Ilow_global) and the indices of the cached rows that keep the required kernel evaluations (d_Iup_cache, d_Ilow_cache) . (4) Other parameters: an array pointing to the regularization parameter values d_c , an array pointing to the nonconverged binary tasks d_active , the number of training samples in the dataset ntraining and the number of nonconverged binary tasks activeTasks . Both reduce kernels are launched on a 2-D grid where the blocks along the x dimension select specific subsets of the training samples, and the y dimension specifies the binary task to work on.

Finally, once the new Lagrange multiplier values have been calculated, we check for convergence of the QP program: If task k has converged, where τ is the tolerance parameter. The algorithm finishes when all the N tasks have converged.

In the testing phase, we need to calculate for k = 1 … N and For each test sample it is required to evaluate an entire row of the kernel matrix, this row will be shared by all N binary tasks. In order to increase the efficiency of the calculation, we classify as many test samples simultaneously as allowed by the device memory.

We estimate the maximum number P of test samples that we can classify at a time based on the available device memory, and we break the test dataset into partitions of P samples. For each of these partitions we calculate using CUBLAS sgemm . Then for each sample p = 1 … P , we carry out a parallel reduction on the device to calculate This step is called Test Reduce and is illustrated in Figure 20.7 . Finally, back in the host, we add the unregularized bias parameter b _k to obtain and calculate (4).

The Test Reduce kernel function takes the following arguments: (1) Input arrays: the binary labels d_y , the Lagrange multiplier values d_a , an array with the dot products of the training samples d_Xdot1 , an array with the dot products of the testing samples d_Xdot2 , an array with the results of the sgemm operation d_ReductionF . (2) Output arrays: the array that will store the results of the reduction d_ReducedF . (3) Other parameters: the number of training samples in the dataset ntraining , the index of the test sample local to the partition being processed ii , the index of the test sample global to the test dataset iRow , the parameters kernel functions beta, c1, c2 , and c3 and the indicator of the kernel function used kernelcode . The kernel is launched on a 2-D grid where the blocks along the x dimension select specific subsets of the testing samples, and the y dimension specifies the binary task to work on.

In general, maximum multiprocessor occupancy does not necessarily guarantee best performance. Nevertheless, we chose the number of threads per block and the number of blocks per grid to maximize the device multiprocessor occupancy, but then searched the performance peak experimentally. Fortunately, for the case of multiclass SVMs, maximum occupancy and higher performance resulted to be aligned. Because of the similar nature of the Map, the Local Reduce, and Test Reduce kernel functions, the same block and grid sizes were used in all three cases.

Large classification problems achieve maximum occupancy by using 128 threads per block and 64 blocks per binary task. This implementation will also work for small classification problems by launching kernel functions with less of blocks and less threads. However, these cases might not result on a 100% of multiprocessor occupancy and consequently would be suboptimal.

The Update kernel function launches one thread per nonconverged binary task on a one-dimensional grid of blocks. The maximum number of threads per block is set to 128. In practice most classification problems involve less than 128 binary tasks; hence, a single block will be launched. This leads to low multiprocessor occupancy, but it is still faster than moving the computation of the Lagrange multiplier update to the host.

Graf et al. proposed an algorithm that would allow solving large-scale classification problems on clusters using individual instances of SVMs on a Cascade topology [2] . The characteristics of different topologies were investigated by Lu et al . [12] . In both cases, parallelism was achieved by distributing the SVM problem across multiple machines running single-threaded SVM solvers. In this section, we explain how we adapted the Cascade SVM algorithm to run on a multicore and multi-GPU scenario.

In order to orchestrate the operation of multiple devices, a port-based asynchronous messaging pattern was used. Typically, ports are communication end points associated to a state . The posting of a message to a port is followed by a predefined handler receiving and processing the message based on the actual state. Each port is composed by a queue and a thread pool that manages the messages as they arrive. The existence of this queue makes posting a nonblocking call, letting the sender thread proceed to do other work [9] .

In the Multi-GPU Cascade SVM algorithm, each SVM instance is associated to a single device and the state of the SVM is composed by all the variables involved in the training and testing phases. We added a port with the corresponding queue and thread pool on top of the SVM to handle messages asynchronously. Finally, message handlers invoke device kernels based on the SVM state and the message type and its content. In general, thread pools in charge of absorbing the messages accumulated in the queue are composed by multiple threads. Nevertheless, some multiprocessor devices only allow being managed by the same host thread during the entire execution of the program in order to maintain the context between device calls. This is the case for devices with CUDA Compute Capability 1.2; therefore, our thread pools were limited to a single thread, thus guaranteeing that communication with the device would be always performed by the same thread. Latest devices enable concurrent kernel execution to be allowed to increase the number of threads in the thread pool. We call the host thread, the Master thread, and the threads assigned to each of the devices, Slave threads. Figure 20.8 illustrates the structure of the port used to invoke SVM functions asynchronously; this is the basic building block of the Cascade SVM.

The Multi-GPU Cascade SVM algorithm is composed by a series of scatter-gather iterations initiated by the host that work as follows:

Figure 20.9 illustrates the structure of the Multi-GPU Cascade SVM and its modular composition using multiple instances of the single-device solver.

The performance tests measured in this subsection were carried out in a single machine with Intel Core i7 920 @ 2.67GHz and 6GB of RAM running Ubuntu 9.04 (64 bit). The graphics processor model used was a NVIDIA Tesla C1060 with 240 stream processors—each of them with a frequency of 1.3GHz. The card had 4GB of memory and a memory bandwidth of 102GB/s.

Table 20.3 shows the measured training and testing time for both binary and multiclass-SVM problems compared with LIBSVM. All datasets resulted on reductions of the training and testing times. It is observed that the GPU implementation benefited particularly classification problems with the largest numbers of dimensions. MNIST and USPS datasets, which have samples with hundreds of dimensions, resulted in the largest speedup both during the training phase and the testing phase.

The training time was reduced for these datasets in the range of (16x-57x), while the testing time was reduced (13x-112x). Nevertheless, binary and multiclass problems composed by samples with tens of dimensions, such as SHUTTLE or LETTER, obtained a reduced but still respectable acceleration, (3x-25x) for training and (2x-3x) for testing. These results are consistent with the binary SVM in [5] .

Table 20.4 shows the comparison of accuracy results for binary and multiclass classification. Results show that classification accuracy in the GPU does as well as the LIBSVM solver. Even if both optimization algorithms run with a tolerance value τ = 0.001, there is some variation in the number of support vectors, the value of the offset, and the number of iterations. It is speculated that this difference might be due to the application of second-order heuristics [11] or shrinking techniques [8] in LIBSVM. The number of iterations for multiclass problems is not comparable because the GPU solver runs all SMO instances concurrently, whereas LIBSVM does it sequentially.

The execution of the Multi-GPU Cascade SVM algorithm on two layers (four multiprocessor devices) resulted on an additional speedup for the largest and widest datasets. Smaller datasets will not gain additional acceleration, and the parallelization will be affected by the coordination overhead.

The WEB (binary) dataset reduced the SVM training time from 157 s to 106 s (1.48x) resulting on a total acceleration of 22.16x over LIBSVM, while MNIST (OVA 10) reduced the training time from 2067 s to 1180 s (1.75x) resulting on a total of 100.77x over LIBSVM.