Computation Offloading and Task Scheduling for DNN-Based Applications in Cloud-Edge Computing

Zheyi Chen, Junqin Hu, Xing Chen, Jia Hu, Xianghan Zheng, Geyong MinIEEE Access 2020 · OpenReview

Abstract

Deep neural network (DNN) applications demand significant computational resources, often exceeding the capabilities of mobile devices. Computation offloading to edge or cloud servers provides a solution, but improper scheduling can lead to excessive latency. This paper addresses the challenge of minimizing average response time in multi-task parallel scheduling within a cloud-edge environment. We formulate the offloading problem and propose two solutions: a Greedy Algorithm and a Genetic Algorithm. Experimental results demonstrate that both methods outperform traditional scheduling schemes, with the Genetic Algorithm providing superior response times at the cost of higher computational overhead.

1. Introduction

The proliferation of DNN-based applications—such as real-time image recognition and natural language processing—on mobile devices has created a critical need for efficient resource management. While mobile devices offer low-latency local processing, they are constrained by battery life and processing power. Conversely, remote clouds offer vast resources but introduce significant network latency. Edge computing serves as a middle tier, providing localized high-performance computing. This paper investigates how to optimally partition and schedule DNN layers across this three-tier architecture (Mobile-Edge-Cloud) to minimize the average response time for multiple concurrent users.

2. Problem Formulation: The Resource-Latency Trade-off

The core objective is to minimize the average response time for a set of DNN tasks. Each DNN application is modeled as a sequence of layers (subtasks). The environment consists of heterogeneous nodes (mobile, edge, cloud) with varying processing capacities and communication bandwidths.

Offloading decisions must account for:

  • Processing Time: The time required to execute a layer on a specific node.
  • Transmission Time: The time to transfer data between nodes, which depends on the output size of the preceding layer and the network bandwidth.
  • Waiting Time: The time a task spends in a queue, influenced by the node's concurrency level.

3. Proposed Scheduling Algorithms

To solve the complex scheduling problem, two distinct approaches were developed.

3.1 Greedy Algorithm

The Greedy Algorithm is designed for rapid decision-making. It employs a Shortest Job First (SJF) strategy, assigning each subtask to the node that provides the minimum estimated response time at that moment. This method is computationally efficient, making it suitable for real-time applications, though it may occasionally settle for local optima rather than a global minimum.

3.2 Genetic Algorithm (GA)

The Genetic Algorithm adopts an evolutionary approach to find near-optimal scheduling schemes. It represents potential schedules as "chromosomes" and iteratively improves the population through:

  • Selection: Favoring schedules with lower response times.
  • Crossover: Combining elements of high-performing schedules.
  • Mutation: Introducing random changes to explore the solution space and avoid local optima.

4. Experimental Results and Analysis

The algorithms were evaluated using a simulated 7-layer DNN workload across 12 concurrent tasks. Key findings include:

  • Performance Gains: Both proposed algorithms significantly reduced response times compared to "Cloud-only" or basic "Load Balancing" approaches. In high-load scenarios, the cloud-only approach exceeded 5000ms, while the GA maintained response times under 1500ms.
  • Algorithm Comparison: The Genetic Algorithm consistently outperformed the Greedy Algorithm by approximately 5-10% in terms of response time. However, the GA required significantly more computation time (~2.5s vs <0.25s for 96 tasks).
  • Edge Collaboration: Scenarios involving connected edge nodes showed further improvements, as nodes could share workloads to alleviate local bottlenecks.

5. Conclusion

Intelligent task scheduling at the layer level is essential for deploying complex DNNs in mobile environments. While the Genetic Algorithm offers the best performance for minimizing latency, the Greedy Algorithm provides a viable alternative for scenarios requiring near-instantaneous scheduling decisions. Future work will focus on incorporating energy consumption constraints and exploring Reinforcement Learning to handle dynamic network conditions and fluctuating resource availability.

Summary updated

Abstract

Due to the high demands of deep neural network (DNN) based applications on computational capability, it is hard for them to be directly run on mobile devices with limited resources. Computation offloading technology offers a feasible solution by offloading some computation-intensive tasks of neural network layers to edges or remote clouds that are equipped with sufficient resources. However, the offloading process might lead to excessive delays and thus seriously affect the user experience. To address this important problem, we first regard the average response time of multi-task parallel scheduling as our optimization goal. Next, the problem of computation offloading and task scheduling for DNN-based applications in cloud-edge computing is formulated with a scheme evaluation algorithm. Finally, the greedy and genetic algorithms based methods are proposed to solve the problem. The extensive experiments are conducted to demonstrate the effectiveness of the proposed methods for scheduling tasks of DNN-based applications in different cloud-edge environments. The results show that the proposed methods can obtain the near-optimal scheduling performance, and generate less average response time than traditional scheduling schemes. Moreover, the genetic algorithm leads to less average response time than the greedy algorithm, but the genetic algorithm needs more running time.
BibTeX
@inproceedings{chen2020computation,
  author = {Zheyi Chen and Junqin Hu and Xing Chen and Jia Hu and Xianghan Zheng and Geyong Min},
  title = {{Computation Offloading and Task Scheduling for DNN-Based Applications in Cloud-Edge Computing}},
  booktitle = {IEEE Access},
  year = {2020},
  url = {https://openreview.net/forum?id=WmKoSoOnpT},
}
Figure