17 research outputs found
Artifact for: HaliVer: Deductive Verification and Scheduling Languages Join Forces
No full text<p>These are the experiments conducted with HaliVer. This artifact is prepared together with the <a href="https://zenodo.org/records/7113223">TACAS 23 Artifact Evaluation VM - Ubuntu 22.04 LTS.</a></p><p>It allows you the run the experiments of the paper `HaliVer: Deductive Verification and Scheduling Languages Join Forces`.</p><p>It also contains a tutorial on how to work with HaliVer itself.</p>
Artifact for: HaliVer: Deductive Verification and Scheduling Languages Join Forces
No full text<p>These are the experiments conducted with HaliVer. This artifact is prepared together with the <a href="https://zenodo.org/records/7113223">TACAS 23 Artifact Evaluation VM - Ubuntu 22.04 LTS.</a></p><p>It allows you the run the experiments of the paper `HaliVer: Deductive Verification and Scheduling Languages Join Forces`.</p><p>It also contains a tutorial on how to work with HaliVer itself.</p>
Artifact for: HaliVer: Deductive Verification and Scheduling Languages Join Forces
No full text<p>These are the experiments conducted with HaliVer. This artifact is prepared together with the <a href="https://zenodo.org/records/7113223">TACAS 23 Artifact Evaluation VM - Ubuntu 22.04 LTS.</a></p><p>It allows you the run the experiments of the paper `HaliVer: Deductive Verification and Scheduling Languages Join Forces`.</p><p>It also contains a tutorial on how to work with HaliVer itself.</p>
Formal Methods for GPGPU Programming: Is the Demand Met?
Full text linkOver the years, researchers have developed many formal method tools to support software development. However, hardly any studies are conducted to determine whether the actual problems developers encounter are sufficiently addressed. For the relatively young field of GPU programming, we would like to know whether the tools developed so far are sufficient, or whether some problems still need attention. To this end, we first look at what kind of problems programmers encounter in OpenCL and CUDA. We gather problems from Stack Overflow and categorise them with card sorting. We find that problems related to memory, synchronisation of threads, threads in general and performance are essential topics. Next, we look at (verification) tools in industry and research, to see how these tools addressed the problems we discovered. We think many problems are already properly addressed, but there is still a need for easy to use sound tools. Alternatively, languages or programming styles can be created, that allows for easier checking for soundness
HaliVer: Deductive Verification and Scheduling Languages Join Forces
No full textThe HaliVer tool integrates deductive verification into the popular scheduling language Halide, used for image processing pipelines and array computations. HaliVer uses Vercors, a separation logic-based verifier, to verify the correctness of (1) the Halide algorithms and (2) the optimised parallel code produced by \halide when an optimisation schedule is applied to the algorithm. This allows proving complex, optimised code correct while reducing the effort to provide the required verification annotations. For both approaches, the same specification is used. We evaluated the tool on several optimised programs generated from characteristic Halide algorithms, using all but one of the essential scheduling directives available in Halide. Without annotation effort, Haliver proves memory safety in almost all programs. With annotations Haliver, additionally, proves functional correctness properties. We show that the approach is viable and reduces the manual annotation effort by an order of magnitude
HaliVer: Deductive Verification and Scheduling Languages Join Forces
Full text linkThe HaliVer tool integrates deductive verification into the popular
scheduling language Halide, used for image processing pipelines and array
computations. HaliVer uses Vercors, a separation logic-based verifier, to
verify the correctness of (1) the Halide algorithms and (2) the optimised
parallel code produced by \halide when an optimisation schedule is applied to
the algorithm. This allows proving complex, optimised code correct while
reducing the effort to provide the required verification annotations. For both
approaches, the same specification is used. We evaluated the tool on several
optimised programs generated from characteristic Halide algorithms, using all
but one of the essential scheduling directives available in Halide. Without
annotation effort, Haliver proves memory safety in almost all programs. With
annotations Haliver, additionally, proves functional correctness properties. We
show that the approach is viable and reduces the manual annotation effort by an
order of magnitude
HaliVer:Deductive Verification and Scheduling Languages Join Forces
Full text linkThe HaliVer tool integrates deductive verification into the popular scheduling language Halide, used for image processing pipelines and array computations. HaliVer uses Vercors, a separation logic-based verifier, to verify the correctness of (1) the Halide algorithms and (2) the optimised parallel code produced by \halide when an optimisation schedule is applied to the algorithm. This allows proving complex, optimised code correct while reducing the effort to provide the required verification annotations. For both approaches, the same specification is used. We evaluated the tool on several optimised programs generated from characteristic Halide algorithms, using all but one of the essential scheduling directives available in Halide. Without annotation effort, Haliver proves memory safety in almost all programs. With annotations Haliver, additionally, proves functional correctness properties. We show that the approach is viable and reduces the manual annotation effort by an order of magnitude
Verifying a Radio Telescope Pipeline Using HaliVer:Solving Nonlinear and Quantifier Challenges
Full text linkThis paper describes a case study to verify memory safety of a radio telescope pipeline, which was targeted with the PADRE project of Astron, SURF and the Netherlands eScienceCenter. As performance is important for this application, the implementation of the radio telescope pipeline should run on a GPU device. Therefore, we encoded the radio telescope pipeline using the Halide scheduling language, which achieved a significant speedup. Next, we used the HaliVer tool to automatically generate formal pre- and postconditions, loop invariants and assertions, which the deductive verifier VerCors can use to prove memory safety. We identified two challenges for the automatic generation of formal annotations for a tool such as VerCors. The first challenge was related to the flattening of multi-dimensional arrays to single arrays and the second challenge concerns the use of many arrays in a program in combination with many quantifiers to specify read and write permissions. For both challenges, we propose solutions, and implemented these. Not every solution proved successful. We discuss the lessons learned and future plans to solve a core scalability issue for large optimised parallel programs.</p
HaliVer: Deductive Verification and Scheduling Languages Join Forces
Full text linkThe HALIVER tool integrates deductive verification into the popular scheduling language HALIDE, used for image processing pipelines and array computations. HALIVER uses VERCORS, a separation logic-based verifier, to verify the correctness of (1) the HALIDE algorithms and (2) the optimised parallel code produced by HALIDE when an optimisation schedule is applied to an algorithm. This allows proving complex, optimised code correct while reducing the effort to provide the required verification annotations. For both approaches, the same specification is used. We evaluated the tool on several optimised programs generated from characteristic HALIDE algorithms, using all but one of the essential scheduling directives available in HALIDE. Without annotation effort, HALIVER proves memory safety in almost all programs. With annotations HALIVER, additionally, proves functional correctness properties. We show that the approach is viable and reduces the manual annotation effort by an order of magnitude
Formal Methods for GPGPU Programming: Is the Demand Met?
No full textOver the years, researchers have developed many formal method tools to support software development. However, hardly any studies are conducted to determine whether the actual problems developers encounter are sufficiently addressed. For the relatively young field of GPU programming, we would like to know whether the tools developed so far are sufficient, or whether some problems still need attention. To this end, we first look at what kind of problems programmers encounter in OpenCL and CUDA. We gather problems from Stack Overflow and categorise them with card sorting. We find that problems related to memory, synchronisation of threads, threads in general and performance are essential topics. Next, we look at (verification) tools in industry and research, to see how these tools addressed the problems we discovered. We think many problems are already properly addressed, but there is still a need for easy to use sound tools. Alternatively, languages or programming styles can be created, that allows for easier checking for soundness
