arXiv preprint ·
Parametrized Exact Hardware-Software Partitioning
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
When optimizing computing architecture for specific computationally intensive tasks, such as evaluating or training a neural network, it is important to identify what computational subtasks will offer the greatest decrease in cost (e.g., wall clock time or energy usage). This problem is known as Hardware-Software (HS) Partitioning, and it has a variety of formulations, many of which are NP-Hard. In this paper, we will define a family of HS Partitioning formulations which admit an exact fixed parameter tractable algorithm based on the directed pathwidth of the given task graph and show that this family of problems contains multiple existing formulations such as makespan minimization. Finally, we examine task graphs with small directed pathwidth that arise in real world applications and show that our algorithm can provide a speed up of up to 200x over a comparable linear programming approach utilizing the Gurobi ILP Library.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Explicit Asymptotic Bounds for Sequential Calibration Beyond $T^{2/3}$
Generating cyclic pivot Gray codes for well-ordered $k$-degenerate graphs in constant amortized time
How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics
Envy-free Allocations with Individual Payments
When Can Stateless Recovery Defeat Byzantine Quorum Safety? A Tight Normal Form for Single-Step BFT
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.