Parallelising inference on cluster graphs
Date
2020-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: Cluster graphs (CGs), a technique used in machine learning, are computationally very
complex and often are slow to converge to an answer. There are also various approaches
that lead to convergence. Some approaches converge faster than others. However, finding
the optimal approach is non-trivial. We investigated the use of a new parallel inference
algorithm, comparing it to the current state of the art inference algorithms, such as parallel splash belief propagation and residual belief update. These were tested on several
CGs, ranging from a simple sudoku solver to a PGM that does satellite image denoising.
The results from these tests were as follows: for satellite image denoising a 5.3 times speedup was achieved, plateauing at 10 threads; for the sudoku solver the speedup ranged from
2.0 times to 4.0 times speed-up, normally plateauing around six threads. From the results
it is clear that the algorithms perform better the more clusters are present. It is also
important to note that hyperthreading affects the speed-up, as is shown by the reduction
in CPU instructions per cycle the more threads are being used.
AFRIKAANSE OPSOMMING: "Cluster graphs" (CGs), 'n tegniek wat gebruik word in masjienleer, verg ingewikkelde berekeninge en is dikwels stadig om na 'n antwoord te konvergeer. Daar is ook verskillende benaderings wat lei tot konvergensie. Sommige benaderings konvergeer vinniger as ander. Om die optimale benadering te vind is egter nie triviaal nie. Ons ondersoek die gebruik van 'n nuwe algoritme vir parallelle inferensie, en vergelyk dit met die huidige moderne inferensie-algoritmes soos "parallel splash belief propagation" en "residual belief propagation". Dit word op verskeie CG's getoets, wat wissel van 'n eenvoudige sudoku-oplosser tot 'n CG wat satellietbeelde ontruis. Die resultate van hierdie toetse was as volg: vir die satellietbeeld ontruising was dit 5.3 maal bespoedig en het by 10 "threads" 'n plato bereik; vir die sudoku-oplosser het dit bespoedig met tussen 2.0 en 4.0 maal en het normaalweg 'n plato bereik rondom ses "threads". Van die resultate is dit duidelik dat die algoritmes beter vaar hoe meer "clusters" daar is. Dit is ook belangrik om op te merk dat "hyperthreading" die hoeveelheid wat die toetse bespoedig beïnvloed, soos gewys deur die vermindering in CPU instruksies per siklus hoe meer "threads" gebruik word.
AFRIKAANSE OPSOMMING: "Cluster graphs" (CGs), 'n tegniek wat gebruik word in masjienleer, verg ingewikkelde berekeninge en is dikwels stadig om na 'n antwoord te konvergeer. Daar is ook verskillende benaderings wat lei tot konvergensie. Sommige benaderings konvergeer vinniger as ander. Om die optimale benadering te vind is egter nie triviaal nie. Ons ondersoek die gebruik van 'n nuwe algoritme vir parallelle inferensie, en vergelyk dit met die huidige moderne inferensie-algoritmes soos "parallel splash belief propagation" en "residual belief propagation". Dit word op verskeie CG's getoets, wat wissel van 'n eenvoudige sudoku-oplosser tot 'n CG wat satellietbeelde ontruis. Die resultate van hierdie toetse was as volg: vir die satellietbeeld ontruising was dit 5.3 maal bespoedig en het by 10 "threads" 'n plato bereik; vir die sudoku-oplosser het dit bespoedig met tussen 2.0 en 4.0 maal en het normaalweg 'n plato bereik rondom ses "threads". Van die resultate is dit duidelik dat die algoritmes beter vaar hoe meer "clusters" daar is. Dit is ook belangrik om op te merk dat "hyperthreading" die hoeveelheid wat die toetse bespoedig beïnvloed, soos gewys deur die vermindering in CPU instruksies per siklus hoe meer "threads" gebruik word.
Description
Thesis (MEng)--Stellenbosch University, 2020.
Keywords
Inference, UCTD, Parallelism (Linguistics), Machine learning, Cluster graphs, Artificial intelligence, Document clustering