Presentation
Ordering-Centric: A Scalable and Exact Method for Scheduling with Resource Constraints
DescriptionResource-constrained scheduling is a fundamental and NP-hard problem in high level syntheis, crucial for optimizing the performance and efficiency of hardware designs. Despite significant advances, existing exact methods, such as holistic modeling approaches (e.g., time-indexed ILP/MILP) and iterative search techniques (e.g., SDC-SAT), continue to struggle with scalability, limiting their applicability to large-scale problems.
This paper proposes leveraging the inherent structural properties of resource binding, such as symmetry and redundancy, to segment the NP-hard RCS problem into three subproblems: unconstrained scheduling, resource sharing, and operation ordering. Additionally, we design and implement a new scheduling algorithm centered on operation order to address these subproblems. This algorithm optimizes the search process by focusing on operation order issues and strategically bypasses resource sharing calculations through the use of symmetry and redundancy, thus significantly improving the search efficiency.
Experimental results validate the proposed method's superiority, achieving at least average speedups of 71.96x and 19.22x over two state-of-the-art methods. This work presents a novel perspective on exact scheduling methodologies, offering a scalable and efficient solution for High-Level Synthesis (HLS) challenges.
This paper proposes leveraging the inherent structural properties of resource binding, such as symmetry and redundancy, to segment the NP-hard RCS problem into three subproblems: unconstrained scheduling, resource sharing, and operation ordering. Additionally, we design and implement a new scheduling algorithm centered on operation order to address these subproblems. This algorithm optimizes the search process by focusing on operation order issues and strategically bypasses resource sharing calculations through the use of symmetry and redundancy, thus significantly improving the search efficiency.
Experimental results validate the proposed method's superiority, achieving at least average speedups of 71.96x and 19.22x over two state-of-the-art methods. This work presents a novel perspective on exact scheduling methodologies, offering a scalable and efficient solution for High-Level Synthesis (HLS) challenges.
Event Type
Networking
Work-in-Progress Poster
TimeMonday, June 236:00pm - 7:00pm PDT
LocationLevel 2 Lobby