Document Open Access Logo

Worst-Case Execution Time Analysis of Predicated Architectures

Authors Florian Brandner, Amine Naji

PDF
Thumbnail PDF

File

OASIcs.WCET.2017.6.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Florian Brandner
Amine Naji

Cite As Get BibTex

Florian Brandner and Amine Naji. Worst-Case Execution Time Analysis of Predicated Architectures. In 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017). Open Access Series in Informatics (OASIcs), Volume 57, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/OASIcs.WCET.2017.6

Abstract

The time-predictable design of computer architectures for the use in (hard) real-time systems is becoming more and more important, due to the increasing complexity of modern computer architectures. The design of predictable processor pipelines recently received considerable attention. The goal here is to find a trade-off between predictability and computing power.

Branches and jumps are particularly problematic for high-performance processors. For one, branches are executed late in the pipeline. This either leads to high branch penalties (flushing) or complex software/hardware techniques (branch predictors). Another side-effect of branches is that they make it difficult to exploit instruction-level parallelism due to control dependencies.

Predicated computer architectures allow to attach a predicate to the instructions in a program. An instruction is then only executed when the predicate evaluates to true and otherwise behaves like a simple nop instruction. Predicates can thus be used to convert control dependencies into data dependencies, which helps to address both of the aforementioned problems.

A downside of predicated instructions is the precise worst-case execution time (WCET) analysis of programs making use of them. Predicated memory accesses, for instance, may or may not have an impact on the processor's cache and thus need to be considered by the cache analysis. Predication potentially has an impact on all analysis phases of a WCET analysis tool. We thus explore a preprocessing step that explicitly unfolds the control-flow graph, which allows us to apply standard analyses that are themselves not aware of predication.

Subject Classification

