Energy efficiency is a key concern in circuit design. With the end of Dennard scaling, voltages no longer scale with transistor size, making full-capacity operation unsustainable due to heat and power limits. Power gating offers a solution, but controlling independent power domains is challenging. Large domains are manageable but inefficient; small domains are efficient but require intricate control.

We present the Sparse Synchronous model (SSM) of computation, which allows a programmer to specify software timing more precisely than the traditional “heartbeat” of mainstream operating systems or the synchronous languages. SSM is a mix of semantics inspired by discrete event simulators and the synchronous languages designed to operate in resource-constrained environments such as microcontrollers. SSM provides precise timing prescriptions, concurrency, and determinism. We implement SSM in SSML, a toy language along with a runtime system that includes a scheduler, memory manager, and an interface that works with a real-time operating system to keep the model synchronized with the real world. Experimentally, we find our implementation is able to perform jitter-free I/O in the 10s of kHz on a microcontroller.

Speed and ease of accelerator design is a growing need. High level programming languages have provided significant gains in the software world, but lag in the hardware realm. We present a hardware implementation of a garbage collector, which automates memory management, one of the major conveniences of modern software languages. Our garbage collector is integrated with a Haskell to hardware HLS flow. The collector runs concurrently with the application, using already-idle memory slots to do its work with little to no impact on performance. To achieve this, our collector exploits rapid synchronization that is straightforward in hardware but very difficult in software. With this synchronization, the collector is able to safely pop in and out of very fine pockets of idleness on a cycle by cycle, heap by heap basis. In most cases our collector incurred negligible overhead, and slowed the application only when the heaps were so tiny that the application was unable to proceed with its operation until the collector had freed more space. Our experiments further show that our concurrent collector performs best under an eager collection policy that collects garbage well-before the application exhausts the available memory. Although this eager strategy performs more collection operations than strictly necessary, the application never pauses and the collector operates entirely in the background.

Speed and ease of accelerator design is a growing need. High level programming languages have provided significant gains in the software world, but lag for hardware. We present a hardware implementation of a garbage collector that automates memory management, one of the major conveniences of modern software languages. Our garbage collector runs concurrently with the application it serves, using already-idle memory slots to do its work with little to no impact on performance. To achieve this, our collector exploits rapid synchronization that is straightforward in hardware but difficult in software. This synchronization enables the collector to interleave with fine pockets of idleness on a per-cycle, per-heap basis. Our collector typically incurred negligible overhead, only slowing the application to wait for collection to free memory when the heaps were so small that the collector could not keep pace with allocation. We also found that our concurrent collector performs best under an eager collection policy that collects garbage well before the application exhausts the available memory. Although this eager strategy performs more collection operations than strictly necessary, the application never pauses because our collector operates entirely in the background.

We describe the development of a new programming language Scoria and its compiler. Scoria is a high-level reactive real-time language based on the sparse synchronous model (SSM), designed to produce time- and power-efficient low-level C code that can run on small IoT devices. While the compiler is not yet in a state where it is meaningful to measure power usage, we carefully profile the timing behaviour and identify bottlenecks that can improve performance. The language and compiler are implemented as an Embedded Domain-Specific Language (EDSL) on top of Haskell.

We present the Sparse Synchronous model (SSM) of computation, which allows a programmer to specify software timing more precisely than the traditional “heartbeat” of mainstream operating systems or the synchronous languages. SSM is a mix of semantics inspired by discrete event simulators and the synchronous languages designed to operate in resource-constrained environments such as microcontrollers. SSM provides precise timing prescriptions, concurrency, and determinism. We present SSM, its motivations, and details of a lightweight runtime system upon which a future language will be built.

Hardware accelerators are one promising solution to contend with the end of Dennard scaling and the slowdown of Moore's law. For mature workloads that are regular and have high compute per byte, hardening an application into one or more hardware modules is a standard approach. However, for some applications, we find that a programmable homogeneous architecture is preferable.

We present a technique for implementing dataflow networks as compositional hardware circuits. We first define an abstract dataflow model with unbounded buffers that supports data-dependent blocks (mux, demux, and nondeterministic merge); we then show how to faithfully implement such networks with bounded buffers and handshaking. Handshaking admits compositionality: our circuits can be connected with or without buffers, and combinational cycles arise only from a completely unbuffered cycle. While bounding buffer sizes can cause the system to deadlock prematurely, the system is guaranteed to produce the same, correct, data before then. Thus, unless the system deadlocks, inserting or removing buffers only affects its performance. We demonstrate how this enables design space to be explored.

We explore on-chip network topologies for the Q100, an analytic query accelerator for relational databases. In such data-centric accelerators, interconnects play a critical role by moving large volumes of data. In this paper we show that various interconnect topologies can trade a factor of 2.5x in performance for 3.3x area. Moreover, standard topologies (e.g., ring or mesh) are not optimal.

Previous database accelerator proposals such as the Q100 provide a fixed set of database operators, chosen to support a target query workload. Some queries may not be well-supported by a fixed accelerator, typically because they need more resources/operators of a particular kind than the accelerator provides. By Amdahl's law, these queries become relatively more expensive as they are not fully accelerated. We propose a second-level accelerator, DB-Mesh, to take up some of this workload. DB-Mesh is an asynchronous systolic array that is more generic than the Q100, and can be configured to run a variety of operators with configurable parameters such as record widths. We demonstrate DB-Mesh applied to nested loops joins, an operator that is not directly supported on the Q100. We show that a naïve implementation has the potential for deadlock, and show how to avoid deadlock with a careful design. We also demonstrate how the data flow policy used in the array influences system throughput.

We present a technique for implementing dataflow networks as compositional hardware circuits. We first define an abstract dataflow model with unbounded buffers that supports data-dependent blocks (mux, demux, and nondeterministic merge); we then show how to faithfully implement such networks with bounded buffers and handshaking. Handshaking admits compositionality: our circuits can be connected with or without buffers and still compute the same function without introducing spurious combinational cycles. As such, inserting or removing buffers affects the performance but not the functionality of our networks, which we demonstrate through experiments that show how design space can be explored.

To simplify the implementation of dataflow systems in hardware, we present a technique for designing latency- insensitive dataflow blocks. We provide buffering with backpressure, resulting in blocks that compose into deep, high-speed pipelines without introducing long combinational paths. Our input and output buffers are easy to assemble into simple unit- rate dataflow blocks, arbiters, and blocks for Kahn networks. We prove the correctness of our buffers, illustrate how they can be used to assemble arbitrary dataflow blocks, discuss pitfalls, and present experimental results that suggest our pipelines can operate at a high clock rate independent of length.

The MEMOCODE design contest for 2014 was centered around the emulation of the 1978 Taito video game Space Invaders. The challenge is to improve the speed of a cycle-accurate software emulator for the game. Contestants had a month toope improve the provided code, which already ran fairly well on the ARM-based Raspberry Pi platform. Entries were judged on how much faster their code ran and its quality. The winning groups used a variety of optimization techniques ranging from dynamic binary translation, data-structure restructuring, and improving instruction and data caching.

The MEMOCODE design contest for 2012 is exact substring matching: a simplified form of the DNA sequence alignment problem. The challenge is to efficiently locate millions of 100-base-pair short read sequences in a 3-million-base-pair reference genome. Contestants had a month to create a fast system that ran on a given set of test data. Entries were judged both on absolute time and the product of time and system cost. The two winning groups, which were invited to contribute papers describing their solutions, judiciously chose algorithms that exploited powerful hardware. The two winning entries employed a hash algorithm running on a Convey HC-1 FPGA/multicore hybrid with an aggressive memory system and a Burrows-Wheeler/hash hybrid running on a 12-core Intel system was second.

The ninth International Conference on the Application of Concurrency to System Design (ACSD) was held in July 2009 in Augsburg, Germany.Following a tradition, Fundamenta Informaticae publishes a special issue with revised and extended versions of a selection of the best papers from ACSD.The current issue is the eighth special issue devoted to ACSD.ACSD serves as a forum for disseminating theoretical results with application potential and advanced methods and tools for the design of complex concurrent systems.The conference aims at cross-fertilizing both theoretical and applied research on the following topics:• design methods, tools and techniques based on models of computation and concurrency (dataflow models, communicating automata, Petri nets, process algebras, state charts, MSCs, etc.), (performance) analysis, verification, testing and synthesis;• hardware / software co-design, platform-based design, component-based design, refinement techniques, hardware / software abstractions, co-simulation and verification;

