{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/34099"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/34099","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"A Parallel Implementation Of Hierarchical Belief Propagation","abstract":"Though Belief Propagation (BP) algorithms generate high quality results for a wide range of Markov Random Field (MRF) formulated energy minimization problems, they require large memory bandwidths and could not achieve real-time performance when applied to many real-life inference tasks. There is an increasing demand for efficient parallel inference algorithms as the size of problems increase and computer architectures move towards multi-core. In this work, we proposed a new high speed parallel computational structure for hierarchical Belief Propagation on shared memory architecture, which is based on a modification and generalization of the hierarchical BP algorithm presented by Felzenszwalb and Huttenlocher. Our parallel hierarchical belief propagation (PHBP) computational structure supports arbitrary grouping of nodes in multiscale computation and works for graphs in general topologies (including non grid structure graphs). Secondly, a fully parallel framework of hierarchical BP using sequential asynchronous message updating scheme (accelerated message updating) is developed. We achieved parallelization of both pre-computation portion and computational intense message passing portion. Lastly, we empirically evaluated the performance of algorithm on several computer vision tasks where we achieved nearly linear parallel scaling and outperform other alternative algorithms. Specifically, for the task of restoring a 608*456 noisy image with 16 gray levels, our PHBP takes around 100ms while a comparable result needs around 30s using Parallel Splash on a same 8 core shared memory system.","abstract_html":"Though Belief Propagation (BP) algorithms generate high quality results for a wide range of Markov Random Field (MRF) formulated energy minimization problems, they require large memory bandwidths and could not achieve real-time performance when applied to many real-life inference tasks. There is an increasing demand for efficient parallel inference algorithms as the size of problems increase and computer architectures move towards multi-core. In this work, we proposed a new high speed parallel computational structure for hierarchical Belief Propagation on shared memory architecture, which is based on a modification and generalization of the hierarchical BP algorithm presented by Felzenszwalb and Huttenlocher. Our parallel hierarchical belief propagation (PHBP) computational structure supports arbitrary grouping of nodes in multiscale computation and works for graphs in general topologies (including non grid structure graphs). Secondly, a fully parallel framework of hierarchical BP using sequential asynchronous message updating scheme (accelerated message updating) is developed. We achieved parallelization of both pre-computation portion and computational intense message passing portion. Lastly, we empirically evaluated the performance of algorithm on several computer vision tasks where we achieved nearly linear parallel scaling and outperform other alternative algorithms. Specifically, for the task of restoring a 608*456 noisy image with 16 gray levels, our PHBP takes around 100ms while a comparable result needs around 30s using Parallel Splash on a same 8 core shared memory system.","abstract_has_math":false,"creators":["Tian, Yuan"],"institution":"Cornell University","degree_name":"M.S., Electrical Engineering","degree_level":"Master of Science","degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":["Manohar, Rajit"],"committee_members":["Martinez, Jose F.","Chen, Tsuhan"],"year":2013,"date_issued":"2013-05-26","date_published":"2013-05-26","updated_at":"2026-11-19T03:16:49Z","subjects":["Belief Propagation","Graphical Models","Parallelism"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["8267695"],"render_values":[{"text":"8267695","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/34099","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/34099","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://ecommons.cornell.edu/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aecommons.cornell.edu%3A1813%2F34099","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.chair","label":"Chair","values":["Manohar, Rajit"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Martinez, Jose F.","Chen, Tsuhan"]},{"key":"dc:creator","label":"Author","values":["Tian, Yuan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2013-09-05T15:57:11Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2018-05-27T06:00:35Z"]},{"key":"dc:date.issued","label":"Date","values":["2013-05-26"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Master of Science"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S., Electrical Engineering"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Cornell University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Belief Propagation","Graphical Models","Parallelism"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["8267695"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/34099"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"16aaa476-c037-41d0-9ec8-a47b145982fa\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>A Parallel Implementation Of Hierarchical Belief Propagation</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2013-05-26</PublicationDate> <Authors> <Author> <DisplayName>Tian, Yuan</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>Belief Propagation</Keyword> <Keyword>Graphical Models</Keyword> <Keyword>Parallelism</Keyword> <Abstract>Though Belief Propagation (BP) algorithms generate high quality results for a wide range of Markov Random Field (MRF) formulated energy minimization problems, they require large memory bandwidths and could not achieve real-time performance when applied to many real-life inference tasks. There is an increasing demand for efficient parallel inference algorithms as the size of problems increase and computer architectures move towards multi-core. In this work, we proposed a new high speed parallel computational structure for hierarchical Belief Propagation on shared memory architecture, which is based on a modification and generalization of the hierarchical BP algorithm presented by Felzenszwalb and Huttenlocher. Our parallel hierarchical belief propagation (PHBP) computational structure supports arbitrary grouping of nodes in multiscale computation and works for graphs in general topologies (including non grid structure graphs). Secondly, a fully parallel framework of hierarchical BP using sequential asynchronous message updating scheme (accelerated message updating) is developed. We achieved parallelization of both pre-computation portion and computational intense message passing portion. Lastly, we empirically evaluated the performance of algorithm on several computer vision tasks where we achieved nearly linear parallel scaling and outperform other alternative algorithms. Specifically, for the task of restoring a 608*456 noisy image with 16 gray levels, our PHBP takes around 100ms while a comparable result needs around 30s using Parallel Splash on a same 8 core shared memory system.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Tian, Yuan"]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description.abstract","label":"Abstract","values":["Though Belief Propagation (BP) algorithms generate high quality results for a wide range of Markov Random Field (MRF) formulated energy minimization problems, they require large memory bandwidths and could not achieve real-time performance when applied to many real-life inference tasks. There is an increasing demand for efficient parallel inference algorithms as the size of problems increase and computer architectures move towards multi-core. In this work, we proposed a new high speed parallel computational structure for hierarchical Belief Propagation on shared memory architecture, which is based on a modification and generalization of the hierarchical BP algorithm presented by Felzenszwalb and Huttenlocher. Our parallel hierarchical belief propagation (PHBP) computational structure supports arbitrary grouping of nodes in multiscale computation and works for graphs in general topologies (including non grid structure graphs). Secondly, a fully parallel framework of hierarchical BP using sequential asynchronous message updating scheme (accelerated message updating) is developed. We achieved parallelization of both pre-computation portion and computational intense message passing portion. Lastly, we empirically evaluated the performance of algorithm on several computer vision tasks where we achieved nearly linear parallel scaling and outperform other alternative algorithms. Specifically, for the task of restoring a 608*456 noisy image with 16 gray levels, our PHBP takes around 100ms while a comparable result needs around 30s using Parallel Splash on a same 8 core shared memory system."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["A Parallel Implementation Of Hierarchical Belief Propagation"]},{"key":"dspace:entity.type","label":"Dspace Entity Type","values":["Publication"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"cerif:openaire":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"16aaa476-c037-41d0-9ec8-a47b145982fa\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>A Parallel Implementation Of Hierarchical Belief Propagation</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2013-05-26</PublicationDate> <Authors> <Author> <DisplayName>Tian, Yuan</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>Belief Propagation</Keyword> <Keyword>Graphical Models</Keyword> <Keyword>Parallelism</Keyword> <Abstract>Though Belief Propagation (BP) algorithms generate high quality results for a wide range of Markov Random Field (MRF) formulated energy minimization problems, they require large memory bandwidths and could not achieve real-time performance when applied to many real-life inference tasks. There is an increasing demand for efficient parallel inference algorithms as the size of problems increase and computer architectures move towards multi-core. In this work, we proposed a new high speed parallel computational structure for hierarchical Belief Propagation on shared memory architecture, which is based on a modification and generalization of the hierarchical BP algorithm presented by Felzenszwalb and Huttenlocher. Our parallel hierarchical belief propagation (PHBP) computational structure supports arbitrary grouping of nodes in multiscale computation and works for graphs in general topologies (including non grid structure graphs). Secondly, a fully parallel framework of hierarchical BP using sequential asynchronous message updating scheme (accelerated message updating) is developed. We achieved parallelization of both pre-computation portion and computational intense message passing portion. Lastly, we empirically evaluated the performance of algorithm on several computer vision tasks where we achieved nearly linear parallel scaling and outperform other alternative algorithms. Specifically, for the task of restoring a 608*456 noisy image with 16 gray levels, our PHBP takes around 100ms while a comparable result needs around 30s using Parallel Splash on a same 8 core shared memory system.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Tian, Yuan"],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:contributor.chair":["Manohar, Rajit"],"dc:contributor.committeemember":["Martinez, Jose F.","Chen, Tsuhan"],"dc:creator":["Tian, Yuan"],"dc:date.accessioned":["2013-09-05T15:57:11Z"],"dc:date.available":["2018-05-27T06:00:35Z"],"dc:date.issued":["2013-05-26"],"dc:description.abstract":["Though Belief Propagation (BP) algorithms generate high quality results for a wide range of Markov Random Field (MRF) formulated energy minimization problems, they require large memory bandwidths and could not achieve real-time performance when applied to many real-life inference tasks. There is an increasing demand for efficient parallel inference algorithms as the size of problems increase and computer architectures move towards multi-core. In this work, we proposed a new high speed parallel computational structure for hierarchical Belief Propagation on shared memory architecture, which is based on a modification and generalization of the hierarchical BP algorithm presented by Felzenszwalb and Huttenlocher. Our parallel hierarchical belief propagation (PHBP) computational structure supports arbitrary grouping of nodes in multiscale computation and works for graphs in general topologies (including non grid structure graphs). Secondly, a fully parallel framework of hierarchical BP using sequential asynchronous message updating scheme (accelerated message updating) is developed. We achieved parallelization of both pre-computation portion and computational intense message passing portion. Lastly, we empirically evaluated the performance of algorithm on several computer vision tasks where we achieved nearly linear parallel scaling and outperform other alternative algorithms. Specifically, for the task of restoring a 608*456 noisy image with 16 gray levels, our PHBP takes around 100ms while a comparable result needs around 30s using Parallel Splash on a same 8 core shared memory system."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:format.mimetype":["application/pdf"],"dc:identifier.bibid":["8267695"],"dc:identifier.uri":["https://hdl.handle.net/1813/34099"],"dc:language.iso":["en_US"],"dc:subject":["Belief Propagation","Graphical Models","Parallelism"],"dc:title":["A Parallel Implementation Of Hierarchical Belief Propagation"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["open.access"],"thesis:degree_discipline":["Electrical Engineering"],"thesis:degree_level":["Master of Science"],"thesis:degree_name":["M.S., Electrical Engineering"],"thesis:institution_name":["Cornell University"]},"updated_at":"2026-11-19T03:16:49Z"}