{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/120199"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/120199","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Parallel and heterogeneous computing for static timing analysis","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","abstract_has_math":false,"creators":["Guo, Guannan"],"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":["Wong, Martin D.F.","Huang, Tsung-Wei","Chen, Deming","Patel, Sanjay"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-05","date_published":"2023-05","updated_at":"2026-07-22T22:24:57Z","subjects":["Static Timing Analysis","Parallel And Heterogeneous Computing"],"languages":["en","eng"],"rights":["Copyright 2023 Guannan Guo"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/120199","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Wong, Martin D.F.","Huang, Tsung-Wei","Chen, Deming","Patel, Sanjay"]},{"key":"dc:creator","label":"Author","values":["Guo, Guannan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-05","2023-01-31"]},{"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":["Static Timing Analysis","Parallel And Heterogeneous Computing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2023 Guannan Guo"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/120199"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","The student, Guannan Guo, accepted the attached license on 2023-01-29 at 03:49.","The student, Guannan Guo, submitted this Dissertation for approval on 2023-01-29 at 04:08.","This Dissertation was approved for publication on 2023-01-31 at 16:24.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18835 on 2023-09-01 at 17:07:18","The increasing complexity in digital design has spurred demand for faster design closure. As a primary timing measurement tool frequently used in design stage and optimization stage, static timing analysis (STA) has become one of the major performance bottlenecks in digital design. In this thesis, we study a novel parallel programming model and heterogeneous computing algorithms to boost timing analysis. As multi-core systems have become common in modern electronics, how to fit timing analysis into the multi-threading and heterogeneous computing environment is a trending research topic. We explore this direction with a new task-based multi-threading framework and several heterogeneous computing algorithms. We demonstrate their superior efficiency over existing tools. Critical path generation is a major objective timing analysis. Optimization tools always need to report on critical paths under several path constraints. In Chapter 1, we propose a path generation algorithm which can fulfill all practical path constraints and outperforms an industrial timing analysis tool. We also highlight its potential for multi-threading by leveraging a unified framework to task dependency graph, called Taskflow. In Chapter 2, we point out the scalability limitation by parallelizing with a multi-core CPU system. So we are highly motivated to accelerate the process of path generation in Path-based Analysis (PBA) within a heterogeneous computing environment. Our GPU-accelerated algorithm promotes PBA to a new performance milestone. In Chapter 3, we introduce an algorithm that enables path constraints satisfaction on the GPU. Our algorithm maintains high computation throughput while exploring critical paths in the search space required by the path constraints. In Chapter 4, we further improve our GPU-accelerated PBA algorithm with fine-grained optimizations. We integrate these optimizations together as a unified framework, which achieves speed-up for 3–5 times. In Chapter 5, we propose a STA graph partitioning framework that overcomes the GPU memory bottleneck. We believe this partitioning framework can allow us to offload the STA workload of industrial designs to multiple GPUs for further acceleration. The last chapter concludes this thesis and highlights the main contributions. We also point to several directions for the future work."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Parallel and heterogeneous computing for static timing analysis"]}]}],"canonical_facts":{"dc:contributor":["Wong, Martin D.F.","Huang, Tsung-Wei","Chen, Deming","Patel, Sanjay"],"dc:creator":["Guo, Guannan"],"dc:date":["2023-05","2023-01-31"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","The student, Guannan Guo, accepted the attached license on 2023-01-29 at 03:49.","The student, Guannan Guo, submitted this Dissertation for approval on 2023-01-29 at 04:08.","This Dissertation was approved for publication on 2023-01-31 at 16:24.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18835 on 2023-09-01 at 17:07:18","The increasing complexity in digital design has spurred demand for faster design closure. As a primary timing measurement tool frequently used in design stage and optimization stage, static timing analysis (STA) has become one of the major performance bottlenecks in digital design. In this thesis, we study a novel parallel programming model and heterogeneous computing algorithms to boost timing analysis. As multi-core systems have become common in modern electronics, how to fit timing analysis into the multi-threading and heterogeneous computing environment is a trending research topic. We explore this direction with a new task-based multi-threading framework and several heterogeneous computing algorithms. We demonstrate their superior efficiency over existing tools. Critical path generation is a major objective timing analysis. Optimization tools always need to report on critical paths under several path constraints. In Chapter 1, we propose a path generation algorithm which can fulfill all practical path constraints and outperforms an industrial timing analysis tool. We also highlight its potential for multi-threading by leveraging a unified framework to task dependency graph, called Taskflow. In Chapter 2, we point out the scalability limitation by parallelizing with a multi-core CPU system. So we are highly motivated to accelerate the process of path generation in Path-based Analysis (PBA) within a heterogeneous computing environment. Our GPU-accelerated algorithm promotes PBA to a new performance milestone. In Chapter 3, we introduce an algorithm that enables path constraints satisfaction on the GPU. Our algorithm maintains high computation throughput while exploring critical paths in the search space required by the path constraints. In Chapter 4, we further improve our GPU-accelerated PBA algorithm with fine-grained optimizations. We integrate these optimizations together as a unified framework, which achieves speed-up for 3–5 times. In Chapter 5, we propose a STA graph partitioning framework that overcomes the GPU memory bottleneck. We believe this partitioning framework can allow us to offload the STA workload of industrial designs to multiple GPUs for further acceleration. The last chapter concludes this thesis and highlights the main contributions. We also point to several directions for the future work."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/120199"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Guannan Guo"],"dc:subject":["Static Timing Analysis","Parallel And Heterogeneous Computing"],"dc:title":["Parallel and heterogeneous computing for static timing analysis"],"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:57Z"}