Abstract
Lookup tables are widely used in hardware to store arrays of constant values. For instance, complex mathematical functions in hardware are typically implemented through table-based methods such as plain tabulation, piecewise linear approximation, and bipartite or multipartite table methods, which primarily rely on lookup tables to evaluate the functions. Storing extensive tables of constant values, however, can lead to excessive hardware costs in resource-constrained edge devices such as FPGAs. In this paper, we propose a method, called CompressedLUT, as a lossless compression scheme to compress arrays of arbitrary data, implemented as lookup tables. Our method exploits decomposition, self-similarities, higher-bit compression, and multilevel compression techniques to maximize table size savings with no accuracy loss. CompressedLUT uses addition and arithmetic right shift beside several small lookup tables to retrieve original data during the decoding phase. Using such cost-effective elements helps our method use low area and deliver high throughput. For evaluation purposes, we compressed a number of different lookup tables, either obtained by direct tabulation of 12-bit elementary functions or generated by other table-based methods for approximating functions at higher resolutions, such as multipartite table method at 24-bit, piecewise polynomial approximation method at 36-bit, and hls4ml library at 18-bit resolutions. We implemented the compressed tables on FPGAs using HLS to show the efficiency of our method in terms of hardware costs compared to previous works. Our method demonstrated 60% table size compression and achieved 2.33 times higher throughput per slice than conventional implementations on average. In comparison, previous TwoTable and LDTC works compressed the lookup tables on average by 33% and 37%, which resulted in 1.63 and 1.29 times higher throughput than the conventional implementations, respectively. CompressedLUT is available as an open source tool.
Original language | English (US) |
---|---|
Title of host publication | FPGA 2024 - Proceedings of the 2024 ACM/SIGDA International Symposium on Field Programmable Gate Arrays |
Publisher | Association for Computing Machinery, Inc |
Pages | 2-11 |
Number of pages | 10 |
ISBN (Electronic) | 9798400704185 |
DOIs | |
State | Published - Apr 1 2024 |
Event | 32nd ACM International Symposium on Field-Programmable Gate Arrays, FPGA 2024 - Monterey, United States Duration: Mar 3 2024 → Mar 5 2024 |
Publication series
Name | FPGA 2024 - Proceedings of the 2024 ACM/SIGDA International Symposium on Field Programmable Gate Arrays |
---|
Conference
Conference | 32nd ACM International Symposium on Field-Programmable Gate Arrays, FPGA 2024 |
---|---|
Country/Territory | United States |
City | Monterey |
Period | 3/3/24 → 3/5/24 |
Bibliographical note
Publisher Copyright:© 2024 ACM.
Keywords
- function evaluation
- hardware acceleration
- high-level synthesis
- lookup table
- lossless compression
- table size reduction
- table-based method