Parallel Symbiotic Random Number Generator for Training Tsetlin Machines on FPGA

The logical proposition (clause) based underpinning and computationally minimal training procedure of Tsetlin Machines (TM) allows for exploration of on-chip training on resource limited FPGAs for edge applications. The core challenge is finding a suitable trade-off between memory, compute requirement and performance. The use of Coalesced Tsetlin Machines (CoTM) instead of vanilla TM can mitigate on-chip memory requirements by $\approx(1 / M)$, thanks to clause sharing among the M classes in a multi-class classification problem. However, the stochastic learning procedure involved in training TMs continue to pose a significant compute bottleneck for on-chip implementations. It requires important design decisions concerning generation of billions of floating-point pseudo random numbers (PRNs) in real-time. This paper proposes a major breakthrough in utilizing existing on-chip Digital Signal Processing (DSP) blocks on FPGA to generate massive amounts of high-quality PRNs to train CoTM in real-time. In the proposed design, the entire computation is performed on-chip and the peripheral interactions include only the transfer of input features and the classification output. Compared to traditional linear feedback shift register (LFSR), this paper, for the first time, explores the use of Mid-Square and Weyl functions on DSP blocks interlinked with look-up table based XOR-shift method to generate PRNs. The interlink enables symbiotic generation of seeds when required by either the Mid-square, Weyl or XOR-shift. The proposed designs with either the Weyl or Mid-square generators outperform LFSRs by offering the same CoTM training behavior and similar accuracy when compared with software generated random numbers.