{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/90537"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/90537","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Breadth-first search for social network graphs on heterogenous platforms","abstract":"DSpace SAF Submission Ingestion Package generated from Vireo submission #9220 on 2016-07-07 at 13:30:40","abstract_html":"DSpace SAF Submission Ingestion Package generated from Vireo submission #9220 on 2016-07-07 at 13:30:40","abstract_has_math":false,"creators":["Remis, Luis Carlos 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":["Garzaran, Maria Jesus"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-07-07T19:53:52Z","date_published":"2016-07-07T19:53:52Z","updated_at":"2026-07-22T22:26:32Z","subjects":["Breadth-first search (BFS)","Graphs","Social networks","Heterogenous","Graphics processing unit (GPU)"],"languages":["en"],"rights":["Copyright 2016 Luis Carlos Maria Remis"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/90537","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Garzaran, Maria Jesus"]},{"key":"dc:creator","label":"Author","values":["Remis, Luis Carlos Maria"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2016-07-07T19:53:52Z","2016-04-21","2016-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":["Breadth-first search (BFS)","Graphs","Social networks","Heterogenous","Graphics processing unit (GPU)"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2016 Luis Carlos Maria Remis"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/90537"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["DSpace SAF Submission Ingestion Package generated from Vireo submission #9220 on 2016-07-07 at 13:30:40","Made available in DSpace on 2016-07-07T19:53:52Z (GMT). No. of bitstreams: 2 REMIS-THESIS-2016.pdf: 935899 bytes, checksum: 18708371b74e1838f9d1bd506b181baa (MD5) LICENSE.txt: 4220 bytes, checksum: 5b23a0394c5f10d1b1d6f89611d27cff (MD5) Previous issue date: 2016-04-21","Breadth-First Search (BFS) is the core of many graph analysis algorithms, and it is useful in many problems including social network, computer network analysis, and data organization, but, due to its irregular behav- ior, its parallel implementation is very challenging. There are several approaches that implement efficient algorithms for BFS in multicore architectures and in Graphics Processors, but an efficient implementation of BFS for heterogeneous systems is even more complicated, as the task of distributing the work among the main cores and the accelerators becomes a big challenge. As part of this work, we have assessed different heterogenous shared-memory architectures (from high- end processors to embedded mobile processors, both composed by a multi-core CPU and an integrated GPU) and implemented different approaches to perform BFS. This work introduces three heterogeneous approaches for BFS: Selective, Concurrent, and Async. Contributions of this work includes both the analysis of BFS performance on Heterogenous platforms, as well as in depth analysis of social network graphs and its implications on the BFS algorithm. The results show that BFS is very input dependent, and that the structure of the graph is one of the prime factors to analyze in order to develop good and scalable algorithms. The results also show that heterogenous platforms can provide acceleration to even irregular algorithms, reaching speed-ups of 2.2x in the best case. It is also shown how the different system configurations and capabilities impact the performance and how the shared-memory system can reach bandwidth limitations that prevent performance improvements despite having higher utilization of the resources.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-07-07 without embargo terms","The student, Luis Carlos Maria Remis, accepted the attached license on 2016-04-20 at 14:02.","The student, Luis Carlos Maria Remis, submitted this Thesis for approval on 2016-04-20 at 14:07.","This Thesis was approved for publication on 2016-04-21 at 10:50."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Breadth-first search for social network graphs on heterogenous platforms"]}]}],"canonical_facts":{"dc:contributor":["Garzaran, Maria Jesus"],"dc:creator":["Remis, Luis Carlos Maria"],"dc:date":["2016-07-07T19:53:52Z","2016-04-21","2016-05"],"dc:description":["DSpace SAF Submission Ingestion Package generated from Vireo submission #9220 on 2016-07-07 at 13:30:40","Made available in DSpace on 2016-07-07T19:53:52Z (GMT). No. of bitstreams: 2 REMIS-THESIS-2016.pdf: 935899 bytes, checksum: 18708371b74e1838f9d1bd506b181baa (MD5) LICENSE.txt: 4220 bytes, checksum: 5b23a0394c5f10d1b1d6f89611d27cff (MD5) Previous issue date: 2016-04-21","Breadth-First Search (BFS) is the core of many graph analysis algorithms, and it is useful in many problems including social network, computer network analysis, and data organization, but, due to its irregular behav- ior, its parallel implementation is very challenging. There are several approaches that implement efficient algorithms for BFS in multicore architectures and in Graphics Processors, but an efficient implementation of BFS for heterogeneous systems is even more complicated, as the task of distributing the work among the main cores and the accelerators becomes a big challenge. As part of this work, we have assessed different heterogenous shared-memory architectures (from high- end processors to embedded mobile processors, both composed by a multi-core CPU and an integrated GPU) and implemented different approaches to perform BFS. This work introduces three heterogeneous approaches for BFS: Selective, Concurrent, and Async. Contributions of this work includes both the analysis of BFS performance on Heterogenous platforms, as well as in depth analysis of social network graphs and its implications on the BFS algorithm. The results show that BFS is very input dependent, and that the structure of the graph is one of the prime factors to analyze in order to develop good and scalable algorithms. The results also show that heterogenous platforms can provide acceleration to even irregular algorithms, reaching speed-ups of 2.2x in the best case. It is also shown how the different system configurations and capabilities impact the performance and how the shared-memory system can reach bandwidth limitations that prevent performance improvements despite having higher utilization of the resources.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-07-07 without embargo terms","The student, Luis Carlos Maria Remis, accepted the attached license on 2016-04-20 at 14:02.","The student, Luis Carlos Maria Remis, submitted this Thesis for approval on 2016-04-20 at 14:07.","This Thesis was approved for publication on 2016-04-21 at 10:50."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/90537"],"dc:language":["en"],"dc:rights":["Copyright 2016 Luis Carlos Maria Remis"],"dc:subject":["Breadth-first search (BFS)","Graphs","Social networks","Heterogenous","Graphics processing unit (GPU)"],"dc:title":["Breadth-first search for social network graphs on heterogenous platforms"],"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:26:32Z"}