More Web Proxy on the site http://driver.im/

research-article

Free access

Near-optimal deployment of dataflow applications on many-core platforms with real-time guarantees

Authors:

Stefanos Skalistis,

Alena SimalatsarAuthors Info & Claims

DATE '17: Proceedings of the Conference on Design, Automation & Test in Europe

Pages 752 - 757

Published: 27 March 2017 Publication History

Abstract

Safe and optimal deployment of data-streaming applications on many-core platforms requires the realistic estimation of task Worst-Case Execution Time (WCET). On the other hand, task WCET depends on the deployment solution, due to the varying number of interferences on shared resources, thus introducing a cyclic dependency. Moreover, WCET is still an over-approximation of the Actual Execution Time (AET), thus leaving room for run-time optimisation. In this paper we introduce an offline/online optimisation approach. In the offline phase, we first break the cyclic dependency and acquire safe and near-optimal solutions for tasks partitioning/placement, mapping, scheduling and buffer allocation. Then, we tighten the WCETs and update the scheduling function accordingly. In the online phase we introduce a safe distributed readjustment of the offline schedule, based on the AET. Experiments on a Kalray MPPA-256 platform show a tightening of the guaranteed latency up to 46% in the offline phase, and 41% latency reduction in the online phase. In total, we achieve more than 50% of latency reduction.

References

[1]

J. Combaz, J.-C. Fernandez, T. Lepley, and J. Sifakis, "QoS control for optimality and safety," in EMSOFT'05, pp. 90--99, ACM, 2005.

Digital Library

[2]

W. Thies and S. Amarasinghe, "An empirical characterization of stream programs and its implications for language and compiler design," PACT '10, (New York, NY, USA), pp. 365--376, ACM, 2010.

Digital Library

[3]

G. Kahn, "The semantics of a simple language for parallel programming," in Information processing, Aug 1974.

[4]

E. A. Lee and D. G. Messerschmitt, "Synchronous data flow," Proceedings of the IEEE, vol. 75, no. 9, pp. 1235--1245, 1987.

[5]

S. Skalistis and A. Simalatsar, "Worst-case execution time analysis for many-core architectures with NoC," in International Conference on Formal Modeling and Analysis of Timed Systems, FORMATS, 2016.

[6]

S. Cotton, O. Maler, J. Legriel, and S. Saidi, "Multi-criteria optimization for mapping programs to multi-processors," in IEEE International Symposium on Industrial Embedded Systems (SIES), IEEE, 2011.

[7]

P. Tendulkar, P. Poplavko, I. Galanommatis, and O. Maler, "Many-core scheduling of data parallel applications using SMT solvers," in Digital System Design (DSD), 2014 17th Euromicro Conference on, IEEE, 2014.

Digital Library

[8]

Kalray, "Kalray MPPA-256," 2015.

[9]

P. Tendulkar, P. Poplavko, and O. Maler, "Symmetry breaking for multi-criteria mapping and scheduling on multicores," in Formal Modeling and Analysis of Timed Systems, pp. 228--242, Springer, 2013.

Digital Library

[10]

I. Kadayif, M. Kandemir, and U. Sezer, "An integer linear programming based approach for parallelizing applications in on-chip multiprocessors," in Proceedings of the 39th Annual Design Automation Conference, DAC '02, (New York, NY, USA), pp. 703--706, ACM, 2002.

Digital Library

[11]

J. Legriel, C. Le Guernic, S. Cotton, and O. Maler, "Approximating the pareto front of multi-criteria optimization problems.," in TACAS, pp. 69--83, Springer, 2010.

Digital Library

[12]

R. P. Dick and N. K. Jha, "Mogac: a multiobjective genetic algorithm for hardware-software cosynthesis of distributed embedded systems," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 17, no. 10, pp. 920--935, 1998.

Digital Library

[13]

H. Cho, B. Ravindran, and E. D. Jensen, "An optimal real-time scheduling algorithm for multiprocessors," in Real-Time Systems Symposium, 2006. RTSS'06. 27th IEEE International, pp. 101--110, IEEE, 2006.

Digital Library

[14]

P. Regnier, G. Lima, E. Massa, G. Levin, and S. Brandt, "Run: Optimal multiprocessor real-time scheduling via reduction to uniprocessor," in Real-Time Systems Symposium (RTSS), pp. 104--115, IEEE, 2011.

Digital Library

[15]

A. Weichslgartner, D. Gangadharan, S. Wildermann, M. Glaß, and J. Teich, "Daarm: Design-time application analysis and run-time mapping for predictable execution in many-core systems," in Proceedings of the 2014 International Conference on Hardware/Software Codesign and System Synthesis, CODES '14, pp. 34:1--34:10, ACM, 2014.

