{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/108168"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/108168","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"A pixel-parallel architecture for graph cuts inference","abstract":"In recent years, the advancement in machine learning techniques has greatly improved the perceived qualities of many real-life applications such as computer vision and machine listening. But, most machine learning techniques require massive computing power. In practice, deploying such techniques raises challenges for hardware design, since traditional computing systems are not suitable to fully support computationally intensive machine learning algorithms. This dissertation reports on the design and implementation of custom hardware for fast and efficient machine learning applications. In the field of machine learning, the process of making the most likely decision based on observations is referred to as inference, which often re- quires efficient algorithms. The method of graph cuts converts a maximum a posteriori (MAP) inference problem on Markov random fields (MRFs) into a network flow, which can be solved in a direct manner. Many computer vision problems can be conveniently cast as an inference task to find a most likely label for each pixel. The method is thus widely used, but computation- ally burdensome given the need to run iterative network flow computations on every pixel of an image. Prior accelerator attempts, on either GPU or FPGA, have failed to exploit the problem’s attractive, maximum available parallelism: Push-relabel style network flow solvers can run in parallel across every pixel of an image. In this dissertation, we describe the design and implementation of the first pixel-parallel graph cuts inference accelerator. The architecture is scalable, and relies on predominantly local neighbor-calculation among pixels. A checkerboard scheduling scheme takes advantage of maximum parallelism while avoiding critical data dependencies in the push-relabel network flow computation. We first demonstrate the advantage of our pixel-parallel architecture by implementing two pixel-processor arrays with 256 processors and 1024 processors on FPGAs. Our implementations can accelerate a segmentation task on images’ cropped areas, referred to as image tiles, with 8-by-32 pixels or 16-by-64 pixels. In experiments, our accelerators achieved about 300-400X speedups over a sequential implementation. Next, to overcome the physical restraints of hardware resource and memory size, and to accelerate graph cuts on larger images, we developed methods to divide images into virtual regions, which can then be efficiently processed on a physical processor array. We then design a complete memory system for the inference engine, from on-chip to off-chip memory. To achieve better performance, other design challenges are also addressed, such as the need of implementing a hardware-friendly relabel heuristic for faster convergence. Experiment results show that the proposed virtual − image system achieved 5-7X speedups compared with other FPGA accelerators, and about 2X speedup compared with a GPU open-source implementation, on benchmark images of size ranging from 320-by-480 to 640-by-480.","abstract_html":"In recent years, the advancement in machine learning techniques has greatly improved the perceived qualities of many real-life applications such as computer vision and machine listening. But, most machine learning techniques require massive computing power. In practice, deploying such techniques raises challenges for hardware design, since traditional computing systems are not suitable to fully support computationally intensive machine learning algorithms. This dissertation reports on the design and implementation of custom hardware for fast and efficient machine learning applications. In the field of machine learning, the process of making the most likely decision based on observations is referred to as inference, which often re- quires efficient algorithms. The method of graph cuts converts a maximum a posteriori (MAP) inference problem on Markov random fields (MRFs) into a network flow, which can be solved in a direct manner. Many computer vision problems can be conveniently cast as an inference task to find a most likely label for each pixel. The method is thus widely used, but computation- ally burdensome given the need to run iterative network flow computations on every pixel of an image. Prior accelerator attempts, on either GPU or FPGA, have failed to exploit the problem’s attractive, maximum available parallelism: Push-relabel style network flow solvers can run in parallel across every pixel of an image. In this dissertation, we describe the design and implementation of the first pixel-parallel graph cuts inference accelerator. The architecture is scalable, and relies on predominantly local neighbor-calculation among pixels. A checkerboard scheduling scheme takes advantage of maximum parallelism while avoiding critical data dependencies in the push-relabel network flow computation. We first demonstrate the advantage of our pixel-parallel architecture by implementing two pixel-processor arrays with 256 processors and 1024 processors on FPGAs. Our implementations can accelerate a segmentation task on images’ cropped areas, referred to as image tiles, with 8-by-32 pixels or 16-by-64 pixels. In experiments, our accelerators achieved about 300-400X speedups over a sequential implementation. Next, to overcome the physical restraints of hardware resource and memory size, and to accelerate graph cuts on larger images, we developed methods to divide images into virtual regions, which can then be efficiently processed on a physical processor array. We then design a complete memory system for the inference engine, from on-chip to off-chip memory. To achieve better performance, other design challenges are also addressed, such as the need of implementing a hardware-friendly relabel heuristic for faster convergence. Experiment results show that the proposed virtual − image system achieved 5-7X speedups compared with other FPGA accelerators, and about 2X speedup compared with a GPU open-source implementation, on benchmark images of size ranging from 320-by-480 to 640-by-480.","abstract_has_math":false,"creators":["Gao, Tianqi"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Rutenbar, Rob A.","Chen, Deming","Forsyth, Daviad","Wong, Martin","Blank, William Thomas"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-08-26T23:58:41Z","date_published":"2020-08-26T23:58:41Z","updated_at":"2026-07-22T22:24:47Z","subjects":["Hardware accelerator, FPGA, Machine Learning, Computer Vision, Markov Random Fields, Graph Cuts, Computer Architecture"],"languages":["en"],"rights":["Copyright 2020 Tianqi Gao"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/108168","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Rutenbar, Rob A.","Chen, Deming","Forsyth, Daviad","Wong, Martin","Blank, William Thomas"]},{"key":"dc:creator","label":"Author","values":["Gao, Tianqi"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-08-26T23:58:41Z","2022-08-26T23:58:55Z","2020-05-07","2020-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"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":["Hardware accelerator, FPGA, Machine Learning, Computer Vision, Markov Random Fields, Graph Cuts, Computer Architecture"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2020 Tianqi Gao"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/108168"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In recent years, the advancement in machine learning techniques has greatly improved the perceived qualities of many real-life applications such as computer vision and machine listening. But, most machine learning techniques require massive computing power. In practice, deploying such techniques raises challenges for hardware design, since traditional computing systems are not suitable to fully support computationally intensive machine learning algorithms. This dissertation reports on the design and implementation of custom hardware for fast and efficient machine learning applications. In the field of machine learning, the process of making the most likely decision based on observations is referred to as inference, which often re- quires efficient algorithms. The method of graph cuts converts a maximum a posteriori (MAP) inference problem on Markov random fields (MRFs) into a network flow, which can be solved in a direct manner. Many computer vision problems can be conveniently cast as an inference task to find a most likely label for each pixel. The method is thus widely used, but computation- ally burdensome given the need to run iterative network flow computations on every pixel of an image. Prior accelerator attempts, on either GPU or FPGA, have failed to exploit the problem’s attractive, maximum available parallelism: Push-relabel style network flow solvers can run in parallel across every pixel of an image. In this dissertation, we describe the design and implementation of the first pixel-parallel graph cuts inference accelerator. The architecture is scalable, and relies on predominantly local neighbor-calculation among pixels. A checkerboard scheduling scheme takes advantage of maximum parallelism while avoiding critical data dependencies in the push-relabel network flow computation. We first demonstrate the advantage of our pixel-parallel architecture by implementing two pixel-processor arrays with 256 processors and 1024 processors on FPGAs. Our implementations can accelerate a segmentation task on images’ cropped areas, referred to as image tiles, with 8-by-32 pixels or 16-by-64 pixels. In experiments, our accelerators achieved about 300-400X speedups over a sequential implementation. Next, to overcome the physical restraints of hardware resource and memory size, and to accelerate graph cuts on larger images, we developed methods to divide images into virtual regions, which can then be efficiently processed on a physical processor array. We then design a complete memory system for the inference engine, from on-chip to off-chip memory. To achieve better performance, other design challenges are also addressed, such as the need of implementing a hardware-friendly relabel heuristic for faster convergence. Experiment results show that the proposed virtual − image system achieved 5-7X speedups compared with other FPGA accelerators, and about 2X speedup compared with a GPU open-source implementation, on benchmark images of size ranging from 320-by-480 to 640-by-480.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2022-05-01","The student, Tianqi Gao, accepted the attached license on 2020-05-06 at 20:44.","The student, Tianqi Gao, submitted this Dissertation for approval on 2020-05-06 at 20:53.","This Dissertation was approved for publication on 2020-05-07 at 17:16.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15262 on 2020-08-25 at 17:29:59","Made available in DSpace on 2020-08-26T23:58:41Z (GMT). No. of bitstreams: 3 GAO-DISSERTATION-2020.pdf: 10660811 bytes, checksum: c4c4d0be1d702749a584df3c77a38318 (MD5) LICENSE.txt: 4207 bytes, checksum: 031756b015bf82805d3846f36a5c149e (MD5) PROQUEST_LICENSE.txt: 4553 bytes, checksum: 5ac169c46c560725e5e88fd0a875a7ef (MD5) Previous issue date: 2020-05-07","Embargo set by: Seth Robbins for item 115781 Lift date: 2022-08-26T23:58:55Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["A pixel-parallel architecture for graph cuts inference"]}]}],"canonical_facts":{"dc:contributor":["Rutenbar, Rob A.","Chen, Deming","Forsyth, Daviad","Wong, Martin","Blank, William Thomas"],"dc:creator":["Gao, Tianqi"],"dc:date":["2020-08-26T23:58:41Z","2022-08-26T23:58:55Z","2020-05-07","2020-05"],"dc:description":["In recent years, the advancement in machine learning techniques has greatly improved the perceived qualities of many real-life applications such as computer vision and machine listening. But, most machine learning techniques require massive computing power. In practice, deploying such techniques raises challenges for hardware design, since traditional computing systems are not suitable to fully support computationally intensive machine learning algorithms. This dissertation reports on the design and implementation of custom hardware for fast and efficient machine learning applications. In the field of machine learning, the process of making the most likely decision based on observations is referred to as inference, which often re- quires efficient algorithms. The method of graph cuts converts a maximum a posteriori (MAP) inference problem on Markov random fields (MRFs) into a network flow, which can be solved in a direct manner. Many computer vision problems can be conveniently cast as an inference task to find a most likely label for each pixel. The method is thus widely used, but computation- ally burdensome given the need to run iterative network flow computations on every pixel of an image. Prior accelerator attempts, on either GPU or FPGA, have failed to exploit the problem’s attractive, maximum available parallelism: Push-relabel style network flow solvers can run in parallel across every pixel of an image. In this dissertation, we describe the design and implementation of the first pixel-parallel graph cuts inference accelerator. The architecture is scalable, and relies on predominantly local neighbor-calculation among pixels. A checkerboard scheduling scheme takes advantage of maximum parallelism while avoiding critical data dependencies in the push-relabel network flow computation. We first demonstrate the advantage of our pixel-parallel architecture by implementing two pixel-processor arrays with 256 processors and 1024 processors on FPGAs. Our implementations can accelerate a segmentation task on images’ cropped areas, referred to as image tiles, with 8-by-32 pixels or 16-by-64 pixels. In experiments, our accelerators achieved about 300-400X speedups over a sequential implementation. Next, to overcome the physical restraints of hardware resource and memory size, and to accelerate graph cuts on larger images, we developed methods to divide images into virtual regions, which can then be efficiently processed on a physical processor array. We then design a complete memory system for the inference engine, from on-chip to off-chip memory. To achieve better performance, other design challenges are also addressed, such as the need of implementing a hardware-friendly relabel heuristic for faster convergence. Experiment results show that the proposed virtual − image system achieved 5-7X speedups compared with other FPGA accelerators, and about 2X speedup compared with a GPU open-source implementation, on benchmark images of size ranging from 320-by-480 to 640-by-480.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2022-05-01","The student, Tianqi Gao, accepted the attached license on 2020-05-06 at 20:44.","The student, Tianqi Gao, submitted this Dissertation for approval on 2020-05-06 at 20:53.","This Dissertation was approved for publication on 2020-05-07 at 17:16.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15262 on 2020-08-25 at 17:29:59","Made available in DSpace on 2020-08-26T23:58:41Z (GMT). No. of bitstreams: 3 GAO-DISSERTATION-2020.pdf: 10660811 bytes, checksum: c4c4d0be1d702749a584df3c77a38318 (MD5) LICENSE.txt: 4207 bytes, checksum: 031756b015bf82805d3846f36a5c149e (MD5) PROQUEST_LICENSE.txt: 4553 bytes, checksum: 5ac169c46c560725e5e88fd0a875a7ef (MD5) Previous issue date: 2020-05-07","Embargo set by: Seth Robbins for item 115781 Lift date: 2022-08-26T23:58:55Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/108168"],"dc:language":["en"],"dc:rights":["Copyright 2020 Tianqi Gao"],"dc:subject":["Hardware accelerator, FPGA, Machine Learning, Computer Vision, Markov Random Fields, Graph Cuts, Computer Architecture"],"dc:title":["A pixel-parallel architecture for graph cuts inference"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:47Z"}