Development of Tropical Algebraic Accelerator with Energy Efficient Time-Domain Computing for Combinatorial Optimization and Machine Learning

Qiankai Cao, Xi Chen, Jie Gu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Tropical algebra solves complex problems with only sum and min/max operations replacing expensive multiplication and addition in linear algebra. Due to the low computing cost, tropical algebra has recently gained significant attention in a broad range of areas such as combinatorial optimization, scheduling, machine learning, etc. In this paper, we propose a generic hardware accelerator architecture for tropical algebra supporting a wide range of applications. Novel time-domain (TD) computing accelerators with special mapping, precision expansion and, unrolling techniques are proposed to further improve hardware efficiency. Test results on various tropical calculations including linear regression, dynamic programming, and neural network are shown to demonstrate an energy saving from 1.5X to 2.1X, latency saving from 2.6X to 5.2X, or an overall energy-delay-product (EDP) improvement from 3.9X-10.5X compared with conventional digital implementation manifesting the promise of the algebraic solution on low power edge devices.

Original languageEnglish (US)
Title of host publication2023 IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9798350311754
DOIs
StatePublished - 2023
Event2023 IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2023 - Vienna, Austria
Duration: Aug 7 2023Aug 8 2023

Publication series

NameProceedings of the International Symposium on Low Power Electronics and Design
Volume2023-August
ISSN (Print)1533-4678

Conference

Conference2023 IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2023
Country/TerritoryAustria
CityVienna
Period8/7/238/8/23

Keywords

  • dynamic programming
  • shortest path problems
  • time-domain computing
  • tropical algebra

ASJC Scopus subject areas

  • General Engineering

Fingerprint

Dive into the research topics of 'Development of Tropical Algebraic Accelerator with Energy Efficient Time-Domain Computing for Combinatorial Optimization and Machine Learning'. Together they form a unique fingerprint.

Cite this