Support Vector Machine Implementation on MPI-CUDA and Tensorflow Framework

MPI is a standard interface for communication between different nodes in distributed memory, where each node has its local address space and runs independently. MPI provides node-to-node communication and collective communication through the communication network between the nodes. The MPI programming model follows the Single Program Multiple Data (SPMD) model, where a set of nodes executes the same instructions on different data. The instructions are loaded onto all nodes, but each node can follow a different execution path. There are many implementations that follow the MPI standard; the most popular of them are MPICH and LAMMPI [5].

CUDA is an API used for leveraging GPU parallel architecture in General-Purpose Programming (GPGPU). NVIDIA introduced the CUDA API for the first time in November 2006 to overcome the limitations of using GPUs in GPGPU due to the difficulty of knowing and interacting with DirectX or OpenGL. In the CUDA programming model, the GPU can be considered as a massive parallel Single Instruction Multiple Data (SIMD) Streaming Multiprocessor (SM) array. A group of grid/block/thread can be assigned to execute a kernel [7].

A kernel is a program to be executed with each thread, using thread identifier and block identifier. Each thread can perform the kernel task on a different set of data in parallel. The CPU, or ’host,’ is responsible for launching the kernel to be executed on the GPU, or ’device.’ It also sends input kernel data from its memory ’host memory’ to the GPU ’device memory. Then, it copies the result back from ’device memory’ to ’host memory’ Each SM has its own shared memory, which is common to all the processors inside it. It also has constant memory caches. Communication between different SMs occurs through device memory, which is available to all the processors of the SM [7, 8, 9].

MPI represents a distributed memory architecture, while CUDA represents a shared memory architecture. The hybrid memory architecture combines both distributed and shared memory architectures. Each node has its own multicore processor that can be utilized as part of a shared architecture memory model. Different nodes are considered part of a distributed memory architecture, communicating through a network and using various communication directives to exchange messages among them [10, 11]. This is illustrated in Fig.1.

Recently, many efficient and easy-to-use ML frameworks have been introduced to accommodate the increasing complexity of ML algorithms. They allow beginners and experts to develop their own ML techniques. TensorFlow is one such ML framework library. TensorFlow is an open-source ML library interface for expressing ML algorithms and executing predefined ML algorithms

TensorFlow is used for high-performance numerical computation. Its flexible architecture allows easy implementation and deployment on cross-platforms (desktops, clusters of servers, CPUs, GPUs, TPUs, and mobile devices), and it can run on several operating systems [6]. TensorFlow is an expression where a tensor is data, and flow is the expressing flow for this data in a dataflow graph ($TensorFlow=Tensor+Flow=Data+Flow$). A dataflow graph is a form of a directed graph consisting of a set of nodes and edges between them, where nodes describe instructions, and edges represent the data flow [6]. TensorFlow implementations are represented in two steps; the first of them is constructing a dataflow graph, the second uses a session to run instructions in this graph and evaluate the output result. The session is the runtime environment of a graph, where instructions are executed, and tensors are calculated, as shown in Fig.2.

SVM is binary classifier ML algorithm. Given a set of training data samples $X=\{x_{1},x_{2}\dots x_{n}\}$, where n is the size of $X$ , $x\in R_{d}$ and d input feature size, $yi\in\{1,-1\}$ is the class label of input sample $x_{i}$. Assuming classes are linearly separable, SVM aim to find a hyperplane that gives the maximum margin between two classes of data in $X$. ”Support vectors” are the vectors of both classes located on the margin hyperplane [12]. In most cases, training data samples are not linearly separable, so this hyperplane is not exist. Using Kernel function gives advantage to SVM for non-linearly separable classes [13]. However SVM is a binary classifier technique, but it can be used as multi-class classifier. The “one-against-one” is the more suitable method for practical use than other methods. For $m$ classes, there are $m(m-1)/2$ independent binary classification problems [14].

Sequential minimum optimization (SMO) algorithm used to solve the SVM binary training quadratic problem, where training data samples are divided into smaller working set. SMO solves the smallest task at each step to find only two optimization variables and update two Lagrange multipliers under the Karush-Kuhn-Tucker (KKT) constraints [15, 16, 17].

