{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/104846"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/104846","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"A GPU implementation of tiled belief propagation on Markov random fields","abstract":"In this work, we present a parallelized version of tiled belief propagation for stereo matching. The proposed algorithm is implemented in CUDA to leverage parallel processing capabilities of GPUs. In our solution, the original tiled BP algorithm is combined with a number of optimizations specific to parallel programs in CUDA. For the given test inputs, the proposed solution runs in 7.96 milliseconds on Nvidia Tesla C2050, achieving acceptable accuracy with respect to the reference code. This work has been published in 2013 Eleventh ACM/IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE 2013), winning the MEMOCODE Design Contest 2013 in the adjusted cost-accuracy category. To the best of authors knowledge, this represented the first work in optimizing a parallelized version of the tiled BP algorithm. After presenting our approach, at selecting an appropriate candidate algorithm for parallelization and implementing in on GPU by applying a series of appropriate optimizations, we discuss the current state of the art on stereo matching, that has been presented since publishing this work.","abstract_html":"In this work, we present a parallelized version of tiled belief propagation for stereo matching. The proposed algorithm is implemented in CUDA to leverage parallel processing capabilities of GPUs. In our solution, the original tiled BP algorithm is combined with a number of optimizations specific to parallel programs in CUDA. For the given test inputs, the proposed solution runs in 7.96 milliseconds on Nvidia Tesla C2050, achieving acceptable accuracy with respect to the reference code. This work has been published in 2013 Eleventh ACM/IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE 2013), winning the MEMOCODE Design Contest 2013 in the adjusted cost-accuracy category. To the best of authors knowledge, this represented the first work in optimizing a parallelized version of the tiled BP algorithm. After presenting our approach, at selecting an appropriate candidate algorithm for parallelization and implementing in on GPU by applying a series of appropriate optimizations, we discuss the current state of the art on stereo matching, that has been presented since publishing this work.","abstract_has_math":false,"creators":["Kotsifakou, Maria"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Adve, Vikram S."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019-08-23T19:55:40Z","date_published":"2019-08-23T19:55:40Z","updated_at":"2026-07-22T22:24:42Z","subjects":["stereo matching","tiled belief propagation","GPUs"],"languages":["en"],"rights":["Copyright 2019 Maria Kotsifakou"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/104846","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Adve, Vikram S."]},{"key":"dc:creator","label":"Author","values":["Kotsifakou, Maria"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2019-08-23T19:55:40Z","2019-04-17","2019-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["stereo matching","tiled belief propagation","GPUs"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2019 Maria Kotsifakou"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/104846"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this work, we present a parallelized version of tiled belief propagation for stereo matching. The proposed algorithm is implemented in CUDA to leverage parallel processing capabilities of GPUs. In our solution, the original tiled BP algorithm is combined with a number of optimizations specific to parallel programs in CUDA. For the given test inputs, the proposed solution runs in 7.96 milliseconds on Nvidia Tesla C2050, achieving acceptable accuracy with respect to the reference code. This work has been published in 2013 Eleventh ACM/IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE 2013), winning the MEMOCODE Design Contest 2013 in the adjusted cost-accuracy category. To the best of authors knowledge, this represented the first work in optimizing a parallelized version of the tiled BP algorithm. After presenting our approach, at selecting an appropriate candidate algorithm for parallelization and implementing in on GPU by applying a series of appropriate optimizations, we discuss the current state of the art on stereo matching, that has been presented since publishing this work.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2019-08-22 without embargo terms","The student, Maria Kotsifakou, accepted the attached license on 2019-04-16 at 13:42.","The student, Maria Kotsifakou, submitted this Thesis for approval on 2019-04-16 at 14:12.","This Thesis was approved for publication on 2019-04-17 at 14:45.","DSpace SAF Submission Ingestion Package generated from Vireo submission #13678 on 2019-08-22 at 14:44:09","Made available in DSpace on 2019-08-23T19:55:40Z (GMT). No. of bitstreams: 2 KOTSIFAKOU-THESIS-2019.pdf: 1444354 bytes, checksum: ff5f3d9b71f2658e7947e0c660722e94 (MD5) LICENSE.txt: 4213 bytes, checksum: 3a65a3dd6835e38c55df139e56d44396 (MD5) Previous issue date: 2019-04-17"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["A GPU implementation of tiled belief propagation on Markov random fields"]}]}],"canonical_facts":{"dc:contributor":["Adve, Vikram S."],"dc:creator":["Kotsifakou, Maria"],"dc:date":["2019-08-23T19:55:40Z","2019-04-17","2019-05"],"dc:description":["In this work, we present a parallelized version of tiled belief propagation for stereo matching. The proposed algorithm is implemented in CUDA to leverage parallel processing capabilities of GPUs. In our solution, the original tiled BP algorithm is combined with a number of optimizations specific to parallel programs in CUDA. For the given test inputs, the proposed solution runs in 7.96 milliseconds on Nvidia Tesla C2050, achieving acceptable accuracy with respect to the reference code. This work has been published in 2013 Eleventh ACM/IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE 2013), winning the MEMOCODE Design Contest 2013 in the adjusted cost-accuracy category. To the best of authors knowledge, this represented the first work in optimizing a parallelized version of the tiled BP algorithm. After presenting our approach, at selecting an appropriate candidate algorithm for parallelization and implementing in on GPU by applying a series of appropriate optimizations, we discuss the current state of the art on stereo matching, that has been presented since publishing this work.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2019-08-22 without embargo terms","The student, Maria Kotsifakou, accepted the attached license on 2019-04-16 at 13:42.","The student, Maria Kotsifakou, submitted this Thesis for approval on 2019-04-16 at 14:12.","This Thesis was approved for publication on 2019-04-17 at 14:45.","DSpace SAF Submission Ingestion Package generated from Vireo submission #13678 on 2019-08-22 at 14:44:09","Made available in DSpace on 2019-08-23T19:55:40Z (GMT). No. of bitstreams: 2 KOTSIFAKOU-THESIS-2019.pdf: 1444354 bytes, checksum: ff5f3d9b71f2658e7947e0c660722e94 (MD5) LICENSE.txt: 4213 bytes, checksum: 3a65a3dd6835e38c55df139e56d44396 (MD5) Previous issue date: 2019-04-17"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/104846"],"dc:language":["en"],"dc:rights":["Copyright 2019 Maria Kotsifakou"],"dc:subject":["stereo matching","tiled belief propagation","GPUs"],"dc:title":["A GPU implementation of tiled belief propagation on Markov random fields"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:42Z"}