Parametrized Exact Hardware-Software Partitioning

I. INTRODUCTION

• HS Partitioning selects task-graph vertices for software or hardware execution to minimize a cost subject to a budget.Relevant costs include wall-clock time, energy, chip size, and monetary cost, and bounds may be imposed on these metrics.Source: §I · p. 1
• Many HS Partitioning formulations are NP-hard, and the paper focuses primarily on minimizing task-graph span.Span is the execution time with an unbounded number of parallel processes.Source: §I · p. 1
• The paper identifies a class of HS Partitioning problems that is fixed parameter tractable when parameterized by the task graph's directed pathwidth.The algorithmic cost is determined primarily by this graph parameter.Source: §I · p. 1
• A directed-path-decomposition-based dynamic program yields up to 200x speedup over an equivalent linear-programming formulation.The paper also introduces a recursive-bisection solver for finding directed path decompositions.Source: §I · p. 1
• Real-world neural-network task graphs are examined to show that low directed pathwidth arises naturally.The paper uses the SODA toolchain and notes that RESNET has a pathlike task-graph structure.Source: §I · p. 1

II. BACKGROUND & NOTATION

• The notation [i, j] denotes the integers from i through j, [j] abbreviates [1, j], and P(S) denotes the power set of S.Source: §II · p. 2

A. Directed Path Decompositions

• A path decomposition is a sequence of overlapping vertex sets that covers every vertex continuously and contains both endpoints of each edge in some set.Its width is the maximum set size.Source: A. Directed Path Decompositions · p. 2
• Adjacent separators can be made to differ by one vertex, with singleton end separators, without increasing decomposition width.This form has N = 2n separators for a graph with n vertices.Source: A. Directed Path Decompositions · p. 2
• Dynamic programming on a nice path decomposition uses memory exponential in its width and linear in graph size.Introduce nodes are separators larger than their predecessor; bounded-parameter algorithms have polynomial complexity in graph size.Source: A. Directed Path Decompositions · p. 2
• A directed path decomposition of a DAG requires each directed edge's source to appear in a separator no later than its destination.The figures show an example task graph and its decomposition, with separator {c, d} circled in both.Source: A. Directed Path Decompositions · p. 2, Figure 1 · p. 2

B. HS Partitioning & Related Work

• Many constrained HS partitioning variants are NP-hard, prompting heuristic approaches such as tabu search, ant colony optimization, and genetic algorithms.The paper notes that exact solutions can be difficult for large instances.Source: B. HS Partitioning & Related Work · pp. 2–3
• Shi et al.’s dynamic program optimizes a single “hot” path but applies only to graphs with pathwidth exactly 2; this work extends the setting to small k.The comparison identifies a limitation in the prior method’s applicability.Source: B. HS Partitioning & Related Work · pp. 2–3
• Makespan minimization targets the critical-path length, or execution time with unbounded parallel resources, under the assumption that input task graphs are directed and acyclic.The paper compares against ILP formulations.Source: B. HS Partitioning & Related Work · p. 3
• The LP formulation assigns each task to software or hardware, accounts for execution and cross-partition communication costs, and minimizes maximum task completion time.Hardware-area budgets are among the possible additional constraints in HS partitioning.Source: B. HS Partitioning & Related Work · pp. 2–3
• Machine-learning task graphs can be pathlike, and RESNET contains low-pathwidth subgraphs, though the breadth of pathwidths across applications remains under study.The cited graph structure motivates algorithms that exploit low pathwidth.Source: B. HS Partitioning & Related Work · p. 3

III. METHODOLOGY

• A recurrence based on directed path decompositions captures multiple existing HS-partitioning formulations.The section develops an exact dynamic programming algorithm for the recurrence.Source: §III · p. 3
• The methodology develops an exact dynamic programming algorithm for the recurrence and a novel directed-path-decomposition solver based on recursive bisection.Source: §III · p. 3
• The method introduces a solver for finding directed path decompositions as part of the overall approach.The passage identifies this solver alongside the recurrence and dynamic program.Source: §III · p. 3

A. Dynamic Programming Algorithm

• A directed path decomposition supplies overlapping separators for recursively expressing HS-partitioning cost, starting from the task graph’s final output.The recurrence tracks the proposed partition, separator width, and currently used area; its update function is formulation-specific.Source: A. Dynamic Programming Algorithm · p. 3
• The recurrence can return vectors indexed by separator assignments rather than only scalar values.The passage describes an ordering on vectors Xi → R for each Xi.Source: A. Dynamic Programming Algorithm · p. 3
• For makespan, the per-task time cost is the maximum input-computation and transfer time across inputs, plus the time to execute the task.The formulation assumes no hardware-area limit.Source: A. Dynamic Programming Algorithm · p. 3
• With no hardware-area limit, the table-based algorithm runs in O(nf(k)) time, where f(k) = O(k2^k) and k is the decomposition’s directed pathwidth.Source: A. Dynamic Programming Algorithm · p. 3

B. Directed Path Decompositions

