From Partitioning to Provisioning: Co-Designing DNN Deployment and Infrastructure Capacity

Introduction

Distributed deep neural network (DNN) inference [1], [2] enables computationally demanding models to be executed across interconnected devices. A key enabling technique is DNN partitioning [3], [4], which distributes different portions of a model across devices. For streaming workloads, these portions can operate as a pipeline, allowing successive inputs to be processed concurrently [5], [6]. How to partition and deploy DNNs across computing networks has thus become a fundamental problem in distributed inference.

Existing research has largely approached this problem from a deployment perspective: given an infrastructure with fixed computing and communication capacities, how should a DNN be partitioned and deployed to achieve the best inference performance? Extensive efforts have been devoted to optimizing inference latency [3], [7], [8], throughput [2], [6], and other performance metrics [9], [10] under such resource constraints. While this perspective addresses how to make effective use of existing infrastructure, it leaves open a complementary question: how should the infrastructure itself be provisioned to support the inference workloads deployed on it?

The answer depends on the deployment itself. Partitioning determines where computation occurs and how much data traverses each link [3], [8], thereby shaping where additional capacity is needed. Yet capacity expansion can change which deployment is preferable: a deployment that maximizes throughput with existing resources may be far more expensive to upgrade than an alternative. Deployment and infrastructure capacity must therefore be designed jointly, rather than optimized in sequence.

In this paper, we develop such a co-design framework for pipelined DNN inference. Given a computing network with heterogeneous capacity costs, we jointly optimize the physical deployment path, the partitioning of DNN computational blocks, and the additional computing and communication capacities needed to sustain a target inference throughput. Although this problem couples discrete deployment choices with continuous provisioning decisions, we show that it possesses an exact and efficiently solvable structure on acyclic networks. The key insight is that the bottleneck-stage characterization of pipeline throughput allows the capacity requirements of individual stages to be determined locally. These requirements induce additive provisioning costs along a deployment path, enabling an exact reduction of the joint design problem to a shortest-path problem on a state graph.

The main contributions of this paper are summarized below:

• We formulate an inference-infrastructure co-design problem that jointly determines DNN partitioning, deployment paths, and computing and communication capacity increments. Unlike fixed-capacity deployment optimization, our formulation treats infrastructure capacity as a design variable, allowing inference deployment and capacity provisioning to be optimized together.

• We establish an exact equivalence between the co-design problem on acyclic networks and a shortest-path problem on an appropriately constructed state graph. Based on this structural result, we develop a dynamic programming algorithm that obtains a globally optimal solution in $O(|\mathcal{V}|N + |\mathcal{E}|N^{2})$ time and $O(|\mathcal{V}|N)$ space.

• We evaluate the proposed approach on 400 instances with VGG-16 and ResNet-50 workloads. Compared with two heuristic provisioning strategies that do not jointly optimize deployment and capacity expansion, our approach achieves substantial cost reductions, with median cost ratios reaching 25 and worst-case ratios exceeding 100. These results highlight the importance of co-designing DNN deployment and its supporting infrastructure capacity.

Problem Formulation

We first describe how DNN deployment and network capacities determine pipelined inference throughput, and then formulate the minimum-cost co-design problem under a target throughput requirement.

DNN Deployment Model

The distributed computing network is modeled as a directed graph $G = (\mathcal{V}, \mathcal{E})$, where $\mathcal{V}$ and $\mathcal{E}$ denote the sets of physical nodes and directed links, respectively. The network contains a source node $s \in\mathcal{V}$ and a destination node $t \in\mathcal{V}$, with $s \ne t$, and at least one path from $s$ to $t$ is assumed to exist. Each node $v \in\mathcal{V}$ has existing computing capacity $C_v > 0$, measured in floating-point operations per second. Each link $e \in\mathcal{E}$ has existing communication capacity $B_e > 0$, measured in bits per second. We collect the existing capacities into the vectors $C = (C_v)_{v \in\mathcal{V}}$ and $B = (B_e)_{e \in\mathcal{E}}$.

