BZBo Zhang

Bo Zhang

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Bo Zhang has a total of 30 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Binary Subscript Representation and Efficient Pipelined Number Theoretic Transform

    by Bo Zhang, Mingzhe Zhang, Shoumeng Yan

    As a key operation, the number theoretic transform (NTT) has a significant impact on the performance of emerging cryptosystems, such as fully homomorphic encryption. To better explain NTT algorithms with arbitrary size, radix, order, etc., we introduce the binary subscript representation (BSR), presented by a series of binary strings based on input and output subscripts. By proving bit exchanges of subscripts and the lifespan of twiddle factors, BSR enables a rapid understanding of data flow within each stage and every multiplication, thereby describing how NTT algorithms transform input coefficients into output coefficients. After exploring the design space described by BSR, we propose a pipelined NTT algorithm, possessing the abilities to (i) support NTT and inverse NTT at run-time without internal data rerouting nor external data reordering, (ii) reduce the memory storage of twiddle factors by roughly 50%, (iii) simplify most of the modular multiplications as Shoup modular multiplications, (iv) optimize the modular division over coefficient size N. Later, we implement the algorithm on two pipelined architectures: serial commutator (SC) and multi-path delay commutator (MDC). Along with 212/214 coefficients and 32/64-bit modulus, we totally generate 8 NTT designs. Experimental results demonstrate the advantages of our proposed NTT. For instance, our proposed 212-coefficient 64-bit MDC NTT saves 63.74% area/throughput, compared with state-of-art designs.

  • Exploration of Karatsuba Algorithm for Efficient Barrett Modular Multiplication

    by Bo Zhang, Mingzhe Zhang, Shoumeng Yan

    As a key operation in contemporary cryptosystems, modular multiplication (MM) occupies non-negligible latency and area. We first show optimizations of the k-term Karatsuba algorithm for $ \lfloor AB/r^{k} \rfloor $ and $AB \text {mod}~r^{k}$ that play a significant role in MM. We prove the bijective mapping between $ \lfloor AB/r^{k} \rfloor $ and $AB \text {mod}~r^{k}$ , and propose four methods to build efficient Karatsuba multiplications with arbitrary k values. For $k\in [{1, 32}]$ , the multiplication cost for $ \lfloor AB/r^{k} \rfloor $ and $AB \text {mod}~r^{k}$ is 25.04% less than that for AB on average. Furthermore, we investigate the correlation between operand bitwidth N of MM and decomposition factor k of the Karatsuba algorithm. Karatsuba multiplication with a larger k needs less area in the multiplication phase, but also has a more complex implementation in the evaluation and interpolation phases. Experimental results for Barrett MM with $N=32$ , 64, 128, 256 and $k=1$ , 2, 4, 8 show that MM achieves the minimal area when $N/k=32$ . For instance, our proposed design when $N=256$ saves 21.57% area and 25.71% area/throughput, compared with state-of-art designs.


  • Area-Efficient Barrett Modular Multiplication With Optimized Karatsuba Algorithm

    by Bo Zhang, Shoumeng Yan

    This paper presents an area-efficient Barrett Modular Multiplication (BMM) algorithm, facilitating the development of cryptosystems like fully homomorphic encryption. Instead of implementing three normal multiplications required by classic BMM, our proposed BMM introduces optimizations for multiplication AB, truncated multiplication AB/2f, and modular multiplication ABmod2f. Taking the 4-term Karatsuba algorithm as an example, an N-bit multiplication AB can be decomposed into 9 (N/4)-bit multiplications. Our optimized approaches for truncated multiplication and modular multiplication require an area equivalent to only 6.5 (N/4)-bit multiplications when f≈N. Furthermore, our optimized Karatsuba multiplications introduce efficient (E, I) matrix pairs, circumventing area overhead from complex I matrices and sign extension in multiplication. We also employ Encode algorithm to eliminate many additions needed in BMM and inside multiplications, significantly shortening critical path. Experimental results demonstrate the advantages of our proposed BMM in terms of throughput and area efficiency.


  • Design of a High-Performance Iterative Barrett Modular Multiplier for Crypto Systems

    by Bo Zhang, Zeming Cheng, Massoud Pedram

    Modular multiplication (MM) is a fundamental operation in many cryptographic and arithmetic applications. In this article, we present an improved Barrett modular multiplication (BMM) algorithm and its hardware-efficient implementation. The proposed algorithm leverages parallel computation of quotient and intermediate results, enhancing overall efficiency. To further optimize the algorithm, two optimizations are introduced, replacing expensive multiplications and additions with more efficient compression and encoding operations at each iteration. We first introduce a novel data model that enables the use of a 2-bit adder to handle potential overflow in signed addition. Moreover, by employing a 3-bit addition on intermediate results, we eliminate the need for complete round operations while ensuring the desired result range. The experimental results demonstrate significant improvements in terms of area and computation time compared to existing classic BMM and Montgomery modular multiplication (MMM) designs. Our improved BMM outperforms these designs, particularly in high-radix scenarios. This work provides a valuable contribution to the field of MM, offering a hardware-efficient solution for achieving improved performance in cryptographic and arithmetic systems.


  • A High-Performance, Conflict-Free Memory-Access Architecture for Modular Polynomial Multiplication

    by Zeming Cheng, Bo Zhang, Massoud Pedram

    In this article, we present the HiCoP architecture, a high-performance, conflict-free memory access, modular polynomial multiplication design that accelerates the number-theoretic transform (NTT), inverse NTT (INTT), and modular polynomial multiplications. To optimize hardware costs, the HiCoP architecture utilizes a high-radix reconfigurable butterfly unit (RBU) that can be dynamically configured to perform NTT, INTT, and point-wise multiplications, alongside an area-efficient Montgomery modular multiplier (MMM) tailored for NTT-friendly modulus. Moreover, by integrating pre-processing, post-processing, and Montgomery domain transformations into NTT and INTT operations, we effectively minimize the cycle count for modular polynomial multiplication. Additionally, we propose a novel conflict-free memory access algorithm that simplifies the control logic and eliminates the need for ping-pong memory in the HiCoP architecture. Experimental results of modular polynomial multiplications demonstrate significant performance gains for the HiCoP architecture implemented on the Xilinx Virtex-7 field-programmable gate array (FPGA) platform, with up to $8.75\times $ , $4.15\times $ , $10.57\times $ , and $8.50\times $ improvements in throughput-to-hardware-cost ratio for LUT count, FF count, BRAM count, and DSP count, respectively.


  • Striking a Good Balance Between Area and Throughput of RSFQ Circuits Containing Feedback Loops

    by Mingye Li, Bo Zhang, Massoud Pedram

    Electronic design automation solutions are being developed to support the synthesis and physical design optimization of Rapid Single Flux Quantum (RSFQ) logic circuits with hundreds of thousands of logic cells. The clocked feature of synchronous RSFQ cells results in gate-level pipelined designs, requiring a large number of path-balancing D-flipflops (DFFs). In addition, one also faces the challenge of maintaining high throughput for RSFQ circuits containing feedback loops. To enforce the coincidence of the input and feedback patterns, one can apply a new input pattern every $L$ cycles, where $L$ is the length of the feedback loop. Consequently, the throughput of circuits with feedback loops is only $1/L$ of the clock frequency. In this paper, we present two methods to improve the performance and area of RSFQ circuits, especially targeting circuits with feedback loops: (i) An area-oriented optimization method that removes the path-balancing DFFs by capturing and repeating input patterns. (ii) A throughput-oriented optimization method that enables an RSFQ circuit to receive and correctly process an input pattern every clock cycle. For a large circuit such as S526 in the ISCAS89 benchmark circuits, the circuit can initially receive an input pattern only every 9 cycles. As a result of applying our area-oriented optimization, the circuit admits 33% fewer logic cells while receiving input patterns every 11 cycles. Alternatively, our throughput-oriented optimization yields a circuit that can receive new input patterns on every cycle with nearly the same cell count.


  • An Iterative Montgomery Modular Multiplication Algorithm With Low Area-Time Product

    by Bo Zhang, Zeming Cheng, Massoud Pedram

    This paper presents a highly efficient iterative Montgomery modular multiplication algorithm, wherein the computations of quotient and intermediate result in each iteration are done in parallel. This parallelism breaks the data dependency and thus reduces the computation latency. Moreover, this paper replaces required multiplications and additions in each iteration with compressions and encoding, thereby achieving a computation latency of order $d+6$ where $d=\left\lceil N/m \right\rceil +2$ is the number of iterations, $N$ denotes the bitwidth of modulus $M$ , and $m$ is the number of bits of the multiplier that are processed in each iteration of the algorithm. Hardware realization of the proposed Montgomery modular multiplication on a Xilinx Virtex-7 FPGA device shows $> 41\%$ computation latency saving and $>31\%$ area saving when $N=1,024$ and $m=8$ , compared with the best of previous state-of-art references. These savings amount to more than 63% reduction in terms of the area-latency product metric.


  • Metastability in Superconducting Single Flux Quantum (SFQ) Logic

    by Gourav Datta, Yunkun Lin, Bo Zhang, Peter A. Beerel

    Superconducting digital electronics, especially Single Flux Quantum (SFQ), has emerged as a promising beyond-CMOS technology with Josephson junctions (JJ) as the active device. It has the potential to meet the booming demands of lower power consumption and higher operation speeds in the electronics industry and future exascale supercomputing systems. Despite these promises, scaling SFQ circuits remains a serious challenge that motivates the support of multiple SFQ clock domains. Towards this end, this paper analyzes the impact of setup time violations and metastability in SFQ circuits comparing the derived analytical models to their CMOS counterparts. It also proposes new techniques to reduce the average latency in metastability-tolerant SFQ synchronizers, and evaluates their effects on the layout and critical margin of the design. It further extends the proposed model to estimate the Mean Time Between Failure (MTBF) of flip-flop-based synchronizers and shows that their MTBF with the current feature sizes is unaffected by noise, similar to CMOS. Finally, it curve fits this model to simulations using the state-of-the-art SFQ5ee process and shows that a two-flop SFQ synchronizer with a clock frequency of 25 GHz has an estimated MTBF of ~10 6 years.


  • High-Radix Design of a Scalable Montgomery Modular Multiplier With Low Latency

    by Bo Zhang, Zeming Cheng, Massoud Pedram

    The proposed herein is a scalable high-radix (i.e., $2^m$ ) Montgomery Modular (MM) Multiplication circuit replacing the integer multiplications in each iteration of the Montgomery MM algorithm (related to the product of $m$ bits of the multiplier and the multiplicand) with carry-save compressions and completely eliminating costly multiplications. Furthermore, the proposed Montgomery MM decomposes the multiplicand itself using a radix of $2^w$ with $w\geq 2m$ , thereby achieving a scalable design, which can deliver an issue latency of one cycle and a cycle (count) latency of $O(N^2/(wmp))$ where $p$ denotes the number of available processing elements, each of which is designed to complete the above iteration by computing in part the product of $w$ bits of the multiplicand and $m$ bits of the multiplier. The area complexity of the proposed Montgomery MM is $O(wmp)$ , and thus, the Area-Latency-Product complexity is $O(N^{2})$ .


  • Postrouting Optimization of the Working Clock Frequency of Single-Flux-Quantum Circuits

    by Ting-Ru Lin, Bo Zhang, Massoud Pedram

    With the emergence of large-scale single-flux-quantum (SFQ) circuits, it is highly expected to offload heavy routing tasks to electronic design automation (EDA) tools. The unique characteristic of SFQ circuits is that large clock distribution topologies are generally required to pass clock signals to clocked cells with a fanout limitation for signal evaluation and state transition. The large clock distribution topologies and the fanout limitation pose a great challenge to control clock skew and path delays of an SFQ circuit during the routing step. The values of clock skew and path delays determine not only maximum working frequencies but also hold time violations. However, it is not necessary to develop a timing-driven routing tool specifically for SFQ circuits from scratch because the number of the paths related to frequencies and hold time violations is generally very small. Thus, we present a novel post-routing optimization framework which complements routing tools through reducing path lengths for working frequencies and meandering paths for hold time violations. A framework is developed in which machine learning is applied to analyze wire distributions and then a maze routing algorithm is performed to re-route targeted paths. Based on the MIT-LL SFQ5ee process technology, we demonstrate that the our framework can improve the maximum working frequency by 7% on average over the state-of-the-art EDA routing tool for 14 SFQ circuits while fixing all hold time violations in 180 seconds.