Efficient Techniques for Scheduling DAG Applications in Distributed Environments
| dc.contributor.author | Senapati, Debabrata | |
| dc.date.accessioned | 2024-12-11T06:46:56Z | |
| dc.date.available | 2024-12-11T06:46:56Z | |
| dc.date.issued | 2023 | |
| dc.description | Supervisors: Sarkar, Arnab and Karfa, Chandan | |
| dc.description.abstract | A Cyber-Physical System (CPS) integrates two sub-systems - a cyber sub-system and a physical sub-system. The cyber sub-system is often a heterogeneous distributed computing system that executes applications for regulating mechanisms associated with the physical sub-system, typically consisting of electromechanical components. Real-Time Cyber-Physical Systems (RTCPSs) are characterized by their ability to respond to events that may happen in their operating environment within stipulated time bounds. The accuracy of these systems depends not only on the delivered results but also on their completion times. Applications in today's RT-CPSs are often represented by Directed Acyclic Graphs (DAGs) due to their distributed nature and complex interactions among component functionalities. In such DAGs, nodes represent tasks associated with the application, while edges denote interdependencies among tasks. To meet functionalityspecific high-performance demands, these DAGs are often implemented on heterogeneous RTCPS platforms, where (i) the same task may exhibit different execution time requirements on different processors, and (ii) inter-task messages containing the same amount of data may incur distinct transmission times on the different communication channels due to variations in channel bandwidths. The RT-CPS applications may be aperiodically triggered by an external event or may execute in infinite loops, periodically acquiring data from the environment through sensors at a particular frequency, processing the same, and then producing processed data via actuators. This dissertation deals with the design of resource allocation mechanisms for DAG-structured applications on heterogeneous distributed RT-CPSs. The thesis which unfolds through the dissertation is as follows: For the mentioned system scenarios, the list-based design philosophy is effective towards obtaining low-overhead but efficient scheduling mechanisms for satisfying diverse objectives/constraints related to resource usage efficiency, timeliness, energy, security, temperature, etc. All list scheduling heuristics typically consist of two phases, (i) Task prioritization: for listing tasks in a specific priority order, and (ii) Task-to-processor mapping: for allocating the tasks in the order of their priorities on suitable processors and associating with them appropriate execution start times. The contributions of this thesis are categorized into five phases as follows: (i) The first phase focuses on the development of an efficient real-time DAGscheduling framework which attempts to minimize a generic penalty function. The designed penalty function can be amicably adopted towards its deployment in various application domains such as real-time cyber-physical systems like automotive and avionic systems, cloud computing, smart grids, etc. (ii) In the second phase, we develop a state-space search guided heuristic scheduling algorithm called HMDS, whose objective is to minimize schedule length. By controlling the nature and extent of state-space exploration, HMDS can adapt itself to deliver the best possible solution within a given time bound. (iii) A mechanism for co-scheduling multiple independent periodic DAG applications has been devised in the third phase. The objective of the scheduling algorithm is to minimize dissipated energy. (iv) Subsequently, in the fourth phase, a security-aware real-time DAG scheduling strategy has been designed. The scheme maximizes total security utility for a given application having known minimum security strength specifications for its messages. (v) Finally, in the last phase of the dissertation, we have developed a mechanism to construct minimum makespan schedules for precedence-constrained task graph applications with known thermal characteristics on a heterogeneous processing platform. The efficacy of the developed scheduling schemes has been extensively evaluated through simulation-based experiments using randomly generated DAGs and/or real-world benchmarks. Prototype realplatform implementations as well as real-world case studies have also been presented to exhibit the practical applicability of the proposed algorithms. | |
| dc.identifier.other | ROLL NO.176101003 | |
| dc.identifier.uri | https://gyan.iitg.ac.in/handle/123456789/2728 | |
| dc.language.iso | en | |
| dc.relation.ispartofseries | TH-3183 | |
| dc.title | Efficient Techniques for Scheduling DAG Applications in Distributed Environments | |
| dc.type | Thesis |
Files
License bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- license.txt
- Size:
- 1.71 KB
- Format:
- Item-specific license agreed to upon submission
- Description: