AF:Small: Algorithmic Management of Heterogeneous Resources

University Of Pittsburgh, Pittsburgh PA

Investigators

Abstract

Energy arguably ascended over time as the dominant computational resource circa 2000, when standard information technologies could no longer cope with the consequences of Moore's law, which states that the density of computational units doubles every couple of years. Thus the community is about a decade or two into an information-technology revolution in which a wide range of technologies are being redesigned with energy as a first-class design constraint. Over the last several decades, when time and space were the dominant computational resources, computer-science researchers developed many techniques for designing algorithms that made efficient use of these resources, and for analyzing the time and space required by particular algorithms on simple models of a computer. These techniques are commonly taught in algorithms and theory/complexity classes that are required for computer scientists. The ability to reason abstractly about time and space in simple computational models is undoubtedly a valuable skill for computer scientists and software engineers, and many of the most successful computing companies are famous for job interviews that tests these reasoning skills. The PI's long term goal is to build a body of knowledge related to algorithm design and analysis techniques for problems related to managing heterogeneous resources, and managing energy as a computational resource. The PI expects that this body of knowledge will eventually be taught to future software engineers, and will serve these software engineers, when faced with problems in which power/energy/temperature is the key scarce resource, just as the current algorithmic theory of time as a computation resource now serves them. One of the most common mechanisms for achieving energy efficiency is building a system with heterogeneous devices with different energy/performance characteristics. For a given area and power budget, heterogeneous designs often give significantly better performance, for a given energy/hardware budget, for standard workloads than homogeneous designs. The PI will address algorithmic problems related to managing heterogeneous resources in several technologies arising from this information-technology revolution. Briefly, these problems are online convex optimization with applications to energy-efficient load balancing of data centers, energy-efficient routing in a network, designing combinatorial circuits that optimally trade-off energy efficiency and reliability, determining the complexity of finding schedules that optimally trade-off energy and performance, and analyzing scheduling algorithms on a heterogeneous multiprocessor. Managing heterogeneous resources is algorithmically significantly more challenging than managing heterogeneous resources, and many existing algorithmic techniques are not sufficient for handling these algorithmic problems. This project aims to invent new algorithmic techniques for solving these problems. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.