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

Qiankai Cao; Xi Chen; Jie Gu

doi:10.1109/ISLPED58423.2023.10244267

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

Qiankai Cao, Xi Chen, Jie Gu

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

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 language	English (US)
Title of host publication	2023 IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2023
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9798350311754
DOIs	https://doi.org/10.1109/ISLPED58423.2023.10244267
State	Published - 2023
Event	2023 IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2023 - Vienna, Austria Duration: Aug 7 2023 → Aug 8 2023

Publication series

Name	Proceedings of the International Symposium on Low Power Electronics and Design
Volume	2023-August
ISSN (Print)	1533-4678

Conference

Conference	2023 IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2023
Country/Territory	Austria
City	Vienna
Period	8/7/23 → 8/8/23

Funding

V. CONCLUSION In this work, a generic hardware accelerator architecture is proposed for tropical algebra. Energy efficient time domain computing circuits are further implemented to accelerate the min/max-sum calculations. For various applications, novel mapping methods are developed to support various problem size matching with the accelerator array size. Tropical precision expansion method is proposed to separate data into lower bit data with residual matrix to help reduce hardware cost, while maintaining data integrity. Special unrolling technique is also proposed in time domain that can reduce data conversion between digital and time domain. Experiments on a 65nm design show that for applications of linear regression, DTW, dynamic programming and neural network, an improvement from 1.5X to 2.1X for energy consumption and 2.6X to 5.2X saving for latency are achieved from the proposed design in comparison with conventional digital implementation. An overall energy-delay-product (EDP) improvement from 3.9X to 10.5X is also observed from our test results. VI. ACKNOWLEDGEMENTS This work was supported in part by NSF under grant number CCF-1846424.

Keywords

dynamic programming
shortest path problems
time-domain computing
tropical algebra

ASJC Scopus subject areas

General Engineering

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1109/ISLPED58423.2023.10244267

Cite this

Cao, Q., Chen, X., & Gu, J. (2023). Development of Tropical Algebraic Accelerator with Energy Efficient Time-Domain Computing for Combinatorial Optimization and Machine Learning. In 2023 IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2023 (Proceedings of the International Symposium on Low Power Electronics and Design; Vol. 2023-August). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISLPED58423.2023.10244267

Cao, Qiankai ; Chen, Xi ; Gu, Jie. / Development of Tropical Algebraic Accelerator with Energy Efficient Time-Domain Computing for Combinatorial Optimization and Machine Learning. 2023 IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2023. Institute of Electrical and Electronics Engineers Inc., 2023. (Proceedings of the International Symposium on Low Power Electronics and Design).

@inproceedings{0597e577db2f4c74820b8b09ad99580a,

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

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.",

keywords = "dynamic programming, shortest path problems, time-domain computing, tropical algebra",

author = "Qiankai Cao and Xi Chen and Jie Gu",

note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 2023 IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2023 ; Conference date: 07-08-2023 Through 08-08-2023",

year = "2023",

doi = "10.1109/ISLPED58423.2023.10244267",

language = "English (US)",

series = "Proceedings of the International Symposium on Low Power Electronics and Design",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "2023 IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2023",

address = "United States",

}

Cao, Q, Chen, X & Gu, J 2023, Development of Tropical Algebraic Accelerator with Energy Efficient Time-Domain Computing for Combinatorial Optimization and Machine Learning. in 2023 IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2023. Proceedings of the International Symposium on Low Power Electronics and Design, vol. 2023-August, Institute of Electrical and Electronics Engineers Inc., 2023 IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2023, Vienna, Austria, 8/7/23. https://doi.org/10.1109/ISLPED58423.2023.10244267

Development of Tropical Algebraic Accelerator with Energy Efficient Time-Domain Computing for Combinatorial Optimization and Machine Learning. / Cao, Qiankai; Chen, Xi; Gu, Jie.
2023 IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2023. Institute of Electrical and Electronics Engineers Inc., 2023. (Proceedings of the International Symposium on Low Power Electronics and Design; Vol. 2023-August).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Cao, Qiankai

AU - Chen, Xi

AU - Gu, Jie

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

KW - dynamic programming

KW - shortest path problems

KW - time-domain computing

KW - tropical algebra

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

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

U2 - 10.1109/ISLPED58423.2023.10244267

DO - 10.1109/ISLPED58423.2023.10244267

M3 - Conference contribution

AN - SCOPUS:85173086161

T3 - Proceedings of the International Symposium on Low Power Electronics and Design

BT - 2023 IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2023

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2023 IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2023

Y2 - 7 August 2023 through 8 August 2023

ER -

Cao Q, Chen X, Gu J. Development of Tropical Algebraic Accelerator with Energy Efficient Time-Domain Computing for Combinatorial Optimization and Machine Learning. In 2023 IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2023. Institute of Electrical and Electronics Engineers Inc. 2023. (Proceedings of the International Symposium on Low Power Electronics and Design). doi: 10.1109/ISLPED58423.2023.10244267

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

Abstract

Publication series

Conference

Funding

Keywords

ASJC Scopus subject areas

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this