Temporal Approximate Function Memoization

Georgios Tziantzioulis, Nikos Hardavellas, Simone Campanoni

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

Improving the performance of applications is a core target of computer systems research and has led to the creation of various techniques. Among them is function memoization, an intuitive technique that, unfortunately, failed to live up to its promised potential. Traditional function memoization falls short mainly because it is input-based, meaning the system needs to pattern-match the current invocations inputs with previously seen ones to decide which memoized output value to return. This is often computationally intensive and only suitable for a limited set of functions. However, function calls often exhibit temporal value locality on their output. We capitalize on this observation to create the first output-based function memoization technique. We demonstrate that compiler-directed output-based memoization reduces energy and runtime by 50 to 75 percent (2-4x speedup) at the cost of a relatively small degradation of the applications output quality.

Original languageEnglish (US)
Article number8430631
Pages (from-to)60-70
Number of pages11
JournalIEEE Micro
Volume38
Issue number4
DOIs
StatePublished - Jul 1 2018

Fingerprint

Computer systems
Degradation

Keywords

  • approximate computing
  • energy
  • hardware
  • performance
  • temporal locality

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Cite this

Tziantzioulis, Georgios ; Hardavellas, Nikos ; Campanoni, Simone. / Temporal Approximate Function Memoization. In: IEEE Micro. 2018 ; Vol. 38, No. 4. pp. 60-70.
@article{62f25858b50c46c692ca13a6ab1126f5,
title = "Temporal Approximate Function Memoization",
abstract = "Improving the performance of applications is a core target of computer systems research and has led to the creation of various techniques. Among them is function memoization, an intuitive technique that, unfortunately, failed to live up to its promised potential. Traditional function memoization falls short mainly because it is input-based, meaning the system needs to pattern-match the current invocations inputs with previously seen ones to decide which memoized output value to return. This is often computationally intensive and only suitable for a limited set of functions. However, function calls often exhibit temporal value locality on their output. We capitalize on this observation to create the first output-based function memoization technique. We demonstrate that compiler-directed output-based memoization reduces energy and runtime by 50 to 75 percent (2-4x speedup) at the cost of a relatively small degradation of the applications output quality.",
keywords = "approximate computing, energy, hardware, performance, temporal locality",
author = "Georgios Tziantzioulis and Nikos Hardavellas and Simone Campanoni",
year = "2018",
month = "7",
day = "1",
doi = "10.1109/MM.2018.043191126",
language = "English (US)",
volume = "38",
pages = "60--70",
journal = "IEEE Micro",
issn = "0272-1732",
publisher = "IEEE Computer Society",
number = "4",

}

Temporal Approximate Function Memoization. / Tziantzioulis, Georgios; Hardavellas, Nikos; Campanoni, Simone.

In: IEEE Micro, Vol. 38, No. 4, 8430631, 01.07.2018, p. 60-70.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Temporal Approximate Function Memoization

AU - Tziantzioulis, Georgios

AU - Hardavellas, Nikos

AU - Campanoni, Simone

PY - 2018/7/1

Y1 - 2018/7/1

N2 - Improving the performance of applications is a core target of computer systems research and has led to the creation of various techniques. Among them is function memoization, an intuitive technique that, unfortunately, failed to live up to its promised potential. Traditional function memoization falls short mainly because it is input-based, meaning the system needs to pattern-match the current invocations inputs with previously seen ones to decide which memoized output value to return. This is often computationally intensive and only suitable for a limited set of functions. However, function calls often exhibit temporal value locality on their output. We capitalize on this observation to create the first output-based function memoization technique. We demonstrate that compiler-directed output-based memoization reduces energy and runtime by 50 to 75 percent (2-4x speedup) at the cost of a relatively small degradation of the applications output quality.

AB - Improving the performance of applications is a core target of computer systems research and has led to the creation of various techniques. Among them is function memoization, an intuitive technique that, unfortunately, failed to live up to its promised potential. Traditional function memoization falls short mainly because it is input-based, meaning the system needs to pattern-match the current invocations inputs with previously seen ones to decide which memoized output value to return. This is often computationally intensive and only suitable for a limited set of functions. However, function calls often exhibit temporal value locality on their output. We capitalize on this observation to create the first output-based function memoization technique. We demonstrate that compiler-directed output-based memoization reduces energy and runtime by 50 to 75 percent (2-4x speedup) at the cost of a relatively small degradation of the applications output quality.

KW - approximate computing

KW - energy

KW - hardware

KW - performance

KW - temporal locality

UR - http://www.scopus.com/inward/record.url?scp=85051469478&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85051469478&partnerID=8YFLogxK

U2 - 10.1109/MM.2018.043191126

DO - 10.1109/MM.2018.043191126

M3 - Article

VL - 38

SP - 60

EP - 70

JO - IEEE Micro

JF - IEEE Micro

SN - 0272-1732

IS - 4

M1 - 8430631

ER -