Confidentiality is a crucial security property for many critical applications. As a response to the discovery of numerous micro-architectural side channel attacks such as Spectre, allowing an attacker to extract secret information in pernicious ways, the notion of hardware/software contracts was proposed to formalise the guarantees provided by the hardware to the software. In this paper, we propose to extend this notion to include the guarantees provided by the operating system (OS), so far unspecified in such contracts. We formalize an attacker model adapted to a typical execution model on a shared platform. More precisely, we formalize common thread and memory management policies provided by the OS on top of a hardware model and explore the consequences of potential leaks emerging on such a platform. Our investigation shows that the OS policies play a crucial role in providing security guarantees to code processing sensitive data and thus have to be taken into consideration when writing such code through platform contracts.

Critical real-time systems are getting more and more complex and require ever more computing power. Multi-core platforms, GPUs, and custom accelerators promise to deliver this needed performance. However, these platforms are notoriously hard to analyze and lack predictability in terms of timing properties. Computer architectures and platforms that offer both predictability and performance are thus needed. This work investigates the use of the interactive proof assistant Coq in order to model complex DRAM memory controllers (MCs) for multi-core platforms. The design of predictable high-performance MCs is particularly challenging, since memory requests have to be processed efficiently, while facing interference from other cores in the system. The problem is exacerbated by the complexity of DRAM devices and the various timing constraints they impose. Specifically, this work extends a previous Coq framework by focusing on reusability, which allows designers to develop and prove complex MCs. As a use-case, we present TDMShelve, an MC balancing performance and isolation.

Communication needs in avionics and transportation have radically changed over the recent years. Traditionally, the underlying hard real-time networks were designed in a centralized way, focusing on redundancy and isolation. Today, real-time communication is ubiquitous, from large airplanes to small vehicles. The associated networks must support a wide range of applications, and large amounts of data. Centralized approaches from the avionics domain, e.g., AFDX, are too costly, too heavyweight, and not flexible enough for these applications.In this paper we explore a new distributed network architecture designed to support jumbo airliners, but also small aircraft and drones. Communication redundancy is achieved using redundant paths, which have to be adapted and optimized to the application. The main challenge then is to build an optimized network configuration ensuring safety, fault tolerance, timing, and performance of both critical, and non-critical communication. Minimizing volume and weight of the equipment is also mandatory. Since the solution space is too large to be explored in reasonable time, we propose a genetic algorithm. Our experiments show that our algorithm converges quickly and offers solutions of excellent quality. The computed solutions are in the top 2% among the best solutions obtained using an exhaustive exploration. Our approach thus enables system engineers to quickly explore and choose very good solution for their systems.

Abstract In order to prove conformance to memory standards and bound memory access latency, recently proposed real-time DRAM controllers rely on paper and pencil proofs, which can be troubling: they are difficult to read and review, they are often shown only partially and/or rely on abstractions for the sake of conciseness, and they can easily diverge from the controller implementation, as no formal link is established between both. We propose a new framework written in Coq, in which we model a DRAM controller and its expected behaviour as a formal specification. The trustworthiness in our solution is two-fold: (1) proofs that are typically done on paper and pencil are now done in Coq and thus certified by its kernel, and (2) the reviewer’s job develops into making sure that the formal specification matches the standards—instead of performing a thorough check of the mathematical formalism. Our framework provides a generic DRAM model capturing a set of controller properties as proof obligations, which all implementations must comply with. We focus on properties related to the assertiveness that timing constraints are respected, every incoming request is handled in bounded time, and the DRAM command protocol is respected. We refine our specification with two implementations based on widely-known arbitration policies—First-in First-Out (FIFO) and Time-Division Multiplexing (TDM). We extract proved code from our model and use it as a “trusted core” on a cycle-accurate DRAM simulator.

Intuitively, a counter-intuitive timing anomaly manifests when a locally faster execution becomes globally slower. While the presence of such timing anomalies threatens the soundness and/or scalability of timing analyses, tools to systematically detect them do not exist. The main reason lies in the absence of a definition of counter-intuitive timing anomalies that establishes relations between local and global timing effects. In this paper, we address these relations through an important concept, that of causality, which we further use to revise the formalization of counter-intuitive timing anomalies. We also propose a specialized instance of the notions to implement a detection procedure for out-of-order pipelines.

