Back to search

University of British Columbia

Energy-time complexity of algorithms : modelling the trade-offs of CMOS VLSI

Abstract

dc:description

Power consumption has become one of the most critical concerns for processor design. Parallelism offers a pathway to increased performance under power constraints — many slow processors can complete a parallel implementation of a task using less time and less energy than a fast uniprocessor. This relies on the energy-time trade-offs present in CMOS circuits, including voltage scaling. Understanding these trade-offs and their connection with algorithms will be a key for extracting performance in future multicore processor designs. I propose simple models for analysing algorithms and deriving lower bounds that reflect the energy-time trade-offs and parallelism of CMOS circuits. For example, the models constrain computational elements to lie in a two-dimensional topology. These elements, called processing elements (PEs), compute arbitrary functions of a constant number of input bits and store a constant-bounded memory. PEs are used to implement wires; thus subsuming and accounting for communication costs. Each operation of a PE takes time t and consumes energy e, where eta remains invariant for some fixed α > 0. Not only may different PEs independently trade time for energy in this way, but the same PE may vary the trade-off on an operation by operation basis. Using these models, I derive lower bounds for the ETα costs of sorting, addition and multiplication, where E and T are the total energy and time, and present algorithms that meet these bounds asymptotically. Clearly there exist many algorithms to solve each of these problems, and furthermore there are many choices of how to implement them with processing elements. Fortunately, the tight asymptotic bounds collapse the hierarchy of algorithms, implementations and schedules. This demonstrates that choosing other algorithms or layout schemes may only improve the energy-time "cost" by constant factors. In addition to analysing energy-time optimal algorithms for these problems, I also determine the complexity of many other well-established algorithms. This sheds light on the relative energy-time efficiency of these algorithms, revealing that some "fast" algorithms exploit free communication of traditional computation models. I show that energy-time minimal algorithms are not the same as those that minimize operation count or the computation depth.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2007

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Bingham, Brad D

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/32142

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Bingham, Brad D. Energy-time complexity of algorithms : modelling the trade-offs of CMOS VLSI. master's thesis, University of British Columbia, 2007. http://hdl.handle.net/2429/32142