summaryrefslogtreecommitdiffstats
path: root/introduction.tex
diff options
context:
space:
mode:
authorJohn Wickerson <j.wickerson@imperial.ac.uk>2021-04-13 18:55:42 +0000
committeroverleaf <overleaf@localhost>2021-04-13 19:02:01 +0000
commitc39385507d8b9cf5d042d28b454d07272a7eaeb8 (patch)
tree60a2ccc99b683ac35d555a561931a67aa4d26d15 /introduction.tex
parent065d45676981dfbc34beb805d2d9eaa6108cabfd (diff)
downloadoopsla21_fvhls-c39385507d8b9cf5d042d28b454d07272a7eaeb8.tar.gz
oopsla21_fvhls-c39385507d8b9cf5d042d28b454d07272a7eaeb8.zip
Update on Overleaf.
Diffstat (limited to 'introduction.tex')
-rw-r--r--introduction.tex8
1 files changed, 4 insertions, 4 deletions
diff --git a/introduction.tex b/introduction.tex
index d752d6c..98c408d 100644
--- a/introduction.tex
+++ b/introduction.tex
@@ -21,20 +21,20 @@ Indeed, there are reasons to doubt that HLS tools actually \emph{do} always pres
%Other reasons are more specific:
For instance, Vivado HLS has been shown to apply pipelining optimisations incorrectly\footnote{\url{https://bit.ly/vivado-hls-pipeline-bug}} or to silently generate wrong code should the programmer stray outside the fragment of C that it supports.\footnote{\url{https://bit.ly/vivado-hls-pointer-bug}}
Meanwhile, \citet{lidbury15_many_core_compil_fuzzin} had to abandon their attempt to fuzz-test Altera's (now Intel's) OpenCL compiler since it ``either crashed or emitted an internal compiler error'' on so many of their test inputs.
-And more recently, \citet{du21_fuzzin_high_level_synth_tools} fuzz-tested three commercial HLS tools using Csmith~\cite{yang11_findin_under_bugs_c_compil}, and despite restricting the generated programs to the C fragment explicitly supported by all the tools, they still found that on average 2.5\% of test cases generated a design that did not match the behaviour of the input.
+More recently, \citet{du21_fuzzin_high_level_synth_tools} fuzz-tested three commercial HLS tools using Csmith~\cite{yang11_findin_under_bugs_c_compil}, and despite restricting the generated programs to the C fragment explicitly supported by all the tools, they still found that on average 2.5\% of test cases generated a design that did not match the behaviour of the input.
\paragraph{Existing workarounds}
Aware of the reliability shortcomings of HLS tools, hardware designers routinely check the generated hardware for functional correctness. This is commonly done by simulating the design against a large test-bench. But unless the test-bench covers all inputs exhaustively, which is often infeasible, there is a risk that bugs remain.
-An alternative is to use \emph{translation validation} to prove the input and output equivalent~\cite{pnueli98_trans}. Translation validation has been successfully applied to several HLS optimisations~\cite{kim04_autom_fsmd,karfa06_formal_verif_method_sched_high_synth,chouksey20_verif_sched_condit_behav_high_level_synth,banerjee14_verif_code_motion_techn_using_value_propag,chouksey19_trans_valid_code_motion_trans_invol_loops}.
-But translation validation must be repeated every time the compiler is invoked, and it is an expensive task, especially for large designs.
+An alternative is to use \emph{translation validation}~\cite{pnueli98_trans} to prove the input and output equivalent. Translation validation has been successfully applied to several HLS optimisations~\cite{kim04_autom_fsmd,karfa06_formal_verif_method_sched_high_synth,chouksey20_verif_sched_condit_behav_high_level_synth,banerjee14_verif_code_motion_techn_using_value_propag,chouksey19_trans_valid_code_motion_trans_invol_loops}.
+But translation validation is an expensive task, especially for large designs, and it must be repeated every time the compiler is invoked.
For example, the translation validation for Catapult C~\cite{mentor20_catap_high_level_synth} may require several rounds of expert `adjustments'~\cite[p.~3]{slec_whitepaper} to the input C program before validation succeeds. And even when it succeeds, translation validation does not provide watertight guarantees unless the validator itself has been mechanically proven correct, which is seldom the case.
Our position is that none of the above workarounds are necessary if the HLS tool can simply be trusted to work correctly.
\paragraph{Our solution}
-We have designed a new HLS tool in the Coq theorem prover~\cite{bertot04_inter_theor_provin_progr_devel} and proved that any output it produces always has the same behaviour as its input. Our tool, called \vericert{},\ifANONYMOUS\footnote{Tool name has been changed for blind review.}\fi{} is automatically extracted to an OCaml program from Coq, which ensures that the object of the proof is the same as the implementation of the tool. \vericert{} is built by extending the \compcert{} verified C compiler~\cite{leroy09_formal_verif_realis_compil} with a new hardware-specific intermediate language and a Verilog back end. It supports all C constructs except for case statements, function pointers, recursive function calls, integers larger than 32 bits, floats, and global variables.
+We have designed a new HLS tool in the Coq theorem prover \JW{I think Coq is so standard that it doesn't need a citation (like you don't cite the C programming language, for instance).}~\cite{bertot04_inter_theor_provin_progr_devel} and proved that any output it produces always has the same behaviour as its input. Our tool, called \vericert{},\ifANONYMOUS\footnote{Tool name has been changed for blind review.}\fi{} is automatically extracted to an OCaml program from Coq, which ensures that the object of the proof is the same as the implementation of the tool. \vericert{} is built by extending the \compcert{} verified C compiler~\cite{leroy09_formal_verif_realis_compil} with a new hardware-specific intermediate language and a Verilog back end. It supports all C constructs except for case statements, function pointers, recursive function calls, integers larger than 32 bits, floats, and global variables.
\paragraph{Contributions and Outline}
The contributions of this paper are as follows: