When designing arithmetic circuits, the multiplication of a variable by a constant number can be performed by a series of add/subtract, and shift operations instead of a multiplication (e.g., 7x = 23x – x = (x << 3) – x). This allows for significant reductions in complexity of multiplication circuits, as adders are typically much more hardware-efficient than a generic multiplier, and shift operations can be performed without any overhead by appropriately connecting the concerned signals. This concept extends to the multiplication of a constant matrix by a vector of variables, known as constant matrix multiplication (CMM). So far, there exists no way of discovering CMM algorithms with provably minimal add/subtract count. Here we show how the CMM problem can be reduced to a series of Boolean Satisfiability (SAT) problems, enabling the use of powerful SAT solvers to determine optimal solutions for arbitrary matrices. Modeling the problem in a closed mathematical framework allows us to straightforwardly extend our algorithm towards secondary objectives, namely word-size reductions of the add/subtract operations and pipelining for throughput maximization. Compared to state-of-the-art heuristic methods we are consistently able to achieve improvements regarding the resulting implementation complexity, even for small but practical matrix sizes such as 2 x 2 or 3 x 3. These results enable a reduction in implementation costs for a wide range of practical applications such as digital filters, convolutional cores in artificial neural networks, or the multiplication by complex constants in discrete transforms like the Fast Fourier Transform.

Multiplexers (MUX) are essential elements in FieldProgrammable Gate Arrays (FPGA), widely used in practical applications. Due to the LUT-based architecture of FPGAs, multiplexers that switch among many signals or operate on large word sizes incur significant resource costs, as these costs scale linearly with the data word size. Vivado's automatic synthesis flow often produces sub-optimal MUX implementations, necessitating hand-crafted solutions to minimize resource overhead. Here, we present three MUX implementation schemes that reduce resource usage for various input signal counts. These optimizations enable enhanced resource efficiency in applications ranging from circuits generated by High-Level Synthesis (HLS) tools to optimized digital filters and artificial neural networks.

Modulo scheduling is a highly effective approach for maximizing throughput in loops with static memory dependencies, interleaving computations across consecutive loop iterations. Despite substantial advancements in scheduling procedures, it remains the most computationally intensive phase for high-level synthesis flows. A recent approach encodes the modulo scheduling problem as a series of Boolean satisfiability (SAT) instances, capitalizing on the efficiency of modern SAT solvers. This approach significantly reduces solving time and increases the availability of throughput-optimal solutions compared to integer linear programming-based algorithms. This work introduces two enhancements for SAT-based modulo scheduling: (i) an algorithm to rapidly calculate a lower bound for the schedule length, improving the identification of latency-optimal schedules; and (ii) a streamlined SAT formulation with fewer clauses, facilitating quicker solver decisions. Extensive experimental evaluations show that these improvements lead to an increased number of throughput-optimal and latency-optimal solutions.

The end of Moore’s law and Dennard scaling emphasizes the need for application-specific computing architectures to achieve high resource and energy efficiency and real-time performance. The concept of a silicon compiler remains an enduring aspiration for design time reduction. In order to generate hardware implementations at register transfer level from behavioral descriptions, design automation tools must address challenging and interdependent problems, including allocation, scheduling, and binding. Additionally, manual intervention by the user is necessary to balance the resources vs. performance tradeoff via, for example, function inlining or loop unrolling/pipelining. Existing approaches typically solve these problems sequentially, compromising optimality in favor of simplicity and runtime. Here we show how to model the whole model-based design flow as one holistic integer linear programming (ILP) formulation aiming at consistently deriving the optimal microarchitecture for any given application. Incorporating clock gating minimizes the number of useless operations with negligible resource overhead (if any), while always guaranteeing optimal throughput. The unified nature of the proposed ILP model enables implementations unmatched by state-of-the-art approaches in terms of resource efficiency and measured power consumption. These results facilitate a streamlined design flow for highly optimized embedded systems in the context of model-based design.

Multiplierless constant multiplication using bit-shifts, additions and subtractions has been an active research topic in the last decades. The multiplication with multiple constants, known as the multiple constant multiplication (MCM) problem, is of special interest because of its practical relevance, notably for digital filter implementation. In this work we propose to use the speed of modern Boolean satisfiability (SAT) solvers to find fast and optimal solutions. The solutions are optimal either with respect to the adder count or the bit level cost. In contrast to previous approaches, we also consider negative fundamentals that are sometimes cheaper to realize than their positive counterparts leading to more compact hardware implementations. Our experiments show that our approach is able to find optimal single constant multiplication (SCM) and MCM circuits for practically relevant test instances in reasonable time. We also prove the necessity for the post-add right shift operation for SCM. Using our SAT formulation to enumerate all possible implementations for some of our test instances we show the importance of considering bit-level costs and negative fundamentals when solving MCM problems.

