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

Article

Embedded Software in Network Processors - Models and Algorithms

Authors:

Samarjit Chakraborty,

Matthias Gries,

Alexander Maxiaguine,

Jonas GreutertAuthors Info & Claims

EMSOFT '01: Proceedings of the First International Workshop on Embedded Software

Pages 416 - 434

Published: 08 October 2001 Publication History

Abstract

We introduce a task model for embedded systems operating on packet streams, such as network processors. This model along with a calculus meant for reasoning about packet streams allows a unified treatment of several problems arising in the network packet processing domain such as packet scheduling, task scheduling and architecture/algorithm explorations in the design of network processors. The model can take into account quality of service constraints such as data throughput and deadlines associated with packets. To illustrate its potential, we provide two applications: (a)a new task scheduling algorithm for network processors to support a mix of real-time and non-real-time flows, (b)a scheme for design space exploration of network processors.

References

[1]

R. Agrawal, R. L. Cruz, C. Okino, and R. Rajan. Performance bounds for flow control protocols. IEEE/ACM Transactions on Networking , 7(3):310-323, 1999.

[2]

N. Audsley, A. Burns, M. Richardson, and A. Wellings. Fixed priority preemptive scheduling: A historical perspective. Real-Time Systems , 8:173-198, 1995.

[3]

F. Baccelli, G. Cohen, G.J. Olsder, and J.-P. Quadrat. Synchronization and Linearity . John Wiley, Sons, New York, 1992.

[4]

S.K. Baruah. Dynamic- and static-priority scheduling of recurring real-time tasks, 2001. To appear in Real-Time Systems.

[5]

A. Bavier and L. Peterson. BERT: A scheduler for best effort and real-time tasks. Technical Report TR-602-99, Department of Computer Science, Princeton University, 2001. Revised in January 2001.

[6]

T. Blickle, J. Teich, and L. Thiele. System-level synthesis using evolutionary algorithms. Design Automation for Embedded Systems , 3(1):23-58, 1998.

[7]

J.Y. Le Boudec. Application of network calculus to guaranteed service networks. IEEE Trans on Information theory , 44(3), May 1998.

[8]

J.Y. Le Boudec and P. Thiran. Network Calculus - A Theory of Deterministic Queuing Systems for the Internet . LNCS 2050, Springer Verlag, 2001.

[9]

G.C. Buttazzo. Hard Real-Time Computing Systems - Predictable Scheduling Algorithms and Applications . Kluwer Academic Publishers, 1997.

[10]

G.C. Buttazzo and F. Sensini. Optimal deadline assignment for scheduling soft aperiodic tasks in hard real-time environments. IEEE Transactions on Computers , 48(10):1035-1052, 1999.

[11]

S. Chakraborty, T. Erlebach, and L. Thiele. On the complexity of scheduling conditional real-time code. In Proc. 7th International Workshop on Algorithms and Data Structures (WADS) , LNCS 2125, 2001.

[12]

R.L. Cruz. A calculus for network delay. IEEE Trans. Information Theory , 37(1):114-141, 1991.

[13]

K. Deb. Multi-objective optimization using evolutionary algorithms . John Wiley, Chichester, 2001.

[14]

D. Decasper, Z. Dittia, G.M. Parulkar, and B. Plattner. Router plugins: A software architecture for next-generation routers. IEEE/ACM Transactions on Networking , 8(1):2-15, 2000.

[15]

A. Demers, S. Keshav, and S. Shenkar. Analysis and simulation of a fair queueing algorithm. Journal of Internetworking Research and Experience , 1(1):3-26, 1990.

[16]

E. Kohler, R. Morris, B. Chen, J. Jannotti, and M.F. Kaashoek. The Click modular router. ACM Transactions on Computer Systems , 18(3):263-297, 2000.

[17]

J. Lehoczky, L. Sha, and Y. Ding. The rate monotonic scheduling algorithm. In Proc. IEEE Real-Time Systems Symposium , pages 166-171, 1989.

[18]

C. Liu and J. Layland. Scheduling algorithms for multiprogramming in hard realtime environment. Journal of the ACM , 20(1):46-61, 1973.

[19]

L. Thiele M. Eisenring, E. Zitzler. Handling conflicting criteria in embedded system design. IEEE Design & Test of Computers , 17(2):51-59, 2000.

[20]

G. De Micheli. Synthesis and Optimization of Digital Circuits . McGraw-Hill International Editions, New York, 1994.

[21]

A.K. Mok and D. Chen. A multiframe model for real-time tasks. IEEE Transactions on Software Engineering , 23(10):635-645, 1997.

[22]

The Moses project homepage. http://www.tik.ee.ethz.ch/ ~ moses/.

[23]

M. Naedele, L. Thiele, and M. Eisenring. General task and resource models for processor task scheduling, 1998. TIK Report 45, ETH Zürich.

[24]

M. Naedele, L. Thiele, and M. Eisenring. Characterizing variable task releases and processor capacities. In Proceedings of the 14th IFAC World Congress , 1999.

[25]

A.K. Parekh and R.G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: the single-node case. IEEE/ACM Transactions on Networking , 1(3):344-357, 1993.

[26]

S. Prakash and A.C. Parker. Synthesis of application-specific multiprocessor systems including memory components. In Proc. IEEE Application Specific Array Processors , 1992.

[27]

X. Qie, A. Bavier, L. Peterson, and S. Karlin. Scheduling computations on a software-based router. In Proc. SIGMETRICS , 2001.

[28]

S. Shenker and J. Wroclawski. General characterization parameters for integrated service network elements. RFC 2215, IETF, September 1997.

[29]

