Loading...
Please wait, while we are loading the content...
Similar Documents
A Data-Flow Approach for Compiling the Sequentially Constructive Language ( SCL )
| Content Provider | Semantic Scholar |
|---|---|
| Author | Smyth, Steven Motika, Christian Hanxleden, Reinhard Von |
| Copyright Year | 2015 |
| Abstract | The Sequentially Constructive Language (SCL) is a minimal synchronous language that captures the essence of the Sequentially Constructive Model of Computation (SCMoC), a recently proposed extension of the classical synchronous model of computation. The SCMoC uses sequential scheduling information to increase the class of constructive (legal) synchronous programs. This facilitates the adoption of synchronous programming by users familiar with sequential programming in C or Java, thus simplifying the design of concurrent reactive/embedded systems with deterministic behavior. The theoretical foundations of the SCMoC are fairly well covered by now, and also the upstream compilation from SCCharts (a Statechart dialect) and SCEst (a variant of Esterel) to SCL. In this paper, we focus on how to compile SCL down to data-flow equations, which ultimately can be synthesized to hardware or executed in software. 1 Motivation & Related Work Reactive systems are characterized by their regular interaction with the environment, typically under real-time constraints. Physical time is conceptually divided into a sequence of discrete ticks, and during each tick, the reactive system reads inputs from the environment, processes them according to some internal system state, and then updates the system state and produces outputs to the environment. Reactive systems may implement safety-critical applications where determinate behavior is essential. However, they often entail concurrent threads of control and interact through shared memory, which makes determinacy challenging. This has motivated the development of synchronous languages [3], which have been used successfully in the industry since the 1990s, e. g., for the development of avionics software or power plant control. Edwards [4] and Potop-Butucaru et al. [11] provide good overviews of compilation challenges and approaches for concurrent languages, including synchronous languages. Synchronous languages achieve determinacy for concurrent systems by the synchrony hypothesis, which abstracts from computation time and thus assumes outputs to occur synchronously with the inputs they react to. This is achieved by demanding unique, stable values for all shared variables throughout each tick. This simplifies formal reasoning, and has a natural, physical analogy of welldefined, stable voltages on all wires on a hardware circuit. We thus say that a synchronous program is causal, or constructive, if and only if it corresponds to a circuit where all wires have well-defined voltages for all possible inputs and all possible internal states, independent of variations in signal propagation delays in an actual hardware realization. This Synchronous Model of Computation (SMoC) for concurrent programming contrasts with, e. g., the programming model offered by Java or Posix threads. There the outcome of a program with concurrent threads that share variables may depend on run-time scheduling decisions out of control of the programmer. In Java, achieving determinacy often requires additional, brittle constructs such as semaphores, monitors, barrier synchronizations etc. [9]. However, the classic realization of the synchrony hypothesis comes with restrictions that may be difficult to realize, in particular for novice programmers used to imperative languages such as C or Java. Specifically, the requirement that shared variables cannot change within a tick may come as a surprise. For example, a construct such as “if (x) { x = false }” would be forbidden in the classical SMoC, because x could be true and false within a tick. Instead, one could write for example “if (pre(x)) { x = false }” which states that if x was true in the previous tick, then set it to false in the current tick. This, however, would introduce an artificial tick boundary in a computation that conceptually has nothing to do with the passage of physical time. Conversely, the computation in question is purely sequential, with an obvious order of computation: first the test whether x is true, second the possible assignment to false. Thus there is no race condition between the read and the write of x, and a compiler should have no difficulty to produce determinate code. The desire to combine the foundations and nice properties of synchronous languages with instantaneous memory updates has motivated the development of the Sequentially Constructive model of computation (SCMoC) [17,1]. The basic idea is to use any sequential scheduling information in the program to schedule computations in a determinate fashion, and to use a particular scheduling protocol to order concurrent variable accesses. The SCMoC may still reject certain programs as not being sequentially constructive, such as “fork x=y par y=x join”, where the SCMoC does not know how to order the concurrent accesses to x and y and which is therefore not determinate. However, the SCMoC accepts many more programs than the SMoC. The SCMoC is formally defined with the Sequentially Constructive Graph (SCG), which is textually represented as the Sequentially Constructive Language (SCL). The SCL is rather low-level and very simple yet rich enough to be used as an intermediate language for compiling higher-level languages that want to build on the SCMoC. So far, two such higher-level languages have been proposed. The first language is Sequentially Constructive Statecharts (SCCharts) [15], a dialect of Harel’s statecharts [7]. The second language is Sequentially Constructive Esterel (SCEst) [12], an extension of Esterel [11]. (a) Transformations of the high-level compilation as presented before [10]. The intermediate result of the high-level synthesis is an SCG. (b) Transformations of the low-level data-flow synthesis. Fig. 1. Single-Pass Language-Driven Incremental Compilation (SLIC) approach transforming SCCharts to code. Outline and Contributions The original paper on SCCharts [15] briefly sketched two approaches to compile SCL further into software or hardware, namely the data-flow approach and the priority-based approach. We here present the data-flow approach in detail. In Sec. 2 we explain the SCL and recapitulate definitions that are important for the remainder of the paper. The previously presented compilation chain (cf. Fig. 1) shows that the data-flow approach transforms from the generated SCG to a sequentialized variant and then eventually into code. This transformation is executed in several steps depicted in Fig. 1b. Each step is described in Sec. 3, which is the technical core of this paper. We here follow the Single-Pass Language-Driven Incremental Compilation (SLIC) approach [10] where every step is executed as a Model-to-Model (M2M) transformation, which facilitates a modular compilation chain. We have validated our compilation chain with a range of test cases. This includes fairly extensive use in the class room. In Sec. 4 we report on a mediumsized railway project that uses the data-flow approach to synthesize a railway controller. We conclude in Sec. 5. Fig. 2. Matrix showing the entire mapping throughout the transformation process from SCCharts to circuits. 2 The Sequentially Constructive Language (SCL) This section gives an overview of SCL. It only gives the necessary explanation to understand the data-flow transformations. We refer to the sequentially constructive foundations [17] for a more formal and wider introduction. The minimal SCL is adopted from C and Esterel. The concurrent and sequential control-flow of an SCL program is given by an SCG, which acts as an internal representation for elaboration, analysis and code generation. Rows two and three of Fig. 2 present an overview of SCL and SCG elements and the mapping between them. SCL is a concurrent imperative language with shared variable communication. Variables can be both written and read by concurrent threads. Reads and writes are collectively referred to as variable accesses. SCL programs consist of one or more sequentially ordered statements with the following abstract syntax of statements s ::= x = e | s ; s | if (e) s else s | l: s | goto l | fork s par s join | pause where x is a variable, e is an expression and l ∈ L is a program label. The statements s comprise the standard operations assignment, the sequence operator, conditional statements, labelled commands and jumps. The sublanguage of expressions e used in assignments and conditionals is not restricted. However, we rule out side effects when evaluating e. Our notion of sequential constructiveness is based on the idea that the compiler guarantees a strict “initialize-update-read” (iur) execution schedule during each macro tick. The initialize phase is given by the execution of a class of writes which we call absolute writes (e. g., “x = 1”), while the update phase consists of executing relative writes where scheduling order does not matter (e. g., “x += 2” and “x +=3” can be scheduled in any order, with the same result). All the read accesses, in particular the conditional statements which influence the control-flow, are done last. 2.1 SCG Representation An SCG is a labelled graph G = (N,E) whose statement nodes N correspond to the statements of the program, and whose edges E reflect the sequential execution ordering and data dependencies between the statements. Nodes and edges are further described by various attributes. A node n is labelled by the statement type. Nodes labelled with x = e are referred to as assignment nodes, those with if (e) as condition nodes, all other nodes are referred by their statement type (entry nodes, exit nodes, etc.). Fig. 2 sketches how SCG elements correspond to an SCL program. A technical report [16] describes this mapping in detail. Every edge e has a type e.type that specifies the nature of the particular ordering constraint expressed by e. Edges that follow the initialize-update-read schedule are labeled iur -edges. iur -edges combined with the sequential controlflow edges are termed instantaneous edges. An SC |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_2015_submission_23.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
