자료유형 | 학위논문 |
---|---|
서명/저자사항 | Topology-Aware Job Scheduling and Placement in High Performance Computing and Edge Computing Systems. |
개인저자 | Li, Kangkang. |
단체저자명 | University of Notre Dame. |
발행사항 | [S.l.]: University of Notre Dame., 2019. |
발행사항 | Ann Arbor: ProQuest Dissertations & Theses, 2019. |
형태사항 | 136 p. |
기본자료 저록 | Dissertations Abstracts International 81-06B. Dissertation Abstract International |
ISBN | 9781392756362 |
학위논문주기 | Thesis (Ph.D.)--University of Notre Dame, 2019. |
일반주기 |
Source: Dissertations Abstracts International, Volume: 81-06, Section: B.
|
요약 | The interconnection topology of the computing nodes in a distributed system plays an important role in the way that jobs should be scheduled and allocated. In this work, I address two resource allocation problems. The first problem is topology- aware job scheduling and placement problem in high performance computing (HPC) systems, where a 3D torus-based interconnection topology is used. The second problem is networked virtual machine (VM) and job placement in edge cloud systems, in which a two-layer star topology is applied in the considered edge cloud architecture.For the first resource allocation problem, I address the topology-aware job scheduling and placement problem in a 3D torus-based HPC system, with the objective of reducing system fragmentation and improving system utilization. Firstly, for the job scheduling problem, I propose a packing-based job scheduling strategy, which reduces the external fragmentation caused by using the First Come First Served (FCFS) + backfilling strategy. Secondly, I study the first case of the job placement problem, where each job is allocated a convex prism shape. I propose a topology-aware job placement algorithm based on a local migration process and a global migration process, which aims at reducing internal and external fragmentation in the job placement process. Thirdly, I study the second case of the job placement problem, in which the shapes allocated for communication non-sensitive jobs are not limited to convex prisms. I propose two shape allocation methods to determine the topological shape for each input job, including a zigzag allocation method for communication non-sensitive jobs, and a convex allocation method for communication sensitive jobs. After that, I propose a communication-aware job placement algorithm including a target bin selection method and a bi-directional job placement method to reduce internal and external fragmentation in the job placement process. The evaluation results validate the efficiency of my proposed strategies and algorithms in reducing system fragmentation and improving system utilization.For the second resource allocation problem, I address the networked VM and job placement problem in the edge cloud system. Firstly, for the homogeneous edge cloud system, I propose one optimal algorithm to obtain the maximum number of accepted VMs into the system, and then design another optimal algorithm to minimize the total inter-node communication cost in the homogeneous edge cloud system. Secondly, for the heterogeneous edge cloud system, I propose one optimal algorithm to obtain the maximum number of accepted VMs into the system, and then design another algorithm to minimize the total inter-node communication cost in the heterogeneous edge cloud system. Thirdly, I study the job placement problem under the multi-tenant scenario, which is NP-hard. A heuristic algorithm is proposed to give an efficient solution. The evaluation results validate the efficiency of my algorithms. |
일반주제명 | Computer science. |
언어 | 영어 |
바로가기 | ![]() |