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.

In modulo scheduling, the number of clock cycles between successive inputs (the initiation interval, II) is traditionally an integer, but in this paper, we explore the benefits of allowing it to be a rational number. This rational II can be interpreted as the average number of clock cycles between successive inputs. As the minimum rational II can be less than the minimum integer II, this translates to higher throughput. 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 have applied our scheduler to a standard benchmark of hardware designs, and our results demonstrate a significant speedup compared to state-of-the-art integer-II and rational-II formulations.

A key element for achieving high throughput, e.g. circuits generated with high-level synthesis (HLS) methods and model-based hardware design, is the use of modulo scheduling. Integer linear programming (ILP)-based modulo schedulers are capable of computing schedules that are optimal regarding throughput and latency, while keeping run times to practically usable lengths. However, the generated schedules may lead to an excessive number of registers for storing intermediate values. We propose extensions for ILP-based modulo scheduling that minimizes these registers. The ILP formulation incorporates the elimination of redundant registers by post binding optimization. Extensive experiments on different benchmark sets show average register reductions of 30.4% compared to commonly used minimum lifetime approaches that reduce register requirements. This comes without any loss in throughput or latency and with less than 4% additional scheduling run time compared to state-of-the-art ILP-based modulo schedulers.

Hardware applications in an industrial context often have tight area, latency and throughput requirements or a specific combination thereof. This paper presents a method to improve area and throughput figures for folded circuits generated during a model-based hardware design process. The method targets FPGA implementations and is based on the automatic combination of isomorphic subgraphs and the detailed consideration of pipelined primitive operations for folding core scheduling. In the course of a design space exploration, the user is provided with fine-grain control over the area/throughput trade-off.