STPAcc: Structural TI-Based Pruning for Accelerating Distance-Related Algorithms on CPU-FPGA Platforms

As a promising solution to boost the performance of distance-related algorithms (e.g., K -means and KNN), FPGA-based acceleration attracts lots of attention, but also comes with numerous challenges. In this work, we propose, STPAcc , an optimization framework based on structural triangle-inequality...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computer-aided design of integrated circuits and systems 2022-05, Vol.41 (5), p.1358-1370
Main Authors: Wang, Yuke, Feng, Boyuan, Li, Gushu, Deng, Lei, Xie, Yuan, Ding, Yufei
Format: Article
Language:English
Subjects:
Algorithms
Clustering algorithms
Computational modeling
Domain specific languages
Field programmable gate arrays
FPGA acceleration
Hardware
machine learning algorithms
OpenCL programming
Optimization
Partitioning algorithms
Performance enhancement
Platforms
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:As a promising solution to boost the performance of distance-related algorithms (e.g., K -means and KNN), FPGA-based acceleration attracts lots of attention, but also comes with numerous challenges. In this work, we propose, STPAcc , an optimization framework based on structural triangle-inequality (TI)-based pruning (STP) for accelerating distance-related algorithms on CPU-FPGA platforms. STPAcc provides a domain-specific language to unify distance-related algorithms effectively, a structural TI-based pruning strategy to remove unnecessary distance computations, a coarse-grained workload partitioning and mapping strategy to fully exploit the potentials of the CPU-FPGA platform, and fine-grained hardware optimizations to further improve performance on the FPGA. Intensive experiments show that STPAcc designs achieve 31.42\times speedup and 99.63\times better energy efficiency on average over standard CPU-based implementations.
ISSN:0278-0070
1937-4151
DOI:10.1109/TCAD.2021.3093394