Correctness is an important concern during the development of real-time systems. In addition to the functional correctness, the timing behavior is often formally verified in order to ensure that correct results are delivered in-time for all possible execution conditions. The timing behavior of real-time software is thus often validated through a rigorous timing analysis that aims at determining the worst-case execution time.Timing anomalies present a major obstacle during the validation of timing properties on modern computer platforms. Out-of-order execution and concurrent accesses to shared resources may sometimes lead to – at first sight – surprising timing behavior. Several (semi-)formal definitions have been proposed in the literature in order to capture such situations. However, as we present in this work, none of the existing definitions appears to be precise enough to be systematically used for detecting timing anomalies in modern processors with out-of-order execution.

The interactions among concurrent tasks pose a challenge in the design of real-time multi-core systems, where blocking delays that tasks may experience while accessing shared memory have to be taken into consideration. Various memory arbitration schemes have been devised that address these issues, by providing trade-offs between predictability, average-case performance, and analyzability. Time-Division Multiplexing (TDM) is a well-known arbitration scheme due to its simplicity and analyzability. However, it suffers from low resource utilization due to its non-work-conserving nature. We proposed in our recent work dynamic schemes based on TDM, showing work-conserving behavior in practice, while retaining the guarantees of TDM. These approaches have only been evaluated in a restricted setting. Their applicability in a preemptive setting appears problematic, since they may induce long memory blocking times depending on execution history. These blocking delays may induce significant jitter and consequently increase the tasks' response times. This work explores means to manage and, finally, bound these blocking delays. Three different schemes are explored and compared with regard to their analyzability, impact on response-time analysis, implementation complexity, and runtime behavior. Experiments show that the various approaches behave virtually identically at runtime. This allows to retain the approach combining low implementation complexity with analyzability.

Multi-core architectures pose many challenges in real-time systems, which arise from contention between concurrent accesses to shared memory. Among the available memory arbitration policies, Time Division Multiplexing (TDM) ensures a predictable behavior by bounding access latencies and guaranteed bandwidth to tasks independently from the other tasks. To do so, TDM guarantees exclusive access to the shared memory in a fixed time window. TDM, however, provides a low resource utilization as it is non-work-conserving. Besides, it is very inefficient for resources having highly variable latencies, such as sharing the access to a DRAM memory. The constant length of a TDM slot is, hence, highly pessimistic and causes an underutilization of the memory. To address these limitations, we present dynamic arbitration schemes that are based on TDM. However, instead of arbitrating at the level of TDM slots, our approach operates at the granularity of clock cycles by exploiting slack time accumulated from preceding requests. This allows the arbiter to reorder memory requests, exploit the actual access latencies of requests, and thus improve memory utilization. We demonstrate that our policies are analyzable as they preserve the guarantees of TDM in the worst case, while our experiments show an improved memory utilization on average.

As the performance requirements of today's real-time systems are on the rise, system engineers are increasingly forced to optimize and tune the execution time of real-time software. Apart from usual optimizations targeting the average-case performance of a program, the worst-case execution time bound (WCET) delivered by program analysis tools often has to be improved to meet all the deadlines and ensure a safe operation of the entire system.

This paper presents an asynchronous router design for use in time-division-multiplexed (TDM) networks-on-chip. Unlike existing synchronous, mesochronous and asynchronous router designs with similar functionality, the router is able to silently skip over cycles/TDM-slots where no traffic is scheduled and hence avoid all switching activity in the idle links and router ports. In this way switching activity is reduced to the minimum possible amount. The fact that this relaxed synchronization is sufficient to implement TDM scheduling represents a contribution at the conceptual level. The idea can only be implemented using asynchronous circuit techniques. To this end, the paper explores the use of “click-element” templates. Click-element templates use only flip-flops and conventional gates, and this greatly simplifies the design process when using conventional EDA tools and standard cell libraries. Few papers, if any, have explored this.

Recent developments in register allocation, mostly linked to static single assignment (SSA) form, have shown the benefits of decoupling the problem in two phases: a first spilling phase places load and store instructions so that the register pressure at all program points is small enough, and a second assignment and coalescing phase maps the variables to physical registers and reduces the number of move instructions among registers. This article focuses on the first phase, for which many open questions remain: in particular, we study the notion of optimal spilling (what can be expressed?) and the impact of SSA form (does it help?). To identify the important features for optimal spilling on load-store architectures, we develop a new integer linear programming formulation, more accurate and expressive than previous approaches. Among other features, we can express SSA ϕ-functions, memory-to-memory copies, and the fact that a value can be stored simultaneously in a register and in memory. Based on this formulation, we present a thorough analysis of the results obtained for the SPECINT 2000 and EEMBC 1.1 benchmarks, from which we draw, among others, the following conclusions: (1) rematerialization is extremely important; (2) SSA complicates the formulation of optimal spilling, especially because of memory coalescing when the code is not in conventional SSA (CSSA); (3) microarchitectural features are significant and thus have to be accounted for; and (4) significant savings can be obtained in terms of static spill costs, cache miss rates, and dynamic instruction counts.

Real-time systems need time-predictable architectures to support static worst-case execution time (WCET) analysis. One architectural feature, the data cache, is hard to analyze when different data areas (e.g., heap allocated and stack allocated data) share the same cache. This sharing leads to less precise results of the cache analysis part of the WCET analysis. Splitting the data cache for different data areas enables composable data cache analysis. The WCET analysis tool can analyze the accesses to these different data areas independently. In this paper we present the design and implementation of a cache for stack allocated data. Our port of the LLVM C++ compiler supports the management of the stack cache. The combination of stack cache instructions and the hardware implementation of the stack cache is a further step towards time-predictable architectures.

SUMMARY Application‐specific instruction set processors have proven successful in meeting the various design constraints of modern embedded systems and often provide the only viable trade‐off between computing power and opposing metrics such as power consumption. A promising approach to facilitate the exploration of processor design alternatives are processor description languages, which capture the instruction set and hardware organization of a processor. With the use of those processor models, various design tasks, for example, the adaption of software development tools, the generation of hardware models, and various verification tasks, can be automatized. These languages thus allow effective shortening of development turnaround times. In this work, the novel xADL language is presented, which, in contrast to most contemporary processor description languages, focuses on a structural modeling of the processor's hardware organization. However, a behavioral model of the instruction set is automatically derived using instruction set extraction. This provides a tight coupling between the structural hardware view and the instruction set view of the processor and reduces the complexity of processor models in comparison with existing languages. The feasibility of our approach is demonstrated by a compiler backend generator based on tree pattern matching. An important property of our generator is its ability to automatically verify whether the resulting compiler is complete, that is, it can process all possible input programs. The generated compilers are competitive to handcrafted production compilers, showing speedups of up to 20%for certain benchmarks. On average, moderate slowdowns between 3%and 15%have been observed for several processor models while considerable reductions in code size have been measured. Copyright © 2012 John Wiley & Sons, Ltd.

This paper explores the design of a circuit-switched network-on-chip (NoC) based on time-division-multiplexing (TDM) for use in hard real-time systems. Previous work has primarily considered application-specific systems. The work presented here targets general-purpose hardware platforms. We consider a system with IP-cores, where the TDM-NoC must provide directed virtual circuits -- all with the same bandwidth -- between all nodes. This may not be a frequent scenario, but a general platform should provide this capability, and it is an interesting point in the design space to study. The paper presents an FPGA-friendly hardware design, which is simple, fast, and consumes minimal resources. Furthermore, an algorithm to find minimum-period schedules for all-to-all virtual circuits on top of typical physical NoC topologies like 2D-mesh, torus, bidirectional torus, tree, and fat-tree is presented. The static schedule makes the NoC time-predictable and enables worst-case execution time analysis of communicating real-time tasks.

