1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
\documentclass[acmsmall,screen]{acmart}\settopmatter{}
%% Bibliography style
\bibliographystyle{ACM-Reference-Format}
%% Citation style
\citestyle{acmauthoryear}
%%% The following is specific to OOPSLA '21 and the paper
%%% 'Formal Verification of High-Level Synthesis'
%%% by Yann Herklotz, James D. Pollard, Nadesh Ramanathan, and John Wickerson.
%%%
\setcopyright{rightsretained}
\acmPrice{}
\acmDOI{10.1145/3485494}
\acmYear{2021}
\copyrightyear{2021}
\acmSubmissionID{oopsla21main-p86-p}
\acmJournal{PACMPL}
\acmVolume{5}
\acmNumber{OOPSLA}
\acmArticle{117}
\acmMonth{10}
\usepackage{amsmath}
\usepackage{booktabs}
\usepackage{mathpartir}
\usepackage{pgfplots}
\usepackage{pgfplotstable}
\usepackage{soul}
\usepackage{subcaption}
\usepackage{tikz}
\usepackage{minted}
\usepackage{microtype}
\usepackage{tikz-timing}
\usepackage[normalem]{ulem}
\usetikzlibrary{shapes,calc,arrows.meta}
\usetikzlibrary{pgfplots.groupplots}
\pgfplotsset{compat=1.16}
\setminted{fontsize=\small}
\usemintedstyle{manni}
\newif\ifANONYMOUS
\ANONYMOUSfalse
\newif\ifCOMMENTS
\COMMENTSfalse
\newcommand{\Comment}[3]{\ifCOMMENTS\textcolor{#1}{{\bf [\![#2:} #3{\bf ]\!]}}\fi}
\newcommand\JW[1]{\Comment{red!75!black}{JW}{#1}}
\newcommand\YH[1]{\Comment{green!50!blue}{YH}{#1}}
\newcommand\JP[1]{\Comment{blue!50!black}{JP}{#1}}
\newcommand\NR[1]{\Comment{blue}{NR}{#1}}
\newcommand\JWcouldcut[1]{{\st{#1}}}
\newcommand\NRcouldcut[1]{{\st{#1}}}
\newcommand\NRreplace[2]{{\st{#1} \NR{#2}}}
\newcommand\JWreplace[2]{{\st{#1} \JW{#2}}}
\definecolor{compcert}{HTML}{bebada}
\definecolor{formalhls}{HTML}{8dd3c7}
\definecolor{keywordcolour}{HTML}{8f0075}
\definecolor{functioncolour}{HTML}{721045}
\definecolor{constantcolour}{HTML}{0000bb}
\newcommand\yhkeywordsp[1]{\;\;\texttt{\textcolor{keywordcolour}{#1}}}
\newcommand\yhkeyword[1]{\texttt{\textcolor{keywordcolour}{#1}}}
\newcommand\yhfunctionsp[1]{\;\;\texttt{\textcolor{functioncolour}{#1}}}
\newcommand\yhfunction[1]{\texttt{\textcolor{functioncolour}{#1}}}
\newcommand\yhconstant[1]{\texttt{\textcolor{constantcolour}{#1}}}
\ifANONYMOUS
\newcommand{\vericert}{HLS\-Cert}
\else
\newcommand{\vericert}{Veri\-cert}
\fi
\newcommand{\compcert}{Comp\-Cert}
\newcommand{\legup}{Leg\-Up}
\newcommand{\slowdownOrig}{27}
\newcommand{\slowdownDiv}{2}
\newcommand{\areaIncr}{1.1}
\def\polybench{PolyBench/C}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem*{remark}{Remark}
\begin{document}
\title{Formal Verification of High-Level Synthesis}
%% Author with single affiliation.
\author{Yann Herklotz}
\orcid{0000-0002-2329-1029}
\affiliation{
\institution{Imperial College London}
\country{UK}
}
\email{yann.herklotz15@imperial.ac.uk}
\author{James D. Pollard}
\orcid{0000-0003-1404-1527}
\affiliation{
\institution{Imperial College London}
\country{UK}
}
\email{jamespollard@acm.org}
\author{Nadesh Ramanathan}
\orcid{0000-0001-9083-8349}
\affiliation{
\institution{Imperial College London}
\country{UK}
}
\email{n.ramanathan@ieee.org}
\author{John Wickerson}
\orcid{0000-0001-6735-5533}
\affiliation{
\institution{Imperial College London}
\country{UK}
}
\email{j.wickerson@imperial.ac.uk}
\begin{abstract}
High-level synthesis (HLS), which refers to the automatic compilation of software into hardware, is rapidly gaining popularity. In a world increasingly reliant on application-specific hardware accelerators, HLS promises hardware designs of comparable performance and energy efficiency to those coded by hand in a hardware description language such as Verilog, while maintaining the convenience and the rich ecosystem of software development. However, current HLS tools cannot always guarantee that the hardware designs they produce are equivalent to the software they were given, thus undermining any reasoning conducted at the software level. Furthermore, there is mounting evidence that existing HLS tools are quite unreliable, sometimes generating wrong hardware or crashing when given valid inputs.
To address this problem, we present the first HLS tool that is mechanically verified to preserve the behaviour of its input software. Our tool, called \vericert{}, extends the \compcert{} verified C compiler with a new hardware-oriented intermediate language and a Verilog back end, and has been proven correct in Coq. \vericert{} supports most C constructs, including all integer operations, function calls, local arrays, structs, unions, and general control-flow statements. An evaluation on the \polybench{} benchmark suite indicates that \vericert{} generates hardware that is around an order of magnitude slower (only around 2$\times$ slower in the absence of division) and about the same size as hardware generated by an existing, optimising (but unverified) HLS tool.
\end{abstract}
\begin{CCSXML}
<ccs2012>
<concept>
<concept_id>10010583.10010682.10010684</concept_id>
<concept_desc>Hardware~High-level and register-transfer level synthesis</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10011007.10011074.10011099.10011692</concept_id>
<concept_desc>Software and its engineering~Formal software verification</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10003752.10010124.10010138.10010142</concept_id>
<concept_desc>Theory of computation~Program verification</concept_desc>
<concept_significance>500</concept_significance>
</concept>
</ccs2012>
\end{CCSXML}
\ccsdesc[500]{Hardware~High-level and register-transfer level synthesis}
\ccsdesc[500]{Software and its engineering~Formal software verification}
\ccsdesc[500]{Theory of computation~Program verification}
%% Keywords
%% comma separated list
\keywords{\compcert{}, Coq, high-level synthesis, C, Verilog}
\maketitle
\input{introduction}
\input{algorithm}
\input{verilog}
\input{proof}
\input{evaluation}
\input{related}
\input{limitations}
\input{conclusion}
\begin{acks}
We would like to thank Sandrine Blazy, Jianyi Cheng, Alastair Donaldson, Andreas Lööw, and the
anonymous reviewers for their helpful feedback. This work was financially supported by the EPSRC
via the Research Institute for Verified Trustworthy Software Systems (VeTSS) and the IRIS
Programme Grant (EP/R006865/1).
\end{acks}
%% Bibliography
\bibliography{references.bib}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% TeX-command-extra-options: "-shell-escape"
%%% End:
|
