Department of Computer Science at UH

University of Houston

Department of Computer Science

In Partial Fulfillment of the Requirements for the Degree of
Master of Science

Youngmi Lee

Will defend her thesis

Implementation of two Benefit-Based Algorithms


Recently, the use of multiprocessor platfoms is becoming popular because they can enhance the system performance even though multiprocessor job scheduling is an NP-hard problem. The major hardware manufactures continue to develop the next generation of multiprocessor chips to obtain powerful performance and to address the increasing demand of modern multimedia applications. To improve the performance of the system, several scheduling techniques are researched based on two model: cost-based and benefit-based. Due to a lack of testing platforms, evaluation for proposed scheduling algorithm was difficult.

We design and develop a simulation program that implements two benefit-based algorithms. Both algorithms are used to schedule nonperiodic tasks set and periodic tasks set with a varying number of processors. Also, the simulator can accept specific measurement values defined by the researchers in our RTS laboratory to facilitate the evaluation of both algorithms. Therefore, they are able to compare their proposed greedy benefit-based algorithm with the non-greedy benefit-based algorithm in terms of the following metrics: benefit gained by that scheduling (benefit-awareness), The rate of missed deadlines (tardiness ratio), average processor usage ratio (energy-awareness), and total processor idle time. These results will help researchers analyze which one shows better performance. In addition, the simulation program can be extended whenever additional evaluation options are needed.

Date: Friday, July 24, 2009
Time: 1:00 PM
Place: 563-PGH
Faculty, students, and the general public are invited.
Advisor: Prof. Albert M. K. Cheng