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

Speaker:  Mark Greenstreet
University of British Columbia


Date: Feb 1, 2008
Time 11:00-12:00PM
Venue: Room 3464, HKUST

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.

 Bio:  
    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.