In traditional von Neumann processors, the central register file is an inherent limiting factor in exploiting the instruction-level parallelism (ILP) of programs. To alleviate this problem, many processors follow a hybrid von Neumann/dataflow computing model in which specific instruction sequences are executed in dataflow order by communicating intermediate values directly from producer processing units (PUs) to consumer PUs without using a central register file. However, the intermediate values often reside in local registers of the PUs, which requires a synchronization of the data transports that still limits the exploitation of the ILP.To avoid the use of a central register file and the need for any synchronization between PUs, some newer architectures suggest first-in-first-out (FIFO) buffers instead of local registers at the input and output ports of the PUs. Since values are produced and consumed, and are thus never overwritten (as in registers), the compiler must determine the required number of copies of each value. Furthermore, it is necessary to control the number of copies of values to develop buffer size aware compilation methods. However, the number of variable uses in a sequential program may depend on the future execution. This paper presents transformations for ‘balancing’ a given program, i.e., transforming the program so that for all points in the program, the number of future uses of all variables can be accurately determined in order to allocate the required buffer sizes in the later compilation phases. The classical space-time trade-off is demonstrated by the experimental results which show an improvement of the processor performance with increasing buffer sizes and vice versa. More importantly, the experimental results demonstrate the potential of buffered hybrid dataflow architectures for a scalable use of ILP.

Dataflow process networks (DPNs) provide a convenient model of computation that is often used to model system behavior in model-based designs. With fixed sets of nodes, they are also used as dataflow graphs as an intermediate program representation by compilers to uncover instruction-level parallelism of sequential programs. Many recent processor architectures, which are still von Neumann architectures, also use dataflow computing to increase their exploitation of instruction-level parallelism by exposing their datapaths so that the compiler can take care of the allocation of processing units (PUs), the execution schedules of instructions on the PUs, and the communication of intermediate values between PUs. If the communication paths are buffered, these architectures can be abstracted into a DPN architecture whose PUs and interconnection network are DPN nodes. In this article, we introduce a DPN abstraction of hybrid dataflow/von Neumann architectures and consider the mapping of the nodes of a given dataflow graph to the PUs of such a DPN architecture such that there are no conflicts due to the mapping of different nodes to the same PU. We express the allocation and scheduling constraints in terms of propositional logic for the original dataflow graph and for a modified version of the dataflow graph that simplifies the constraints by introducing levels using copy nodes, such that all nodes receive inputs only from nodes of the previous level. We also formulate equisatisfiable SMT constraints using integer variables to reason directly about the parallel runtime. On this basis, we further present alternative SAT constraints that explicitly encode concurrency, and discuss variants of the constraints for a better understanding of the same.

Many novel processor architectures expose their processing units (PUs) and internal datapaths to the compiler. To avoid an unnecessary synchronization of PUs, the datapaths are often buffered which results in buffered exposed datapath (BED) architectures. This paper suggests a code generation technique for BED architectures from dataflow graphs that are used as intermediate program representations. Inspired by results on queue layouts in graph drawing, we determine in this paper constraints for the node and edge orderings of the dataflow graphs to ensure the first-in-first-out behavior of the buffers. Formalizing these constraints in propositional logic enables SAT solvers to compute optimal PU allocations. Moreover, future code generation techniques may develop heuristics based on the code generation criteria of this paper.

Abstract Conventional processor architectures are restricted in exploiting instruction level parallelism (ILP) due to the relatively low number of programmer-visible registers. Therefore, more recent processor architectures expose their datapaths so that the compiler (1) can schedule parallel instructions to different processing units and (2) can make effective use of local storage of the processing units. Among these architectures, the Synchronous Control Asynchronous Dataflow (SCAD) architecture is a new exposed datapath architecture whose processing units are equipped with first-in first-out (FIFO) buffers at their input and output ports. In contrast to register-based machines, the optimal code generation for SCAD is still a matter of research. In particular, SAT and SMT solvers were used to generate optimal resource constrained and optimal time constrained schedules for SCAD, respectively. As Answer Set Programming (ASP) offers better flexibility in handling such scheduling problems, we focus in this paper on using an answer set solver for both resource and time constrained optimal SCAD code generation. As a major benefit of using ASP, we are able to generatealloptimal schedules for a given program which allows one to study their properties. Furthermore, the experimental results of this paper demonstrate that the answer set solver can compete with SAT solvers and outperforms SMT solvers.This paper is under consideration for acceptance in TPLP.

Conventional processor architectures are restricted in exploiting instruction level parallelism (ILP) due to the limited number of available registers in their instruction sets. Therefore, recent processor architectures expose their datapaths so that the compiler not only schedules instructions to functional units, but also takes care of directly moving values between functional units avoiding the need of registers at all. However, the current compiler technology is still based on classic register architectures where a nearly optimal register mapping is the key for the quality of the generated assembly code. The Synchronous Control Asynchronous Dataflow (SCAD) architecture is a new exposed datapath architecture where processing units (PUs) are equipped with first-in first-out (FIFO) buffers at their inputs and outputs. Code generation for SCAD machines can be done as known for classic queue machines to completely eliminate the use of registers, and to improve the degree of exploited ILP. However, the SCAD code generated this way is not optimal since compared to queue machines, SCAD machines can contain many PUs and buffers which offers the compiler more freedom to reduce unnecessary computational overhead. In this paper, we map the SCAD code generation problem to a satisfiability problem, and then use SAT solvers to generate code without overhead that works with the minimal number of PUs. The generated optimal code will serve as a reference to judge the quality of heuristics that will be finally used in SCAD compilers.

Effectiveness of timing analysis of real-time applications depends on the timing predictability of the underlying execution platform. Modern hardware architectures improve average case performance using complex features. However, these features make Worst Case Execution Time (WCET) analysis complicated often leading to pessimistic derived worst case execution time. We present the preliminary design of Synchronous Control Asynchronous Dataflow (SCAD) - a new model of computation targeting time-predictability and competitive performance. Inorder execution of instructions and capability to bypass memory accesses imparts timing predictability to SCAD computational model. We also motivate a code generation technique to optimally utilize the memory bypassing capability of SCAD and that results in increased instruction level parallelism.