The DNN is represented by an ordered sequence of $N \ge1$ heterogeneous blocks, each of which may be a single layer or a module such as a residual or inception module. To characterize the computation and data transfer requirements, let $Q_n > 0$ denote the number of floating-point operations required by block $n$, for $n = 1, \ldots, N$; and let $D_n > 0$ denote the activation size in bits after the first $n$ blocks, for $n = 0, \ldots, N$. Thus, $D_0$ is the raw input size and $D_N$ is the final output size. To express the computing workload of consecutive blocks assigned to a node, we define the prefix workload $S_0 = 0$ and

A node executing blocks $i + 1, \ldots, j$ then requires $S_j - S_i$ floating-point operations.

A DNN deployment specifies both the physical route through the network and how consecutive DNN blocks are assigned to nodes on that route. We represent it by a path $p$ and a vector of partition points $b_p$. The path $p$ is defined as

where $L_p$ is the number of nodes on $p$, and $v_{p,\ell}$ denotes its $\ell$-th node. Let $\mathcal{P}$ be the set of all such paths. For each $p \in\mathcal{P}$, the vector of partition points is

Let $\mathcal{B}_p$ be the set of all such vectors, where $\mathbb{N}_0$ denotes the non-negative integers. For $\ell=1,\ldots,L_p$, $b_{p,\ell}$ denotes the number of DNN blocks completed along $p$ up to and including node $v_{p,\ell}$. Accordingly, node $v_{p,\ell}$ executes blocks $b_{p,\ell-1}+1,\ldots,b_{p,\ell}$. If $b_{p,\ell}=b_{p,\ell-1}$, the node performs no computation and only forwards the activation. After a node $v_{p,\ell}\ne t$ completes its assigned blocks, it sends the activation of size $D_{b_{p,\ell}}$ over the link $(v_{p,\ell},v_{p,\ell+1})$.

Pipelined Throughput

In pipelined execution, the inference consists of computation stages and communication stages. We consider steady-state pipelined inference with sufficient buffering and no resource contention, where computation and communication stages can overlap across successive inputs. The slowest stage determines the output interval, whose reciprocal gives the inference throughput [8]. For a deployment $(p,b_p)$, the computation time at each node equals its assigned workload divided by its computing capacity. Hence, the maximum computation-stage delay is

For $\ell=1,\ldots,L_p-1$, let $e_{p,\ell}=(v_{p,\ell},v_{p,\ell+1})$ be the $\ell$-th link on $p$. The corresponding communication time depends on the activation size and link capacity, giving the maximum communication-stage delay

The output interval is therefore

The minimum achievable output interval over all feasible deployments is

and the maximum achievable inference throughput under these capacities is $1/T^*(C,B)$.

The Minimum-Cost Co-Design Problem

Suppose the inference service requires a throughput of at least $1/\beta$, where $\beta>0$, or equivalently, an output interval no greater than $\beta$. The goal is to meet this requirement at minimum provisioning cost by jointly determining the DNN deployment and capacity increments.

For every node $v\in\mathcal{V}$, let $x_v\ge0$ be the increment added to $C_v$, and for every link $e\in\mathcal{E}$, let $y_e\ge0$ be the increment added to $B_e$. We collect these increments into the vectors $x=(x_v)_{v\in\mathcal{V}}$ and $y=(y_e)_{e\in\mathcal{E}}$. Since the cost of adding capacity can vary across the network, let $\pi_v^{\mathrm{comp}}>0$ and $\pi_e^{\mathrm{comm}}>0$ be the unit prices of computing capacity and communication capacity, respectively, and collect them into the vectors $\boldsymbol{\pi}^{\mathrm{comp}}=(\pi_v^{\mathrm{comp}})_{v\in\mathcal{V}}$ and $\boldsymbol{\pi}^{\mathrm{comm}}=(\pi_e^{\mathrm{comm}})_{e\in\mathcal{E}}$. We consider linear provisioning costs for simplicity. The proposed method also applies to costs that are separable across nodes and links, non-decreasing in each capacity increment, and zero at zero increment.