Recent developments in register allocation, mostly linked to static single assignment (SSA) form, have shown that it is possible to decouple the problem in two successive phases: a first spilling phase places load and store instructions so that the register pressure at all program points is small enough, a second assignment and coalescing phase maps the remaining variables to physical registers and reduces the number of move instructions among registers. This paper focuses on the first phase, for which many open questions remain: in particular, we study the notion of optimal spilling (what can be expressed?) and the impact of SSA form (does it help?).

The use of tree pattern matching for instruction selection has proven very successful in modern compilers. This can be attributed to the declarative nature of tree grammar specifications, which greatly simplifies the development of fast high-quality code generators. The approach has also been adopted widely by generator tools that aim to automatically extract the instruction selector, as well as other compiler components, for application-specific instruction processors from generic processor models. A major advantage of tree pattern matching is that it is suitable for static analysis and allows to verify properties of a given specification. Completeness is an important example of such a property, in particular for automatically generated compilers. Tree automata can be used to prove that a given instruction selector specification is complete, i.e., can actually generate machine code for all possible input programs. Traditional approaches for completeness tests cannot represent dynamic checks that may disable certain matching rules during code generation. However, these dynamic checks occur very frequently in compilers targeting application-specific processors. The dynamic checks arise from hidden properties that are not captured by the terminal symbols of the tree grammar notation. We apply terminal splitting to the instruction selector specifications that are automatically derived from structural processor models to make these properties explicit. The transformed specification is then verified using a traditional completeness test. If the test fails, counter examples are presented that allow to adopt the compiler or extend the processor model accordingly.

Tracing just-in-time compilers (TJITs) determine frequently executed traces (hot paths and loops) in running programs and focus their optimization effort by emitting optimized machine code specialized to these traces. Prior work has established this strategy to be especially beneficial for dynamic languages such as JavaScript, where the TJIT interfaces with the interpreter and produces machine code from the JavaScript trace.

Java is one of the most popular programming languages for thedevelopment of portable workstation and server applications availabletoday. Because of its clean design and typesafety, it is alsobecoming attractive in the domain of embedded systems. Unfortunately, the dynamic features of the language and its rich class library causeconsiderable overhead in terms of runtime and memory consumption. Efficient techniques to implement Java virtual machines that aresuitable for use in resource constrained environments are thusneeded. In this work we present a solution for very restrictedenvironments based on CACAO. CACAO is a just-in-time compilingvirtual machine implementation, combining high speed and small size. We have modified the original version of CACAO to run without anunderlying operating system within only 1 MB of memory. In additionwe present a new technique to selectively compile methods during theinitialization phase of real-time Java applications to preventunwanted interaction between dynamic compilation and critical tasks. Furthermore we present the YARI soft-core as the execution platformof CACAO within an field-programmable gate array. We compare ourimplementation with two well known Java processors, JOP and Sun'spicoJava-II, on the same technology. Although JOP achieves a higherclock frequency and picoJava-II occupies nearly 4 times the resourceof YARI, our solution is capable to outperform both of them by afactor of up to 2.8 and 2.2 respectively.

Instruction selection is a well-studied compiler phase that translates the compiler's intermediate representation of programs to a sequence of target-dependent machine instructions optimizing for various compiler objectives (e.g. speed and space). Most existing instruction selection techniques are limited to the scope of a single statement or a basic block and cannot cope with irregular instruction sets that are frequently found in embedded systems.

With increasing complexity of modern embedded systems, the availability of highly optimizing compilers becomes more and more important. At the same time, application specific instruction-set processors (ASIPs) are used to fine-tune hardware platforms to the intended application, demanding the availability of retargetable components throughout thewhole tool chain.

Embedded systems have an extremely short time to market and therefore require easily retargetable compilers. Architecture description languages (ADLs) provide a single concise architecture specification for the generation of hardware, instruction set simulators and compilers. In this article, we present an ADL for compiler generation. From a specification, we can derive an optimized tree pattern matching instruction selector, a register allocator and an instruction scheduler. Compared to a hand-crafted back end, the generated compiler produces smaller and faster code.The ADL is rich enough that other tools, such as assemblers, linkers, simulators and documentation, can all be obtained from a single specification.