TL;DR
This paper introduces ReducedLUT, a novel method for compressing lookup tables (LUTs) used in neural networks on FPGAs. By strategically injecting "don't care" conditions, ReducedLUT enhances self-similarities within these tables, enabling significantly better compression (up to 39% reduction in physical LUT utilization) with minimal impact on model accuracy.
What Problem Does This Paper Address?
Field-Programmable Gate Arrays (FPGAs) are increasingly used for accelerating neural network (NN) inference due to their flexibility and efficiency. A common approach is to implement NN functions using Lookup Tables (LUTs). However, as NN models grow in complexity and require higher input resolutions, the size of these LUTs can explode exponentially, quickly exceeding the capacity of an FPGA's physical LUTs (P-LUTs). While compression techniques exist for standard functions, NNs often generate LUTs with irregular, "random-looking" patterns that resist traditional compression methods. This makes it challenging to efficiently map complex NNs onto FPGAs without sacrificing performance or accuracy.
Methods
The core of ReducedLUT lies in its novel approach to LUT compression, building upon the existing CompressedLUT methodology. The key innovation is the strategic use of "don't care" conditions.
- Don't Care Identification: ReducedLUT first identifies "don't care" entries within an L-LUT. These are input combinations that were not observed during the NN's training phase. The paper argues that assigning arbitrary values to these inputs typically has a negligible impact on the overall NN's test accuracy.
- Hardware-Efficient Interpolation: Instead of using the original, potentially complex interpolation values for these don't care entries, ReducedLUT replaces them with values derived from a hardware-efficient interpolation process. This injection of "freedom" into the LUT data is designed to create more self-similarities.
- Enhanced Decomposition: These newly created self-similarities are then exploited by the existing CompressedLUT decomposition algorithm. This algorithm breaks down large L-LUTs into smaller sub-tables and compresses them by identifying and storing only unique sub-tables, along with information on how to reconstruct the others (e.g., via bitwise shifts). By increasing self-similarities, ReducedLUT reduces the number of unique sub-tables that need to be stored.
- Exiguity Parameter: A parameter called "exiguity" is introduced to control the optimization process. It sets a threshold on how many sub-tables can depend on a given unique sub-table for it to be eligible for don't care optimization. This helps to avoid complex dependency chains that could hinder compression or increase runtime.
Datasets
The paper evaluates its method on two publicly accessible datasets commonly used for NN training:
- Jet Substructure Classification (JSC): Used with two configurations, JSC-2L and JSC-5L.
- Handwritten Digit Classification (MNIST):
The models used for evaluation are based on the NeuraLUT project, which provides pre-trained NN architectures designed for FPGA implementation.
Key Insights and Ideas
- "Don't Cares" as a Compression Enabler: The paper demonstrates that "don't care" conditions, often arising from unobserved training data patterns in NNs, are not just irrelevant but can be actively leveraged to improve hardware compression.
- Exploiting NN Inherent Tolerance: Neural networks, due to their over-parameterization, have an inherent tolerance for minor variations in their internal computations. ReducedLUT capitalizes on this by modifying less critical LUT entries without significantly impacting the final output accuracy.
- Self-Similarity is Key: The effectiveness of LUT decomposition techniques hinges on finding self-similarities. ReducedLUT's core idea is to create these self-similarities where they are lacking, making irregular NN LUTs amenable to compression.
- Occam's Razor in Hardware: The authors suggest that the compression decisions made by ReducedLUT, which prioritize simpler structures, align with the principle of Occam's Razor, implying that simpler implementations are often more accurate or generalize better.
Key Results
- Significant P-LUT Reduction: ReducedLUT achieved up to 39% reduction in physical LUT utilization on the JSC_5L benchmark compared to the baseline NeuraLUT approach. For JSC_2L, reductions of up to 36% were observed.
- Minimal Accuracy Degradation: The method resulted in a test accuracy drop of no more than 0.01 accuracy points in practical scenarios.
- Outperforms Existing Methods: ReducedLUT consistently outperformed the existing CompressedLUT method, showing an 8.7% geometric mean reduction in P-LUT utilization across benchmarks.
- MNIST Limitations: For the MNIST dataset, the reduction was smaller (up to 11%) due to its limited output bitwidth, which restricts the ability to separate local variations and thus reduces self-similarities.
- Runtime Overhead: ReducedLUT incurs a runtime overhead, being approximately 1.37 times slower than CompressedLUT per L-LUT input at an exiguity of 250.
Limitations and Future Work
- Focus on Unobserved Data: The current method primarily leverages "don't care" conditions arising from inputs not observed in the training data.
- Infrequently Occurring Values: The authors suggest extending the "don't care" set to include values that occur infrequently in the training data, as these also have minimal impact on generalization.
- Group Compression: Future work could explore compressing groups of L-LUTs together, rather than individually, to enable greater L-LUT sharing across the network and further improve hardware efficiency.
- Trade-off between Compression and Generalization: While the paper shows minimal accuracy loss, it acknowledges a potential tension between optimizing for area reduction and generalization performance, suggesting that the current approach naturally favors the former without harming the latter.
Summary updated