BiS-KM: Enabling Any-Precision K-Means on FPGAs

K-Means is a popular clustering algorithm widely used and extensively studied in the literature. In this paper we explore the challenges and opportunities in using low precision input in conjunction with a standard K-Means algorithm as a way to improve the memory bandwidth utilization on hardware accelerators. Low precision input through quantization has become a standard technique in machine learning to reduce computational costs and memory traffic. When applied in FPGAs, several issues need to be addressed. First and foremost is the overhead of storing the data at different precision levels since, depending on the training objective, different levels of precision might be needed. Second, the FPGA design needs to accommodate varying precision without requiring reconfiguration. To address these concerns, we propose Bit-Serial K-Means (BiS-KM), a combination of a hybrid memory layout supporting data retrieval at any level of precision, a novel FPGA design based on bit-serial arithmetic, and a modified K-Means algorithm tailored to FPGAs. We have tested BiS-KM with various data sets and compared our design with a state-of-the-art FPGA accelerator. BiS-KM achieves an almost linear speedup as precision decreases, providing a more effective way to perform K-Means on FPGAs.