Optimal and heuristic approaches to modulo scheduling with rational initiation intervals in hardware synthesis
File(s)
Accepted version
Author(s)
Sittel, Patrick
Fiege, Nicolai
Wickerson, John
Zipf, Peter
Type
Journal Article
Abstract
A well-known approach for generating custom hardware with high throughput and low resource usage is modulo 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 an integer, but in this paper, we explore the benefits of allowing it to be a rational number. A rational II can be interpreted as the average number 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 w.r.t. II of 1.24× in 35% of the encountered scheduling problems compared to state-of-the-art formulations.
Date Issued
2022-03-01
Date Acceptance
2021-02-10
Citation
IEEE Transactions on Computer - Aided Design of Integrated Circuits and Systems, 2022, 41 (3), pp.614-627
ISSN
0278-0070
Publisher
Institute of Electrical and Electronics Engineers
Start Page
614
End Page
627
Journal / Book Title
IEEE Transactions on Computer - Aided Design of Integrated Circuits and Systems
Volume
41
Issue
3
Copyright Statement
© 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Subjects
Computer Hardware & Architecture
0906 Electrical and Electronic Engineering
1006 Computer Hardware
Publication Status
Published
Date Publish Online
2021-02-18