Locks are used to ensure exclusive access to shared memory locations. Unfortunately, lock operations are expensive, so much work has been done on optimizing their performance for common access patterns. One such pattern is found in networking applications, where there is a single thread dominating lock accesses. An important special case arises when a single-threaded program calls a thread-safe library that uses locks.

Most compilers focus on optimizing performance, often at the expense of memory, but efficient memory use can be just as important in constrained environments such as embedded systems. This paper presents a memory reduction technique for rendezvous communication, which is applied to the deterministic concurrent programming language SHIM. It focuses on reducing memory consumption by sharing communication buffers among tasks. It determines pairs of buffers that can never be in use simultaneously and use a shared region of memory for each pair. The technique produces a static abstraction of a SHIM program's dynamic behavior, which is then analyzed to find buffers that are never occupied simultaneously. Experiments show the technique runs quickly on modest-sized programs and can sometimes reduce memory requirements by half.

Concurrent programming languages are growing in importance with the advent of multi-core systems. However, concurrent programs suffer from problems, such as data races and deadlock, absent from sequential programs. Unfortunately, traditional race and deadlock detection techniques fail on both large programs and small programs with complex behaviors.

This paper argues that repeatable timing is more important and more achievable than predictable timing. It describes microarchitecture approaches to pipelining and memory hierarchy that deliver repeatable timing and promise comparable or better performance compared to established techniques. Specifically, threads are interleaved in a pipeline to eliminate pipeline hazards, and a hierarchical memory architecture is outlined that hides memory latencies.

Most compilers focus on optimizing performance, often at the expense of memory, but efficient memory use can be just as important in constrained environments such as embedded systems.

We consider pipelined architectures of packet processors consisting of a sequence of simple packet-processing modules interconnected by first-in first-out buffers. We propose a new model for describing their function, an automated synthesis technique that generates efficient hardware for them, and an algorithm for computing minimum buffer sizes that allow such pipelines to achieve their maximum throughput. Our functional model provides a level of abstraction familiar to a network protocol designer; in particular, it does not require knowledge of register-transfer-level hardware design. Our synthesis tool implements the specified function in a sequential circuit that processes packet data a word at a time. Finally, our analysis technique computes the maximum throughput possible from the modules and then determines the smallest buffers that can achieve it. Experimental results conducted on industrial-strength examples suggest that our techniques are practical. Our synthesis algorithm can generate circuits that achieve 40 Gb/s on field-programmable gate arrays, equal to state-of-the-art manual implementations, and our buffer-sizing algorithm has a practically short runtime. Together, our techniques make it easier to quickly develop and deploy high-speed network switches.

In a hard real-time embedded system, the time at which a result is computed is as important as the result itself. Modern processors go to extreme lengths to ensure their function is predictable, but have abandoned predictable timing in favor of average-case performance. Real-time operating systems provide timing-aware scheduling policies, but without precise worst-case execution time bounds they cannot provide guarantees.

Multicore shared-memory architectures are becoming prevalent and bring many programming challenges. Among the biggest are data races: accesses to shared resources that make a program's behavior depend on scheduling decisions beyond its control. To eliminate such races, the SHIM concurrent programming language adopts deterministic message passing as it sole communication mechanism. We demonstrate such language restrictions are practical by presenting a SHIM to C-plus-Pthreads compiler that can produce efficient code for shared-memory multiprocessors. We present a parallel JPEG decoder and FFT exhibiting 3.05 and 3.3times speedups on a four-core processor.

The advent of multicore processors requires mainstream concurrent programming languages with high level concurrency constructs and effective debugging techniques. Unfortunately, many concurrent programming languages are non-deterministic and allow data races.

Concurrent programming languages are becoming mandatory with the advent of multi-core processors. Two major concerns in any concurrent program are data races and deadlocks. Each are potentially subtle bugs that can be caused by non-deterministic scheduling choices in most concurrent formalisms. As an alternative, the SHIM concurrent language guarantees the absence of data races by eschewing shared memory, but a SHIM program may still deadlock if a program violates a communication protocol. We present a model-checking-based static deadlock detection technique for the SHIM language. Although SHIM is asynchronous, its semantics allow us to model it synchronously without losing precision, greatly reducing the state space that must be explored. This plus the obvious division between control and data in SHIM programs makes it easy to construct concise abstractions. Experimentally, we find our procedure runs in only a few seconds for modest-sized programs, making it practical to use as part of a compilation chain.

Unlike sequential software, concurrent software needs a structuring mechanism capable of specifying constructs such as pipelines, scatter-gather, and other networks. Concurrent software languages usually provide mechanisms for dynamically creating such structures, but this makes them difficult to analyze statically. In particular, it would be very convenient to be able to put bounds on the resources (memory, processes) required by a particular system.

Designers and high-level synthesis tools can introduce unwanted cycles in digital circuits, and for certain combinational functions, cyclic circuits that are stable and do not hold state are the smallest or most natural representations. Cyclic combinational circuits have well-defined functional behavior yet wreak havoc with most logic synthesis and timing tools, which require combinational logic to be acyclic. As such, some sort of cycle-removal step is necessary to handle these circuits with existing tools. We present a two-stage algorithm for transforming a combinational cyclic circuit into an equivalent acyclic circuit. The first part quickly and exactly characterizes all combinational behavior of a cyclic circuit. It starts by applying input patterns to each input and examining the boundary between gates whose outputs are and are not defined to find additional input patterns that make the circuit behave combinationally. It produces sets of assignments to inputs that together cover all combinational behavior. This can be used to report errors, as an optimization aid, or to restructure the circuit into an acyclic equivalent. The second stage of our algorithm does this restructuring by creating an acyclic circuit fragment from each of these assignments and assembles these fragments into an acyclic circuit that reproduces all the combinational behavior of the original cyclic circuit. Experiments show that our algorithm runs in seconds on real-life cyclic circuits, making it useful in practice.

Patterson and Ditzel [12] did not invent reduced instruction set computers (RISC) in 1980. Earlier computers all had reduced instruction sets. Instead, they argued that trends in computer architecture had gotten off the sweet spot, and that by dropping back a few years and forking a new version of architectures, leveraging what had been learned, they could get better computers by employing simpler instruction sets.

Optimizing sequential cycles is essential for many types of high-performance circuits, such as pipelines for packet processing. Retiming is a powerful technique for speeding pipelines, but it is stymied by tight sequential cycles. Designers usually attack such cycles by manually combining Shannon decomposition with retiming—effectively a form of speculation—but such manual decomposition is error prone. We propose an efficient algorithm that simultaneously applies Shannon decomposition and retiming to optimize circuits with tight sequential cycles. While the algorithm is only able to improve certain circuits (roughly half of the benchmarks we tried), the performance increase can be dramatic (7%–61%) with only a modest increase in area (1%–12%). The algorithm is also fast, making it a practical addition to a synthesis flow.

Packet editing is a fundamental building block of data communication systems such as switches and routers. Circuits that implement this function are critical and define the features of the system. We propose a high-level synthesis technique for a new model for representing packet editing functions. Experiments show our circuits achieve a throughput of up to 40Gb/s on a commercially available FPGA device, equal to state-of-the-art implementations.

Optimizing sequential cycles is essential for many types of high-performance circuits, such as pipelines for packet processing. Retiming is a powerful technique for speeding pipelines, but it is stymied by tight sequential cycles. Designers usually attack such cycles by manually combining Shannon decomposition with retiming - effectively a form of speculationut such manual decomposition is error-prone. We propose an efficient algorithm that simultaneously applies Shannon decomposition and retiming to optimize circuits with tight sequential cycles. While the algorithm is only able to improve certain circuits (roughly half of the benchmarks we tried), the performance increase can be dramatic (7%-61%) with only a modest increase in area (3%-12%). The algorithm is also fast, making it a practical addition to a synthesis flow

Concurrent programming languages should be a good fit for embedded systems because they match the intrinsic parallelism of their architectures and environments. Unfortunately, typical concurrent programming formalisms are prone to races and nondeterminism, despite the presence of mechanisms such as monitors.In this paper, we propose SHIM, the core of a deterministic concurrent language, meaning the behavior of a program is independent of the scheduling of concurrent operations. SHIM does not sacrifice power or flexibility to achieve this determinism. It supports both synchronous and asynchronous paradigms-loosely and tightly synchronized threads-the dynamic creation of threads and shared variables, recursive procedures, and exceptions.We illustrate our programming model with examples including breadth-first-search algorithms and pipelines. By construction, they are race-free. We provide the formal semantics of SHIM and a pre-liminary implementation.

