Dataflow modeling is well suited for a large variety of applications for modern multi-core architectures, e.g., from the signal processing and the control domain. Furthermore, Design Space Exploration (DSE) can be used to explore mappings of tasks to hardware resources (cores of an MPSoC) and their scheduling to obtain optimized trade-off solutions between throughput and resource costs. However, the throughput evaluation of an implementation candidate via compilation-in-the-loop or simulation-based approaches can be extremely time-consuming. Such a deficiency is very detrimental, because a typical DSE run needs to evaluate thousands of implementation candidates. As a remedy, we propose a hybrid-adaptive DSE where a max-plus algebra-based analytic throughput calculation method is used in the initial DSE phase to enable a fast progress of the search space exploration. However, as this analysis may be inaccurate as neglecting some real-world effects like cache and scheduling overhead, throughput measurements are taken later in the DSE. Moreover, we explore the trade-off between scheduling efficiency of implementation candidates—in favor of reducing concurrency—and exploiting concurrency to a large extent for parallel execution of the application. To find solutions of highest achievable throughput, it is shown that not only highly scheduling efficient implementation candidates but also highly parallel implementation candidates are essential when determining the initial population. In this realm, we contribute a method for diversity-based population initialization. For a representative set of benchmarks, it is shown that the combination of the two major contributions allows us to find much higher throughput multi-core solutions within a given exploration time compared to a state-of-the-art DSE approach.

Dataflow modeling is well suited for a wide variety of applications for multi-core architectures, e.g. signal processing and control domain. Additionally, Design Space Exploration (DSE) can be used to explore the distribution of tasks to resources and their scheduling to obtain optimized trade-off solutions between throughput and resource costs. However, the performance evaluation of an implementation candidate in particular via compilation and throughput measurement on the target hardware is prohibitively time-consuming. Thus, we propose to use a max-plus algebra-based analytic throughput calculation method in the initial DSE phase where a fast evaluation with low accuracy is sufficient to guide the search through the design space. However, this analysis neglects some real-world concerns like cache effects and scheduling overhead. Thus, a hybrid DSE is proposed where throughput measurements are taken later in the DSE to get more accurate throughput results for real-world platforms. Results show that our approach is able to find much higher throughput multi-core solutions within a given exploration time compared to a state-of-the-art DSE approach.

State-of-the-art system synthesis techniques employ meta-heuristic optimization techniques for Design Space Exploration (DSE) to tailor application execution, e.g., defined by a dataflow graph, for a given target platform. Unfortunately, the performance evaluation of each implementation candidate is computationally very expensive, in particular on recent multi-core platforms, as this involves compilation to and extensive evaluation on the target hardware. Applying heuristics for performance evaluation on the one hand allows for a reduction of the exploration time but on the other hand may deteriorate the convergence of the optimization technique toward performance-optimal solutions with respect to the target platform. To address this problem, we propose DSE strategies that are able to dynamically trade off between (i) approximating heuristics to guide the exploration and (ii) accurate performance evaluation, i.e., compilation of the application and subsequent performance measurement on the target platform. Technically, this is achieved by introducing a set of additional, but easily computable guiding objective functions, and varying the set of objective functions that are evaluated during the DSE adaptively. One major advantage of these guiding objectives is that they are generically applicable for dataflow models without having to apply any configuration techniques to tailor their parameters to the specific use case. We show this for synthetic benchmarks as well as a real-world control application. Moreover, the experimental results demonstrate that our proposed adaptive DSE strategies clearly outperform a state-of-the-art DSE approach known from literature in terms of the quality of the gained implementations as well as exploration times. Amongst others, we show a case for a two-core implementation where after about 3 hours of exploration time one of our proposed adaptive DSE strategies already obtains a 60% higher performance value than obtained by the state-of-the-art approach. Even when the state-of-the-art approach is given a total exploration time of more than 2 weeks to optimize this value, the proposed adaptive DSE strategy features a 20% higher performance value after a total exploration time of about 4 days.

Determining feasible application mappings for Design Space Exploration (DSE) and run-time embedding is a challenge for modern many-core systems. The underlying NP-complete system-synthesis problem faces tremendously complex problem instances due to the hundreds of heterogeneous processing elements, their communication infrastructure, and the resulting number of mapping possibilities. Thus, we propose to employ a search-space splitting (SSS) technique using architecture decomposition to increase the performance of existing design-time and run-time synthesis approaches. The technique first restricts the search for application embeddings to selected sub-architectures at substantially reduced complexity; therefore, the complete architecture needs to be searched only in case no embedding is found on any sub-system. Furthermore, we introduce a basic learning mechanism to detect promising sub-architectures and subsequently restrict the search to those. We exemplify the SSS for a SAT-based and a problem-specific backtracking-based system synthesis as part of DSE for NoC-based many-core systems. Experimental results show drastically reduced execution times (≈ 15--50 x on a 24×24 architecture) and an enhanced quality of the embedding, since less mappings (≈20--40 x, compared to the non-decomposing procedures) need to be discarded due to a timeout.