Keywords
  • Predication
  • Worst-Case Execution Time Analysis
  • Real-Time Systems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. F. Brandner, S. Hepp, and D. Prokesch. D5.2 - Initial compiler version, 2012. Report of T-CREST Deliverable D5.2, URL: http://www.t-crest.org/page/results.
  2. P. Degasperi, S. Hepp, W. Puffitsch, and M. Schoeberl. A method cache for Patmos. In Proc. of the Symposium on Object/Component/Service-oriented Real-time Distributed Computing. IEEE, 2014. Google Scholar
  3. M. Delvai, W. Huber, P. Puschner, and A. Steininger. Processor support for temporal predictability - the SPEAR design example. In Proc. of the Euromicro Conference on Real-Time Systems, pages 169-176. IEEE, 2003. URL: http://dx.doi.org/10.1109/EMRTS.2003.1212740.
  4. D. L. Dvorak. NASA study on flight software complexity, 2009. NASA Office of Chief Engineer, Technical Excellence Initiative. Google Scholar
  5. A. E. Eichenberger and E. S. Davidson. Register allocation for predicated code. In Proc. of the Int'l Symposium on Microarchitecture, pages 180-191. IEEE, 1995. Google Scholar
  6. H. Falk, S. Altmeyer, P. Hellinckx, B. Lisper, W. Puffitsch, C. Rochange, M. Schoeberl, R. B. Sørensen, P. Wägemann, and S. Wegener. TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research. In Proc. of the Int'l Workshop on Worst-Case Execution Time Analysis, volume 55 of OASIcs, pages 1-10. Schloss Dagstuhl, 2016. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2016.2.
  7. J. A. Fisher, P. Faraboschi, and Y. Cliff. Embedded Computing: A VLIW Approach to Architecture, Compilers and Tools. Morgan Kaufmann (Elsevier), 2005. Google Scholar
  8. C. B. Geyer, B. Huber, D. Prokesch, and P. Puschner. Time-predictable code execution - instruction-set support for the single-path approach. In Proc. of the Int'l Symposium on Object/component/service-oriented Real-time distributed Computing, pages 1-8, 2013. URL: http://dx.doi.org/10.1109/ISORC.2013.6913195.
  9. P. Hu. Static analysis for guarded code. In Proc. of the Int'l Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, pages 44-56. Springer, 2000. Google Scholar
  10. B. Huber, D. Prokesch, and P. Puschner. Combined WCET analysis of bitcode and machine code using control-flow relation graphs. In Proc. of the Conference on Languages, Compilers and Tools for Embedded Systems, pages 163-172. ACM, 2013. URL: http://dx.doi.org/10.1145/2465554.2465567.
  11. R. Johnson and M. Schlansker. Analysis techniques for predicated code. In Proc. of the Int'l Symposium on Microarchitecture, pages 100-113. IEEE, 1996. Google Scholar
  12. E. Kasapaki, M. Schoeberl, R. B. Sørensen, C. Müller, K. Goossens, and J. Sparsø. Argo: A real-time network-on-chip architecture with an efficient GALS implementation. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 24(2):479-492, Feb 2016. URL: http://dx.doi.org/10.1109/TVLSI.2015.2405614.
  13. S. Metzlaff, I. Guliashvili, S. Uhrig, and T. Ungerer. A dynamic instruction scratchpad memory for embedded processors managed by hardware. In Proc. of the Architecture of Computing Systems Conference, pages 122-134. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-19137-4_11.
  14. J. C. H. Park and M. Schlansker. On predicated execution. Technical report HPL-91-58, HP Laboratories, 1991. Google Scholar
  15. P. Puschner. Transforming execution-time boundable code into temporally predictable code. In Proc. of the IFIP World Computer Congress, pages 163-172. Kluwer, 2002. Google Scholar
  16. J. Reineke. A PRET microarchitecture implementation with repeatable timing and competitive performance. In Proc. of the Int'l Conference on Computer Design, pages 87-93. IEEE, 2012. URL: http://dx.doi.org/10.1109/ICCD.2012.6378622.
  17. J. Reineke, I. Liu, H. D. Patel, S. Kim, and E. A. Lee. PRET DRAM controller: Bank privatization for predictability and temporal isolation. In Proc. of the Conference on Hardware/Software Codesign and System Synthesis, pages 99-108, 2011. Google Scholar
  18. C. Rochange, S. Uhrig, and P. Sainrat. Time-Predictable Architectures. ISTE Wiley, 2014. URL: http://dx.doi.org/10.1002/9781118790229.
  19. S.Abbaspour, A. Jordan, and F. Brandner. Lazy spilling for a time-predictable stack cache: Implementation and analysis. In Proc. of the Workshop on Worst-Case Execution Time Analysis, volume 39 of OASIcs, pages 83-92. Schloss Dagstuhl, 2014. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2014.83.
  20. M. Schoeberl, P. Schleuniger, W. Puffitsch, F. Brandner, and C. W. Probst. Towards a time-predictable dual-issue microprocessor: The Patmos approach. In Bringing Theory to Practice: Predictability and Performance in Embedded Systems, volume 18 of OASIcs, pages 11-21. Schloss Dagstuhl, 2011. URL: http://dx.doi.org/10.4230/OASIcs.PPES.2011.11.
  21. J. W. Sias, W.-M. W. Hwu, and D. I. August. Accurate and efficient predicate analysis with binary decision diagrams. In Proc. of the Int'l Symposium on Microarchitecture, pages 112-123. ACM, 2000. URL: http://dx.doi.org/10.1145/360128.360141.
  22. M. Smelyanskiy, S. A. Mahlke, E. S. Davidson, and H.-H. S. Lee. Predicate-aware scheduling: A technique for reducing resource constraints. In Proc. of the Int'l Symposium on Code Generation and Optimization, pages 169-178. IEEE, 2003. Google Scholar
  23. R. A. Starke, A. Carminati, and R. S. De Oliveira. Evaluating the design of a VLIW processor for real-time systems. ACM Trans. Embed. Comput. Syst., 15(3):46:1-46:26, 2016. URL: http://dx.doi.org/10.1145/2889490.
  24. R. A. Starke, A. Carminati, and R. S. de Oliveira. Evaluation of a low overhead predication system for a deterministic VLIW architecture targeting real-time applications. Microprocessors and Microsystems, 49:1-8, 2017. URL: http://dx.doi.org/http://doi.org/10.1016/j.micpro.2016.11.017.
  25. A. Stoutchinin and G. Gao. If-conversion in SSA form. In Proc. of the Int'l Euro-Par Conference, pages 336-345. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-540-27866-5_43.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact