{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/44340"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/44340","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Tiling optimizations for stencil computations","abstract":"This thesis studies the techniques of tiling optimizations for stencil programs. Traditionally, research on tiling optimizations mainly focuses on tessellating tiling, atomic tiles and regular tile shapes. This thesis studies several novel tiling techniques which are out of the scope of traditional research. In order to represent a general tiling scheme uniformly, a unified tiling representation framework is introduced. With the unified tiling representation, three tiling techniques are studied. The first tiling technique is Hierarchical Overlapped Tiling, based on the idea of reducing communication overhead by introducing redundant computations. Hierarchical Overlapped Tiling also applies the idea of hierarchical tiling to take advantage of hardware hierarchy, so that the additional overhead introduced by redundant computations can be minimized. The second tiling technique is called Conjugate-Trapezoid Tiling, which schedules the computations and communications within a tile in an interleaving way in order to overlap the computation time and communication latency. Conjugate-Trapezoid Tiling forms a pipeline of computations and communications, hence the communication latency can be hidden. Third, this thesis studies the tile shape selection problem for hierarchical tiling. It is concluded that optimal tile shape selection for hierarchical tiling is a multidimensional, nonlinear, bi-level programming problem. Experimental results show that the irregular tile shapes selected by solving the optimization problem have the potential to outperform intuitive tiling shapes.","abstract_html":"This thesis studies the techniques of tiling optimizations for stencil programs. Traditionally, research on tiling optimizations mainly focuses on tessellating tiling, atomic tiles and regular tile shapes. This thesis studies several novel tiling techniques which are out of the scope of traditional research. In order to represent a general tiling scheme uniformly, a unified tiling representation framework is introduced. With the unified tiling representation, three tiling techniques are studied. The first tiling technique is Hierarchical Overlapped Tiling, based on the idea of reducing communication overhead by introducing redundant computations. Hierarchical Overlapped Tiling also applies the idea of hierarchical tiling to take advantage of hardware hierarchy, so that the additional overhead introduced by redundant computations can be minimized. The second tiling technique is called Conjugate-Trapezoid Tiling, which schedules the computations and communications within a tile in an interleaving way in order to overlap the computation time and communication latency. Conjugate-Trapezoid Tiling forms a pipeline of computations and communications, hence the communication latency can be hidden. Third, this thesis studies the tile shape selection problem for hierarchical tiling. It is concluded that optimal tile shape selection for hierarchical tiling is a multidimensional, nonlinear, bi-level programming problem. Experimental results show that the irregular tile shapes selected by solving the optimization problem have the potential to outperform intuitive tiling shapes.","abstract_has_math":false,"creators":["Zhou, Xing"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Padua, David A.","Garzaran, Maria J.","Gropp, William D.","Hwu, Wen-Mei W.","Kuhn, Robert H."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-05-24T22:08:20Z","date_published":"2013-05-24T22:08:20Z","updated_at":"2026-07-22T22:25:34Z","subjects":["Optimization","Tiling","Stencil Computation"],"languages":["en"],"rights":["Copyright 2013 Xing Zhou"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/44340","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Padua, David A.","Garzaran, Maria J.","Gropp, William D.","Hwu, Wen-Mei W.","Kuhn, Robert H."]},{"key":"dc:creator","label":"Author","values":["Zhou, Xing"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-05-24T22:08:20Z","2013-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":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"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":["Optimization","Tiling","Stencil Computation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Xing Zhou"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/44340"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis studies the techniques of tiling optimizations for stencil programs. Traditionally, research on tiling optimizations mainly focuses on tessellating tiling, atomic tiles and regular tile shapes. This thesis studies several novel tiling techniques which are out of the scope of traditional research. In order to represent a general tiling scheme uniformly, a unified tiling representation framework is introduced. With the unified tiling representation, three tiling techniques are studied. The first tiling technique is Hierarchical Overlapped Tiling, based on the idea of reducing communication overhead by introducing redundant computations. Hierarchical Overlapped Tiling also applies the idea of hierarchical tiling to take advantage of hardware hierarchy, so that the additional overhead introduced by redundant computations can be minimized. The second tiling technique is called Conjugate-Trapezoid Tiling, which schedules the computations and communications within a tile in an interleaving way in order to overlap the computation time and communication latency. Conjugate-Trapezoid Tiling forms a pipeline of computations and communications, hence the communication latency can be hidden. Third, this thesis studies the tile shape selection problem for hierarchical tiling. It is concluded that optimal tile shape selection for hierarchical tiling is a multidimensional, nonlinear, bi-level programming problem. Experimental results show that the irregular tile shapes selected by solving the optimization problem have the potential to outperform intuitive tiling shapes.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-04-11T18:12:07Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Zhou_Xing.pdf: 2307204 bytes, checksum: 5265e1b8ea60ed159624a9df5401655c (MD5)","Made available in DSpace on 2013-05-24T22:08:20Z (GMT). No. of bitstreams: 2 Xing_Zhou.pdf: 2307204 bytes, checksum: 5265e1b8ea60ed159624a9df5401655c (MD5) license.txt: 4057 bytes, checksum: 69e4473f3b68c70adf28c534211bc43c (MD5)"]},{"key":"dc:title","label":"Title","values":["Tiling optimizations for stencil computations"]}]}],"canonical_facts":{"dc:contributor":["Padua, David A.","Garzaran, Maria J.","Gropp, William D.","Hwu, Wen-Mei W.","Kuhn, Robert H."],"dc:creator":["Zhou, Xing"],"dc:date":["2013-05-24T22:08:20Z","2013-05"],"dc:description":["This thesis studies the techniques of tiling optimizations for stencil programs. Traditionally, research on tiling optimizations mainly focuses on tessellating tiling, atomic tiles and regular tile shapes. This thesis studies several novel tiling techniques which are out of the scope of traditional research. In order to represent a general tiling scheme uniformly, a unified tiling representation framework is introduced. With the unified tiling representation, three tiling techniques are studied. The first tiling technique is Hierarchical Overlapped Tiling, based on the idea of reducing communication overhead by introducing redundant computations. Hierarchical Overlapped Tiling also applies the idea of hierarchical tiling to take advantage of hardware hierarchy, so that the additional overhead introduced by redundant computations can be minimized. The second tiling technique is called Conjugate-Trapezoid Tiling, which schedules the computations and communications within a tile in an interleaving way in order to overlap the computation time and communication latency. Conjugate-Trapezoid Tiling forms a pipeline of computations and communications, hence the communication latency can be hidden. Third, this thesis studies the tile shape selection problem for hierarchical tiling. It is concluded that optimal tile shape selection for hierarchical tiling is a multidimensional, nonlinear, bi-level programming problem. Experimental results show that the irregular tile shapes selected by solving the optimization problem have the potential to outperform intuitive tiling shapes.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-04-11T18:12:07Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Zhou_Xing.pdf: 2307204 bytes, checksum: 5265e1b8ea60ed159624a9df5401655c (MD5)","Made available in DSpace on 2013-05-24T22:08:20Z (GMT). No. of bitstreams: 2 Xing_Zhou.pdf: 2307204 bytes, checksum: 5265e1b8ea60ed159624a9df5401655c (MD5) license.txt: 4057 bytes, checksum: 69e4473f3b68c70adf28c534211bc43c (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/44340"],"dc:language":["en"],"dc:rights":["Copyright 2013 Xing Zhou"],"dc:subject":["Optimization","Tiling","Stencil Computation"],"dc:title":["Tiling optimizations for stencil computations"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:34Z"}