A continuous time markov decision process based on-chip buffer allocation methodology

ABSTRACT

We have presented an optimal on-chip buffer allocation and buffer insertion methodology which uses stochastic models of the architecture. This methodology uses finite buffer space and presents a method to distribute this finite space in an optimal fashion. Such a methodology is useful in managing the scarce buffer resources available on chip as compared to network based data communication which can have large buffer space. The methodology also uses Continuous Time Markov Decision Processes CTMDPs. The modeling of this problem in terms of a CTMDP framework lead to a nonlinear formulation due to usage of bridges in the bus architecture. We present a methodology to split the problem into several smaller, though linear systems and we then solve these subsystems.

REFERENCES

• 1: Tudor Dumitraş , Sam Kerner , Radu Mărculescu, Towards on-chip fault-tolerant communication, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119817]
• 2: E. Feinberg. Optimal control of average reward constrained continuous time finite markov decision processes. Proceedings of the IEEE Conference on Decision and Control, pages 3805--3810, 2002.
• 3: E. Feinberg and A. Shwartz. Handbook of Markov Decision Processes methods and applications. Kluwer, 2002.
• 4: Kanishka Lahiri , Anand Raghunathan , Sujit Dey, Efficient exploration of the SoC communication architecture design space, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 5: Kanishka Lahiri , Anand Raghunathan , Ganesh Lakshminarayana, LOTTERYBUS: a new high-performance communication architecture for system-on-chip designs, Proceedings of the 38th conference on Design automation, p.15-20, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378252]
• 6: Nattawut Thepayasuwan , Vaishali Damle , Alex Doboli, Bus Architecture Synthesis for Hardware-Software Co-Design of Deep Submicron Systems on Chip, Proceedings of the 21st International Conference on Computer Design, p.126, October 13-15, 2003
• 7: Qinru Qiu , Qing Wu , Massoud Pedram, Dynamic power management of complex systems using generalized stochastic Petri nets, Proceedings of the 37th conference on Design automation, p.352-356, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337438]
• 8: C. Taylor and S. Dey. Orbit: An adaptive data shaping technique for robust wireless video clip communication. Proc. of Asilomar Conference on Signals,Systems and Computers, pages 3081--3085, 2003.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.4 VLSI Systems

Additional Classification:
  C. Computer Systems Organization
  C.m MISCELLANEOUS

General Terms:
Design

Keywords:
SoC, buffer space management