A Review of the Current Task Offloading Algorithms,Strategies and Approach in Edge Computing Systems

Task offloading is an important concept for edge computing and the Internet of Things(IoT)because computationintensive tasksmust beoffloaded tomore resource-powerful remote devices.Taskoffloading has several advantages,including increased battery life,lower latency,and better application performance.A task offloading method determines whether sections of the full application should be run locally or offloaded for execution remotely.The offloading choice problem is influenced by several factors,including application properties,network conditions,hardware features,and mobility,influencing the offloading system’s operational environment.This study provides a thorough examination of current task offloading and resource allocation in edge computing,covering offloading strategies,algorithms,and factors that influence offloading.Full offloading and partial offloading strategies are the two types of offloading strategies.The algorithms for task offloading and resource allocation are then categorized into two parts:machine learning algorithms and non-machine learning algorithms.We examine and elaborate on algorithms like Supervised Learning,Unsupervised Learning,and Reinforcement Learning(RL)under machine learning.Under the non-machine learning algorithm,we elaborate on algorithms like non(convex)optimization,Lyapunov optimization,Game theory,Heuristic Algorithm,Dynamic Voltage Scaling,Gibbs Sampling,and Generalized Benders Decomposition(GBD).Finally,we highlight and discuss some research challenges and issues in edge computing.

Energy-efficient reconfigurable processor for QC-LDPC via adaptive coding-voltage-frequency tuning

To apply a quasi-cyclic low density parity check(QC-LDPC)to different scenarios,a data-stream driven pipelined macro instruction set and a reconfigurable processor architecture are proposed for the typical QC-LDPC algorithm.The data-level parallelism is improved by instructions to dynamically configure the multi-core computing units.Simultaneously,an intelligent adjustment strategy based on a programmable wake-up controller(WuC)is designed so that the computing mode,operating voltage,and frequency of the QC-LDPC algorithm can be adjusted.This adjustment can improve the computing efficiency of the processor.The QC-LDPC processors are verified on the Xilinx ZCU102 field programmable gate array(FPGA)board and the computing efficiency is measured.The experimental results indicate that the QC-LDPC processor can support two encoding lengths of three typical QC-LDPC algorithms and 20 adaptive operating modes of operating voltage and frequency.The maximum efficiency can reach up to 12.18 Gbit/(s·W),which is more flexible than existing state-of-the-art processors for QC-LDPC.

A Hybrid Model for Reliability Aware and Energy-Efficiency in Multicore Systems

Recently,Multicore systems use Dynamic Voltage/Frequency Scaling(DV/FS)technology to allow the cores to operate with various voltage and/or frequencies than other cores to save power and enhance the performance.In this paper,an effective and reliable hybridmodel to reduce the energy and makespan in multicore systems is proposed.The proposed hybrid model enhances and integrates the greedy approach with dynamic programming to achieve optimal Voltage/Frequency(Vmin/F)levels.Then,the allocation process is applied based on the availableworkloads.The hybrid model consists of three stages.The first stage gets the optimum safe voltage while the second stage sets the level of energy efficiency,and finally,the third is the allocation stage.Experimental results on various benchmarks show that the proposed model can generate optimal solutions to save energy while minimizing the makespan penalty.Comparisons with other competitive algorithms show that the proposed model provides on average 48%improvements in energy-saving and achieves an 18%reduction in computation time while ensuring a high degree of system reliability.

Effectiveness Analysis of DVFS and DPM in Mobile Devices

The demand for high-performance embedded processors in multimedia mobile electronics is growing and their power consumption thus increasingly threatens battery lifetime. It is usually believed that the dynamic voltage and frequency scaling （DVFS） feature saves significant energy by changing the performance levels of processors to match the performance demands of applications on the fly. However, because the energy efficiency of embedded processors is rapidly improving, the effectiveness of DVFS is expected to change. In this paper, we analyze the benefit of DVFS in state-of-the-art mobile embedded platforms in comparison to those in servers or PCs. To obtain a clearer view of the relationship between power and performance, we develop a measurement methodology that can synchronize time series for power consumption with those for processor utilization. The results show that DVFS hardly improves the energy efficiency of mobile multimedia electronics, and can even significantly worsen energy efficiency and performance in some cases. According to this observation, we suggest that power management for mobile electronics should concentrate on adaptive and intelligent power management for peripherM devices. As a preliminary design, we implement an adaptive network interface card （NIC） speed control that reduces power consumption by 1070 when NIC is not heavily used. Our results provide valuable insights into the design of power management schemes for future mobile embedded systems.

