{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/18310"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/18310","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Compact binning for parallel processing of limited-range functions","abstract":"Limited-range functions are domain-level optimizations to a class of applications where all input elements contribute to all output elements, based on the distance between two given elements. When the contribution of an input element to the output is inversely proportional to the distance, a limited range can be applied, which approximates the contribution to zero beyond a certain cutoff distance. Introducing a limited-range function to the application reduces the computation complexity from O(N2) to O(N). Processing multiple input elements in a limited-range function in parallel can lead to data races without the use of expensive synchronization. That is why a preferred approach is an output-driven one, where multiple output elements are processed in parallel, all sharing the input data set for reads. Typically the input data set is unstructured, which without the use of binning, would result in every output element in the output-driven approach reading all of the input elements to determine which ones fall within its cutoff. Binning is a preconditioning step that sorts the input elements into predetermined bins that are easily accessible by the output, thus allowing the output to only access the bins relevant to its computation. Traditionally, bins were created with uniform size and capacity to enable easy access to them; however, making the bins regular can have severe side-effects on memory requirements to maintain these bins. We propose a technique to allow the bins to vary in capacity in order to reduce the memory overhead, at the cost of added accessing overhead. In this work, we will compare regular binning and our approach, compact binning. We will demonstrate that compact bins can in fact improve the execution performance of limited-range functions executed in parallel.","abstract_html":"Limited-range functions are domain-level optimizations to a class of applications where all input elements contribute to all output elements, based on the distance between two given elements. When the contribution of an input element to the output is inversely proportional to the distance, a limited range can be applied, which approximates the contribution to zero beyond a certain cutoff distance. Introducing a limited-range function to the application reduces the computation complexity from O(N2) to O(N). Processing multiple input elements in a limited-range function in parallel can lead to data races without the use of expensive synchronization. That is why a preferred approach is an output-driven one, where multiple output elements are processed in parallel, all sharing the input data set for reads. Typically the input data set is unstructured, which without the use of binning, would result in every output element in the output-driven approach reading all of the input elements to determine which ones fall within its cutoff. Binning is a preconditioning step that sorts the input elements into predetermined bins that are easily accessible by the output, thus allowing the output to only access the bins relevant to its computation. Traditionally, bins were created with uniform size and capacity to enable easy access to them; however, making the bins regular can have severe side-effects on memory requirements to maintain these bins. We propose a technique to allow the bins to vary in capacity in order to reduce the memory overhead, at the cost of added accessing overhead. In this work, we will compare regular binning and our approach, compact binning. We will demonstrate that compact bins can in fact improve the execution performance of limited-range functions executed in parallel.","abstract_has_math":false,"creators":["Obeid, Nady M."],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Hwu, Wen-Mei W."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-01-14T22:45:48Z","date_published":"2011-01-14T22:45:48Z","updated_at":"2026-07-22T22:25:11Z","subjects":["irregular binning","compact binning","graphics processing units (GPUs)","graphics processors","parallel processing","limited-range functions","gridding","cutoff distance"],"languages":["en"],"rights":["Copyright 2010 Nady M. Obeid"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/18310","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hwu, Wen-Mei W."]},{"key":"dc:creator","label":"Author","values":["Obeid, Nady M."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-01-14T22:45:48Z","2010-12"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"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":["irregular binning","compact binning","graphics processing units (GPUs)","graphics processors","parallel processing","limited-range functions","gridding","cutoff distance"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2010 Nady M. Obeid"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/18310"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Limited-range functions are domain-level optimizations to a class of applications where all input elements contribute to all output elements, based on the distance between two given elements. When the contribution of an input element to the output is inversely proportional to the distance, a limited range can be applied, which approximates the contribution to zero beyond a certain cutoff distance. Introducing a limited-range function to the application reduces the computation complexity from O(N2) to O(N). Processing multiple input elements in a limited-range function in parallel can lead to data races without the use of expensive synchronization. That is why a preferred approach is an output-driven one, where multiple output elements are processed in parallel, all sharing the input data set for reads. Typically the input data set is unstructured, which without the use of binning, would result in every output element in the output-driven approach reading all of the input elements to determine which ones fall within its cutoff. Binning is a preconditioning step that sorts the input elements into predetermined bins that are easily accessible by the output, thus allowing the output to only access the bins relevant to its computation. Traditionally, bins were created with uniform size and capacity to enable easy access to them; however, making the bins regular can have severe side-effects on memory requirements to maintain these bins. We propose a technique to allow the bins to vary in capacity in order to reduce the memory overhead, at the cost of added accessing overhead. In this work, we will compare regular binning and our approach, compact binning. We will demonstrate that compact bins can in fact improve the execution performance of limited-range functions executed in parallel.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2010-12-08T18:12:17Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Obeid_Nady.docx: 19831447 bytes, checksum: 5e5e4603746fb9775ca00b172d28af02 (MD5) Obeid_Nady.pdf: 5133386 bytes, checksum: abec98787a53c6db5948ff1e1406729e (MD5)","Made available in DSpace on 2011-01-14T22:45:48Z (GMT). No. of bitstreams: 3 Obeid_Nady.pdf: 5133386 bytes, checksum: abec98787a53c6db5948ff1e1406729e (MD5) Obeid_Nady.docx: 19831447 bytes, checksum: 5e5e4603746fb9775ca00b172d28af02 (MD5) license.txt: 4058 bytes, checksum: 2f5af6593c657d5126ffe5458ebafd50 (MD5)"]},{"key":"dc:title","label":"Title","values":["Compact binning for parallel processing of limited-range functions"]}]}],"canonical_facts":{"dc:contributor":["Hwu, Wen-Mei W."],"dc:creator":["Obeid, Nady M."],"dc:date":["2011-01-14T22:45:48Z","2010-12"],"dc:description":["Limited-range functions are domain-level optimizations to a class of applications where all input elements contribute to all output elements, based on the distance between two given elements. When the contribution of an input element to the output is inversely proportional to the distance, a limited range can be applied, which approximates the contribution to zero beyond a certain cutoff distance. Introducing a limited-range function to the application reduces the computation complexity from O(N2) to O(N). Processing multiple input elements in a limited-range function in parallel can lead to data races without the use of expensive synchronization. That is why a preferred approach is an output-driven one, where multiple output elements are processed in parallel, all sharing the input data set for reads. Typically the input data set is unstructured, which without the use of binning, would result in every output element in the output-driven approach reading all of the input elements to determine which ones fall within its cutoff. Binning is a preconditioning step that sorts the input elements into predetermined bins that are easily accessible by the output, thus allowing the output to only access the bins relevant to its computation. Traditionally, bins were created with uniform size and capacity to enable easy access to them; however, making the bins regular can have severe side-effects on memory requirements to maintain these bins. We propose a technique to allow the bins to vary in capacity in order to reduce the memory overhead, at the cost of added accessing overhead. In this work, we will compare regular binning and our approach, compact binning. We will demonstrate that compact bins can in fact improve the execution performance of limited-range functions executed in parallel.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2010-12-08T18:12:17Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Obeid_Nady.docx: 19831447 bytes, checksum: 5e5e4603746fb9775ca00b172d28af02 (MD5) Obeid_Nady.pdf: 5133386 bytes, checksum: abec98787a53c6db5948ff1e1406729e (MD5)","Made available in DSpace on 2011-01-14T22:45:48Z (GMT). No. of bitstreams: 3 Obeid_Nady.pdf: 5133386 bytes, checksum: abec98787a53c6db5948ff1e1406729e (MD5) Obeid_Nady.docx: 19831447 bytes, checksum: 5e5e4603746fb9775ca00b172d28af02 (MD5) license.txt: 4058 bytes, checksum: 2f5af6593c657d5126ffe5458ebafd50 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/18310"],"dc:language":["en"],"dc:rights":["Copyright 2010 Nady M. Obeid"],"dc:subject":["irregular binning","compact binning","graphics processing units (GPUs)","graphics processors","parallel processing","limited-range functions","gridding","cutoff distance"],"dc:title":["Compact binning for parallel processing of limited-range functions"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:11Z"}