• The solver constructs directed path decompositions by recursively finding minimal balanced separators and using them as decomposition separators.The approach follows a strategy similar to that used by [27],.Source: B. Directed Path Decompositions · p. 3
• At each iteration, a directed separator divides a candidate into preceding and following vertices, and the next candidate boundary draws from the current boundary and separator.When no separator is found, the remaining interior is returned as that candidate’s solution.Source: Figure 2 · p. 4
• The separator problem has a simple linear-programming formulation that exploits the input graphs’ DAG structure.Source: B. Directed Path Decompositions · p. 4

1) Balanced Directed Separators:

• The formulation places one partition before and the other after the separator in the DAG’s topological order.Incoming edges to the separator originate in x, and outgoing edges lead to y.Source: 1) Balanced Directed Separators · p. 4
• The constraints prevent direct edges from x to y and prevent any vertex from belonging to both partitions.Source: 1) Balanced Directed Separators · p. 4
• Each partition must contain at least one vertex and satisfy an upper size bound imposed by the balance constraint.Source: 1) Balanced Directed Separators · p. 4
• The formulation can use a linear programming solver such as Gurobi, but very large instances may require a more scalable heuristic.The passage gives scalable multilevel methods for vertex separators as an example.Source: 1) Balanced Directed Separators · p. 4

2) Decomposition Solver:

• The solver uses a Flowcutter-based heuristic that recursively bisects a DAG to build a hierarchy of separators.Source: 2) Decomposition Solver · p. 4
• At each step, it separates a candidate’s interior into two partitions and a separator, returning the candidate if no valid split is found or the interior is the whole graph.The candidate consists of boundary B and interior I; initially B is empty and I is the vertex set.Source: 2) Decomposition Solver · p. 4
• The two resulting interiors are recursively decomposed using boundaries drawn from the current boundary and separator; the solver concatenates the left decomposition, separator, and right decomposition.Source: 2) Decomposition Solver · p. 4

IV. EXPERIMENTS

• The evaluation compares dynamic programming with linear programming on synthetic bounded-pathwidth graphs, then examines task graphs from neural-network architectures.Gurobi and GLPK runs had a 10-minute time limit; experiments used an AMD Ryzen 5 7640U.Source: §IV · pp. 4–5

A. Synthetic Graphs

• Synthetic graphs receive uniformly random communication, hardware-time, and software-time weights, with software-time weights set to twice the corresponding hardware-time estimates.Source: A. Synthetic Graphs · p. 5

1) Series-Parallel Graphs:

• The series-parallel tests vary the number of parallel paths across 3, 6, and 9, and the number of layers across 250, 500, 1,000, and 2,000.GLPK is excluded from the plot because it timed out on some of the smallest instances.Source: 1) Series-Parallel Graphs · p. 5
• Almost 200% faster than Gurobi on the largest series-parallel graph, dynamic programming also found an optimal solution for a 2,000-layer graph.The authors describe the 2,000-layer instance as considerably larger than could be comfortably handled by the ILP.Source: 1) Series-Parallel Graphs · p. 5

2) Martingale Graphs:

• Dynamic programming takes only a few seconds on some martingale-graph instances where linear programming exceeds the 10-minute timeout.It has sub-second times for nearly all tested instances; Gurobi takes 36 seconds on the largest martingale input, while the largest series of theta graphs takes over 300 seconds.Source: 2) Martingale Graphs · p. 5

B. Neural Networks

• The RESNET subgraph of convolution, multiplication, and subtraction operations has directed pathwidth 5, and the authors point to chaining many such low-pathwidth subgraphs as the setting where benefits arise.Source: B. Neural Networks · p. 5
• The neural-network task graphs are generated with the SODA toolchain, and the examined architectures are used to find directed path decompositions.Source: B. Neural Networks · p. 5
• Without “torch.const” operations, the highest directed pathwidth among the examined neural-network architectures is 6; the authors say these graphs are amenable to their approach for makespan.With the constant operations, some graphs, including Mobile Net and RESNET, have pathwidth too high for practical fixed-parameter algorithms; the constants do not meaningfully contribute to makespan.Source: B. Neural Networks · p. 5, Table I · p. 5
• All tested solvers find solutions for the real-world graph batch in sub-second times.The authors contrast these relatively simple inputs with denser, more complicated synthetic graphs of bounded directed pathwidth.Source: B. Neural Networks · p. 5

• The conclusion reports more than 200× speedup over conventional linear programming approaches, while Fig. 3 reports up to 200x on the largest series-parallel graphs.Source: §V · p. 5, Figure 3 · p. 6
• The paper concludes that classical HS Partitioning formulations become efficiently solvable when parameterized by the task graph’s directed pathwidth.Source: §V · p. 5
• All tested solvers found solutions for real neural-network graphs in sub-second times.The paper describes these inputs as fairly simple compared with the denser, more complicated synthetic graphs.Source: Figure 4 · p. 6
• Real-world task graphs, including those derived from RESNET, contain substantial low-pathwidth subgraphs, and the paper introduces a generator for low-pathwidth instances.Source: §V · pp. 5–6
• Future work includes richer cost models covering communication overhead or heterogeneous memory, realistic graph generators, and automated pathwidth-aware compilation pipelines.Source: §V · p. 6