After provisioning, the required throughput is achievable if $T^*(C+x,B+y)\le\beta$. We therefore formulate the minimum-cost co-design problem as

If the existing network already meets the throughput requirement, the optimal provisioning cost is zero. Otherwise, although (4) explicitly optimizes only $x$ and $y$, the physical path and partition points are implicitly optimized through $T^*$ in (3). Since the preferred deployment can change with variable capacities, deployment and provisioning decisions are coupled. In the next section, we exploit the acyclic network structure to obtain an exact solution to this co-design problem.

Exact Co-Design on Acyclic Networks

Cost-Weighted State Representation

We represent the deployment decisions in (4) using an auxiliary state graph $G_{\mathrm{S}} = (V_{\mathrm{S}}, E_{\mathrm{S}})$, where $V_{\mathrm{S}}$ is the set of states and $E_{\mathrm{S}}$ is the set of state transitions, both defined later in this section. Two edge weight functions $\delta(\cdot; \boldsymbol{x}, \boldsymbol{y}), w : E_{\mathrm{S}} \to\mathbb{R}_{\geq0}$ are defined in Sections III-A1 and III-A2, respectively.

Introduce a virtual terminal node $\tau\notin\mathcal{V}$. For each node, let $I_v$ denote its feasible block indices, with $I_s = \{0\}$, $I_v = \{0,1,\ldots,N\}$ for every $v \in\mathcal{V} \setminus\{s\}$, and $I_\tau= \{N\}$. The set of states (vertices of $G_{\mathrm{S}}$) is therefore $V_{\mathrm{S}} = \{(v,i): v \in\mathcal{V} \cup\{\tau\}, i \in I_v\}$. A state $(v,i)$ means that the activation after block $i$ has arrived at $v$, before $v$ processes any further blocks. In particular, $(s,0)$ means that the raw input has arrived at $s$ and no DNN blocks have yet been executed; $(\tau,N)$ means that all $N$ blocks have been processed and the final output is available at $t$.

Introduce a virtual link $e_\tau= (t,\tau)$ with $B_{e_\tau} = +\infty$ and $y_{e_\tau} = \pi^{\mathrm{comm}}_{e_\tau} = 0$, so that the weight formulas below apply to $e_\tau$. The set of state transitions (edges of $G_{\mathrm{S}}$) is

For $\xi= ((v,i),(z,j)) \in E_{\mathrm{S}}$, define $v(\xi) \triangleq v$, $e(\xi) \triangleq(v,z)$, $i(\xi) \triangleq i$, $j(\xi) \triangleq j$.

We call a simple path from $(s,0)$ to $(\tau,N)$ in $G_{\mathrm{S}}$ a state path, and let $\mathcal{R}$ be the set of all state paths. For each $r \in\mathcal{R}$, let $E_{\mathrm{S}}(r) \subseteq E_{\mathrm{S}}$ be the set of transitions between states of $r. Figure 1 illustrates $G_{\mathrm{S}}$ for a simple network. We next define the delay and provisioning cost associated with each state transition.

Delay of Transitions

1) Delay of Transitions: For a transition $\xi\in E_{\mathrm{S}}$, the computation at $v(\xi)$ and communication over $e(\xi)$ form two pipeline stages. Under capacity increments $\boldsymbol{x}$ and $\boldsymbol{y}$, its delay is represented as the larger of their delays:

The following lemma shows that state paths preserve both the deployment choices and their output intervals.

Proof: Forward map. Given $(p,\boldsymbol{b}_p)$, let $v_{p,L_p+1}=\tau$ and define $\eta_\ell=(v_{p,\ell},b_{p,\ell-1})$ for $\ell=1,\ldots,L_p+1$. By (1) and (2), each consecutive pair $(\eta_\ell,\eta_{\ell+1})$ belongs to $E_{\mathrm{S}}$. The resulting sequence starts at $(s,0)$ and ends at $(\tau,N)$, and thus defines a state path $r \in\mathcal{R}$.