Digital Library

[16]

M. Bertogna, Real-time scheduling analysis for multiprocessor platforms. PhD thesis, 2008.

[17]

A. Bonfietti, M. Lombardi, M. Milano, and L. Benini, "Throughput constraint for synchronous data flow graphs," in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, vol. 5547 of Lecture Notes in Computer Science, 2009.

Digital Library

[18]

A. Bonfietti, L. Benini, M. Lombardi, and M. Milano, "An efficient and complete approach for throughput-maximal SDF allocation and scheduling on multi-core platforms," in Proceedings of the Conference on Design, Automation and Test in Europe, European Design and Automation Association, 2010.

Digital Library

[19]

F. Galea and R. Sirdey, "A parallel simulated annealing approach for the mapping of large process networks," in Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2012 IEEE 26th International, pp. 1787--1792, IEEE, 2012.

Digital Library

[20]

J. P. Hausmans, S. J. Geuns, M. H. Wiggers, and M. J. Bekooij, "Unified dataflow model for the analysis of data and pipeline parallelism, and buffer sizing," in Formal Methods and Models for Codesign (MEM-OCODE), International Conference on, IEEE, 2014.

Digital Library

[21]

V. A. Nguyen, D. Hardy, and I. Puaut, "Scheduling of parallel applications on many-core architectures with caches: bridging the gap between WCET analysis and schedulability analysis," in 9th Junior Researcher Workshop on Real-Time Computing, Nov 2015.

[22]

P. Burgio, A. Marongiu, P. Valente, and M. Bertogna, "A memory-centric approach to enable timing-predictability within embedded many-core accelerators," in Real-Time and Embedded Systems and Technologies (RTEST), CSI Symposium on, 2015.

[23]

A. Dkhil, S. Louise, and C. Rochange, "Worst-Case Communication Overhead in a Many-Core based Shared-Memory Model," in Junior Researcher Workshop on Real-Time Computing, Nice, octobre 2013.

[24]

G. Giannopoulou, N. Stoimenov, P. Huang, L. Thiele, and B. de Dinechin, "Mixed-criticality scheduling on cluster-based manycores with shared communication and storage resources," Real-Time Systems, pp. 1--51, 2015.

Digital Library

[25]

É. Cota, A. de Morais Amory, and M. S. Lubaszewski, Reliability, Availability and Serviceability of Networks-on-chip. Springer Science & Business Media, 2011.

[26]

B. D. de Dinechin, D. van Amstel, M. Poulhiès, and G. Lager, "Time-critical computing on a single-chip massively parallel processor," in Conference on Design, Automation & Test in Europe, DATE '14, 2014.

Digital Library

Cited By

Didier KPotop-Butucaru DIooss GCohen ASouyris JBaufreton PGraillat A(2019)Correct-by-Construction Parallelization of Hard Real-Time Avionics Applications on Off-the-Shelf Predictable HardwareACM Transactions on Architecture and Code Optimization10.1145/332879916:3(1-27)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.1145/3328799

Near-optimal deployment of dataflow applications on many-core platforms with real-time guarantees
1. General and reference
  1. Cross-computing tools and techniques
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Combining Dataflow Applications and Real-time Task Sets on Multi-core Platforms
SCOPES '17: Proceedings of the 20th International Workshop on Software and Compilers for Embedded Systems

Future real-time embedded systems will increasingly incorporate mixed application models with timing constraints running on the same multi-core platform. These application models are dataflow applications with timing constraints and traditional real-...
parMERASA -- Multi-core Execution of Parallelised Hard Real-Time Applications Supporting Analysability
DSD '13: Proceedings of the 2013 Euromicro Conference on Digital System Design

Engineers who design hard real-time embedded systems express a need for several times the performance available today while keeping safety as major criterion. A breakthrough in performance is expected by parallelizing hard real-time applications and ...
GPU Acceleration for Simulating Massively Parallel Many-Core Platforms
Emerging massively parallel architectures such as a general-purpose processor plus many-core programmable accelerators are creating an increasing demand for novel methods to perform their architectural simulation. Most state-of-the-art simulation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

DATE '17: Proceedings of the Conference on Design, Automation & Test in Europe

March 2017

1814 pages

Publisher

European Design and Automation Association

Leuven, Belgium

Publication History

Published: 27 March 2017

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
60
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)4

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Didier KPotop-Butucaru DIooss GCohen ASouyris JBaufreton PGraillat A(2019)Correct-by-Construction Parallelization of Hard Real-Time Avionics Applications on Off-the-Shelf Predictable HardwareACM Transactions on Architecture and Code Optimization10.1145/332879916:3(1-27)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.1145/3328799

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents