Energy-Time Trade-Offs in Algorithm Analysis and Design

The Hong Kong University of Science & Technology
Department of Computer Science & Engineering
HKUST Theoretical Computer Science Group

		Joint Seminar
------------------------------------------------------------

Speaker:	Professor Mark GREENSTREET
		University of British Columbia

Title:		"Energy-Time Trade-Offs in Algorithm Analysis
		 and Design"

Date:		Friday, 1 February 2008

Time:		11:00am - 12 noon

Venue:		Room 3464 (via lift nos. 25/26)
		The Hong Kong University of Science & Technology

Abstract:

With power consumption placing severe constraints on processor design,
parallelism has become the most promising pathway to further increases in
computer performance. The basic trade-off is that when more time is
allotted for an operation, the operation can be performed using less
energy. Such energy/time trade-offs occur in circuit design, logic design
and micro-architectural trade-offs.  With the central role of power
consumption in limiting computer performance, we have been surprised, even
shocked, that the computer science theory community has apparently
neglected the opportunity for energy/time trade-offs in the design of
algorithms. In this talk, I will present a model for algorithm design and
analysis that incorporates these trade-offs. In this model, we assume that
unlimited parallelism is available, but that communication has a cost that
grows with distance.  Energy and time can be traded with $ET^\alpha$ being
a constant for some $\alpha > 0$. I will give a brief, physical
justification for the model and then apply it to sorting, addition and
multiplication. In each case, I will present a lower-bound for the cost of
the task and present an algorithm that achieves this bound to within
constant factors. I will conclude the talk by describing areas for further
research including analyzing a wider range of algorithms, refining the
model to include more physical constraints and possible applications of
this approach to understanding issues in computer architecture.

This is joint work with Brad Bingham, a graduate student at UBC.


*******************
Biography:

Mark GREENSTREET received the B.Sc. in Electrical Engineering from Caltech
in 1981 and the M.A. and Ph.D. degrees in Computer Science in 1988 and
1993 respectively from Princeton University. His Ph.D. thesis introduced
the source-synchronous method for communication and provided a formal
proof for the correctness of the approach along with a chip to demonstrate
it. Dr. GREENSTREET has been a faculty member in the Computer Science
department at the University of British Columbia where he is now a full
professor. His research interests include high-speed circuit design,
asynchronous circuits, performance analysis, formal verification, and
algorithm analysis.  His research includes active collaborations with
researchers at Intel, Rambus, and SUN Microsystems.