Energy Efficient Scheduler of Aperiodic Jobs for Real-time Embedded Systems

Energy consumption has become a key metric for evaluating how good an embedded system is,alongside more performance metrics like respecting operation deadlines and speed of execution.Schedulability improvement is no longer the only metric by which optimality is judged.In fact,energy efficiency is becoming a preferred choice with a fundamental objective to optimize the system's lifetime.In this work,we propose an optimal energy efficient scheduling algorithm for aperiodic real-time jobs to reduce CPU energy consumption.Specifically,we apply the concept of real-time process scheduling to a dynamic voltage and frequency scaling(DVFS)technique.We address a variant of earliest deadline first(EDF)scheduling algorithm called energy saving-dynamic voltage and frequency scaling(ES-DVFS)algorithm that is suited to unpredictable future energy production and irregular job arrivals.We prove that ES-DVFS cannot attain a total value greater than C/ˆSα,whereˆS is the minimum speed of any job and C is the available energy capacity.We also investigate the implications of having in advance,information about the largest job size and the minimum speed used for the competitive factor of ES-DVFS.We show that such advance knowledge makes possible the design of semi-on-line algorithm,ES-DVFS∗∗,that achieved a constant competitive factor of 0.5 which is proved as an optimal competitive factor.The experimental study demonstrates that substantial energy savings and highest percentage of feasible job sets can be obtained through our solution that combines EDF and DVFS optimally under the given aperiodic jobs and energy models.

CASA:A New IFU Architecture for Power-Efficient Instruction Cache and TLB Designs

The instruction fetch unit （IFU） usually dissipates a considerable portion of total chip power. In traditional IFU architectures, as soon as the fetch address is generated, it needs to be sent to the instruction cache and TLB arrays for instruction fetch. Since limited work can be done by the power-saving logic after the fetch address generation and before the instruction fetch, previous power-saving approaches usually suffer from the unnecessary restrictions from traditional IFU architectures. In this paper, we present CASA, a new power-aware IFU architecture, which effectively reduces the unnecessary restrictions on the power-saving approaches and provides sufficient time and information for the power-saving logic of both instruction cache and TLB. By analyzing, recording, and utilizing the key information of the dynamic instruction flow early in the front-end pipeline, CASA brings the opportunity to maximize the power efficiency and minimize the performance overhead. Compared to the baseline configuration, the leakage and dynamic power of instruction cache is reduced by 89.7% and 64.1% respectively, and the dynamic power of instruction TLB is reduced by 90.2%. Meanwhile the performance degradation in the worst case is only 0.63%. Compared to previous state-of-the-art power-saving approaches, the CASA-based approach saves IFU power more effectively, incurs less performance overhead and achieves better scalability. It is promising that CASA can stimulate further work on architectural solutions to power-efficient IFU designs.

Worst-Case Finish Time Analysis for DAG-Based Applications in the Presence of Transient Faults

Tasks in hard real-time systems are required to meet preset deadlines, even in the presence of transient faults and hence the analysis of worst-case finish time （WCFT） must consider the extra time incurred by re-executing tasks that were faulty. Existing solutions can only estimate WCFT and usually result in significant under- or over-estimation. In this work, we conclude that a sufficient and necessary condition of a task set experiencing its WCFT is that its critical task incurs all expected transient faults. A method is presented to identify the critical task and WCFT in O（IVI ＋ IEI） where IVI and IEI are the number of tasks and dependencies between tasks, respectively. This method finds its application in testing the feasibility of directed acyclic graph （DAG） based task sets scheduled in a wide variety of fault-prone multi-processor systems, where the processors could be either homogeneous or heterogeneous, DVS-capable or DVS-incapable, etc. The common practices, which require the same time complexity as the proposed critical-task method, could either underestimate the worst case by up to 25%, or overestimate by 13%. Based on the proposed critical-task method, a simulated-annealing scheduling algorithm is developed to find the energy efficient fault-tolerant schedule for a given DAG task set. Experimental results show that the proposed critical-task method wins over a common practice by up to 40% in terms of energy saving.

