Exact algorithm speeds up hardware software task splitting dramatically
Parametrized Exact Hardware-Software Partitioning
Data Structures and Algorithms
Summary
Splitting tasks between hardware and software can be very hard, especially when trying to do it in the best possible way. The authors define a new way to look at this problem that allows them to solve it exactly and much faster for certain types of task graphs with special shapes. Their method can speed up calculations by up to 200 times compared to older techniques, making it easier to optimize systems that run things like neural networks. This work applies particularly well when the tasks have a certain ‘directed pathwidth’ property that controls their complexity.
What this means in practice
- •For embedded system developers: Optimize which parts of their code to run in hardware versus software for faster or more energy-efficient embedded devices.
- •For neural network engineers: Accelerate task scheduling in neural network training hardware setups by accurately partitioning computations between hardware and software components.
Authors
Cameron Ibrahim, S M Ferdous, Erdal Mutlu, Ilya Safro, Mahantesh Halappanavar
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.