Scheduling strategies for time-sensitive distributed applications on edge computing

Master Thesis Scheduling strategies for time-sensitive distributed applications on edge computing Author: Eudald Sabaté Creixell Supervisors: Dr. Eduardo Quiñones Dr. María A. Serrano Tutor: Dr. Miquel Moretó A thesis submitted in fulllment of the requirements for the Master in Innovation and Research in Informatics, Computer Networks and Distributed Systems specialization in the Facultat d'Informàtica de Barcelona (FIB) at Universitat Politècnica de Catalunya (UPC) - BarcelonaTech June 22, 2020 Declaration of Authorship I, Eudald Sabaté Creixell, declare that this thesis titled, Scheduling strategies for time-sensitive distributed applications on edge computing and the work presented in it are my own. I conrm that: • This work was done wholly or mainly while in candidature for a master degree at the Universitat Politècnica de Catalunya (UPC) - BarcelonaTech. • Where any part of this thesis has previously been submitted for a degree or any other qualication at Universitat Politècnica de Catalunya (UPC) - BarcelonaTech or any other institution, this has been clearly stated. • Where I have consulted the published work of others, this is always clearly attributed. • Where I have quoted from the work of others, the source is always given. With the exception of such quotations, this thesis is entirely my own work. • I have acknowledged all main sources of help. • Where the thesis is based on work done by myself jointly with others, I have made clear exactly what was done by others and what I have contributed myself. Signed: Date: i Universitat Politècnica de Catalunya (UPC) - BarcelonaTech Abstract Edge computing is a distributed computing paradigm that shifts the computation capabilities close to the data sources. This new paradigm, coupled with the use of parallel embedded processor architectures, is becoming a very promising solution for time-sensitive distributed applications used in Internet of Things and large Cyber-Physical Systems (e.g., those used in smart cities) to alleviate the pressure on centralized solutions. However, the distribution and heterogeneity nature of the edge computing complicates the response-time analysis on these type of applications. This thesis addresses this challenge by proposing a new Directed Acyclic Graph (DAG)-task based system model to characterize: (1) the distribution nature of applications executed on the edge; and (2) the heterogeneous computation and network communication capabilities of edge computing platforms. Based on this system model, this work presents ve dierent scheduling strategies: four sub-optimal but tractable heuristics and an optimal but costly approach based on a mixed integer linear programming (MILP), that minimize the overall response time of distributed time-sensitive applications. To address both issues, and as a proof of concept, we use COMPSs, a framework composed of a task-based programming model and a runtime used to program and eciently distribute time-sensitive applications across the compute continuum. However, COMPSs is agnostic of time-sensitive applications, hence in this work we extend it to consider the dynamic scheduling based on the proposed scheduling strategies. Our results show that our scheduling heuristics outperform current scheduling solutions, while providing an average and upper-bound execution time comparable to the optimal one provided by the MILP allocation approach. ii Acknowledgements First of all, I want to deeply thank my advisors María and Eduardo for their support, guidance and mentoring through the development of this thesis. I want to specially thank them for providing me with the opportunity to participate in two European Projects, CLASS and ELASTIC. I also want to thank the rest of the people of the PPC group at BSC who always oered help whenever I needed. Furthermore, I would like to acknowledge BSC for nancially supporting my master studies. Last but not least, I would like to thank my friends and family for their support during my studies. I specially want to thank my mother, my brother and my father for all the help and unconditional support in the more critical moments throughout my life. iii Contents Declaration of Authorship i Acknowledgements iii Contents iv List of Figures vii List of Tables viii 1 Introduction 1 1.1 Motivation .................................. 1 1.2 Contributions ................................ 2 1.3 Publications and Impact .......................... 3 1.4 Structure of the Thesis ........................... 3 2 State of the Art 5 2.1 Timing Guarantees for Time-Sensitive Applications ........... 5 2.1.1 Timing Analysis .......................... 6 2.1.2 Shared-Memory Parallel Programming .............. 6 2.1.3 Example ............................... 8 2.2 Distributed Systems ............................ 8 2.3 Edge Computing .............................. 10 3 Background: the COMPSs Framework 11 3.1 Overview .................................. 11 3.2 Task-based Programming Model ..................... 12 3.3 Runtime System: DAG and Task Scheduler ............... 13 3.4 Advancing the Scheduling Capabilities of COMPSs ........... 15 iv 4 System Model 17 4.1 The Digraph Compute Continuum Model ................ 17 4.2 The DAG Task Model ........................... 18 4.3 Network Communications ......................... 19 4.4 Redening Volume and Workload Concepts ............... 19 4.5 Putting it all Together: a Real Example ................. 21 5 Task Scheduling Strategies 23 5.1 MILP-based Optimal Task Scheduling .................. 23 5.2 Task Scheduling Heuristics ......................... 26 5.2.1 Heuristics Based on Successors .................. 27 5.2.2 Heuristics Based on Processing Time ............... 29 5.3 Benets of Static Task Scheduling Strategies in Distributed Environments 30 5.4 Tasks Deadlines ............................... 31 5.5 Example ................................... 31 6 A New Scheduling Component for COMPSs 33 6.1 Analysis Phase ............................... 33 6.1.1 Example ............................... 37 6.2 Scheduling Strategies Implemented in COMPSs ............. 37 6.2.1 MILP-based Optimal Task Scheduling .............. 37 6.2.2 Task Scheduling Heuristics .................... 39 6.3 Task Monitoring .............................. 40 6.4 A Reactive Scheduler ............................ 41 7 Evaluation 42 7.1 Experimental Setup ............................ 42 7.1.1 Compute Continuum Conguration ................ 42 7.1.2 Applications ............................. 43 7.2 Performance and Accuracy ......................... 44 7.2.1 Classical Applications ....................... 44 7.2.2 Object Detection and Tracking .................. 46 7.3 Reactive Scheduling: Static Allocation in Dynamic Environments . . . 48 v 7.4 MILP Complexity ............................. 49 8 Conclusions and Future Work 50 Bibliography 52 vi List of Figures 2.1 Time-sensitive DAG task example. Nodes are labeled with their corresponding WCET. .............................. 8 2.2 Scheduling of DAG from Figure 2.1 scheduled in a 3-core system. . . . 8 3.1 Object detection and tracking (ODT) COMPSs example. ........ 12 3.2 DAG representing the application of Figure 3.1. ............. 14 4.1 Compute Continuum model example and values. ............ 21 4.2 DAG task model values of the DAG in Figure 3.2. ........... 22 5.1 MILP task scheduling for the ODT application in 3.1. ......... 31 5.2 LPT task scheduling for the ODT application in 3.1. .......... 32 6.1 iPerf output for Bandwidth retrieval of Ethernet IEEE 802.3. . . . . . 34 6.2 dot le for the DAG of the ODT application in 3.2. ........... 36 6.3 prv le for retrieving the tasks execution times. ............. 37 6.4 Logging le extract to retrieve the payload size produced by task 1 from 4.2. ...................................... 37 6.5 Input le generated by the proling mechanism for ODT application. . 38 6.6 MILP output for the ODT application input in 6.5. ........... 39 7.1 Boxplot of the execution time of each COMPSs applications under different scheduling strategies (Ethernet). .................. 45 7.2 Object detection and tracking COMPSs application. .......... 47 7.3 Execution time (multiple iterations) and Rub of the object detection and tracking, in a dynamic compute continuum environment (from 4 to 3 computing resources). ......................... 48 vii List of Tables 7.1 Number of nodes N , and communication and computation volumes, volcomm and volcomp , for each application. ................ 48 7.2 MILP and best scheduling heuristic execution times in seconds. . . . . 49 viii Chapter 2. State of the Art parallel programming, which allows to eectively process vast amounts of data simultaneously. OpenMP [21] and NVIDIA CUDA [22] parallel programming models used to program real-time devices have demonstrated that can provide real-time guarantees on the nal resources [7,8,5,23,6]. However, the use of parallel programming models increases the complexity of the timing analysis and schedulability of time-sensitive applications executed in real-time systems due to the fact that the tasks of the application are executed on heterogeneous systems, providing dierent WCET for the same task based on where it is executed [5,23]. Moreover, unless parallel programming is not managed carefully, it can also introduce overhead, thus aecting the nal real-time performance [24]. The DAG task model was introduced with the appearance of shared memory processors and multi-core processors under dierent scheduling algorithms [11,25,26] to better express the parallelism oered by these architectures, thus allowing a further exploitation of parallelism within workows. The use of DAGs has also enabled multicore processors to schedule periodic parallel tasks with implicit deadlines [11]. Recently with the introduction of heterogeneous architectures due to the increasing demands of modern cyber-physical embedded systems, it is a common trend to combine high-performance multi-core CPU hosts with a certain number of applicationspecic accelerators. The DAG model evolved as it needed to take into account different implementations of each task on heterogeneous platforms [27]. Furthermore, the use of the DAG model allowed to improve the impact of the response time upperbound by ooading computation to those accelerators, providing a more accurate response time upper-bound [28]. As systems evolved from single-core to multi-core, and in time to heterogeneous and distributed real-time systems, the DAG task model becomes more complex due to the fact that distributed systems are heterogeneous by nature, and so, the WCET annotated for each node is transformed into a WCET for each implementation of that node in each device that is able to execute it. Regarding the edges composing the DAG, they need to provide information on the amount of data exchanged between nodes (or tasks), as in distributed systems there exists the need to characterize the data transfers and communication between the underlying devices composing them. 7 Chapter 2. State of the Art Figure 2.1: Time-sensitive DAG task example. Nodes are labeled with their corresponding WCET. Figure 2.2: Scheduling of DAG from Figure 2.1 scheduled in a 3-core system. 2.1.3 Example Figure 2.1 depicts an example of a DAG characterizing a parallel time-sensitive application, composed by 9 tasks each labeled with their corresponding WCET, and 12 edges representing the precedence constraints among them. Considering a real-time multi-core system of three cores, we schedule the DAG from Figure 2.1, thus obtaining the scheduling shown in Figure 2.2. 2.2 Distributed Systems In the context of smart cities and industrial automation, a vast amount of Internet of Things (IoT) and Cyber-Physical Systems (CPS) devices with real-time requirements for the time-sensitive applications are needed which need to be distributed in order to cover the maximum amount of area. These distributed systems are heterogeneous by nature due to the fact that are composed by an immense amount of dierent devices 8 Chapter 2. State of the Art and hence challenging any centralized solution, hence also providing reliability to avoid system failures. Moreover, the vast amount of geographically-distributed data collected by the dierent devices needs to be processed in a distributed manner [29] in order to improve the eciency in the data analytics process and to achieve their timing requirements. Apache Spark [30], a cluster computing framework for real-time large-scale data processing, has been widely considered as it provides an ecient solution to parallelize and distribute the computation of Big Data analytics among the distributed system [29,31]. However, real-time distributed systems introduce a new challenge: deadline assignment . This problem refers to the process of assigning local deadlines to each of the real-time tasks composing a distributed application, with the objective of being able to meet a global end-to-end deadline, which is tightly related with the QoS assigned to the time-sensitive distributed applications. Deadline assignment became a challenge due to the fact that an increasing number of workows are concurrently running on a distributed system even though several algorithms to approach the deadline assignment problem have been presented [18,19,32]. Vehicular systems and automotive systems are also an example of heterogeneous distributed real-time systems. In these scenarios, the scheduling not only of real-time tasks composing the distributed application is critical, but also the communications that take place between the devices composing the distributed system should be taken into account [33]. In order to model those systems and to provide an optimal scheduling, integer linear programming (ILP) is widely considered [34]. ILP formulations allow to solve the allocation problems of parallel and distributed functions providing an optimal but costly solution, while it can also be tuned in order to assign deadlines and activation times to tasks such that tasks partitioned onto dierent virtual processors can be analyzed separately [35]. Even though ILP provides the optimal solution, it comes as a high processing cost in terms of time. Hence, much literature exists regarding heuristic approaches and scheduling algorithms that provide task allocation and scheduling [36,37,38]. From the High-Performance Computing (HPC) domain, task based schedulers have been widely proposed for distributed environments. The representation of the 9 Chapter 2. State of the Art workow as a DAG, coupled together with scheduling algorithms that benet from the information provided by the DAG itself, allow to improve the performance of distributed systems [39,40]. 2.3 Edge Computing Edge computing [1] is a new distributed computing paradigm that shifts the computation as close as possible to where the data is originated, allowing to manage the increasing number of data sources and alleviating the pressure on centralized solutions, which makes him a perfect candidate for contexts such as the smart cities and industrial automation. Moreover, the use of powerful parallel embedded processor architectures at the edge side (e.g., NVIDIA Jetson AGX [2], Xilinx Versal [3], Kalray MPPA [4]) can also help alleviating this pressure due to their huge computing capabilities, while providing lower network costs and more energy ecient solutions. However, the challenges from distributed systems described in Section 2.2 also apply in edge computing. Furthermore, the compute continuum composed by heterogeneous devices increases the complexity of both the development and deployment of the time-sensitive applications. This also complicates the response time analysis of such applications as network connections need to be considered [36,37,38]. 10 Chapter 3 Background: the COMPSs Framework This chapter presents background information on task-based programming models and DAG representation. In particular, we present COMPSs [9,10,41], a task-based programming model and runtime framework, used in the high-performance computing (HPC) domain for the development of parallel applications and their execution over distributed infrastructures, such as clusters, clouds and containerized platforms. In this work, without loss of generality, COMPSs has been selected and adapted for the implementation and performance evaluation of the proposed scheduling techniques for time-sensitive distributed applications over edge computing platforms. However, it should be stressed that the proposed solutions are not limited to the COMPSs environment, but can be generally tested with any suitable task-based programming model. 3.1 Overview The main objective of the COMPSs framework is to facilitate the parallelization and execution of sequential source codes (written in C/C++, Python or Java) in distributed computing environments. The application is agnostic of the underlying distributed infrastructure, i.e., they do not include any detail that could tie them to a particular platform, boosting portability among diverse infrastructures. Clearly, this is a very convenient property in heterogeneous environments such as the edge computing paradigm. 11 Chapter 3. Background: the COMPSs Framework 1 @task ( returns = numpy. ndarray ) 2 def get_frame () : 3 return get_next_frame_from_video () 5 @task (frame = IN , returns = list ) 6 def get_objects_from_frame(frame) : 7 return yolo . detect ( frame ) 9 @task (list_objects = IN , returns = list ) 10 def tracker ( list_objects ) : 11 return tracker . track ( list_objects ) 13 @task (list_objects = IN , frame = IN ) 14 def collect_and_display ( list_objects , frame): 15 for obj in list_objects: 16 display ( obj , frame ) 18 ### Main function ### 19 while ( true ) : 20 frame = get_frame () 21 list_obj= get_objects_from_frame ( frame ) 22 for i in range (0 , 2) : 23 list_obj [ i ] = tracker (list_obj) 24 collect_and_display ( list_obj , frame ) Figure 3.1: Object detection and tracking (ODT) COMPSs example. The COMPSs framework is composed of a task-based programming model which aims to ease the development of parallel applications, and a runtime system that exploits the inherent parallelism of applications, dened in the following sections. 3.2 Task-based Programming Model The COMPSs programmer is responsible of identifying the portions of code, named COMPSs tasks, that can be distributed, by simply annotating the sequential source code. Data dependencies and their directionality (i.e.,in, out or inout) must be also identied. Upon them, the runtime determines the order in which COMPSs tasks are executed and also the data transfers across the distributed system. A COMPSs task with an in or inout data dependency cannot start its execution until the COMPSs task with an out or inout dependency over the same data element is completed. Figure 3.1 shows an example of a COMPSs application for object detection and tracking (ODT) written in Python (PyCOMPSs [41]). COMPSs tasks are identied with a standard Python decorator @task , at lines 1, 4, 7, and 10. The returns argument species the data type of the value returned by the function (if any). The 12 Chapter 3. Background: the COMPSs Framework IN denes the input data directionality of parameters. The main code starts at line 15, where a loop iterates while detecting and tracking objects from an input video, e.g., from a street camera of the city. Each iteration operates over a video frame, rst getting it using the COMPSs task at line 1. Then, the object detection is computed using YOLO [42], a well-know real-time object detection system (COMPSs task at line 4). At line 18, the application processes in parallel dierent detected objects to track them (COMPSs task at line 7). Finally, the updated list of tracked objects, list_obj , is merged and objects detected and tracked are displayed at line 20 (COMPSs task at line 10). 3.3 Runtime System: DAG and Task Scheduler The available computing resources composing the compute continuum are identied in the XML conguration les resources.xml and project.xml by the COMPSs programmer. Each computing resource represents a COMPSs worker, which is the runtime entity in charge of executing the COMPSs tasks. The resources.xml le serves as a list of all congured and available workers in the environment, whereas the project.xml represents the subset of resources to be used for one specic application. COMPSs is based on the master-workers paradigm, in which the COMPSs master is the component in charge of executing the main code of the application through means of the runcompss command line interface. Moreover, it is also the component in charge of detecting the COMPSs tasks at runtime, scheduling and spawning them asynchronously to the dened set of distributed and interconnected computing resources that execute them in parallel (as soon as all its data dependencies are honored). The data elements marked as in and inout are transferred to the compute resource in which the task will execute. This data transfers are identied in the COMPSs framework by tags, which represent the dierent input/output parameters that tasks either receive or produce, respectively. These tags allow to avoid unnecessary transfers if the aforementioned parameters are already available in a particular worker, that is, if the parameter has been previously transferred due to another task executed in the same worker requesting the same parameter. The tags representing the dierent transfers are updated accordingly in case the task updates the value 13 Chapter 3. Background: the COMPSs Framework 𝑣2𝑣4 𝑣3 𝑣5 𝑣6 𝑣1 get _ frame() get _ objects _ from _ frame() tracker() collect _ and _ display() Figure 3.2: DAG representing the application of Figure 3.1. of the parameters received, thus facilitating the master to manage whenever a given worker already contains the transfer required by the task it will execute. The task-based programming model of COMPSs is supported by its runtime system, which manages several aspects of the application execution. For this, the runtime maintains the internal representation of the parallelism of the COMPSs application as a DAG. Each node corresponds to a COMPSs task and edges represent data dependencies. As an example, Figure 3.2 shows the DAG representation of one iteration of the COMPSs workow presented in Figure 3.1. Each instantiated COMPSs task is represented by a dierent node, with colors identifying the dierent task functionalities. Based on this DAG, the runtime can automatically detect data dependencies between COMPSs tasks. As soon as a task becomes ready, the COMPSs scheduler is then in charge of ooading its execution onto one of the available computing resources and transferring the input parameters before starting the execution. Concretely, upon receiving a dependency-free task, denoted as a ready task , the COMPSs task scheduler selects a resource to host its execution taking into account several parameters: (1) capabilities and status of the set of available resources, and (2) constraints of the invoked task. Algorithm 1shows a simple overview of the COMPSs scheduler to distribute and execute tasks. The way COMPSs tasks and resources to allocate them are selected, by functions Get_Ready_Task and Get_Resource , respectively, determine the dierent scheduling strategies that can be implemented. When an available resource is selected, the input parameters are transferred if the worker selected has not received them yet ( Transfer_Data ) and the task can initiate the execution ( Execute_Task ). Note that the data transfer between dependent COMPSs tasks does not start until the descendant one is scheduled and assigned to a computing resource to host its execution, 14 Chapter 3. Background: the COMPSs Framework Algorithm 1 Pseudo code of a distributed tasks scheduler. 1: function schedule_tasks 2: while Not_Empty( ready _ queue ) do 3: task ← Get_Ready_Task( ready _ queue ) 4: resource ← Get_Resource() 5: Transfer_Data( task, resource ) 6: Execute_Task( task, resource ) 7: end while 8: end function thus limiting the overlapping of communication with computation. COMPSs already provides dierent schedulers to be used based on the family of schedulers that consider only ready tasks: • First In, First Out (FIFO): a very simple scheduler that selects ready tasks based on the order of entrance in the ready queue, that is, a task that rst is the one with the highest priority. • Last In, First Out (LIFO): scheduler that selects ready tasks based on order of arrival, however the last task entering in the ready queue is the one with highest priority. Both schedulers select the next task to execute on the Get_Ready_Task( ready _ queue ) method based on the priority given by the order of entrance to the ready tasks, as explained above. Furthermore, both schedulers use the First Idle approach to select the resource to host the execution of the previously selected tasks in Get_Resource() , which selects the rst available computing resource. 3.4 Advancing the Scheduling Capabilities of COMPSs Despite the expressiveness of the task-based programming model to develop distributed applications, and the capabilities of the runtime to be independent of the available infrastructure, COMPSs is agnostic of time-sensitive applications as it does not take further advantage of the DAG constructed neither includes relevant information required in order to provide an upper-bound response time of the applications being executed. We enhance the scheduling capabilities of COMPSs to eectively address this issue by providing new scheduling algorithms in COMPSs (see Chapter 6) based on 15 Chapter 3. Background: the COMPSs Framework the system model (see Chapter 4) and the scheduling strategies proposed in this thesis (see Chapter 5). 16 Chapter 5 Task Scheduling Strategies In this chapter we present our ve dierent scheduling strategies based on the system model presented in Chapter 4: an optimal scheduling strategy based on mixed integer linear programming (MILP), and four novel tasks scheduling heuristics. The proposed scheduling strategies handle the computation and communication factors of a distributed application G= (V, E) executed on a compute continuum Gcc = (Vcc, Ecc) , with the objective of minimizing the overall end-to-end response time. On one hand, the MILP-based strategy optimizes the allocation of nodes vi∈V to those edge computing resources pk∈Vcc in which the execution time upper bound Ci,k and the data transfers time Ttransf i,j among resources are minimized. On the other hand, the heuristics prioritize the selection of nodes and resources with a similar objective, but making local decisions to speed up the scheduling process. 5.1 MILP-based Optimal Task Scheduling Given a time-sensitive distributed application G= (V, E) , and a set of interconnected edge computing nodes Gcc = (Vcc, Ecc) , the objective function of the MILP is to minimize the time interval between the starting time of the source node vsource ∈E and the completion time of the sink node vsink ∈E . Input parameters. The input parameters considered in the MILP are the following: 1. succi,j ∈(0,1),1≤i≤N, 1≤j≤N , a binary variable representing the edges in E . It equals to 1 if (vi, vj)∈E , 0 otherwise. 23 Chapter 5. Task Scheduling Strategies 2. zi,j ∈R, zi,j ≥0,1≤i≤N, 1≤j≤N , the data transfer size of edges (vi, vj)∈E . 3. zidi,j are strings, 1≤i≤N, 1≤j≤N , representing the data transfer identiers of edges (vi, vj)∈E . 4. source , the index of vsource ∈V . 5. sink , the index of vsink ∈V . 6. ibwk,l =1 bwk,l ,1≤k≤M, 1≤l≤M , the inverse of the transport bandwidth bwk,l of the communication link (pk, pl)∈Ecc . Notice that, ibwk,k = 0,∀bwk,k = ∞ , and ibwk,l =−1 if bwk,l =−1 . 7. mfs ∈R , the maximum frame size 1 . 8. h∈R , the size of the headers 2 . 9. Ci,k ∈R,1≤i≤N, 1≤k≤M , the execution time upper bound of vi∈V when executing in the edge computing resource pk∈Vcc ; Ci,k =−1 if vi cannot execute in pk . Problem variables. The decision variables considered in the MILP are: 1. Yi,k ∈(0,1),∀vi∈V, ∀pk∈Vcc , a binary variable to represent the optimal allocation function . It equals to 1 if task vi executes on pk , 0 otherwise (see Section 4.4). 2. ti∈R, ti≥0,∀vi∈V , the starting time of vi . 3. ai,j ∈(0,1),∀vi, vj∈V , an auxiliary binary variable that equals 1 if vi is executed before vj , 0 otherwise. 4. dupi,j ∈(0,1),∀vi, vj∈V , a binary variable that is used to represent whether a transfer for a specic parameter has to be done or not. It equals to 1 if there exists a task vj executed in the same resource as vk∈V such that succi,j == succi,k == 1 and both vj and vk receive the same output parameter from vi , and tj≤tk , 0 otherwise. 1 Given the time complexity of MILP, when dierent communication technologies are involved, the worst case is considered, i.e., mfs =min(mfsk,l),∀(pk, pl)∈Ecc . 2 Similarly to mfs , we consider h=max(hk,l),∀(pk, pl)∈Ecc . 24 Chapter 5. Task Scheduling Strategies Initial assumption. vsource starts the execution at time instant 0: tsource = 0 . Constrains. The constrains are the following ones: 1. Each task vi∈V can be executed only by a single computing resource pk∈Vcc : M X k=1 Yi,k = 1,∀vi∈V 2. Each task vi∈V can execute in a computing resource pk∈Vcc if there exists implementation, i.e., if Ci,k 6=−1 : M X k=1 Ci,k ·Yi,k ≥0,∀vi∈V 3. The starting time of a successor task vj∈V is greater or equal than the completion time of all its predecessor tasks vi∈V plus the corresponding data transfer time given by Ttransf i,j (see Equation 4.1) 3 : succi,j ·ti+M X k=1 Ci,k ·Yi,k+ +lzi,j mfsm·h+zi,j· M X k=1 M X l=1 ibwk,l ·Yi,k ·Yj,l≤tj,∀vi∈V, ∀vj∈V 4. The execution of tasks within the same computing resource cannot overlap, i.e., if two tasks vi and vj are executed in pk∈Vcc then, either vi nishes before the vj starts, or vice versa: Yi,k = 1 ∧Yj,k = 1 ⇒(ti+Ci,k ≤tj∨tj+Cj,k ≤ti),∀vi∈V, ∀vj∈V, ∀pk∈Vcc 5. Two dependent tasks (vi, vj)∈E ( succi,j = 1 ) cannot be allocated in computing resources pk and pl , respectively, if they are not connected (i.e., if ibwk,l =−1 ): succi,j ·Yi,k ·Yj,l ·ibwk, l ≥0,∀vi∈V, ∀vj∈V, ∀pk∈Vcc,∀pl∈Vcc 3 Notice that the inverse of the bandwidth ( ibwk,l ) is used because the MILP implementations does not support dividing by a decision variable (i.e., Yi,k and Yj,l ). 25 Chapter 5. Task Scheduling Strategies 6. For each task vi that only has one direct descendant vj such that (vi, vj)∈E ( succi,j = 1 ) and the data transfer identier is not null ( zidi,j ! = ”0” ), the data transfer needs to be accounted: dupi,j == 1 if N X k=1 (zidi,k! = ”0”) == 1,∀vi∈V, ∀vj∈V 7. Given three tasks vi, vj and vl such that (vi, vj)∈E ( succi,j = 1 ) and (vi, vk)∈ E ( succi,l = 1 ), that both vj and vl receive the same input parameter from vi identied by the same non-null tag ( zidi,j =zidi,l ) and both tasks are executed by the same computing resource pk∈Vcc , the data transfer has to be accounted only the rst time this transfer takes place: dupi,j ≤2−Yj,k ·Yl,k −(tj≥tl), dupi,k ≥Yj,k ·Yl,k + (tj≥tl)−1 Constrains (4) and (7) include the quadratic function of a decision variable, making the problem non linear, and constrain (5) includes logical functions and and or , to facilitate the explanation. Well know techniques are applied to linearize these constrains [45,46]. Objective function. The objective function aims to minimize the execution time upper bound of the distributed application. It is equivalent to minimize the starting time plus execution time upper bound of vsink . The MILP objective function also represents a valid response time upper bound of the real-time distributed workow: Rub =min tsink + M X k=1 Csink,k ·Ysink,k (5.1) 5.2 Task Scheduling Heuristics Given the time complexity of the MILP strategy (see Section 7), we propose four heuristics that have been inspired on existing approaches aiming to minimize the endto-end response time of parallel applications for shared memory processor architectures 26 Chapter 5. Task Scheduling Strategies [8,47,48]. The four proposed schemes take into account two sets of priority rules, described in the following two subsections. 5.2.1 Heuristics Based on Successors In the rst two proposed heuristics, the internal structure of the DAG G prioritizes the next ready task to be allocated. A task vi∈V is ready if all its direct predecessor nodes vj∈V: (vj, vi)∈E have been completed. • Largest Number of Successors in Next Level (LNSNL). This heuristic selects the task vi with the largest number of direct successors, with the objective of increasing the number of nodes that become ready when vi completes. • Largest Number of Successors (LNS). This heuristic selects the task vi with the largest number of successors, with the objective of prioritizing the execution of those portions of the DAG with the highest number of nodes, and so potentially, the largest impact on the execution time of the application. Once vi is selected, the LNSNL and the LNS approaches apply a Best Fit (BF) strategy to select the computing resource pk∈Vcc where the completion time of vi is minimized. The completion time is computed considering (1) the start time of vi , that depends on the last idle time of each pk and the transfer times Ttransf j,i ,∀(vj, vi)∈E , and (2) the execution time Ci,k on each computing resource pk . Algorithm 2presents the pseudo source-code of the LNSNL and LNS scheduling heuristics. The input parameters are the distributed application G and the compute continuum Gcc models (line 1). The algorithm starts by initializing M , as the number of available computing resources, and N , as the number of tasks. The ready queue Q is initialized with the source node vsource of G (line 3) and the set of allocated tasks A is initialized to empty (line 4). An array L of size M , initialized to 0 , is used to store the last idle time of each resource (line 5). For each node in G , the number of successors that each heuristic will consider is computed (line 6): in case of LNS , all (recursive) successors of each task are accounted, whereas in case of LNSNL , only the direct successors are considered. A loop iterates (between lines 7-25) until all nodes in G have been allocated. At each iteration, a new ready task vi∈Q is selected ( nextNode ) based on the maximum 27 Chapter 5. Task Scheduling Strategies Algorithm 2 LNS/LNSNL task scheduling heuristic 1: procedure LNS_LNSNL ( G= (V, E), Gcc = (Vcc, Ecc) ) 2: M← |Vcc| ; N← |V| 3: Q← {vsource} // Ready Queue 4: A← ∅ // Set of pairs (task, computing resource) 5: L[ ] ← ARRAY (M, 0) // Last idle time of each computing resource 6: nSucc[ ] ← ComputeSuccessors (E) 7: while ∼ Empty (Q) do 8: maxSucc ←0 9: for each vi∈Q do // Selects a ready task 10: if nSucc[i]≥maxSucc then 11: nextNode ←vi 12: maxSucc ←nSucc[i] 13: end if 14: end for 15: minCT ← ∞ 16: for each pk∈Vcc do // Selects computing resource 17: time ← CompletionTime (G, nextNode, Gcc, pk, L) 18: if minCT > time then 19: minCT =time 20: bestRes =pk 21: end if 22: end for 23: L[bestRes]←minCT + 1 24: Q← UpdateReadyQueue (Q, A, G, nextNode) 25: A←A∪ {(nextNode, bestRes)} 26: end while 27: Rub = maxM k=1 L[pk] 28: return Rub , A 29: end procedure number of successors criterion (lines 9-14), which determines the priority rule that distinguishes LNS and LNSNL. The selected node is then allocated to the resource pk∈Vcc that minimizes its completion time, named bestRes (lines 15-22). The completion time is computed by the procedure CompletionTime considering the last idle time of each resource L , the task execution times Ci,k on each resource, and the transfer times Ttrans j,i of the data required from nextNode predecessors. However, Ttrans j,i = 0 in the case in which the identier of the transfer zidi,j has already been used in the same computing resource pk due to a prior task also requesting it, and hence, it will already be present. Once nextNode has been allocated to the resource bestRes , the last idle time of that resource L[bestRes] is updated (line 23). The procedure UpdateReadyQueue removes nextNode from the ready queue and inserts the successors without any pending predecessor (line 24). Moreover, the set of allocated tasks A is also updated (line 25). The response time upper bound Rub is computed by selecting the maximum of the idle times for each resource in L (line 27). 28 Chapter 5. Task Scheduling Strategies 5.2.2 Heuristics Based on Processing Time In the second set of heuristics, the minimum completion time of all ready tasks is rst computed. This pre-selects a computing resource pk∈Vcc to execute each ready task. Then, among all the ready tasks, the next task vi∈V to execute is selected based on: • Shortest Processing Time (SPT). It selects the task vi with the shortest completion time, i.e., prioritizing the smallest nodes (in terms of Ci,k ) in the fastest computing resources. • Longest Processing Time (LPT). It selects the task vi with the longest completion time, with the objective of prioritizing the biggest nodes in the fastest computing resources. Algorithm 3 SPT task scheduling heuristic 1: procedure SPT ( G= (V, E), Gcc = (Vcc, Ecc) ) 2: M← |Vcc| ; N← |V| ; Q← {vsource} ; A← ∅ ; L[ ] ← ARRAY (M, 0) 3: while ∼ Empty (Q) do 4: minCT ← ARRAY (|Q|,0) ; bestRes ← ARRAY (|Q|,0) 5: for each vi∈Q do // Selects a ready task 6: minCT [i]← ∞ 7: for each pk∈Vcc do 8: time ← CompletionTime (G, vi, Gcc, pk, L) 9: if minCT [i]> time then 10: minCT [i] = time ; bestRes[i] = pk 11: end if 12: end for 13: end for 14: nextNode = minvi∈QminCT [i] 15: L[bestRes[nextNode]] ←minCT [nextNode] + 1 16: Q← UpdateQueue (Q, A, G, nextNode) 17: A←A∪ {(nextNode, bestRes[nextNode])} 18: end while 19: Rub = maxM k=1 L[pk] 20: return Rub , A 21: end procedure Algorithm 3shows the pseudo source-code of the SPT scheduling heuristic. The line 2 is equivalent to Algorithm 2, and a loop (lines 3-18) similarly iterates until all nodes in G have been allocated. At each iteration, an inner loop iterates (lines 5-13) over the ready tasks vi∈Q , to compute the minimum completion time of vi on all the compute resources pk∈Vcc , and select the one that minimizes this time (loop between lines 7-12). Among all the ready tasks, the one with the minimum completion time, nextNode (line 14) is selected. Then, the last idle time of the computing resource bestRes[nextNode] where nextNode executes is updated (line 15). The ready queue 29 Chapter 5. Task Scheduling Strategies Q and the set of allocated tasks A are also updated accordingly (lines 16 and 17). Finally, Rub is computed (line 19). The LPT scheduling heuristic is equivalent to Algorithm 3, with the dierence that, instead of the minimum, the maximum of the minimum completion time of all ready tasks is considered (line 14). 5.3 Benets of Static Task Scheduling Strategies in Distributed Environments The main motivation of the proposed static task scheduling approaches is the ability to provide a response time upper bound for time-sensitive distributed applications. Interestingly, as we show in the evaluation chapter, the use of such strategies also benets the average application response time. Common dynamic scheduling strategies assign a task to a given computing resource as soon as the task becomes ready and the resource becomes idle. Only at this point in time the destination resource is known, and the data transfer of input data dependencies can be initiated. When the transfer is completed, the new scheduled task can start its execution. In the proposed static scheduling strategy instead, the data transfer can be initiated as soon as all the predecessor tasks complete, because the destination resource in which successor tasks execute is known a priori. As a result, the overlapping of computation and communication operations can be improved, so that the data input parameters of the new scheduled task are already available at the destination computing resource when the task becomes ready to execute. However, the use of static task scheduling strategies in dynamic environments, such as the edge computing one, may seem counter-intuitive. In edge computing environments, the setup may vary in terms of available computing resources and connectivity. As we explain in next subsection, the proposed heuristics allow to quickly react to changes in the compute continuum model, and re-allocate the time-sensitive distributed applications to the new compute continuum model. Section 7.3 presents a simple experiment that shows the ability of dynamically re-conguring the system. 30 Chapter 5. Task Scheduling Strategies (1) 711 (2) 160 (5) 189 (3) 186 (4) 176 (6) 97 0773 933 1406 Time 1110 1309 Figure 5.1: MILP task scheduling for the ODT application in 3.1. 5.4 Tasks Deadlines Deadlines can be assigned to tasks by using any of the ve scheduling approaches presented in Sections 5.1 and 5.2 and taking advantage of the provided end times (or start times) of the scheduling. These deadlines represent assigned points in time to each task upon which that particular task should have nished their execution. Apart from the deadlines assigned to the tasks composing the time-sensitive application, the deadline of the last task of the DAG, that is, the sink node can be used to represent the global end-to-end deadline, the Rub , used to improve the QoS of these applications. The deadlines can be further used to dene policies based on a certain threshold of deadlines misses, and upon the violation of this threshold a certain action is triggered as presented in section 6.3. 5.5 Example Taking the application described in 3.1, Figure 5.1 represents the actual scheduling obtained by the MILP-based optimal task scheduling considering the compute continuum setup and the DAG task model values described in Figures 4.1 and 4.2. The arrows in Figure 5.1 represent the data transfers between tasks, and each Y-axis represents the computing resources in the compute continuum. Note that from task v2 there is only one dashed arrow to task v3 , and not to any of the other descendants (neither v4 nor v5 ). That is because for v4 no transfer is needed due to the fact that it is executing on the same resource as v2 , whereas for task v5 no data 31 Chapter 5. Task Scheduling Strategies (1) 711 (2) 160 (6) 97 0773 933 1417 Time 1145 1319 (5) 189 (3) 211 (4) 196 Figure 5.2: LPT task scheduling for the ODT application in 3.1. transfer is needed as the same parameter has already been transferred for task v3 . The Rub obtained is represented by the last node to execute (namely the sink node), which in this case is 1406 milliseconds. Figure 5.2 displays the task scheduling provided by the LPT heuristic for the same application. However, if comparing the task scheduling obtained by the MILP with the one provided by the LPT it can be seen that the scheduling decisions of the latter for the three yellow tasks ( v3 , v4 and v5 ) is the inverse of the one provided by the MILP. This decision is the one causing that the start of the execution of task v6 is delayed, hence obtaining a dierent Rub for both allocations, with a dierence of 11 milliseconds more in the solution provided by LPT. Both the scheduling decisions and the response time upper bound Rub obtained for the rest of the scheduling strategies, that is LNS, LNSNL and SPT, are the same as the ones provided by the MILP in 5.1. Taking Figure 5.1 and 5.2 as examples for the deadlines assigned to tasks mentioned in Section 5.4, task 1 should nish its execution before the given end time assigned by the scheduling strategies, that is, 711 milliseconds after the workow's start. In the same sense, task 2 should nish its execution in both strategies as the deadline assigned to the task is 933 milliseconds, that is, its start time plus its execution time ( 773 + 160 = 993 ms ). 32 Chapter 6. A New Scheduling Component for COMPSs 1 Task 1 (C = 711.291) executes on computing resource 1 starting at 0 2 Task 2 (C = 160.243) executes on computing resource 2 starting at 773.610330388 3 Task 3 (C = 186.319) executes on computing resource 1 starting at 933.857976958 4 Task 4 (C = 176.137) executes on computing resource 2 starting at 933.856976958 5 Task 5 (C = 189.445) executes on computing resource 1 starting at 1120.176976958 6 Task 6 (C = 97.274) executes on computing resource 3 starting at 1309.700195905 Figure 6.6: MILP output for the ODT application input in 6.5. then parsed by another bash script and used in COMPSs to guide the allocation of tasks to resources. However, in this case, the dynamic re-conguration is not feasible due to the time complexity of the MILP (see Section 7.4). 6.2.2 Task Scheduling Heuristics A new scheduler has been developed, which is the component in COMPSs in charge of receiving and dealing with the actual COMPSs tasks by allocating them to the dierent resources in the compute continuum accordingly to the selected scheduling heuristic. This new scheduler is not related with the family of ready schedulers present in COMPSs, whose behavior is depicted in 1, thus not only scheduling ready tasks. runcompss already provides a ag that allows to choose among the dierent available schedulers, allowing to select the new scheduler by adding scheduler="es.bsc.compss.scheduler.HeuristicScheduler" . Moreover, this new scheduler component enhances the COMPSs runtime as it is able to anticipate (whenever possible) the data transfers of two dependent COMPSs tasks allocated in dierent computing resources. This is achieved by the creation of a new class, TransferValueAction , that advances the transfer of the data element belonging to a predecessor task to the computing resource selected to host the new task, whenever the predecessor nishes its execution, as described in Section 5.3. These heuristics require the input le presented in previous section with the information gathered in the proling of both the COMPSs application and the compute continuum in order to provide the sub-optimal scheduling. To do so, we have used the runcompss ag scheduler_cong_le that provides the path to the conguration le upon which the scheduler receives not only 39 Chapter 6. A New Scheduling Component for COMPSs the location of the input le, but also other information such as the heuristic scheduling strategy to use. Upon receiving the input le and the desired task scheduling strategy, the scheduler loads the content of the le and triggers the computation of the selected heuristic, which provides both a new task scheduling and the response time upper-bound Rub . Moreover, this scheduling allows to obtain the start and end times in between the tasks are supposed to execute, thus beneting the monitoring of deadlines of each task 6.3 Task Monitoring In a real-case scenario there are other situations which generates events that trigger the re-computation of the task scheduling, for example, missing a certain amount of deadlines assigned to tasks. However, COMPSs does not take into account the timings required to measure whether these assigned deadlines are met. In order to allow COMPSs to be aware of these times we have also enhanced the already implemented COMPSs Task Monitor . The Task Monitor includes methods that allow to gather at runtime the exact start and end execution times of a given task. Furthermore, it enables the enhanced scheduler to easily retrieve these timings given a specic task, thus allowing the scheduler to compare if the current times violate the assigned deadlines. This modications allow to enhance the execution model even more, specially in the case of the cloud in which scaling in (dynamically removing cloud resources) and scaling out (dynamically adding resources) can be performed based on the amount of these deadlines that are missed. For example, Prometheus [54], an open-source systems monitoring and alerting toolkit, is used to publish the amount of deadlines missed in a given COMPSs workow, which provides the cloud an easy retrieval of these metrics to decide whenever to trigger the scale in or scale out policies in order to guarantee a certain QoS. As new resources are dynamically added or removed, the scheduling needs to be re-adapted to take them into account, described in the next section. 40 Chapter 6. A New Scheduling Component for COMPSs 6.4 A Reactive Scheduler The procedure that has been described so far refers to a pure static scheduling mechanism. First of all, the application and the compute continuum setup are analyzed and modeled prior to the actual execution. Then, the scheduler receives this information to compute the actual task-to-resource allocation and applies it in the COMPSs execution. However, the compute continuum setup can be updated at runtime when new computing resources become up and running, or whenever a connection established between resources disappears. These events trigger a re-computation of the scheduling heuristic, which imposes a new response time upper bound Rub , and thus implying a new scheduling, based on the new compute continuum setup. The scheduler is informed through messages that contain the list of updated computing resources detected by another COMPSs component whenever there is a change in the resources in the compute continuum. Hence, the scheduler is able to react by updating the proling information at runtime based on the list of computing resources received, and re-schedules the workow considering these changes. In the case of removing a resource, the scheduler disables the information belonging to that one in particular, and hence it is not considered when the re-scheduling is applied. On the other hand, in the case of adding a resource the scheduler just enables the information so it is considered again by the scheduling heuristic. 41 Chapter 7 Evaluation In this chapter we evaluate the response time upper bound provided by the heuristics and the MILP formulation, and also the average and maximum observed execution times compared with the baseline COMPSs scheduling strategies. 7.1 Experimental Setup The ve proposed scheduling strategies considered in the evaluation are presented in Chapter 5and implemented in COMPSs as explained in Chapter 6, and the results are compared with the dynamic scheduling strategies presented in the pseudo code described in Algorithm 1. 7.1.1 Compute Continuum Conguration We considered four computing resources: a Raspberry Pi 3, featuring a 4-core ARMv7 Processor; a NVIDIA Jetson TX2 featuring a 4-core ARMv8 host processor and a NVIDIA Pascal GPU with 256 NVIDIA CUDA cores; a NVIDIA Jetson AGX Xavier featuring a 8-core ARMv8 host processor and a 512-Core Volta GPU; and a 4-core Intel(R) i7-4600U processor. We evaluate two dierent congurations for the communications: (1) all resources connected through Ethernet IEEE 802.3 (labeled as Ethernet ), and (2) the NVIDIA GPUs connected through Ethernet, and the Intel multi-core and Raspberry Pi through Wi IEEE 802.11ac (labeled as Hybrid Ethernet + Wi ). 42 Chapter 7. Evaluation 7.1.2 Applications For the evaluation of the proposed scheduling heuristics, seven well-known HPC applications are rst considered: 1. Matrix Multiplication (Matmul) (56 nodes), a simple application for matrix multiplication. 2. Cholesky Factorization (38 nodes), commonly used for ecient linear equation solvers, Monte Carlo simulations, or kalman lters acceleration (used in vehicle navigation systems to track pedestrians or bicyclists [55]), it processes a matrix of real oating-point numbers using low-level functions from the LAPACK library [56]. 3. QR Factorization (36 nodes), that decomposes a matrix into a product of an orthogonal and an upper triangular matrix. 4. Max Norm (13), a simple application that computes the maximum number in a list of 16000 elements. 5. Principal Component Analysis (PCA) (26 nodes), applicable in machine learning and data mining elds among others, to reduce the number of variables in a dataset. 6. Terasort (27 nodes), a popular application that sorts one terabyte of randomly distributed data by also using the MapReduce procedure. 7. Map/Reduce Matrix Multiplication (M/R Matmul) (22 nodes), a matrix multiplication that is computed by applying the MapReduce procedure. A real use case application for Object detection and tracking (ODT) , described in Figure 3.1, has also been considered. As input, a video of 2 minutes and 21 seconds of duration is used, with a total number of 150 frames. To increase complexity, we consider a DAG with 5 iterations (each processing a frame). All applications are executed 50 times to compute the average and the maximum observed execution times. The execution time upper bound of COMPSs tasks, Ci,k,∀vi∈V, ∀pk∈Vcc , is computed as the maximum observed time plus a 50% of 43 Chapter 7. Evaluation safety margin. This is a common industrial practice that relies on software proling reinforced by the use of safety margins [20]. Similarly, a 5% of safety margin is used for the data transfer times. With respect to the payload zi,j,∀(vi, vj)∈E , when it is not a xed value (e.g., if it depends on the number of detected objects), the maximum observed payload is used as a safe upper bound. 7.2 Performance and Accuracy This section presents the evaluation of the proposed scheduling strategies in terms of the observed execution times (average and maximum) and the response time upper bound. 7.2.1 Classical Applications Figure 7.1 shows the boxplots for the classical HPC applications on the compute continuum ( Ethernet conguration). It shows the distribution of the execution time for the proposed scheduling strategies ( MILP, LNSNL, LNS, LPT and SPT , and for the baseline COMPSs scheduler ( FIFO or LIFO ) that performs best in terms of average execution time. Moreover, the Rub provided by the scheduling strategies is also depicted. As shown, all the proposed strategies clearly outperform the baseline COMPSs schedulers in terms of best, average and maximum observed execution times. The reason is that the proposed algorithms improve scheduling by taking into account the timing information of the system model. Moreover, as seen in Section 5.3, they anticipate data transfers, enabling the overlap of computation and communication tasks. In terms of average execution time, MILP is 55% , 76% , 37% , 67% , 26% , 45% and 57% , faster than the baseline COMPSs scheduler for the Matrix Multiplication, Cholesky, QR, Max Norm, PCA, Terasort and MapReduce Matrix Multiplication applications, respectively. Similarly, the best heuristic for each application is faster by 54% (SPT), 75% (LNSNL), 37% (LNS), 62% (LNSNL), 24% (LNSNL), 40% (LPT) and 52% (SPT). Interestingly, due to the static nature of our solutions, the execution time variation of our scheduling strategies is much smaller than the baseline COMPSs schedulers, 44 Chapter 7. Evaluation Response time upper bound Rub (a) Matmul (b) Cholesky (c) QR Factorization (d) Max Norm (e) PCA (f) Terasort (g) M/R Matmul Figure 7.1: Boxplot of the execution time of each COMPSs applications under dierent scheduling strategies (Ethernet). resulting in a more stable execution. This trend is clearly observed for all the applications. If we now focus on the accuracy of the MILP solution and the scheduling heuristics, the Rub for the MILP is 31% , 53% , 34% , 45% , 11% , 45% and 36% higher than the maximum observed execution time for the dierent HPC applications, respectively. A similar trend is also observed in the best scheduling heuristics for each application, being 35% (SPT), 26% (LNSNL), 31% (LNS), 38% (LNSNL), 17% (LNSNL), 34% (LPT) and 24% (SPT) higher. This overestimation allows to safely provide timing guarantees to the applications. In all the cases, the dierence between Rub and the 45 Chapter 7. Evaluation maximum observed execution time is smaller when the variability of the execution time is higher; this is clearly observed if we compare the PCA (higher variability, smaller dierence) and the Cholesky (smaller variability, higher dierence). In terms of the Rub estimation, the MILP solution outperforms the scheduling heuristics. The Rub provided by the best heuristic for each application results in an increment of 4.33% (SPT), 6.84% (LNSNL), 1.74% (LNS), 8.78% (LNSNL), 6.38% (LNSNL), 0.97% (LPT), and 1.64% (SPT) compared to the Rub obtained by MILP. Notice that the MILP strategy does not provide the optimal result for the Matmul, Merge/Reduce Matmul, QR and Terasort applications due to time restrictions, while the heuristics provide a much faster solution (see discussion in Section 7.4). It is worth mentioning that no heuristic clearly outperforms the others, as the performance of each one depends on the application (e.g., the shape of the DAG or the execution time of all tasks). A clear example is shown for the SPT strategy, which is the best heuristic for the Matmul and M/R Matmul applications (and provides a similar Rub as the MILP) but the worst by far for QR and Cholesky. The reason is that in both the QR and the Cholesky applications a bad scheduling decision makes a very long task to execute while the rest of resources are idle because all the shortest tasks have been already executed, while in the rest of heuristics the long tasks are executed in parallel with other tasks. 7.2.2 Object Detection and Tracking Figure 7.2a shows the boxplots for the ODT application on the compute continuum (Ethernet conguration). Similar outcomes have been observed with respect to the classical HPC applications. Firstly, our task scheduling strategies clearly outperform the COMPSs baseline scheduler. In this case in which we have a more complex system, the dierences are even more evident. The best scheduling heuristic for this application is LNS. Considering average execution times, MILP and LNS are 80.8% and 76.3% faster than the LIFO COMPSs scheduler, respectively. This is extremely important when considering applications with timing requirements, e.g., in the situation of an alert when a pedestrian is detected. Furthermore, the execution time variation of our scheduling strategies is again much smaller than the one achieved with the COMPSs scheduler. The Rub of the LNS heuristic increments 10.8% w.r.t. to the MILP solution. 46 Chapter 7. Evaluation Figure 7.2b shows an interesting comparison when executing the application on the two dierent compute continuum setups, i.e., Ethernet and Hybrid Ethernet + Wi , for the LNS strategy. Even though the execution for the Hybrid setup outperforms the Ethernet setup (in terms of minimum observed and average execution times), the variability introduced when using Wi connections is much higher, leading to higher values for the maximum observed time. Overall, we conclude that the proposed scheduling strategies signicantly outperform the COMPSs baseline scheduling strategies. The scheduling heuristics provide comparable results to the ones obtained with the optimal but costly MILP approach. The selection of a heuristic depends on the actual setup of the system. Moreover, due to the static nature of our scheduling strategies, the execution time variability of distributed applications is signicantly reduced, resulting in a more stable execution that also allows a dynamic reconguration, as discussed in Section 7.3. (a) Ethernet compute continuum (b) LNS heuristic. Figure 7.2: Object detection and tracking COMPSs application. 47 Chapter 7. Evaluation Response time upper bound Rub COMPSs application execution time Figure 7.3: Execution time (multiple iterations) and Rub of the object detection and tracking, in a dynamic compute continuum environment (from 4 to 3 computing resources). 7.3 Reactive Scheduling: Static Allocation in Dynamic Environments As described in Section 5.3 and in Chapter 6, the proposed scheduling heuristics allow to quickly react to changes in the compute continuum model, appropriately reallocating the tasks and providing a new response-time upper bound. This is demonstrated in Figure 7.3, where the evolution of the execution time of 50 executions of the object detection and tracking application is depicted. During the rst 25 executions, the Ethernet compute continuum conguration described in Section 7.1.1 is considered. Then, we disconnect the Xavier GPUs, leaving only 3 available edge devices. This forces the re-scheduling of tasks and a new Rub is provided at the 26th execution. COMPSs MILP Best Heuristic App N volcomm volcomp volcomm volcomp MMul 56 6192.1182 10219.114 6539.6154 10219.114 Cho 38 1047.4992 3019.097 1222.0824 2930.571 QR 36 3102.5515 7210.551 4115.4598 12420.82 Max1 13 25.2588 1817.138 1.4789 2022.802 PCA 26 30.2914 3329.288 32.739 3413.293 Tera 26 3.0182 3899.114 3.4084 5617.271 M/RMul 22 1899.1662 3611.704 2115.0076 3724.256 ODT 32 3791.1277 4228.118 4751.2155 4469.456 Table 7.1: Number of nodes N , and communication and computation volumes, volcomm and volcomp , for each application. 48 BIBLIOGRAPHY [28] M. A. Serrano and E. Quiñones, Response-time analysis of dag tasks supporting heterogeneous computing, in 2018 55th ACM/ESDA/IEEE Design Automation Conference (DAC) , pp. 16, IEEE, 2018. [29] A. J. Howard, T. Lee, S. Mahar, P. Intrevado, and D. Myung-Kyung Woodbridge, Distributed data analytics framework for smart transportation, in 2018 IEEE 20th International Conference on High Performance Computing and Communications (HPCC/SmartCity/DSS) , pp. 13741380, 2018. [30] A. d. S. Veith and M. D. de Assuncao, Apache Spark , pp. 7781. Springer International Publishing, 2019. [31] N. Maleki, M. Loni, M. Daneshtalab, M. Conti, and H. Fotouhi, Sofa: A sparkoriented fog architecture, in IECON 2019 - 45th Annual Conference of the IEEE Industrial Electronics Society , pp. 27922799, 2019. [32] J. J. Gutiérrez and H. Pérez, Theory and practice of edf scheduling in distributed real-time systems, in Ada-Europe International Conference on Reliable Software Technologies , pp. 123137, Springer, 2018. [33] R. Lange, A. C. Bonatto, F. Vasques, and R. S. de Oliveira, Timing Analysis of hybrid FlexRay, CAN-FD and CAN vehicular networks, in 42nd Annual Conference of the IEEE Industrial Electronics Society (IECON) , pp. 47254730, Oct 2016. [34] Q. Zhu, H. Zeng, W. Zheng, M. D. Natale, and A. Sangiovanni-Vincentelli, Optimization of task allocation and priority assignment in hard real-time distributed systems, ACM Trans. Embed. Comput. Syst. , vol. 11, no. 4, 2013. [35] Y. Wu, Z. Gao, and G. Dai, Deadline and activation time assignment for partitioned real-time application on multiprocessor reservations, Journal of Systems Architecture , vol. 60, no. 3, pp. 247257, 2014. [36] G. Xie, R. Li, and K. Li, Heterogeneity-driven end-to-end synchronized scheduling for precedence constrained tasks and messages on networked embedded systems, Journal of Parallel and Distributed Computing , vol. 83, pp. 1  12, 2015. 55 BIBLIOGRAPHY [37] D. Zhang, Y. Ma, C. Zheng, Y. Zhang, X. S. Hu, and D. Wang, Cooperativecompetitive task allocation in edge computing for delay-sensitive social sensing, in 2018 IEEE/ACM Symposium on Edge Computing (SEC) , pp. 243259, 2018. [38] H. R. Faragardi, S. Dehnavi, M. Kargahi, A. V. Papadopoulos, and T. Nolte, A time-predictable fog-integrated cloud framework: One step forward in the deployment of a smart factory, in 2018 Real-Time and Embedded Systems and Technologies (RTEST) , pp. 5462, 2018. [39] H. Alrammah, Y. Gu, C. Wu, and S. Ju, Scheduling for energy eciency and throughput maximization in a faulty cloud environment, in 2017 IEEE 23rd International Conference on Parallel and Distributed Systems (ICPADS) , pp. 561 569, IEEE, 2017. [40] Q. Wu and Y. Gu, Supporting distributed application workows in heterogeneous computing environments, in 2008 14th IEEE International Conference on Parallel and Distributed Systems , pp. 310, IEEE, 2008. [41] E. Tejedor, Y. Becerra, G. Alomar, A. Queralt, R. M. Badia, J. Torres, T. Cortes, and J. Labarta, Pycompss: Parallel computational workows in python, The International Journal of High Performance Computing Applications , vol. 31, no. 1, pp. 6682, 2017. [42] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi, You only look once: Unied, real-time object detection, in 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , pp. 779788, 2016. [43] IEEE Standard for Ethernet, IEEE Std 802.3-2018 (Revision of IEEE Std 802.3-2015) , pp. 15600, Aug 2018. [44] IEEE Standard for 802.11, IEEE Std 802.11ac-2013 (Amendment to IEEE Std 802.11-2012, as amended by IEEE Std 802.11ae-2012, IEEE Std 802.11aa-2012, and IEEE Std 802.11ad-2012) , pp. 1425, 2013. [45] M. F. Hasan and I. Karimi, Piecewise linear relaxation of bilinear programs using bivariate partitioning, AIChE journal , vol. 56, no. 7, pp. 18801893, 2010. 56 BIBLIOGRAPHY [46] O. Keren, I. Levin, and R. Stankovi£, Linearization of logical functions dened by a set of orthogonal terms. ii. algorithmic aspects, Automation and Remote Control , vol. 72, no. 4, p. 818, 2011. [47] M. Pinedo, Scheduling: theory, algorithms, and systems, 2012. [48] K. E. Raheb, C. T. Kiranoudis, P. P. Repoussis, and C. D. Tarantilis, Production scheduling with complex precedence constraints in parallel machines, Computing and Informatics , vol. 24, no. 3, pp. 297319, 2012. [49] A. Tirumala, F. Qin, J. M. Dugan, J. A. Ferguson, and K. A. Gibbs, iperf: Tcp/udp bandwidth measurement tool, 2005. [50] The DOT Language, 2011. URL: https://graphviz.org/doc/info/lang. html . [51] P. GNU, Free Software Foundation. Bash (3.2. 48)[Unix shell program], 2007. [52] H. Gelabert and G. Sánchez, Extrae user guide manual for version 2.2. 0, Barcelona Supercomputing Center (B. Sc.) , 2011. [53] IBM ILOG, Cplex optimization studio, 2014. URL: https://www.ibm.com/ products/ilog-cplex-optimization-studio . [54] B. Brazil, Prometheus: Up & Running: Infrastructure and Application Performance Monitoring . " O'Reilly Media, Inc.", 2018. [55] J. Levinson, J. Askeland, J. Becker, J. Dolson, D. Held, S. Kammel, J. Z. Kolter, D. Langer, O. Pink, V. Pratt, et al. , Towards fully autonomous driving: Systems and algorithms, in 2011 IEEE Intelligent Vehicles Symposium (IV) , pp. 163168, IEEE, 2011. [56] E. Jones, T. Oliphant, P. Peterson, et al. , SciPy: Open source scientic tools for Python, 2001. 57