• Provably Correct Development of Reconfigurable Hardware Designs via Equational Reasoning

    Ian Graves, Adam Procter, William L. Harrison, and Gerard Allwein. 2015 International Conference on Field-Programmable Technology (FPT 2015).

    There is a semantic gap between the hardware definition languages used to design and implement hardware and the languages and logics used to formally specify and verify them. Bridging this gap—i.e., constructing formal models from existing hardware artifacts—can be costly, time-consuming, and error prone—and yet utterly necessary if formal verification is to proceed. This work demonstrates that this gap can be collapsed by starting in a pure functional language that is also a hardware description language, and that equational style verifications may be performed directly on the source text of a hardware design, thereby significantly lowering the verification cost for reconfigurable designs. When combined with an efficient compiler, this methodology achieves both good performance and low cost verification.
  • Semantics Driven Hardware Design, Implementation, and Verification with ReWire

    Adam Procter, William L. Harrison, Ian Graves, Michela Becchi, and Gerard Allwein. Accepted at the 2015 ACM SIGPLAN/SIGBED Conference on Languages, Compilers, Tools and Theory for Embedded Systems (LCTES 2015), Portland, Oregon, June 18-19, 2015.

    There is no such thing as high assurance without high assurance hardware. High assurance hardware is essential, because any and all high assurance systems ultimately depend on hardware that conforms to, and does not undermine, critical system properties and invariants. And yet, high assurance hardware development is stymied by the conceptual gap between formal methods and hardware description languages used by engineers. This paper presents ReWire, a functional programming language providing a suitable foundation for formal verification of hardware designs, and a compiler for that language that translates high-level, semantics-driven designs directly into working hardware. ReWire's design and implementation are presented, along with a case study in the design of a secure multicore processor, demonstrating both ReWire's expressiveness as a programming language and its power as a framework for formal, high-level reasoning about hardware systems.
  • Hardware Synthesis from Functional Embedded Domain-Specific Languages: A Case Study in Regular Expression Compilation

    Ian Graves, Adam Procter, William L. Harrison, Michela Becchi, and Gerard Allwein. Accepted at the 11th International Symposium on Applied Reconfigurable Computing (ARC 2015), Bochum, Germany, April 13-17, 2015.

    Although FPGAs have the potential to bring software-like flexibility and agility to the hardware world, designing for FPGAs remains a difficult task divorced from standard software engineering norms. A better programming flow would go far towards realizing the potential of widely deployed, programmable hardware. We propose a general methodology based on domain specific languages embedded in the functional language Haskell to bridge the gap between high level abstractions that support programmer productivity and the need for high performance in FPGA circuit implementations. We illustrate this methodology with a framework for regular expression to hardware compilers, written in Haskell, that supports high programmer productivity while producing circuits whose performance matches and, indeed, exceeds that of a state of the art, hand-optimized VHDL-based tool. For example, after applying a novel optimization pass, throughput increased an average of 28.3% over the state of the art tool for one set of benchmarks. All code discussed in the paper is available online.
  • Semantics-Driven Design and Implementation of High-Assurance Hardware

    Adam Procter. Ph.D. Dissertation, University of Missouri, Department of Computer Science, December 2014.

    Modularity, that is the division of complex systems into less complex and more easily understood parts, is a pervasive concern in computer science, and hardware design is no exception. Existing hardware design languages such as Verilog and VHDL support modular design by enabling hardware designers to decompose designs into structural features that may be developed independently and connected together to form more complex devices. In the realm of high assurance for security, however, this sort of modularity is often of limited utility. Security properties are notoriously non-compositional, i.e. subsystems that independently satisfy some security property cannot necessary be relied upon to maintain that property when operating in tandem.

    The aim of this research is to establish semantically modular techniques for hardware design and implementation, in contrast to the conventional structural notion of modularity. A semantically modular design is constructed by adding "layers" of semantic features, such as state and reactivity, one at a time. From the high assurance aspect, semantic modularity enables different layers of semantic features to be reasoned about independently, greatly simplifying the structure of correctness proofs and improving their reusability. The major contribution of this work is a prototype compiler called ReWire which translates semantically modular hardware specifications to efficient implementations on FPGAs. In this dissertation I present the design and implementation of the ReWire compiler, along with a number of case studies illustrating both the practicality of the ReWire compiler and the elegance of the semantically modular approach to hardware verification.
  • Cheap (But Functional) Threads

    William L. Harrison and Adam Procter. Accepted for publication in Higher-Order and Symbolic Computation.

    This article demonstrates how a powerful and expressive abstraction from concurrency theory plays a dual rôle as a programming tool for concurrent applications and as a foundation for their verification. This abstraction—monads of resumptions expressed using monad transformers—is cheap: it is easy to understand, easy to implement, and easy to reason about. We illustrate the expressiveness of the resumption monad with the construction of an exemplary multitasking operating system kernel with process forking, preemption, message passing, and synchronization constructs in the pure functional programming language Haskell.
  • Semantics-directed Machine Architecture in ReWire

    Adam Procter, William L. Harrison, Ian Graves, Michela Becchi, and Gerard Allwein. Proceedings of the 2013 International Conference on Field-Programmable Technology (ICFPT'13), Kyoto, December 2013.

    The functional programming community has developed a number of powerful abstractions for dealing with diverse programming models in a modular way. Beginning with a core of pure, side effect free computation, modular monadic semantics (MMS) allows designers to construct domain-specific languages by adding layers of semantic features, such as mutable state and I/O, in an à la carte fashion. In the realm of interpreter and compiler construction, the benefits of this approach are manifold and well explored. This paper advocates bringing the tools of MMS to bear on hardware design and verification. In particular, we shall discuss a prototype compiler called ReWire which translates high-level MMS hardware specifications into working circuits on FPGAs. This enables designers to tackle the complexity of hardware design in a modular way, without compromising efficiency.
  • Formal semantics of heterogeneous CUDA-C: A modular approach with applications

    Chris Hathhorn, Michela Becchi, William L. Harrison and Adam Procter. Proceedings of the 2012 Systems Software Verification Conference (SSV'12), Sydney, November 2012.

    We extend an off-the-shelf, executable formal semantics of C (Ellison and Roșu's 𝕂 Framework semantics) with the core features of CUDA-C. The hybrid CPU/GPU computation model of CUDA-C presents challenges not just for programmers, but also for practitioners of formal methods. Our formal semantics helps expose and clarify these issues. We demonstrate the usefulness of our semantics by generating a tool from it capable of detecting some race conditions and deadlocks in CUDA-C programs. We discuss limitations of our model and argue that its extensibility can easily enable a wider range of verification tasks.
  • The Confinement Problem in the Presence of Faults

    William L. Harrison, Adam Procter, and Gerard Allwein. Proceedings of the 14th International Conference on Formal Engineering Methods (ICFEM'12), Kyoto, November 2012.

    In this paper, we establish a semantic foundation for the safe execution of untrusted code. Our approach extends Moggi’s computational λ-calculus in two dimensions with operations for asynchronous concurrency, shared state and software faults and with an effect type system à la Wadler providing fine-grained control of effects. An equational system for fault isolation is exhibited and its soundness demonstrated with a semantics based on monad transformers. Our formalization of the equational system in the Coq theorem prover is discussed. We argue that the approach may be generalized to capture other safety properties, including information flow security.
  • A Virtual Memory Based Runtime to Support Multi-tenancy in Clusters with GPUs

    Michela Becchi, Kittisak Sajjapongse, Ian Graves, Adam Procter, Vignesh Ravi, and Srimat Chakradhar. Proceedings of the 21st International Symposium on High-Performance Parallel and Distributed Computing (HPDC'12), Delft, June 2012.

    Graphics Processing Units (GPUs) are increasingly becoming part of HPC clusters. Nevertheless, cloud computing services and resource management frameworks targeting heterogeneous clusters including GPUs are still in their infancy. Further, GPU software stacks (e.g., CUDA driver and runtime) currently provide very limited support to concurrency.

    In this paper, we propose a runtime system that provides abstraction and sharing of GPUs, while allowing isolation of concurrent applications. A central component of our runtime is a memory manager that provides a virtual memory abstraction to the applications. Our runtime is flexible in terms of scheduling policies, and allows dynamic (as opposed to programmer-defined) binding of applications to GPUs. In addition, our framework supports dynamic load balancing, dynamic upgrade and downgrade of GPUs, and is resilient to their failures. Our runtime can be deployed in combination with VM-based cloud computing services to allow virtualization of heterogeneous clusters, or in combination with HPC cluster resource managers to form an integrated resource management infrastructure for heterogeneous clusters. Experiments conducted on a three-node cluster show that our GPU sharing scheme allows up to a 28% and a 50% performance improvement over serialized execution on short- and long-running jobs, respectively. Further, dynamic inter-node load balancing leads to an additional 18-20% performance benefit.
  • The Design of a Practical Theorem Prover for a Lazy Functional Language

    Adam Procter, William L. Harrison, and Aaron Stump. Proceedings of the 2012 Symposium on Trends in Functional Programming (TFP'12), St Andrews, UK, June 2012.

    Pure, lazy functional languages like Haskell provide a sound basis for formal reasoning about programs in an equational style. In practice, however, equational reasoning about correctness proofs is underutilized. In the context of Haskell, we suggest that part of the reason for this is the lack of accessible tools for machine-checked equational reasoning. This paper outlines the design of MProver, a proof checker which fills just that niche. MProver features first-class support for reasoning about potentially undefined computations (particularly important in a lazy setting), and an extended notion of Haskell-like type classes, enabling a highly modular style of program verification that closely follows familiar functional programming idioms.
  • Towards Semantics-directed System Design and Synthesis

    William L. Harrison, Benjamin Schulz, Adam Procter, Andrew Lukefahr, and Gerard Allwein. Proceedings of the 2011 International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA'11), Las Vegas, July 2011. Invited paper.

    High assurance systems have been defined as systems “you would bet your life on.” This article discusses the application of a form of functional programming—what we call “monadic programming”—to the generation of high assurance and secure systems. Monadic programming languages leverage algebraic structures from denotational semantics and functional programming—monads—as a flexible, modular organizing principle for secure system design and implementation. Monadic programming languages are domain-specific functional languages that are both sufficiently expressive to express essential system behaviors and semantically straightforward to support formal verification.
  • Model-driven Engineering from Modular Monadic Semantics: Implementation Techniques Targeting Hardware and Software

    William L. Harrison, Adam M. Procter, Jason Agron, Garrin Kimmell, and Gerard Allwein. Proceedings of the IFIP Working Conference on Domain Specific Languages (DSLWC), Oxford, July 2009.

    Recent research has shown how the formal modeling of concurrent systems can benefit from monadic structuring. With this approach, a formal system model is really a program in a domain specific language defined by a monad for shared-state concurrency. Can these models be compiled into efficient implementations? This paper addresses this question and presents an overview of techniques for compiling monadic concurrency models directly into reasonably efficient software and hardware implementations. The implementation techniques described in this article form the basis of a semantics-directed approach to model-driven engineering.
  • Making Monads First-class with Template Haskell

    Pericles S. Kariotis, Adam M. Procter, and William L. Harrison. Proceedings of the ACM SIGPLAN 2008 Haskell Symposium (Haskell '08), Victoria, BC, Canada, September 2008.

    Monads as an organizing principle for programming and semantics are notoriously difficult to grasp, yet they are a central and powerful abstraction in Haskell. This paper introduces a domain-specific language, MonadLab, that simplifies the construction of monads, and describes its implementation in Template Haskell. MonadLab makes monad construction truly first class, meaning that arcane theoretical issues with respect to monad transformers are completely hidden from the programmer. The motivation behind the design of MonadLab is to make monadic programming in Haskell simpler while providing a tool for non-Haskell experts that will assist them in understanding this powerful abstraction.
  • Asynchronous Exceptions as an Effect

    William L. Harrison, Gerard Allwein, Andy Gill, and Adam Procter. Proceedings of the Ninth International Conference on Mathematics of Program Construction (MPC'08), Marseille, July 2008.

    Asynchronous interrupts abound in computing systems, yet they remain a thorny concept for both programming and verification practice. The ubiquity of interrupts underscores the importance of developing programming models to aid the development and verification of interrupt-driven programs. The research reported here recognizes asynchronous interrupts as a computational effect and encapsulates them as a building block in modular monadic semantics. The resulting modular semantic model can serve as both a guide for functional programming with interrupts and as a formal basis for reasoning about interrupt-driven computation as well.