LSC: A Large-Scale Consensus-Based Clustering Algorithm for High-Performance FPGAs

With recent advances in Field Programmable Gate Array (FPGA) architecture and design, the robustness and scalability of design implementation tools is becoming increasingly important. In an FPGA implementation flow, the basic logic elements (BLEs) like flip-flops (FFs) and lookup tables (LUTs) are clustered into adaptive logic modules (ALMs) and Logic Array Blocks (LABs). Clustering is a key stage in the flow that determines whether a design can fit onto the target FPGA device, and whether the Quality of Results (QoR) goals are met. Traditionally, FPGA implementation tools have used greedy clustering techniques. This paper presents an innovative clustering algorithm based on a new concept of consensus building at a large scale (LSC). The LSC algorithm is designed to work with designs with millions of elements, and to the best of our knowledge, this is the first parallel clustering algorithm in the industry. In our industrial designs benchmark set using modern FPGA devices on two deep submicron technology nodes, the new clustering engine results in average improvements of 0.5% and 2.5% in maximum clock frequency (Fmax) for the two target devices. Additionally, wiring usage is improved on the average by 2.8% and 6.5% respectively. The fitting success rate of highly utilized designs is also improved significantly with the new clustering engine.