A Compound Prescheduling Algorithm for Real-Time Tasks’ Battery-Aware Scheduling

To minimize battery consumption for portable devices, the prescheduling policy of battery-aware scheduling was improved by optimizing slack distribution. A battery-aware compound task scheduling （BACTS） algorithm considering various aspects including task deadline, current and execution time was proposed and evaluated with the previously prevailing earliest deadline first （EDF） algorithm. The results indicate the proposed BACTS algorithm manages to figure out a feasible schedule （if available） in battery-aware task scheduling even for disorganized connected task graphs beyond the solving ability of EDF. Its schedule achieves better performance with lower charge consumption after prescheduling, and also lower or equal optimum charge consumption after voltage scaling.

Slack-Nibbling Battery-Aware Task Scheduling

Dynamic voltage scaling （DVS） is an efficient approach to maximize the battery life of portable devices. A novel overall planning strategy （OPS II） balancing slack supply and demand for DVS is proposed. An OPS II-based slack-nibbling overall planning strategy （SNOPS） algorithm is also proposed, which iteratively nibbles slacks for appropriate tasks selected by an overall planning dynamic priority function to perform DVS until the slack is exhausted and an optimum voltage setting is obtained. For a high-load task set, SNOPS manages to recover battery overload while maintaining schedulability. For random variable-load task sets, SNOPS achieves a saving of 29.51% battery capacity on average, the suboptimal gap is 27.84% narrower than that of our previously proposed OPS-based algorithm, and 92.10% narrower than that of the algorithm proposed by Chowdhury et al. Results indicate that OPS n manages to save battery to various extents while maintaining schedulability, and demonstrates good load compatibility and close-to-optimal performance on average.

Energy Efficient Block-Partitioned Multicore Processors for Parallel Applications

Due to the increasing power consumption in modern computing systems, energy management has become an important research area in the last decade. Recently, multicore has emerged to be an energy efficient architecture that exploits parallelisms in modern applications. However, as the number of cores on a single chip continues to increase, it has been a grand challenge on how to effectively manage the energy efficiency of multicore-based systems. In this paper, based on the voltage island and dynamic voltage and frequency scaling （DVFS） techniques, we investigate the energy efficiency of block-partitioned multieore processors, where cores are grouped into blocks with the cores on one block sharing a DVFS- enabled power supply. Depending on the number of cores on each block, we study both symmetric and asymmetric block configurations. We develop a system-level power model （which can support various power management techniques） and derive both block- and system-wide energy-efficient frequencies for systems with block-partitioned multieore processors. Based on the power model, we prove that, for embarrassingly parallel applications, having all cores on a single block can achieve the same energy savings as that of the individual block configuration （where each core forms a single block and has its own power supply）. However, for applications with limited degrees of parallelism, we show the superiority of the buddy-asymmetric block configuration, where the number of required blocks （and power supplies） is logarithmically related to the number of cores on the chip, in that it can achieve the same amount of energy savings as that of the individual block configuration. The energy efficiency of different block configurations is further evaluated through extensive simulations with both synthetic as well as a real life application.

Probabilistic Delay Fault Model for DVFS Circuits

Decreasing the power supply voltage in dynamic voltage frequency scaling to save power con- sumption may introduce extra delays in CMOS circuits, which may cause errors. This paper presents the probabilistic delay fault model （PDFM）, which describes the probability of an error occurring as a function of the power supply voltage and the clock period in synchronous CMOS circuits. In a wide range of applica- tions （graphic, video, digital filtering, etc.）, errors occurring with low probability and not remaining for a long time are acceptable. For combinational circuits which have long critical paths with low probability of excita- tion, a performance increase is achieved with a certain rate of errors determined by the PDFM compared with the traditional design which considers the worst case. The PDFM applied to array multipliers and ripple carry adders shows the agreement of the predicted probabilities with simulated delay histograms to support the practicality of using the PDFM to select power supply voltage and clock period in dynamic voltage fre- quency scaling circuits with tolerable error rates.