# Exploiting Duplications for Efficient Task Offloading in Multi-User Edge Computing
## 1 Introduction  
The proliferation of IoT applications, e.g., object recognition, vehicular systems and self-driving [1, 2, 3], have pushed the horizon of a novel computing paradigm--Multi-access Edge Computing (MEC) [4]. In MEC, a number of edge servers are deployed close to the user, and the computation-intensive tasks from end users are uploaded to and processed in the network of edge servers. After that, the results are returned to end user devices [5, 6]. As a result, the completion time of services and the energy consumption of end user devices can be reduced. Traditional offloading schemes [7] upload the entire task to edge servers. These approaches fail to utilize the parallelism between end devices and edge servers. To address this issue, the recent studies [8, 9] decompose the task into a number of subtasks and upload some of them to edge servers. In this way, end devices and edge servers can execute their subtasks in parallel, such that the overall completion time is reduced. For example, the authors in [8] synthetically considered the computation workload of subtasks, dependency among subtasks and wireless transmission time. In doing this, the subtasks can be rationally scheduled in the edge server or local devices, and the makespan of applications can be reduced. However, in the approaches based on task decomposition, more communication delay is introduced as the information exchange among subtasks that are not located in the sameprocessor needs to be done through the wireless links. To better understand the limitations of the existing works and reveal further optimization space, we study an example of task offloading for the object recognition applications [10], as shown in Figure 1.  
The task topology is depicted as a directed acyclic graph (DAG) as shown in Figure 1a. Each rectangle denotes a subtask with the execution delay labeled. An arrowed line from rectangle A to rectangle B denotes that subtask B depends on the results of subtask A. We can see that the object recognition first inputs the target image to the \"Pre-processing\" subtask. Based on the results of \"Pre-processing\", \"Shape\" and \"Texture\" will extract the object shapes and texture, respectively. Based on the extractions, the \"Classification\" subtask can recognize the object as a specific class of objects. Figure 1b shows the basic idea of traditional offloading works [7; 11; 12], which treat the four subtasks as a whole and offload them to edge servers. This approach overlooks the parallelism between users and edge servers. Figure 1c shows the basic idea of the recent works based on task decomposition [8; 13], which chooses some of the subtasks to offload, and thus the overall delay is reduced. From Table 1, through the offloading strategies based on task decomposition, the latency is reduced from 110 to 100 ms due to parallelism. However, from Figure 1c, we can see that considerable time (from 0 to 50 ms) is wasted in the \"idle\" slot because the subtask \"Texture\" needs to wait for the computational results from the subtask \"Pre\". The reason is that uploading subtasks requires the information exchange among them to be done through wireless links (an additional communication round is needed from \"Pre\" to \"Texture\"). To further reduce the execution delay and fully exploit the parallelism between local devices and edge servers, an intuitive yet reasonable solution is to duplicate the _Pre-processing_ module in the local devices (Figure 1d), and the overall execution delay can be further reduced to 86 ms. \begin{table}
\begin{tabular}{c c c} \hline \hline  & **Energy Cost (Local Execution Time)** & **Overall Delay** \\ \hline Figure 1b & 0 ms & 110 ms \\ \hline Figure 1c & 50 ms & 100 ms \\ \hline Figure 1d & 80 ms & 86 ms \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The delay comparison. Figure 1: Case study. (**a**) the DAG of object recognition. (**b**) entire task offloading strategy (**c**) subtask offloading strategy.