Computer Science Research Seminar

11:30 am - 12:30 pm, Wednesday, November 21, 2009

Prof. Keqin Li

SUNY Distinguished Professor

Title: Power-Aware Task Scheduling on Multiprocessor Computers with Dynamic Voltage and Speed



Task scheduling on multiprocessor computers with dynamically variable voltage and speed is investigated as combinatorial optimization problems, namely, the problem of minimizing schedule length with energy consumption constraint and the problem of minimizing energy consumption with schedule length constraint. The first problem has applications in general multiprocessor computing systems where energy consumption is an important concern and in mobile computers where energy conservation is a main concern. The second problem has applications in real-time multiprocessing systems where timing constraint is a major requirement. These problems emphasize the tradeoff between power and performance and are defined such that the power-performance product is optimized by fixing one factor and minimizing the other. The first problem has not been well studied before. Although the second problem is raised with the same motivation as previous studies, our approach is significantly different, that is, instead of comparing the performance of heuristic algorithms among themselves experimentally, we compare the performance of our algorithms with optimal solutions analytically and validate our results experimentally. It is noticed that these problems have not been studied in such a framework consistent with traditional scheduling theory. It is found that both problems are equivalent to the sum of powers problem and can be decomposed into two subproblems, namely, scheduling tasks and determining power supplies. Such decomposition makes design and analysis of heuristic algorithms tractable. We analyze the performance of list scheduling algorithms and equal-speed algorithms and prove that these algorithms are asymptotically optimal. Our extensive simulation data validate our analytical results and provide deeper insight into the performance of our heuristic algorithms.


Dr. Keqin Li received B.S. degree in computer science from Tsinghua University, China, in 1985, and Ph.D. degree in computer science from the University of Houston in 1990. In March 2009, the Board of Trustees of the State University of New York (the nations largest comprehensive system of public higher education) appointed Dr. Keqin Li to the rank of SUNY Distinguished Professor, the state universitys highest faculty designation, for his internationally recognized prolific research and exemplary scholarship and leading role in the area of parallel and distributed computing. Professor Lis research interests are mainly in the areas of design and analysis of algorithms, parallel and distributed computing, and computer networking. He has contributed extensively to approximation algorithms, parallel algorithms, job scheduling, task dispatching, load balancing, performance evaluation, dynamic tree embedding, scalability analysis, parallel computing using optical interconnects, wireless networks, and optical networks. His current research interests include power-aware computing, location management in wireless communication networks, lifetime maximization in sensor networks, and file sharing in peer-to-peer systems. He has published over 210 journal articles, book chapters, and research papers in refereed international conference proceedings. He has received several Best Paper Awards for his highest quality work. His research has been supported by US National Science Foundation, US National Aeronautics and Space Administration, SUNY Research Foundation, and State of New York/United University Professions. Professor Li has served in various capacities for numerous international conferences as general chair, program chair, workshop chair, track chair, and steering/advisory/award/program committee member.

For more information about this colloquium, please contact Habib M. Ammari at