Skip Navigation

Doctoral Defense

Scheduling Load Computation and Communication in Virtualized Networks

Fei Wu

December 5, 2018
3:30 PM
Light Engineering room 250
Advisor: Prof. Thomas Robertazzi

Parallel processing (or parallel computing) is a field in electrical engineering and computer science related to the application of many computers running in parallel to solve computationally intensive problems. The main goal of parallel processing is to provide users with performance which no single computer may deliver. Scheduling is an important task allowing parallel systems to perform efficiently and reliably. In general, scheduling can be considered managing the execution of jobs which required certain re- sources (processors, CPUs, memory, etc.) in such a way that certain optimality and/or feasibility criteria are met. Such optimality conditions can be shortest finishing time, lowest monetary cost and so on. Scheduling is crucial for parallel processing since it allows parallel system to have an optimal performance according to users’ preferences.

For modern computation systems, divisible load is a special type of data which can be divided into arbitrary sizes and independently processed in parallel. Such loads are commonly encountered in applications which are processing a great amount of similar data units. During the past decade, divisible load theory has been proved as a powerful tool in scheduling for parallel systems.

In this thesis, we consider a time-sharing parallel system where the processors are multi-task capable. For a multi-task processor, the processor’s speed may be time-varying due to the arrival and departure of other background jobs.

To this end, we first studied an optimal divisible load scheduling problem on a single level tree network, whose processing speed and channel speed are time-varying. Two cases are studied where the arrival and departure times of background jobs are known or unknown beforehand. Numerical tests and evaluations are performed for these two cases under different numbers of background jobs and processors.

Also, based on the scheduling algorithm, an optimal sequencing problem was studied for both minimum finishing time and minimum monetary cost. A reinforcement learning method was introduced to train the optimal sequence for both cases under a time-varying system. Various numerical tests were performed to evaluate the performance of our algorithm.