In [18, 19], the SMO is implemented in parallel, making full use of the advantage of the huge computational power of GPU devices. In MPI-CUDA implementation [20], we launched a thread per independent training data sample. Hence, most of the SMO computation steps can run in parallel. Then, convergence checks were executed on the host for every set of iterations on the device, as shown in Fig.3. Moreover, Fig.4 illustrates the use of Hybrid MPI-CUDA to execute the multi-class training problem. It involves running multiple parallel binary SMOs to implement a parallel multi-class SMO. We distribute the number of parallel binary SMOs among the MPI working nodes [20].

As with many implementations of algorithms in TensorFlow, SVM is described as a directed graph consisting of nodes and edges, where nodes represent instructions (operations), and edges represent data flow. A ’Variable’ is a special instruction (operation) without computation; it is used only for storing any parameters of a described algorithm. A ’Placeholder’ is a tensor that will always be fed. After graph construction, a TensorFlow session is used to execute the graph and compute the result [21, 22].

For the SVM binary training problem, the directed graph consists of three steps. The first of them is initializing the input training data samples using ’Placeholders’. The second step is defining SVM ’Variables’ and describing the Gaussian RBF kernel function. The third step is describing the SVM model and declaring the gradient descent optimizer algorithm, as shown in Fig.5. After describing the graph for SVM binary training process, a TensorFlow session is used to run it and compute the output result. Multiple running sessions are used to implement the SVM multiclass training process with the ’one-against-one’ approach.

Table I shows the experimental datasets. The first dataset is a hyperspectral dataset consisting of 1096x715 pixels and nine ground-truth classes labeled as water, trees, grass, parking lot, bare soil, asphalt, bitumen, tiles, and shadow. The second dataset is the Iris flower multivariate dataset with 150 total data samples and 3 classes (setosa, virginica, versicolor). The third dataset is the Breast Cancer Wisconsin dataset with 569 data samples and 2 possible classes (benign, malignant).

Table II shows the hardware specifications for the machine used to carry out these experiments. CUDA Version 9.0 and MPICH2 are used to implement SVM MPI-CUDA, while SVM Tensorflow is implemented using TensorFlow version 1.8.0. Both implementations run on Windows 10 (64-bit).

For the Pavia Centre dataset, Table III and Fig.6 present the binary training times at various sample sizes for a binary class SVM. This comparison involves the CUDA-GPU implementation against the Tensorflow-GPU implementation. Specifically, CUDA-GPU achieved a speedup of 154.3X over Tensorflow-GPU with 800 sample points for each class. Similarly, Table IV and Fig.7 present the training times for multiclass SVM on different sample sizes using the hybrid MPI-CUDA implementation over Multi-Tensorflow for the same dataset. MPI-CUDA achieved a speedup of 14.9X over Multi-Tensorflow with 800 sample points per each class.

Table V shows the training times for the Iris Flower dataset with 2 classes, where CUDA-GPU achieved a speedup of 60.5X over Tensorflow-GPU. Additionally, for the Breast Cancer dataset, CUDA-GPU achieved a speedup of 117.9X. The overall results indicate that the speedup is proportionally related to the training datapoint size. Utilizing the CUDA API provides explicit control over the number of worker streaming multiprocessors (SM), thread/block, and memory management, as opposed to the implicit control in Tensorflow. Due to this explicit control, the SVM CUDA implementation demonstrates a speedup over the SVM Tensorflow implementation in the tested datasets.

Furthermore, the MPI communication overhead between nodes in the MPI-CUDA implementation may influence the overall performance, but it is only required for transferring input data at the beginning of the execution and sending the result data at the end of execution. There is no communication needed during the execution, resulting in a small overhead on system performance. Despite the MPI communication in SVM MPI-CUDA, this implementation achieved a speedup over the Multi-Tensorflow implementation in all the tested datasets.

Finally, Table VI shows the training time for the Iris Flower dataset and the Breast Cancer dataset on Tensorflow-CPU and Tensorflow-GPU. There is no change in running the same Tensorflow implementation on both CPU and GPU, as Tensorflow has a flexible architecture that allows easy deployment over different platforms.