An Efficient and Scalable Clocking Assignment Algorithm for Multi-Threaded Multi-Phase Single Flux Quantum Circuits

Abstract

This paper proposes an approximation algorithm for clocking assignments that minimizes the insertion of path balancing DFFs for multi-threaded multi-phase clocking of SFQ circuits. Existing SFQ multi-phase clocking solutions have been shown to effectively reduce the number of required DFFs in-serted, however, the associated clock assignment algorithms have exponential complexity and can have prohibitively long runtimes for large circuits, limiting the scalability of this approach. Our proposed algorithm is based on a linear program (LP) that leads to solutions that are experimentally on average within 5% of the optimum, permitting multi-phase clocking schemes to scale to larger SFQ circuits than previous state of the art clocking assignment methods. We further extend our algorithm to support fanout sharing of the added DFFs, saving, on average, an additional 11 % of the inserted DFFs compared to the state of the art. Compared to traditional full path balancing (FPB) methods across 12 benchmarks, our enhanced LP saves 68.8 %, 80.0%, and 87.6% of the inserted DFFs for 2,3, and 4 clock phases respectively. Finally, we extend this approach to the generation of circuits that completely mitigate potential hold-time violations at the cost of either reduced DFF savings or, more generally, adding a clock phase.