Programming concurrent systems is substantially more difficult than programming sequential systems, yet most embedded systems need concurrency. We believe this should be addressed through higher-level models of concurrency that eliminate many of the usual challenges, such as nondeterminism arising from races.The shim model of computation provides deterministic concurrency, and there already exist ways of implementing it in hardware and software. In this work, we describe how to produce more efficient C code from shim systems.We propose two techniques: a largely mechanical one that produces tail-recursive code for simulating concurrency, and a more clever one that statically analyzes the communication pattern of multiple processes to produce code with far less overhead. Experimentally, we find our tail-recursive technique produces code that runs roughly twice as fast as a baseline; our statically-scheduled code can run up to twelve times faster.

Concurrent programming languages are good for embedded systems because they match the parallelism of their environments, but most concurrent languages are nondeterministic, making coding in them unwieldy. We present R-SHIM, the core of a language with concurrent recursive procedure calls and disciplined shared variables that remains deterministic - the behavior of a program is scheduling-independent

Generic simulation components, such as fixed-precision arithmetic routines, make it easier to quickly assemble system simulations, but generic components tend to simulate more slowly than their manually-written specialized counterparts. So a system modeler is normally forced to choose between building a simulation quickly or running it quickly.This paper explores the use of program specialization as a way to address this conundrum. Through hints provided by the author of a generic library and aggressive compiler optimizations, program specialization can automatically rewrite a generic component into a specialized one with performance comparable to a careful manual implementation. As a result, the user of such a specializable library can quickly assemble a simulation from generic components whose performance can equal that of a more tedious implementation.Experimental results show that program specialization provides a three- to seven-times speed-up on an important class of simulations: signal processing kernels in SystemC that manipulate fixed-precision numbers.

Typical embedded hardware/software systems are implemented using a combination of C and an HDL such as Verilog. While each is well-behaved in isolation, combining the two gives a nondeterministic model of computation whose ultimate behavior must be validated through expensive (cycle-accurate) simulation. We propose an alternative for describing such systems. Our software/hardware integration medium (shim) model, effectively Kahn networks with rendezvous communication, provides deterministic concurrency. We present the Tiny-shim language for such systems and its semantics, demonstrate how to implement it in hardware and software, and discuss how it can be used to model a real-world system. By providing a powerful, deterministic formalism for expressing systems, designing systems, and verifying their correctness will become easier

Many techniques for synthesizing digital hardware from C-like languages have been proposed, but none have emerged as successful as Verilog or VHDL for register-transfer-level design. Familiarity is the main reason C-like languages have been proposed for hardware synthesis. Synthesize hardware from C, proponents claim, and a C programmer can be turned into a hardware designer. Another common motivation is hardware/software codesign: today's systems usually contain a mix of hardware and software, and it is often unclear initially which portions to implement in hardware. Here, using a single language should simplify the migration task. The paper surveys several C-like hardware synthesis languages and looks at two of the fundamental challenges, concurrency and timing control.

Typical embedded hardware/software systems are implemented using a combination of C and an hdl such as Verilog. While each is well-behaved in isolation, combining the two gives a nondeterministic model whose ultimate behavior must be validated through expensive (cycle-accurate) simulation.We propose an alternative for describing such systems. Our shim (software/hardware integration medium) model, effectively Kahn networks with rendezvous communication, provides deterministic concurrency. We present the Tiny-shim language for such systems and its semantics, demonstrate how to implement it in hardware and software, and discuss how it can be used to model a real-world system.By providing a powerful, deterministic formalism for expressing systems, designing systems and verifying their correctness will become easier.

Deterministic asynchronous concurrent formalisms are valuable because determinism greatly simplifies the design and validation of such systems and most concurrent formalisms are nondeterministic. This paper connects two of the more successful deterministic asynchronous formalisms: Kahn's dataflow networks and Josephs's deterministic receptive processes. The main result: a divergence-free deterministic receptive process is a Kahn process in that it can be modeled by a continuous function from input to output sequences, thus verifying it is compositionally deterministic. This result provides a bridge between two communities, enabling results from the asynchronous digital hardware community to be used in the context of dataflow computation and vice versa.

Device drivers are difficult to write and error-prone. They are usually written in C, a fairly low-level language with minimal type safety and little support for device semantics. As a result, they have become a major source of instability in operating system code.This paper presents NDL, a language for device drivers. NDL provides high-level abstractions of device resources and constructs tailored to describing common device driver operations. We show that NDL allows for the coding of a semantically correct driver with a code size reduction of more than 50% and a minimal impact on performance.

While concurrency in embedded systems is most often supplied by real-time operating systems, this approach can be unpredictable and difficult to debug. Synchronous concurrency, in which a system marches in lockstep to a global clock, is conceptually easier and potentially more efficient because it can be statically scheduled beforehand.We present an algorithm for generating efficient sequential code from such synchronous concurrent specifications. Starting from a concurrent program dependence graph generated from the synchronous, concurrent language Esterel, we generate efficient, statically scheduled sequential code while adding a minimal amount of runtime scheduling overhead.Experimentally, we obtain speedups as high as six times over existing techniques. While we applied our technique to Esterel, it should be applicable to other synchronous, concurrent languages.

Cyclic circuits that do not hold state or oscillate are often the most convenient representation for certain functions, such as arbiters, and can easily be produced inadvertently in high-level synthesis, yet are troublesome for most circuit analysis tools.This paper presents an algorithm that generates an acyclic circuit that computes the same function as a given cyclic circuit for those inputs where the cyclic circuit does not oscillate or hold state. The algorithm identifies all patterns on inputs and internal nodes that lead to acyclic evaluation orders for the cyclic circuit, which are represented as acyclic circuit fragments, then combines these to produce an acyclic circuit that can exhibit all of these behaviors.Experimental results suggest this potentially exponential algorithm is practical for small circuits and may be improved to handle larger circuits. This algorithm should make dealing with cyclic combinational circuits nearly as easy as dealing with their acyclic counterparts.

Twelve years ago, Proceedings of the IEEE devoted a special section to the synchronous languages. This paper discusses the improvements, difficulties, and successes that have occured with the synchronous languages since then. Today, synchronous languages have been established as a technology of choice for modeling, specifying, validating, and implementing real-time embedded applications. The paradigm of synchrony has emerged as an engineer-friendly design method based on mathematically sound tools.

Embedded systems often include a traditional processor capable of executing sequential code, but both control and data-dominated tasks are often more naturally expressed using one of the many domain-specific concurrent specification languages. This article surveys a variety of techniques for translating these concurrent specifications into sequential code. The techniques address compiling a wide variety of languages, ranging from dataflow to Petri nets. Each uses a different method, to some degree chosen to match the semantics of concurrent language. Each technique is considered to consist of a partial evaluator operating on an interpreter. This combination provides a clearer picture of how parts of each technique could be used in a different setting.

Embedded hard real-time software systems often need fine-grained parallelism and precise control of timing, things typical real-time operating systems do not provide. The Esterel language has both, but compiling large Esterel programs has been challenging, producing either needlessly slow or large code. This paper presents the first Esterel compiler able to compile large Esterel programs into fast, small code. By choosing a concurrent control-now graph (CCFG) as its intermediate representation, it preserves many of the control constructs to produce code that can be 100 times faster and half the size than code from other compilers with similar capacity. The primary contribution is an algorithm that generates efficient sequential code from a CCFG. While developed specifically for compiling Esterel, the algorithm could be used to compile other synchronous languages with fine-grained parallelism.

Embedded real-time software systems often need fine-grained parallelism and precise control over time, things typical real-time operating systems do not provide. The Esterel language has both, but Existing compilers produce slow code for large programs.

This paper addresses the design of reactive real-time embedded systems. Such systems are often heterogeneous in implementation technologies and design styles, for example by combining hardware application-specific integrated circuits (ASICs) with embedded software. The concurrent design process for such embedded systems involves solving the specification, validation, and synthesis problems. We review the variety of approaches to these problems that have been taken.