Modulo scheduling is the premier technique for throughput maximization of loops in high-level synthesis by interleaving consecutive loop iterations. The number of clock cycles between data insertions is called the initiation interval (II). For throughput maximization, this value should be as low as possible; therefore, its minimization is the main optimization goal. Despite its long historical existence, modulo scheduling always remained a relevant research topic over the years with many exact and heuristic algorithms available in the literature. Nevertheless, we are able to leverage the scalability of modern Boolean Satisfiability (SAT) solvers to outperform state-of-the-art ILP-based algorithms for latency-optimal modulo scheduling for both integer and rational IIs. Our algorithm is able to compute valid modulo schedules for the whole CHStone and MachSuite benchmark suites, with 99% of the solutions being proven to be throughput optimal for a timeout of only 10 minutes per candidate II. For various time limits, not a single tested scheduler from the state of the art is able to compute more verified optimal solutions or even a single schedule with a higher throughput than our proposed approach. Using an HLS toolflow, we show that our algorithm can be effectively used to generate Pareto-optimal FPGA implementations regarding throughput and resource usage.

Modulo scheduling is a commonly used high-level synthesis (HLS) technique to maximize throughput by overlapping the computation of consecutive loop iterations [1] – [5] . For maximum throughput, the number of cycles to wait between successive sample insertions (called initiation interval, II) should be as low as possible.

In order to provide high throughput for custom hardware implementations, academic and commercial high-level synthesis (HLS) tools use loop pipelining by modulo scheduling. When provided a resource allocation and a schedule, the binding algorithm can be used to reduce the number of required lifetime registers (LR) and multiplexers (MUX). Contrary to non-modulo schedules, optimal solutions to the binding problem for implementing modulo schedules with respect to minimizing required LRs and MUXs have not been published. To address this topic, we propose a novel optimal binding algorithm to simultaneously minimize MUX and LR costs for loop pipelining using Integer Linear Programming. We evaluated our algorithm on a set of commonly used benchmark instances from digital signal processing and report that all encountered problems could be solved, with 36.53% of the solutions being optimal within a time limit of only five minutes. Compared to worst case evaluations, we report MUX and LR savings of up to 42.74% and 26.62%, respectively. To evaluate the impact on the resulting circuit after place and route, we studied FPGA implementations of several benchmark instances and recorded look-up table and flip-flop reductions of up to 13.70% and 5.24%, respectively, compared to previous work and to an extensive set of randomly generated bindings when state-of-the-art algorithms fail to find a feasible solution.

Compared to integer initiation intervals (II), rational IIs improve throughput achieved by loop pipelining in many cases. This comes at the expense of a higher need for data path elements (i.e., multiplexers and registers) and the need for solving more complex scheduling problems. To optimally solve these problems, we improved an existing ILP formulation for latency-optimal modulo scheduling with rational IIs that now finds 6.08x more solutions and 6.10x as many optimal ones within the same time budget. Compared to the best alternative from previous work, our improved algorithm finds 1.15x more solutions and 2.97x as many optimal ones.

A well-known approach for generating custom hardware with high throughput and low resource usage ismodulo scheduling, in which the number of clock cycles between successive inputs [the initiation interval (II)] can be lower than the latency of the computation. The II is traditionally aninteger, but in this article, we explore the benefits of allowing it to be arationalnumber. A rational II can be interpreted as theaveragenumber of clock cycles between successive inputs. Since the minimum rational II can be less than the minimum integer II, higher throughput is possible; moreover, allowing rational IIs gives more options in a design-space exploration. We formulate rational-II modulo scheduling as an integer linear programming (ILP) problem that is able to find latency-optimal schedules for a fixed rational II. We also propose two heuristic approaches that make rational-II scheduling more feasible: one based on identifying strongly connected components in the data-flow graph, and one based on iteratively relaxing the target II until a solution is found. We have applied our methods to a standard benchmark of hardware designs, and our results demonstrate an average speedup with respect to II of$1.24\times $in 35% of the encountered scheduling problems compared to state-of-the-art formulations.