{"id":{"repo_id":"usf","oai_identifier":"oai:digitalcommons.usf.edu:etd-10181"},"canonical_url":"https://search.ndltd.org/etd/usf/oai:digitalcommons.usf.edu:etd-10181","repository":{"repo_id":"usf","name":"University of South Florida","base_url":"https://digitalcommons.usf.edu/do/oai/"},"display":{"title":"Algorithms and Framework for Computing 2-body Statistics on Graphics Processing Units","abstract":"Various types of two-body statistics (2-BS) are regarded as essential components of low-level data analysis in scientific database systems. In relational algebraic terms, a 2-BS is essentially a Cartesian product between two datasets (or two instances of the same dataset) followed by a user-defined aggregate. The quadratic complexity of these computations hinders the timely processing of data. Thus using modern parallel hardware has become an obvious solution to meet such challenges. This dissertation presents our recent work in designing and optimizing parallel algorithms for 2-BS computation on Graphics Processing Units (GPUs). The unique architecture, however, provides abundant opportunities for optimizing the algorithm towards better performance and achieving high utilization of hardware resources. While a typical 2-BS problem can be summarized into a straightforward parallel computing pattern, traditional knowledge from (general) parallel computing often falls short in delivering the best possible performance. Therefore, we present a suite of techniques to decompose 2-BS problems and methods for the effective use of computing resources on GPUs. We also developed analytical models that guided us towards finding the best parameters of our GPU programs. As a result, we achieve the design of highly-optimized 2-BS algorithms that significantly outperform the best-known GPU and CPU implementations. Although 2-BS problems share the same core computations, each 2-BS problem, however, carries its own characteristics that calls for different strategies in code optimization. For that, we developed a software framework that automatically generates high-performance GPU code based on a few parameters and short primer code inputs. We further present two case studies to demonstrate that code generated by this framework reaches a very high level of efficiency. In addition to the general problem, we also studied a particular group of 2-BS problems, in which the computation can be reduced by using an index structure. Whereas the traditional knowledge of the index tree structure cannot utilize the full performance of GPUs, we present a technique to optimize the index searching for GPUs. The GPU index-searching is verified by applications of 2-BS, which show the very high performance.","abstract_html":"Various types of two-body statistics (2-BS) are regarded as essential components of low-level data analysis in scientific database systems. In relational algebraic terms, a 2-BS is essentially a Cartesian product between two datasets (or two instances of the same dataset) followed by a user-defined aggregate. The quadratic complexity of these computations hinders the timely processing of data. Thus using modern parallel hardware has become an obvious solution to meet such challenges. This dissertation presents our recent work in designing and optimizing parallel algorithms for 2-BS computation on Graphics Processing Units (GPUs). The unique architecture, however, provides abundant opportunities for optimizing the algorithm towards better performance and achieving high utilization of hardware resources. While a typical 2-BS problem can be summarized into a straightforward parallel computing pattern, traditional knowledge from (general) parallel computing often falls short in delivering the best possible performance. Therefore, we present a suite of techniques to decompose 2-BS problems and methods for the effective use of computing resources on GPUs. We also developed analytical models that guided us towards finding the best parameters of our GPU programs. As a result, we achieve the design of highly-optimized 2-BS algorithms that significantly outperform the best-known GPU and CPU implementations. Although 2-BS problems share the same core computations, each 2-BS problem, however, carries its own characteristics that calls for different strategies in code optimization. For that, we developed a software framework that automatically generates high-performance GPU code based on a few parameters and short primer code inputs. We further present two case studies to demonstrate that code generated by this framework reaches a very high level of efficiency. In addition to the general problem, we also studied a particular group of 2-BS problems, in which the computation can be reduced by using an index structure. Whereas the traditional knowledge of the index tree structure cannot utilize the full performance of GPUs, we present a technique to optimize the index searching for GPUs. The GPU index-searching is verified by applications of 2-BS, which show the very high performance.","abstract_has_math":false,"creators":["Pitaksirianan, Napath"],"institution":"University of South Florida","degree_name":"Doctor of Philosophy (Ph.D.)","degree_level":"Dissertation","degree_discipline":"Computer Science and Engineering","degree_department":null,"school":null,"contributors":["Yicheng Tu, Ph.D.","Adriana Iamnitchi, Ph.D.","Yao Liu, Ph.D.","Hadi Charkhgrad, Ph.D.","Sagar Pandit, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-02-19T08:00:00Z","date_published":"2020-02-19T08:00:00Z","updated_at":"2026-11-19T08:44:51Z","subjects":["CUDA","Database System","GPGPU","GPU","Parallel Computing","Computer Engineering","Computer Sciences"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usf.edu/etd/8984","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usf.edu/etd/8984","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usf.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usf.edu%3Aetd-10181","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Yicheng Tu, Ph.D.","Adriana Iamnitchi, Ph.D.","Yao Liu, Ph.D.","Hadi Charkhgrad, Ph.D.","Sagar Pandit, Ph.D."]},{"key":"dc:creator","label":"Author","values":["Pitaksirianan, Napath"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-02-19T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science and Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation","Ph.D."]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (Ph.D.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of South Florida"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["CUDA","Database System","GPGPU","GPU","Parallel Computing","Computer Engineering","Computer Sciences"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usf.edu/etd/8984"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Various types of two-body statistics (2-BS) are regarded as essential components of low-level data analysis in scientific database systems. In relational algebraic terms, a 2-BS is essentially a Cartesian product between two datasets (or two instances of the same dataset) followed by a user-defined aggregate. The quadratic complexity of these computations hinders the timely processing of data. Thus using modern parallel hardware has become an obvious solution to meet such challenges. This dissertation presents our recent work in designing and optimizing parallel algorithms for 2-BS computation on Graphics Processing Units (GPUs). The unique architecture, however, provides abundant opportunities for optimizing the algorithm towards better performance and achieving high utilization of hardware resources. While a typical 2-BS problem can be summarized into a straightforward parallel computing pattern, traditional knowledge from (general) parallel computing often falls short in delivering the best possible performance. Therefore, we present a suite of techniques to decompose 2-BS problems and methods for the effective use of computing resources on GPUs. We also developed analytical models that guided us towards finding the best parameters of our GPU programs. As a result, we achieve the design of highly-optimized 2-BS algorithms that significantly outperform the best-known GPU and CPU implementations. Although 2-BS problems share the same core computations, each 2-BS problem, however, carries its own characteristics that calls for different strategies in code optimization. For that, we developed a software framework that automatically generates high-performance GPU code based on a few parameters and short primer code inputs. We further present two case studies to demonstrate that code generated by this framework reaches a very high level of efficiency. In addition to the general problem, we also studied a particular group of 2-BS problems, in which the computation can be reduced by using an index structure. Whereas the traditional knowledge of the index tree structure cannot utilize the full performance of GPUs, we present a technique to optimize the index searching for GPUs. The GPU index-searching is verified by applications of 2-BS, which show the very high performance."]},{"key":"dc:title","label":"Title","values":["Algorithms and Framework for Computing 2-body Statistics on Graphics Processing Units"]}]}],"canonical_facts":{"dc:contributor":["Yicheng Tu, Ph.D.","Adriana Iamnitchi, Ph.D.","Yao Liu, Ph.D.","Hadi Charkhgrad, Ph.D.","Sagar Pandit, Ph.D."],"dc:creator":["Pitaksirianan, Napath"],"dc:date":["2020-02-19T08:00:00Z"],"dc:description":["Various types of two-body statistics (2-BS) are regarded as essential components of low-level data analysis in scientific database systems. In relational algebraic terms, a 2-BS is essentially a Cartesian product between two datasets (or two instances of the same dataset) followed by a user-defined aggregate. The quadratic complexity of these computations hinders the timely processing of data. Thus using modern parallel hardware has become an obvious solution to meet such challenges. This dissertation presents our recent work in designing and optimizing parallel algorithms for 2-BS computation on Graphics Processing Units (GPUs). The unique architecture, however, provides abundant opportunities for optimizing the algorithm towards better performance and achieving high utilization of hardware resources. While a typical 2-BS problem can be summarized into a straightforward parallel computing pattern, traditional knowledge from (general) parallel computing often falls short in delivering the best possible performance. Therefore, we present a suite of techniques to decompose 2-BS problems and methods for the effective use of computing resources on GPUs. We also developed analytical models that guided us towards finding the best parameters of our GPU programs. As a result, we achieve the design of highly-optimized 2-BS algorithms that significantly outperform the best-known GPU and CPU implementations. Although 2-BS problems share the same core computations, each 2-BS problem, however, carries its own characteristics that calls for different strategies in code optimization. For that, we developed a software framework that automatically generates high-performance GPU code based on a few parameters and short primer code inputs. We further present two case studies to demonstrate that code generated by this framework reaches a very high level of efficiency. In addition to the general problem, we also studied a particular group of 2-BS problems, in which the computation can be reduced by using an index structure. Whereas the traditional knowledge of the index tree structure cannot utilize the full performance of GPUs, we present a technique to optimize the index searching for GPUs. The GPU index-searching is verified by applications of 2-BS, which show the very high performance."],"dc:identifier":["https://digitalcommons.usf.edu/etd/8984"],"dc:subject":["CUDA","Database System","GPGPU","GPU","Parallel Computing","Computer Engineering","Computer Sciences"],"dc:title":["Algorithms and Framework for Computing 2-body Statistics on Graphics Processing Units"],"thesis:degree_discipline":["Computer Science and Engineering"],"thesis:degree_level":["Dissertation","Ph.D."],"thesis:degree_name":["Doctor of Philosophy (Ph.D.)"],"thesis:institution_name":["University of South Florida"]},"updated_at":"2026-11-19T08:44:51Z"}