Complexity of Scheduling in Synthesizing Hardware from Concurrent Action Oriented Specifications

Gaurav Singh, S. S. Ravi, Sumit Ahuja, Sandeep K. Shukla

TL;DR

This paper delves into the computational complexity of scheduling problems within the CAOS (Concurrent Action Oriented Specifications) hardware synthesis framework, particularly focusing on optimizing for peak power consumption. The authors establish NP-completeness for several key scheduling problems and propose approximation algorithms and heuristics to tackle these challenges in practical hardware design scenarios.

What Problem Does This Paper Address?

High-level synthesis (HLS) aims to automate the creation of hardware designs from behavioral specifications. Concurrent Action Oriented Specifications (CAOS), exemplified by Bluespec System Verilog (BSV), offer a powerful way to model highly concurrent systems using atomic transactions. A critical step in CAOS-based synthesis is scheduling – deciding which actions to execute in each clock cycle to achieve efficient hardware in terms of area, latency, and power.

While CAOS simplifies concurrency management, it introduces new scheduling challenges, especially when considering peak power constraints. Peak power, the maximum power consumed in any single time slot, is crucial for modern designs to avoid thermal issues and ensure reliability. The paper addresses the fundamental question: What is the computational complexity of scheduling actions in CAOS to meet peak power constraints, and how can we efficiently find good, if not optimal, schedules?

Methods

The paper employs a rigorous theoretical approach, leveraging computational complexity theory to analyze the scheduling problems. Key methods include:

  • NP-completeness proofs: The authors demonstrate that several core scheduling problems related to CAOS are NP-complete. This is achieved through reductions from known NP-complete problems like Maximum Independent Set (MIS) and Partition. This establishes that finding optimal solutions is likely intractable for large instances.
  • Approximation Algorithms: For problems proven to be NP-complete, the paper proposes approximation algorithms. These algorithms aim to find solutions that are provably close to the optimal solution within a certain factor, offering a practical trade-off between solution quality and computation time.
  • Heuristics: The paper also discusses heuristics, which are algorithms designed to find good solutions quickly, though without strict performance guarantees.
  • Problem Transformation: A significant technique is the transformation of CAOS scheduling problems into well-studied problems like Maximum Independent Set (MIS), Minimum Coloring, and Bin Packing. This allows the application of existing, powerful algorithms and theoretical results from these domains to the CAOS context.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic design rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • CAOS scheduling is computationally hard: The core insight is that even with the high-level abstraction of CAOS, the problem of optimally scheduling actions, especially under peak power constraints, is computationally intractable (NP-complete). This means we generally cannot expect to find perfect solutions quickly for complex designs.
  • Strong connection to graph problems: The paper masterfully demonstrates how CAOS scheduling problems map directly to classic graph theory problems like Maximum Independent Set and Graph Coloring. This is a powerful insight because it allows us to leverage decades of research in graph algorithms for hardware scheduling.
  • Peak power is a significant challenge: The paper highlights that managing peak power is not a trivial add-on but fundamentally complicates the scheduling problem, often making it harder than scheduling without such constraints.
  • Approximation is key for practicality: Given the NP-completeness, the paper emphasizes that practical solutions will rely on approximation algorithms and heuristics that offer good performance guarantees rather than exact optimal solutions.
  • Bluespec's practical implications: The paper frequently relates its theoretical findings back to the practicalities of the Bluespec compiler, showing how these theoretical results can inform the design and understanding of real-world synthesis tools.

Key Results

  • NP-completeness proofs: The paper formally proves that the Maximum Non-conflicting Subset of Actions (MNS) problem and the Minimum Length Schedule Construction (MLS) problem are NP-complete.
  • Approximation bounds: For the MNS problem, it's shown that no $O(n^{1-\epsilon})$-approximation algorithm exists unless P=ZPP. For a special case where actions conflict with at most $\Delta$ others, a $(\Delta+1)$-approximation algorithm is presented.
  • Efficient solution for MNA-PP: The Maximum Number of Actions in a Time Slot Subject to Peak Power Constraint (MNA-PP) problem is shown to be solvable efficiently in $O(n \log n)$ time using a greedy algorithm.
  • NP-completeness of MU-PP: The Maximizing Utility Subject to Peak Power Constraint (MU-PP) problem is proven to be NP-complete, reducing from the KNAPSACK problem.
  • NP-completeness of MPP-DECISION: The problem of determining if a schedule of length $L$ exists satisfying peak power $P$ is shown to be NP-complete, even for fixed $L=2$. It's also shown to be strongly NP-complete when $L$ is part of the instance.
  • Approximation for MM-PP: The Minimizing Makespan Subject to Peak Power Constraint (MM-PP) problem can be efficiently approximated by leveraging algorithms for the Bin Packing problem.

Limitations and Future Work

  • Confluent Sets of Actions: The paper notes that for designs described using "confluent sets of actions," re-scheduling to meet peak power constraints is suitable because it doesn't alter the final output. However, for designs that are not confluent, re-scheduling might lead to functional changes, which is a limitation for general applicability.
  • Precedence Constraints: The authors mention that a future research direction is to investigate whether the approximation algorithms can be extended to scheduling problems that include precedence constraints among actions. This would make the framework more applicable to a wider range of hardware designs.
  • Practical Implementation: While the paper provides theoretical foundations and algorithmic approaches, the practical implementation and performance tuning of these algorithms within a real synthesis tool like Bluespec would be a significant undertaking.
  • Specific Hardware Architectures: The analysis is general to CAOS. Future work could explore how specific hardware architectures or design styles might influence the complexity or approximation ratios of these scheduling problems.

Summary updated

Abstract

Concurrent Action Oriented Specifications (CAOS) formalism such as Bluespec Inc.'s Bluespec System Verilog (BSV) has been recently shown to be effective for hardware modeling and synthesis. This formalism offers the benefits of automatic handling of concurrency issues in highly concurrent system descriptions, and the associated synthesis algorithms have been shown to produce efficient hardware comparable to those generated from hand-written Verilog/VHDL. These benefits which are inherent in such a synthesis process also aid in faster architectural exploration. This is because CAOS allows a high-level description (above RTL) of a design in terms of atomic transactions, where each transaction corresponds to a collection of operations. Optimal scheduling of such actions in CAOS-based synthesis process is crucial in order to generate hardware that is efficient in terms of area, latency and power. In this paper, we analyze the complexity of the scheduling problems associated with CAOS-based synthesis and discuss several heuristics for meeting the peak power goals of designs generated from CAOS. We also discuss approximability of these problems as appropriate.
BibTeX
@inproceedings{singh2007complexity,
  author = {Gaurav Singh and S. S. Ravi and Sumit Ahuja and Sandeep K. Shukla},
  title = {{Complexity of Scheduling in Synthesizing Hardware from Concurrent Action Oriented Specifications}},
  booktitle = {Power-aware Computing Systems},
  year = {2007},
  url = {https://openreview.net/forum?id=8pjaiiUp91},
}
Figure