DOPart: Competitive-Ratio Optimal Online Offloading of Sequentially Dependent Tasks

This work is motivated by the need for real-time partitioning of a deep neural network inference job and offloading part of it from a resource-constrained device to a resource-rich server. Since both the processing delay of different job stages and the communication delay of offloading usually are unknown ahead of time, this problem is naturally modelled as online offloading of sequentially dependent computational tasks from a local processor to a remote processor. We aim to minimize the total delay of all tasks by utilizing local and remote computational resources, while considering the impact of the offloading delay. We propose Delay-optimal Online Partitioning (DOPart), a lightweight online algorithm that uses an adaptive thresholding strategy to solve the offloading problem. We derive the competitive ratio for DOPart and show that it is optimal in the sense that no other deterministic online algorithm can achieve a lower competitive ratio. Furthermore, it provides bounded performance guarantees even under imprecise parameter estimation. Through experimenting with AlexNet, VGG-19, and ResNet-34, we demonstrate that DOPart substantially outperforms state-of-the-art online solutions.