Large scale many-core systems are able to execute concurrently changing mixes of different parallel applications. Hybrid application mapping combines the strengths of design-time exploration/analysis of resource constellations for task-to-core mappings with the flexibility of choosing concrete mappings at run time. However, state-of-the-art design space exploration (DSE) techniques so far ignore the problem of symmetries in modern heterogeneous architectures: not only recurring patterns in the architecture but the mapping of tasks to instances of the same processor type may unnecessarily increase the search space by redundant, symmetrical implementations which typically affects the quality of the DSE. As a remedy, we propose a novel meta-heuristic DSE approach that eliminates architectural symmetries by abstracting the problem to a clustering of tasks and their mapping to processor types. However, we demonstrate that simple task clustering and type mappings may again introduce encoding symmetries in our search space. Thus, we present a formulation of the task clustering and type mapping as a 0-1 integer linear program (ILP) which eliminates all architectural as well as encoding symmetries from the search space. We also contribute a formal feasibility check to ensure that only implementations with at least one feasible concrete mapping are considered. To further improve the search process for feasible solutions, we apply satisfiability modulo theories-like learning techniques: from each infeasible implementation, we extract conditions why the implementation is infeasible and enrich our 0-1 ILP by additional constraints continuously during the DSE. Experimental results show that a DSE equipped with the novel symmetry-eliminating search space and the proposed learning techniques clearly outperforms a state-of-the-art approach known from literature in terms of the quality of the gained implementation classes.

Application modeling using dynamic dataflow graphs is well-suited for multi-core platforms. However, there is often a mismatch between the fine granularity of the application and the platform. Tailoring this granularity to the platform promises performance gains by (a) reducing dynamic scheduling overhead and (b) exploiting compiler optimizations. In this paper, we propose a throughput-optimizing compilation approach that uses Quasi-Static Schedules (QSSs) to combine actors of static dataflow subgraphs. Our proposed approach combines core allocation, QSSs, and actor binding in a Design Space Exploration (DSE), optimizing the throughput for a number of available cores. During the DSE, each implementation candidate is compiled to and evaluated on the target hardware---here an Intel i7 and an ARM Cortex-A9. Experimental results including synthetic benchmarks as well as a real-world control application show that our proposed holistic compilation approach outperforms classic DSEs that are agnostic of QSS as well as a DSE that employs QSS as a post-processing step. Amongst others, we show a case where the compilation approach obtains a speedup of 9.91 x for a 4-core implementation, while a classic DSE only obtains a speedup of 2.12 x.

We propose a dynamic scheduling approach for the concurrent execution of logical actor instances on a single synthesized actor instance. Based on a formal dataflow model of computation, the proposed approach can be applied to a wide range of applications in a model-based design flow. As case-study, we evaluate a bus-cycle-accurate SystemC RTL model based on an InfiniBand network adapter in a PCI Express system.

Today, parts of an ESL model can be automatically synthesized to a low-level implementation, e. g., via high-level synthesis. However, to build a complete working virtual prototype directly from a given ESL model, one still has to perform several design steps manually. The work-at-hand tackles this problem by introducing bridge components already in the ESL model. These components influence Design Space Exploration (DSE) by adding their characteristics like cost and latency into evaluation. The complete system is divided into several subsystems connected through bridges, we call this process communication-driven decomposition. Once an optimized implementation solution is found by DSE and selected by the designer, every subsystem of this ESL model is handed over to the individual synthesis tool. Here, if two subsystems will be synthesized by different tools, the bridge connecting these two subsystems will be automatically duplicated into two instances and assigned to each subsystem. Then, synthesis tools generate code for each subsystem (including the bridge inside each subsystem). In the last step, the system integration process merges the corresponding bridge pairs together to build a complete virtual prototype. To automate the proposed design flow, we have developed a framework that automatically divides an ESL model into subsystems and synthesizes the interfaces for all bridges which strongly simplifies system integration. The designer is therefore free from the interface realization. Hence, the overall design development cycle is shortened. As a proof of concept, a distributed control application is presented to give evidence of the proposed technique's applicability and the achieved productivity gain.