Inverse map. Let $r \in\mathcal{R}$ be represented by the sequence $((u_1,i_1),\ldots,(u_{k-1},i_{k-1}),(u_k,i_k))$, where $u_1=s$, $i_1=0$, $u_{k-1}=t$, and $i_k=N$. By (5), $(u_\ell,u_{\ell+1}) \in E \cup\{e_\tau\}$ for all $\ell=1,\ldots,k-1$. Since $G$ is acyclic, $u_1,\ldots,u_{k-1}$ are pairwise distinct, and hence $p=(u_1,\ldots,u_{k-1}) \in\mathcal{P}$. Moreover, since $i_\ell\leq i_{\ell+1}$ for all $\ell=1,\ldots,k-1$, $\boldsymbol{b}_p=(i_1,\ldots,i_{k-1},i_k) \in\mathcal{B}_p$. Thus, the forward and inverse constructions are mutually inverse, proving the bijection.

Interval equality. Each transition $\xi_\ell=(\eta_\ell,\eta_{\ell+1})$ represents the computation at node $v_{p,\ell}$ followed by transmission over its outgoing link. Let $e_{p,L_p}=e_\tau$. Since $B_{e_\tau}=+\infty$, the final transition has zero communication delay. Therefore,

By (3) and Lemma 1, the minimum output interval can be expressed entirely over state paths:

Cost of Transitions

2) Cost of Transitions: By (6), a state path meets the throughput target if every transition on it has a delay no greater than $\beta$. For each $\xi\in E_{\mathrm{S}}$, $\delta(\xi;\boldsymbol{x},\boldsymbol{y})\leq\beta$ is equivalent to

Together with the non-negativity constraints, these inequalities give the minimum computing and communication capacity increments required by $\xi$:

where $[x]^+ \triangleq\max\{0,x\}$. Using the unit capacity prices, we define the provisioning cost of transition $\xi$ as

An Exact Shortest-Path Solution

Lemma [1] establishes a correspondence between DNN deployments and state paths, while $w(\xi)$ gives the minimum

Algorithm 1 Provisioning on a State Graph (PSG)

Input: $G = (\mathcal{V}, \mathcal{E})$, $C$, $B$, $Q_1,\ldots,Q_N$, $D_0,\ldots,D_N$, $\beta$, $\boldsymbol{\pi}^{\mathrm{comp}}$, $\boldsymbol{\pi}^{\mathrm{comm}}$

Output: optimal physical path $p^*$, partition points $b_{p^*}$, and capacity increments $\mathbf{x}^*,\mathbf{y}^*$

1: compute $S_0,\ldots,S_N$ and a topological order $v_1,\ldots,v_{|\mathcal{V}|}$ of $\mathcal{V}$; set $v_{|\mathcal{V}|+1}\leftarrow\tau$
2: $\operatorname{dist}(s,0)\leftarrow 0$, $\operatorname{dist}(v,i)\leftarrow+\infty$ for all other states, and clear $\operatorname{pred}$
3: for $d=1,\ldots,|\mathcal{V}|+1$ do
4:   for all $i\in I_{v_d}$ with $\operatorname{dist}(v_d,i)<+\infty$ do
5:     for all $(v_d,z)\in\mathcal{E}\cup\{e_\tau\}$ do
6:       for all $j\in I_z$ with $j\ge i$ do
7:         $\xi\leftarrow((v_d,i),(z,j))$
8:         compute $w(\xi)$
9:         if $\operatorname{dist}(v_d,i)+w(\xi)<\operatorname{dist}(z,j)$ then
10:          $\operatorname{dist}(z,j)\leftarrow\operatorname{dist}(v_d,i)+w(\xi)$
11:          $\operatorname{pred}(z,j)\leftarrow(v_d,i)$
12:        end if
13:      end for
14:    end for
15:  end for
16: end for
17: backtrack $\operatorname{pred}$ from $(\tau,N)$ to $(s,0)$ into a state path $r^*$
18: return $(p^*,b_{p^*},\mathbf{x}^*,\mathbf{y}^*)$ from $r^*$ as in the proofs of {xref}`Lemma 1` and {xref}`Theorem 1`, of cost $\operatorname{dist}(\tau,N)$

provisioning cost for each transition. If the physical network is acyclic, no physical node or link is used more than once along a state path. These costs can therefore be added along the path, leading to the following exact equivalence.

Proof. For any transition $\xi\in\mathcal{E}_S$, the delay requirement and non-negative capacity increments give

Let $J(\mathbf{x},\mathbf{y})=(\boldsymbol{\pi}^{\mathrm{comp}})^{\mathsf{T}}\mathbf{x}+(\boldsymbol{\pi}^{\mathrm{comm}})^{\mathsf{T}}\mathbf{y}$. For any feasible $(\mathbf{x},\mathbf{y})$, (6) guarantees a state path $r\in\mathcal{R}$ satisfying $\delta(\xi;\mathbf{x},\mathbf{y})\le\beta$ for every $\xi\in\mathcal{E}_S(r)$. Since $G$ is acyclic, no physical node or link appears more than once on $r$. Thus, by (7) and the non-negative capacity prices,

Conversely, let $r^*$ be a shortest state path, and set $x^*_{v(\xi)}=\rho(\xi)$ and $y^*_{e(\xi)}=\sigma(\xi)$ for all $\xi$ of $r^*$, with all other increments set to zero. By (7), this allocation is feasible. Since no physical resource is repeated along $r^*$,

The corresponding deployment follows from Lemma 1. ▪

By Theorem 1, the co-design problem reduces to a shortest-path problem on $G_S$ when $G$ is acyclic. Since every state transition follows a physical link or $e_\tau$, a topological order of $G$, with $\tau$ placed last, also gives a topological order of the state graph. We can therefore solve the problem by dynamic programming without explicitly constructing $G_S$. Maintain a label $\operatorname{dist}(v,i)$, set to $0$ at $(s,0)$ and $+\infty$ elsewhere. Each transition $\xi=((v,i),(z,j))$ is relaxed according to

Processing states in topological order yields the optimal cost $\operatorname{dist}(\tau,N)$. The predecessor pointers recover the corresponding deployment and capacity increments, as detailed in Algorithm 1.

Proof. Optimality follows from Theorem 1, since the relaxations in (8) are performed in topological order. The state graph $G_S$ has $O(|\mathcal{V}|N)$ states and $O(|\mathcal{E}|N^2)$ transitions. Each transition is processed once, and its weight is computed in $O(1)$ time. Since transitions are generated on demand from $\mathcal{E}$, the state graph need not be explicitly stored. Thus, only $O(|\mathcal{V}|N)$ distance labels and predecessor pointers are required. ▪

The same algorithm applies to the separable, non-decreasing provisioning costs described in Section II-C. It suffices to redefine $w(\xi)=f_{v(\xi)}(\rho(\xi))+g_{e(\xi)}(\sigma(\xi))$, where $f_v$ and $g_e$ are non-decreasing on $\mathbb{R}_{\ge0}$ and zero at zero.

Numerical Results

We evaluate the benefit of minimum-cost co-design by comparing PSG (Algorithm 1) with two provisioning heuristics that use throughput-optimal deployments to guide capacity upgrades. The experiments consider randomly generated tiered networks with VGG-16 and ResNet-50 workloads.

