Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Prevent Deadlock and Remove Blocking for Self-Timed Systems

  • Conference paper
  • First Online:

Abstract

In the design of distributed embedded systems, designers face two problems: how to prevent deadlock and how to improve performance. An accurate model providing abstractions for functionality and performance is important to solve these problems. Self-timed system model that conducts communications based on handshaking protocols is suitable to model these distributed embedded systems. This paper studies the fundamental properties of self-timed systems and proposes solutions of the above two problems. First, we present the necessary and sufficient conditions for a self-timed system constructed from an application to incur deadlocks; then we propose approaches to prevent any deadlocks in constructing self-timed systems. Second, we observe that the different pace of data progressing on two paths, having common source/destination nodes, may cause blocking events (not deadlock) which dramatically degrade the system performance. We establish theorems to detect blocking events and design Mixed-Integer Linear Programming (MILP) formulas to eliminate these events. Experimental results show that most self-timed systems constructed by a straightforward approach incur possible deadlocks, while our proposed methods guarantee no deadlocks. Furthermore, our proposed techniques to eliminate blocking events achieve 48.23 % performance improvements on average, compared with the straightforward approach.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

Notes

  1. 1.

    There are two types of buffers: in-buffer and out-buffer. The in-buffer(out-buffer) indicates that the buffering unit is attached to the in-port(out-port) of ansu.

References

  1. Beerel, P.A., Lines, A., Davies, M., Kim, N.H.: Slack matching asynchronous designs. In: Proceedings of ASYNC, pp. 184–194 (2006)

    Google Scholar 

  2. Burns, S.M.: Performance analysis and optimization of asynchronous circuits (1991)

    Google Scholar 

  3. Chao, L.F., Sha, E.M.: Scheduling data-flow graphs via retiming and unfolding. IEEE Trans. Parallel Dist. Syst.8(12), 1259–1267 (1997)

    Article  Google Scholar 

  4. Chong, J., Satish, N., Catanzaro, B.C., Ravindran, K., Keutzer, K.: Efficient parallelization of H. 264 decoding with macro block level scheduling. In: Proceedings of ICME, pp. 1874–1877 (2007)

    Google Scholar 

  5. Dick, R.P., Rhodes, D.L., Wolf, W.: TGFF: task graphs for free. In: Proceedings of CODES, pp. 97–101 (1998)

    Google Scholar 

  6. Gill, G., Singh, M.: Automated microarchitectural exploration for achieving throughput targets in pipelined asynchronous systems. In: Proceedings of ASYNC, pp. 117–127. IEEE (2010)

    Google Scholar 

  7. Greenstreet, M.R.: Stari: A Technique for High-bandwidth Communication. Ph.D. thesis, Princeton, NJ, USA (1993), uMI Order No. GAX93-11221

    Google Scholar 

  8. Jiang, W., Zhuge, Q., Chen, X., Yang, L., Yi, J., Sha, E.M.: Properties of self-timed ring architectures for deadlock-free and consistent configuration reaching maximum throughput. J. Signal Process. Syst. pp. 1–15 (2015), http://dx.doi.org/10.1007/s11265-015-0984-6, doi:10.1007/s11265-015-0984-6

  9. Jiang, W., Zhuge, Q., Yi, J., Yang, L., Sha, E.H.: On self-timed ring for consistent mapping and maximum throughput. In: Proceedings of RTCSA, pp. 1–9 (2014)

    Google Scholar 

  10. Johnson, D.B.: Finding all the elementary circuits of a directed graph. SIAM J. Comput.4(1), 77–84 (1975)

    Article MathSciNet MATH  Google Scholar 

  11. Kroft, D.: All paths through a maze. Proc. IEEE55(1), 88–90 (1967)

    Article  Google Scholar 

  12. Parhi, K.K., Messerschmitt, D.G.: Static rate-optimal scheduling of iterative data-flow programs via optimum unfolding. IEEE Trans. Comput.40(2), 178–195 (1991)

    Article  Google Scholar 

  13. Prakash, P., Martin, A.J.: Slack matching quasi delay-insensitive circuits. In: Proceedings of ASYNC, pp. 195–204. IEEE (2006)

    Google Scholar 

  14. Smirnov, A., Taubin, A.: Heuristic based throughput analysis and optimization of asynchronous pipelines. In: Proceedings of ASYNC, pp. 162–172. IEEE (2009)

    Google Scholar 

  15. Stuijk, S., Geilen, M., Basten, T.: SDF3: SDF for free. In: Proceedings of ACSD, vol. 6, pp. 276–278 (2006)

    Google Scholar 

  16. Van Berkel, C., Josephs, M.B., Nowick, S.M.: Applications of asynchronous circuits. Proc. IEEE87(2), 223–233 (1999)

    Article  Google Scholar 

  17. Williams, T.E.: Performance of iterative computation in self-timed rings. J. VLSI Signal Process. Syst. Signal, Image Video Technol. vol. 7(1–2), pp. 17–31 (1994)

    Google Scholar 

  18. Wolf, M.: High-Performance Embedded Computing: Applications in Cyber-Physical Systems and Mobile Computing. Morgan Kaufmann, Newnes (2014)

    Google Scholar 

  19. Zivojnovic, V., Velarde, J., Schlager, C., Meyr, H.: DSPstone: a DSP-oriented benchmarking methodology. In: Proceedings of ICSPAT (1994)

    Google Scholar 

Download references

Acknowledgements

This work is partially supported by National 863 Program 2013AA013202, 2015AA015304, Chongqing High-Tech Research Program cstc2014yykfB40007, NSFC 61472052, NSFC 61173014.

Author information

Authors and Affiliations

  1. College of Computer Science, Chongqing University, Chongqing, 400044, China

    Edwin H. -M. Sha, Weiwen Jiang, Qingfeng Zhuge, Xianzhang Chen & Lei Yang

  2. Key Laboratory of Dependable Service Computing in Cyber Physical Society, Ministry of Education, Chongqing, 400044, China

    Edwin H. -M. Sha & Qingfeng Zhuge

Authors
  1. Edwin H. -M. Sha

    You can also search for this author inPubMed Google Scholar

  2. Weiwen Jiang

    You can also search for this author inPubMed Google Scholar

  3. Qingfeng Zhuge

    You can also search for this author inPubMed Google Scholar

  4. Xianzhang Chen

    You can also search for this author inPubMed Google Scholar

  5. Lei Yang

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toWeiwen Jiang.

Editor information

Editors and Affiliations

  1. Central South University, Changsha, China

    Guojun Wang

  2. The University of Sydney, Sydney, New South Wales, Australia

    Albert Zomaya

  3. University of Murcia, Murcia, Murcia, Spain

    Gregorio Martinez

  4. Hunan University , Changsha, China

    Kenli Li

Rights and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Sha, E.H.M., Jiang, W., Zhuge, Q., Chen, X., Yang, L. (2015). Prevent Deadlock and Remove Blocking for Self-Timed Systems. In: Wang, G., Zomaya, A., Martinez, G., Li, K. (eds) Algorithms and Architectures for Parallel Processing. ICA3PP 2015. Lecture Notes in Computer Science(), vol 9528. Springer, Cham. https://doi.org/10.1007/978-3-319-27119-4_11

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp