Distributed systems are everywhere. From large datacenters to mobile devices, an ever richer assortment of applications and services relies on distributed systems, infrastructure, and protocols. Despite their ubiquity, testing and debugging distributed systems remains notoriously hard. Moreover, aside from inherent design challenges posed by partial failure, concurrency, or asynchrony, there remain significant challenges in the implementation of distributed systems. These programming challenges stem from the increasing complexity of the concurrent activities and reactive behaviors in a distributed system on the one hand, and the need to effectively leverage the parallelism offered by modern multi-core hardware, on the other hand. This thesis contributes Kompics, a programming model designed to alleviate some of these challenges. Kompics is a component model and programming framework for building distributed systems by composing message-passing concurrent components. Systems built with Kompics leverage multi-core machines out of the box, and they can be dynamically reconfigured to support hot software upgrades. A simulation framework enables deterministic execution replay for debugging, testing, and reproducible behavior evaluation for large-scale Kompics distributed systems. The same system code is used for both simulation and production deployment, greatly simplifying the system development, testing, and debugging cycle. We highlight the architectural patterns and abstractions facilitated by Kompics through a case study of a non-trivial distributed key-value storage system. CATS is a scalable, fault-tolerant, elastic, and self-managing key-value store which trades off service availability for guarantees of atomic data consistency and tolerance to network partitions. We present the composition architecture for the numerous protocols employed by the CATS system, as well as our methodology for testing the correctness of key CATS algorithms using the Kompics simulation framework. Results from a comprehensive performance evaluation attest that CATS achieves its claimed properties and delivers a level of performance competitive with similar systems which provide only weaker consistency guarantees. More importantly, this testifies that Kompics admits efficient system implementations. Its use as a teaching framework as well as its use for rapid prototyping, development, and evaluation of a myriad of scalable distributed systems, both within and outside our research group, confirm the practicality of Kompics. / Kompics / CATS / REST

Systems with multiple transmitting and receiving antennas in large-scale (LS-MIMO - large-scale multipleinput multiple-output) enable high spectral and energy efficiency gains, which results in an increase in the data transmission rate in the same band, without increasing the transmitted power per user. In addition, with the increase of the number of antennas in the base station (BS) it is possible to attend to a larger number of users per cell, in the same occupied band. Furthermore, it has been found in the literature that the reported advantages of LS-MIMO systems can be obtained with a large number of antennas on at least one side of the communication, usually in BS due to physical restriction in user equipments. However, such advantages have their cost: the use of a large number of antennas also difficult tasks involving signal processing, such as estimation of channel coefficients, precoding and signal detection. It is at this juncture that this Doctoral Thesis is developed, in which the computational complexity of performing efficient detection methods in LSMIMO communication systems is explored through the analysis of algorithms and optimization techniques in the solution of specific problems and still open. More precisely, this Thesis discusses and proposes promising detection techniques in LS-MIMO systems, aiming to improve performance metrics - in terms of error rate - and computational complexity - in terms of the number of mathematical operations. Initially, the problem is introduced through a conventional MIMO system model, where channels with imperfect estimates and correlation between transmitter (Tx) and receiver (Rx) antennas are considered. Preprocessing techniques based on lattice reduction (LR) are applied in linear detectors, in addition to the sphere decoder (SD), which proposes a lookup table procedure in order to provide a reduction in computational complexity. It is shown that the LR method in the pre-detection results in a significant performance gain in both the condition of uncorrelated and correlated channels, and in the latter scenario the improvement is even more remarkable due to the diversity gain provided. On the other hand, the complexity involved in the application of LR in high correlation scenarios becomes preponderant in linear detectors. In the LR-SD using the lookup table procedure, the optimum gain was reached in all scenarios, as expected, and resulted in a lower complexity than maximum likelihood (ML) detector, even with maximum correlation between antennas, which represents the most complex scenario for the LR technique. Next, the message passing (MP) detector is investigated, which makes use of Markov random fields (MRF) and factor graph (FG) graphical models. Moreover, it is shown in the literature that the message damping (MD) method applied to the MRF detector brings relevant performance gain without increasing computational complexity. On the other hand, the DF value is specified for only a restricted range of scenarios. Numerical results are extensively generated, in order to obtain a range of analysis of the MRF with MD, which resulted in the proposition of an optimal value for the DF, based on numerical curve fitting. Finally, in the face of the MGS detector, two approaches are proposed to reduce the negative impact caused by the random solution when high modulation orders are employed. The first is based on an average between multiple samples, called aMGS (averaged MGS). The second approach deploys a direct restriction on the range of the random solution, limiting in d the neighborhood of symbols that can be sorted, being called d-sMGS. Numerical simulation results show that both approaches result in gain of convergence in relation to MGS, especially: in regions of high system loading, d-sMGS detection demonstrated significant gain in both performance and complexity compared to aMGS and MGS; although in low-medium loading, the aMGS strategy showed less complexity, with performance marginally similar to the others. Furthermore, it is concluded that increasing the dimensions of the system favors a smaller restriction in the neighborhood. / Sistemas com múltiplas antenas transmissoras e múltiplas antenas receptoras em larga escala (LS-MIMO - large-scale multiple-input multiple-output) possibilitam altos ganhos em eficiência espectral e energética, o que resulta em aumento da taxa de transmissão de dados numa mesma banda ocupada, sem acréscimo da potência transmitida por usuário. Além disso, com o aumento do número de antenas na estação rádio-base (BS- base station) possibilita-se o atendimento de maior número de usuários por célula, em uma mesma banda ocupada. Ademais, comprovou-se na literatura que as vantagens relatadas dos sistemas LS-MIMO podem ser obtidas com um grande número de antenas em, pelo menos, um dos lados da comunicação, geralmente na BS devido à restrição física nos dispositivos móveis. Contudo, tais vantagens têm seu custo: a utilização de um grande número de antenas também dificulta tarefas que envolvem processamento de sinais, como estimação dos coeficientes de canal, precodificação e detecção de sinais. É nessa conjuntura em que se desenvolve esta Tese de Doutorado, na qual se explora o compromisso desempenho versus complexidade computacional de métodos eficientes de detecção em sistemas de comunicações LS-MIMO através da análise de algoritmos e técnicas de otimização na solução de problemas específicos e ainda em aberto. Mais precisamente, a presente Tese discute e propõe técnicas promissoras de detecção em sistemas LS-MIMO, visando a melhoria de métricas de desempenho - em termos de taxa de erro - e complexidade computacional - em termos de quantidade de operações matemáticas. Inicialmente, o problema é introduzido através de um modelo de sistema MIMO convencional, em que são considerados canais com estimativas imperfeitas e com correlação entre as antenas transmissoras (Tx) e entre as receptoras (Rx). Aplicam-se técnicas de pré-processamanto baseadas na redução treliça (LR - lattice reduction) em detectores lineares, além do detector esférico (SD - sphere decoder), o qual é proposto um procedimento de tabela de pesquisa a fim de prover redução na complexidade computacional. Mostra-se que o método LR na pré-detecção resulta em ganho de desempenho significante tanto na condição de canais descorrelacionados quanto fortemente correlacionados, sendo que, neste último cenário a melhoria é ainda mais notável, devido ao ganho de diversidade proporcionado. Por outro lado, a complexidade envolvida na aplicação da LR em alta correlação torna-se preponderante em detectores lineares. No LR-SD utilizando o procedimento de tabela de pesquisa, o ganho ótimo foi alcançado em todos os cenários, como esperado, e resultou em complexidade inferior ao detector de máxima verossimilhança (ML - maximum likelihood), mesmo com máxima correlação entre antenas, a qual representa o cenário de maior complexidade a técnica LR. Em seguida, o detector por troca de mensagens (MP - message passing) é investigado, o qual faz uso de modelos grafos do tipo MRF (Markov random fields) e FG (factor graph). Além disso, mostra-se na literatura que o método de amortecimento de mensagens (MD - message damping) aplicado ao detector MRF traz relevante ganho de desempenho sem aumento na complexidade computacional. Por outro lado, o valor do DF (damping factor) é especificado para somente uma variedade restrita de cenários. Resultados numéricos são extensivamente gerados, de forma a dispor de uma gama de análises de comportamento do MRF com MD, resultando na proposição de um valor ótimo para o DF, baseando-se em ajuste de curva numérico. Finalmente, em face ao detector MGS (mixed Gibbs sampling), são propostas duas abordagens visando a redução do impacto negativo causado pela solução aleatória quando altas ordens de modulação são empregadas. A primeira é baseada em uma média entre múltiplas amostras, chamada aMGS (averaged MGS). A segunda abordagem realiza uma restrição direta no alcance da solução aleatória, limitando em até d a vizinhança de símbolos que podem ser sorteados, sendo chamada de d-sMGS (d-simplificado MGS). Resultados de simulação numérica demonstram que ambas abordagens resultam em ganho de convergência em relação ao MGS, destacando-se: em regiões de alto carregamento, a detecção d-sMGS demonstrou ganho expressivo tanto em desempenho quanto em complexidade se comparada à aMGS e MGS; já em baixo-médio carregamentos, a estratégia aMGS demonstrou menor complexidade, com desempenho marginalmente semelhante às demais. Além disso, conclui-se que o aumento do número de dimensões do sistema favorece uma menor restrição na vizinhança.

Un grand nombre des problèmes d'optimisation, ainsi que des problèmes inverses, combinatoires ou hors équilibre qui apparaissent en physique statistique des systèmes complexes, peuvent être représentés comme un ensemble des variables en interaction sur un certain réseau. Bien que la recette universelle pour traiter ces problèmes n'existe pas, la compréhension qualitative et quantitative des problèmes complexes sur des graphes a fait des grands progrès au cours de ces dernières années. Un rôle particulier a été joué par des concepts empruntés de la physique des verres de spin et la théorie des champs, qui ont eu beaucoup de succès en ce qui concerne la description des propriétés statistiques des systèmes complexes et le développement d'algorithmes efficaces pour des problèmes concrets.En première partie de cette thèse, nous étudions des problèmes de diffusion sur des réseaux, avec la dynamique hors équilibre. En utilisant la méthode de cavité sur des trajectoires dans le temps, nous montrons comment dériver des équations dynamiques dites "message-passing'' pour une large classe de modèles avec une dynamique unidirectionnelle -- la propriété clef qui permet de résoudre le problème. Ces équations sont asymptotiquement exactes pour des graphes localement en arbre et en général représentent une bonne approximation pour des réseaux réels. Nous illustrons cette approche avec une application des équations dynamiques pour résoudre le problème inverse d'inférence de la source d'épidémie dans le modèle "susceptible-infected-recovered''.Dans la seconde partie du manuscrit, nous considérons un problème d'optimisation d'appariement planaire optimal sur une ligne. En exploitant des techniques de la théorie de champs et des arguments combinatoires, nous caractérisons une transition de phase topologique qui se produit dans un modèle désordonné simple, le modèle de Bernoulli. Visant une application à la physique des structures secondaires de l'ARN, nous discutons la relation entre la transition d'appariement parfait-imparfait et la transition de basse température connue entre les états fondu et vitreux de biopolymère; nous proposons également des modèles généralisés qui suggèrent une correspondance exacte entre la matrice des contacts et la séquence des nucléotides, permettant ainsi de donner un sens à la notion des alphabets effectifs non-entiers. / A large number of optimization, inverse, combinatorial and out-of-equilibrium problems, arising in the statistical physics of complex systems, allow for a convenient representation in terms of disordered interacting variables defined on a certain network. Although a universal recipe for dealing with these problems does not exist, the recent years have seen a serious progress in understanding and quantifying an important number of hard problems on graphs. A particular role has been played by the concepts borrowed from the physics of spin glasses and field theory, that appeared to be extremely successful in the description of the statistical properties of complex systems and in the development of efficient algorithms for concrete problems.In the first part of the thesis, we study the out-of-equilibrium spreading problems on networks. Using dynamic cavity method on time trajectories, we show how to derive dynamic message-passing equations for a large class of models with unidirectional dynamics -- the key property that makes the problem solvable. These equations are asymptotically exact for locally tree-like graphs and generally provide a good approximation for real-world networks. We illustrate the approach by applying the dynamic message-passing equations for susceptible-infected-recovered model to the inverse problem of inference of epidemic origin. In the second part of the manuscript, we address the optimization problem of finding optimal planar matching configurations on a line. Making use of field-theory techniques and combinatorial arguments, we characterize a topological phase transition that occurs in the simple Bernoulli model of disordered matching. As an application to the physics of the RNA secondary structures, we discuss the relation of the perfect-imperfect matching transition to the known molten-glass transition at low temperatures, and suggest generalized models that incorporate a one-to-one correspondence between the contact matrix and the nucleotide sequence, thus giving sense to the notion of effective non-integer alphabets.

Distributed systems are everywhere. From large datacenters to mobile devices, an ever richer assortment of applications and services relies on distributed systems, infrastructure, and protocols. Despite their ubiquity, testing and debugging distributed systems remains notoriously hard. Moreover, aside from inherent design challenges posed by partial failure, concurrency, or asynchrony, there remain significant challenges in the implementation of distributed systems. These programming challenges stem from the increasing complexity of the concurrent activities and reactive behaviors in a distributed system on the one hand, and the need to effectively leverage the parallelism offered by modern multi-core hardware, on the other hand. This thesis contributes Kompics, a programming model designed to alleviate some of these challenges. Kompics is a component model and programming framework for building distributed systems by composing message-passing concurrent components. Systems built with Kompics leverage multi-core machines out of the box, and they can be dynamically reconfigured to support hot software upgrades. A simulation framework enables deterministic execution replay for debugging, testing, and reproducible behavior evaluation for largescale Kompics distributed systems. The same system code is used for both simulation and production deployment, greatly simplifying the system development, testing, and debugging cycle. We highlight the architectural patterns and abstractions facilitated by Kompics through a case study of a non-trivial distributed key-value storage system. CATS is a scalable, fault-tolerant, elastic, and self-managing key-value store which trades off service availability for guarantees of atomic data consistency and tolerance to network partitions. We present the composition architecture for the numerous protocols employed by the CATS system, as well as our methodology for testing the correctness of key CATS algorithms using the Kompics simulation framework. Results from a comprehensive performance evaluation attest that CATS achieves its claimed properties and delivers a level of performance competitive with similar systems which provide only weaker consistency guarantees. More importantly, this testifies that Kompics admits efficient system implementations. Its use as a teaching framework as well as its use for rapid prototyping, development, and evaluation of a myriad of scalable distributed systems, both within and outside our research group, confirm the practicality of Kompics. / <p>QC 20130520</p>

Multi-antenna wireless communication systems that employ a large number of antennas have recently stirred a lot of research interest. This is mainly due to the possibility of achieving very high spectral efficiency, power efficiency, and link reliability in such large-scale multiple-input multiple-output (MIMO) systems. An emerging architecture for large-scale multiuser MIMO communications is one where each base station (BS) is equipped with a large number of antennas (tens to hundreds of antennas) and the user terminals are equipped with fewer antennas (one to four antennas) each. The backhaul communication between base stations is also carried out using large number of antennas. Because of the high dimensionality of large-scale MIMO signals, the computational complexity of various transceiver operations can be prohibitively large. Therefore, low complexity techniques that scale well for transceiver signal processing in such large-scale MIMO systems are crucial. The transceiver operations of interest include signal encoding at the transmitter, and channel estimation, detection and decoding at the receiver. This thesis focuses on the design and analysis of novel low-complexity transceiver signal processing schemes for large-scale MIMO systems. In this thesis, we consider two types of large-scale MIMO systems, namely, massive MIMO systems and generalized spatial modulation MIMO (GSM-MIMO) systems. In massive MIMO, the mapping of information bits to modulation symbols is done using conventional modulation alphabets (e.g., QAM, PSK). In GSM-MIMO, few of the avail-able transmit antennas are activated in a given channel use, and information bits are conveyed through the indices of these active antennas, in addition to the bits conveyed through conventional modulation symbols. We also propose a novel modulation scheme named as precoder index modulation, where information bits are conveyed through the index of the chosen precoder matrix as well as the modulation symbols transmitted. Massive MIMO: In this part of the thesis, we propose a novel MIMO receiver which exploits channel hardening that occurs in large-scale MIMO channels. Channel hardening refers to the phenomenon where the off-diagonal terms of HH H become much weaker compared to the diagonal terms as the size of the channel gain matrix H increases. We exploit this phenomenon to devise a low-complexity channel estimation scheme and a message passing algorithm for signal detection at the BS receiver in massive MIMO systems. We refer to the proposed receiver as the channel hardening-exploiting message passing (CHEMP) receiver. The key novelties in the proposed CHEMP receiver are: (i) operation on the matched filtered system model, (ii) Gaussian approximation on the off-diagonal terms of the HH H matrix, and (iii) direct estimation of HH H instead of H and use of this estimate of HH H for detection The performance and complexity results show that the proposed CHEMP receiver achieves near-optimal performance in large-scale MIMO systems at complexities less than those of linear receivers like minimum mean squared error (MMSE) receiver. We also present a log-likelihood ratio (LLR) analysis that provides an analytical reasoning for this better performance of the CHEMP receiver. Further, the proposed message passing based detection algorithm enables us to combine it with low density parity check (LDPC) decoder to formulate a joint message passing based detector-decoder. For this joint detector-decoder, we design optimized irregular binary LDPC codes specific to the massive MIMO channel and the proposed receiver through EXIT chart matching. The LDPC codes thus obtained are shown to achieve improved coded bit error rate (BER) performance compared to off-the-shelf irregular LDPC codes. The performance of the CHEMP receiver degrades when the system loading factor (ratio of the number of users to the number of BS antennas) and the modulation alpha-bet size are large. It is of interest to devise receiver algorithms that work well for high system loading factors and modulation alphabet sizes. For this purpose, we propose a low-complexity factor-graph based vector message passing algorithm for signal detection. This algorithm uses a scalar Gaussian approximation of interference on the basic sys-tem model. The performance results show that this algorithm performs well for large modulation alphabets and high loading factors. We combine this detection algorithm with a non-binary LDPC decoder to obtain a joint detector-decoder, where the field size of the non-binary LDPC code is same as the size of the modulation alphabet. For this joint message passing based detector-decoder, we design optimized non-binary irregular LDPC codes tailored to the massive MIMO channel and the proposed detector. GSM-MIMO: In this part of the thesis, we consider GSM-MIMO systems in point-to-point as well as multiuser communication settings. GSM-MIMO has the advantage of requiring only fewer transmit radio frequency (RF) chains than the number of transmit antennas. We analyze the capacity of point-to-point GSM-MIMO, and obtain lower and upper bounds on the GSM-MIMO system capacity. We also derive an upper bound on the BER performance of maximum likelihood detection in GSM-MIMO systems. This bound is shown to be tight at moderate to high signal-to-noise ratios. When the number of transmit and receive antennas are large, the complexity of en-coding and decoding of GSM-MIMO signals can be prohibitively high. To alleviate this problem, we propose a low complexity GSM-MIMO encoding technique that utilizes com-binatorial number system for bits-to-symbol mapping. We also propose a novel layered message passing (LaMP) algorithm for decoding GSM-MIMO signals. Low computational complexity is achieved in the LaMP algorithm by detecting the modulation bits and the antenna index bits in two deferent layers. We then consider large-scale multiuser GSM-MIMO systems, where multiple users employ GSM at their transmitters to communicate with a BS having a large number of receive antennas. For this system, we develop computationally efficient message passing algorithms for signal detection using vector Gaussian approximation of interference. The performance results of these algorithms show that the GSM-MIMO system outperforms the massive MIMO system by several dBs for the same spectral efficiency. Precoder index modulation: It is known that the performance of a communication link can be enhanced by exploiting time diversity without reducing the rate of transmission using pseudo random phase preceding (PRPP). In order to further improve the performance of GSM-MIMO, we apply PRPP technique to GSM-MIMO systems. PRPP provides additional diversity advantage at the receiver and further improves the performance of GSM-MIMO systems. For PRPP-GSM systems, we propose methods to simultaneously precode both the antenna index bits and the modulation symbols using rectangular precoder matrices. Finally, we extend the idea of index modulation to pre-coding and propose a new modulation scheme referred to as precoder index modulation (PIM). In PIM, information bits are conveyed through the index of a prehared PRPP matrix, in addition to the information bits conveyed through the modulation symbols. PIM is shown to increase the achieved spectral efficiency, in addition to providing diver-sity advantages.

Face au déluge actuel de données principalement non structurées, les graphes ont démontré, dans une variété de domaines scientifiques, leur importance croissante comme language abstrait pour décrire des interactions complexes entre des objets complexes. L’un des principaux défis posés par l’étude de ces réseaux est l’inférence de propriétés macroscopiques à grande échelle, affectant un grand nombre d’objets ou d’agents, sur la seule base des interactions microscopiquesqu’entretiennent leurs constituants élémentaires. La physique statistique, créée précisément dans le but d’obtenir les lois macroscopiques de la thermodynamique à partir d’un modèle idéal de particules en interaction, fournit une intuition décisive dans l’étude des réseaux complexes.Dans cette thèse, nous utilisons des méthodes issues de la physique statistique des systèmes désordonnés pour mettre au point et analyser de nouveaux algorithmes d’inférence sur les graphes. Nous nous concentrons sur les méthodes spectrales, utilisant certains vecteurs propres de matrices bien choisies, et sur les graphes parcimonieux, qui contiennent une faible quantité d’information. Nous développons une théorie originale de l’inférence spectrale, fondée sur une relaxation de l’optimisation de certaines énergies libres en champ moyen. Notre approche est donc entièrement probabiliste, et diffère considérablement des motivations plus classiques fondées sur l’optimisation d’une fonction de coût. Nous illustrons l’efficacité de notre approchesur différents problèmes, dont la détection de communautés, la classification non supervisée à partir de similarités mesurées aléatoirement, et la complétion de matrices. / In an era of unprecedented deluge of (mostly unstructured) data, graphs are proving more and more useful, across the sciences, as a flexible abstraction to capture complex relationships between complex objects. One of the main challenges arising in the study of such networks is the inference of macroscopic, large-scale properties affecting a large number of objects, based solely on he microscopic interactions between their elementary constituents. Statistical physics, precisely created to recover the macroscopic laws of thermodynamics from an idealized model of interacting particles, provides significant insight to tackle such complex networks.In this dissertation, we use methods derived from the statistical physics of disordered systems to design and study new algorithms for inference on graphs. Our focus is on spectral methods, based on certain eigenvectors of carefully chosen matrices, and sparse graphs, containing only a small amount of information. We develop an original theory of spectral inference based on a relaxation of various meanfield free energy optimizations. Our approach is therefore fully probabilistic, and contrasts with more traditional motivations based on the optimization of a cost function. We illustrate the efficiency of our approach on various problems, including community detection, randomized similarity-based clustering, and matrix completion.

This master's thesis deals with demonstration of various approaches to probabilistic inference in Bayesian networks. Basics of probability theory, introduction to Bayesian networks, methods for Bayesian inference and applications of Bayesian networks are described in theoretical part. Inference techniques are explained and complemented by their algorithm. Techniques are also illustrated on example. Practical part contains implementation description, experiments with demonstration applications and conclusion of the results.

Magnetic resonance images (MRI) are acquired by sampling the current of induced electromotiveforce (EMF). EMF is induced due to flux of the net magnetic field from coherent nuclear spins with intrinsic magnetic dipole moments. The spins are excited by (non-ionizing) radio frequency electromagnetic radiation in conjunction with stationary and gradient magnetic fields. These images reveal detailed internal morphological structures as well as enable functional assessment of the body that can help diagnose a wide range of medical conditions. The aim of this project was to unwrap phase contrast cine magnetic resonance images, targeting the great vessels. The maximum encoded velocity (venc) is limited to the angular phase range [-π, π] radians. This may result in aliasing if the venc is set too low by the MRI personnel. Aliased images yield inaccurate cardiac stroke volume measurements and therefore require acquisition retakes. The retakes might be avoided if the images could be unwrapped in post-processing instead. Using computer vision, the angular phase of flow measurements as well as the angular phase of retrospectively wrapped image sets were unwrapped. The performances of three algorithms were assessed, Laplacian algorithm, sequential tree-reweighted message passing and iterative graph cuts. The associated energy formulation was also evaluated. Iterative graph cuts was shown to be the most robust with respect to the number of wraps and the energies correlated with the errors. This thesis shows that there is potential to reduce the number of acquisition retakes, although the MRI personnel still need to verify that the unwrapping performances are satisfactory. Given the promising results of iterative graph cuts, next it would be valuable to investigate the performance of a globally optimal surface estimation algorithm.

Training a Support Vector Machine (SVM) requires the solution of a very large quadratic programming (QP) optimization problem. Sequential Minimal Optimization (SMO) is a decomposition-based algorithm which breaks this large QP problem into a series of smallest possible QP problems. However, it still costs O(n2) computation time. In our SVM implementation, we can do training with huge data sets in a distributed manner (by breaking the dataset into chunks, then using Message Passing Interface (MPI) to distribute each chunk to a different machine and processing SVM training within each chunk). In addition, we moved the kernel calculation part in SVM classification to a graphics processing unit (GPU) which has zero scheduling overhead to create concurrent threads. In this thesis, we will take advantage of this GPU architecture to improve the classification performance of SVM.