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