Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Parallelising inference on cluster graphs
Thesis (MEng)--Stellenbosch University, 2020.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2020
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613903865774080 |
|---|---|
| access_status_str | Open Access |
| author | Verburgh, Cornel |
| author2 | Du Preez, Johan |
| author_browse | Du Preez, Johan Verburgh, Cornel |
| author_facet | Du Preez, Johan Verburgh, Cornel |
| author_sort | Verburgh, Cornel |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (MEng)--Stellenbosch University, 2020. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/109186 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:43:33.016Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2020 |
| publishDateRange | 2020 |
| publishDateSort | 2020 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/109186 Parallelising inference on cluster graphs Verburgh, Cornel Du Preez, Johan Barnard, Arno Stellenbosch University. Faculty of Engineering. Dept. of Electrical and Electronic Engineering. Inference UCTD Parallelism (Linguistics) Machine learning Cluster graphs Artificial intelligence Document clustering Thesis (MEng)--Stellenbosch University, 2020. 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. Masters 2020-11-23T07:30:12Z 2021-01-31T19:38:53Z 2020-11-23T07:30:12Z 2021-01-31T19:38:53Z 2020-12 Thesis http://hdl.handle.net/10019.1/109186 en_ZA Stellenbosch University 116 pages : illustrations application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Inference UCTD Parallelism (Linguistics) Machine learning Cluster graphs Artificial intelligence Document clustering Verburgh, Cornel Parallelising inference on cluster graphs |
| title | Parallelising inference on cluster graphs |
| title_full | Parallelising inference on cluster graphs |
| title_fullStr | Parallelising inference on cluster graphs |
| title_full_unstemmed | Parallelising inference on cluster graphs |
| title_short | Parallelising inference on cluster graphs |
| title_sort | parallelising inference on cluster graphs |
| topic | Inference UCTD Parallelism (Linguistics) Machine learning Cluster graphs Artificial intelligence Document clustering |
| url | http://hdl.handle.net/10019.1/109186 |
| work_keys_str_mv | AT verburghcornel parallelisinginferenceonclustergraphs |