Both heuristics use throughput-optimal deployments to guide provisioning, without accounting for capacity prices. PFP (Provisioning under Frozen-Partitioning) fixes an initial throughput-optimal deployment and purchases the minimum capacity increments needed to meet $\beta$. PWF (Provisioning with Water-Filling) reduces the bottleneck stage delays of the current deployment to the next lower delay level or $\beta$, and recomputes a throughput-optimal deployment after each upgrade. When (3) admits multiple throughput-optimal deployments, PWF selects one of them (the first found by the solver) rather than enumerating all optima. For any $d>0$,

Entity	Distribution	Unit
$C_v$, source & access tier	$U[6,30]$	GFLOP/s
$C_v$, middle tier	$U[30,90]$	GFLOP/s
$C_v$, remote tier & $t$	$U[90,180]$	GFLOP/s
$B_e$, links to access tier	$U[30,100]$	Mbps
$B_e$, links to middle tier	$U[100,300]$	Mbps
$B_e$, links to remote tier & $t$	$U[300,1000]$	Mbps
$\pi_v^{\mathrm{comp}}$, nodes	$\mathrm{LU}[0.1,10]$	per GFLOP/s
$\pi_e^{\mathrm{comm}}$, links	$\mathrm{LU}[0.01,1]$	per Mbps

let $\rho_d(\xi)$ and $\sigma_d(\xi)$ denote $\rho(\xi)$ and $\sigma(\xi)$ in Section III-A2 with $\beta$ replaced by $d$. Algorithm 2 summarizes PWF, which terminated on all tested instances.

The DNN workloads are analytic block profiles of VGG-16 ($N = 16$) and ResNet-50 ($N = 18$) with $224 \times224$ inputs. Block workloads and activation sizes are derived from layer shapes, assuming FP32 activations and two floating-point operations per multiply-accumulate, with max-pooling folded into the preceding VGG-16 block and global average pooling folded into the last ResNet-50 block.

We generate 50 tiered DAGs, each consisting of a source $s$, three intermediate tiers (access, middle, and remote) with 2–3 nodes each, and a destination $t$. Each node has 1–3 randomly selected links to the next tier, except remote-tier nodes, which each connect to $t$. The resulting networks contain 8–11 nodes and at least one path from $s$ to $t$. Existing capacities and unit prices follow the distributions in Table I.

For each topology and DNN, we set $\beta= \alpha T^*(C, B)$, where $\alpha\in\{0.25, 0.4, 0.6, 0.8\}$. Since $\alpha< 1$, all instances require additional capacity. Using the same 50 topologies for both DNNs yields $50 \times2 \times4 = 400$ instances. We measure the ratio of each heuristic’s provisioning cost to the optimal cost obtained by PSG.

Figure 2 compares the provisioning-cost ratios over all 400 instances. PFP incurs median ratios of 5.1–8.6 for VGG-16 and 6.5–25.3 for ResNet-50, with worst cases of 144 and 639, respectively. PWF matches the optimum in 80% of ResNet-50 instances at $\alpha= 0.8$, but its median ratios remain 4.1–9.4 for VGG-16 and reach 5.6 for ResNet-50, with a worst case of 44. For VGG-16, the median ratios of both heuristics increase as $\alpha$ decreases, reaching 8.6 (PFP) and 9.4 (PWF) at $\alpha= 0.25$.

The cost gap reflects a key difference: the heuristics choose capacity upgrades without considering prices, whereas PSG minimizes price-weighted costs across feasible deployments. These results show that joint optimization can lead to much lower provisioning costs, even when deployment is updated during provisioning. In our Python implementation on an AMD Ryzen 7 8845H CPU, the median runtimes are 0.25, 0.28, and 1.8 ms for PSG, PFP, and PWF, respectively, showing that PSG remains computationally efficient on the tested instances.

Conclusion

This paper established an exact approach to co-designing DNN deployment and infrastructure capacity over acyclic

networks. Beyond the algorithmic result, the broader insight is that the value of computing and communication capacity depends on how it serves the inference workload as a whole, rather than on individual resources in isolation. This points toward a fundamental shift in AI infrastructure planning: from expanding available resources to strategically provisioning capacity where it delivers the greatest end-to-end benefit.

References