L. Thiele, S. Chakraborty, and M. Naedele. Real-time calculus for scheduling hard real-time systeme. In Proc. IEEE Internation Conference on Circuits and Systems , 2000.

[30]

E. Zitzler, J. Teich, and S.S. Bhattacharyya. Evolutionary algorithms for the synthesis of embedded software. IEEE Transactions on VLSI Systems , 8(4):452 - 456, August 2000.

Cited By

Kuiper GKurtin PBekooij M(2017)Hybrid Latency Minimization Approach using Model Checking and Dataflow AnalysisProceedings of the 20th International Workshop on Software and Compilers for Embedded Systems10.1145/3078659.3078665(41-50)Online publication date: 12-Jun-2017
https://dl.acm.org/doi/10.1145/3078659.3078665
Henia RRioux LSordon NGarcia GPanunzio MWoodside MWoodside M(2015)Integrating Formal Timing Analysis in the Real-Time Software Development ProcessProceedings of the 2015 Workshop on Challenges in Performance Methods for Software Development10.1145/2693561.2693562(35-40)Online publication date: 31-Jan-2015
https://dl.acm.org/doi/10.1145/2693561.2693562
Garay GOrtega JDíaz ACorrales LAlarcón-Aquino V(2013)System performance evaluation by combining RTC and VHDL simulationJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2013.09.00659:10(1277-1298)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1016/j.sysarc.2013.09.006
Show More Cited By

Embedded Software in Network Processors - Models and Algorithms
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

Timing analysis of embedded software for speculative processors
ISSS '02: Proceedings of the 15th international symposium on System Synthesis

Static timing analysis of embedded software is important for systems with hard real-time constraints. To accurately estimate time bounds, it is essential to model the underlying micro architecture. In this paper, we study static timing analysis of ...
Branchless cycle prediction for embedded processors
SAC '06: Proceedings of the 2006 ACM symposium on Applied computing

Modern embedded processors access the Branch Target Buffer (BTB) every cycle to speculate branch target addresses. Such accesses, quite often, are unnecessary as there is no branch instruction among those fetched.In this work we introduce Branchless ...
A retargetable register allocation framework for embedded processors
LCTES '04

This paper describes the FlexCC2 register allocation framework. FlexCC2 is an optimizing retargetable C compiler for embedded processors, and in particular for DSP processors. Embedded processors often contain features such as irregular and constrained ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EMSOFT '01: Proceedings of the First International Workshop on Embedded Software

October 2001

502 pages

ISBN:3540426736

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 08 October 2001

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kuiper GKurtin PBekooij M(2017)Hybrid Latency Minimization Approach using Model Checking and Dataflow AnalysisProceedings of the 20th International Workshop on Software and Compilers for Embedded Systems10.1145/3078659.3078665(41-50)Online publication date: 12-Jun-2017
https://dl.acm.org/doi/10.1145/3078659.3078665
Henia RRioux LSordon NGarcia GPanunzio MWoodside MWoodside M(2015)Integrating Formal Timing Analysis in the Real-Time Software Development ProcessProceedings of the 2015 Workshop on Challenges in Performance Methods for Software Development10.1145/2693561.2693562(35-40)Online publication date: 31-Jan-2015
https://dl.acm.org/doi/10.1145/2693561.2693562
Garay GOrtega JDíaz ACorrales LAlarcón-Aquino V(2013)System performance evaluation by combining RTC and VHDL simulationJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2013.09.00659:10(1277-1298)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1016/j.sysarc.2013.09.006
Georges JDivoux TRondeau ÉLasaulce SFiems DHarrison PVandendorpe L(2011)Network calculusProceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools10.5555/2151688.2151733(399-407)Online publication date: 16-May-2011
https://dl.acm.org/doi/10.5555/2151688.2151733
Vastag SLasaulce SFiems DHarrison PVandendorpe L(2011)Modeling quantitative requirements in SLAs with network calculusProceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools10.5555/2151688.2151732(391-398)Online publication date: 16-May-2011
https://dl.acm.org/doi/10.5555/2151688.2151732
Bouillard AJunier ALasaulce SFiems DHarrison PVandendorpe L(2011)Worst-case delay bounds with fixed priorities using network calculusProceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools10.5555/2151688.2151731(381-390)Online publication date: 16-May-2011
https://dl.acm.org/doi/10.5555/2151688.2151731
Jian-ping WYun-sheng ZHong-xia HGuo ZTan HZhang JYang DWu Y(2011)Analysis and compute of real-time signal flow delay for network on-chipProceedings of the 2011 International Conference on Innovative Computing and Cloud Computing10.1145/2071639.2071666(107-112)Online publication date: 13-Aug-2011
https://dl.acm.org/doi/10.1145/2071639.2071666
Bouillard AJouhet LThierry É(2010)Tight performance bounds in the worst-case analysis of feed-forward networksProceedings of the 29th conference on Information communications10.5555/1833515.1833708(1316-1324)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833708
Bouillard AJouhet LThierry EBaras J(2008)Computation of a (min,+) multi-dimensional convolution for end-to-end performance analysisProceedings of the 3rd International Conference on Performance Evaluation Methodologies and Tools10.4108/ICST.VALUETOOLS2008.4349(1-7)Online publication date: 20-Oct-2008
https://dl.acm.org/doi/10.4108/ICST.VALUETOOLS2008.4349
Perathoner SWandeler EThiele LHamann ASchliecker SHenia RRacu RErnst RHarbour MKirsch CWilhelm R(2007)Influence of different system abstractions on the performance analysis of distributed real-time systemsProceedings of the 7th ACM & IEEE international conference on Embedded software10.1145/1289927.1289959(193-202)Online publication date: 30-Sep-2007
https://dl.acm.org/doi/10.1145/1289927.1289959
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents