A Scheduling Strategy for Synchronous Elastic Designs

• Autorzy: Carmona J. , Cortadella J. , Julvez J. , Kishinevsky M.
• Języki publikacji: EN

Abstrakty

EN

With the scaling of process technologies, communication delays represent a bottleneck for the performance of circuits. One of the main issues that has to be handled is the variability of such delays. Latency-insensitive circuits offer a form of elasticity that tolerates variations in those delays. This flexibility usually requires the addition of a control layer that synchronizes the flow of information. This paper proposes a method for eliminating the complexity of the control layer, replacing it by a set of iterative schedulers that decide when to activate computations. Unlike previous approaches, this can be achieved with low complexity algorithms and without extra circuitry.

Słowa kluczowe

EN

marked graph model; tight marking; merging of transitions

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 108, nr 1/2
• Strony: 1--21
• Opis fizyczny: Bibliogr. 27 poz., tab., wykr.

Twórcy

autor

Carmona J.

autor

Cortadella J.

autor

Julvez J.

autor

Kishinevsky M.

• Universitat Politecnica de Catalunya, Carrer de Jordi Girona, Barcelona, Spain,

Bibliografia

• [1] ISCAS benchmark home page. http://www.cerc.utexas.edu/itc99-benchmarks/bench.html.
• [2] J. Boucaron, J. Millo, and R. de Simone. Formal methods of scheduling for latency-insensitive designs. EURASIP journal on Embedded Systems, 2006.
• [3] F. R. Boyer, E. M. Aboulhamid, Y. Savaria, and M. Boyer. Optimal design of synchronous circuits using software pipelining techniques. ACM Trans. Design Autom. Electr. Syst., 6(4):516-532, 2001.
• [4] J. Campos and M. Silva. Structural Techniques and Performance Bounds of Stochastic Petri Net Models. In Advances in Petri Nets 1992, volume 609 of LNCS. Springer, 1992.
• [5] L. Carloni, K. McMillan, and A. Sangiovanni-Vincentelli. Theory of latency-insensitive design. IEEE Transactions on Computer-Aided Design, 20(9):1059-1076, Sept. 2001.
• [6] L. P. Carloni and A. L. Sangiovanni-Vincentelli. Performance analysis and optimization of latency insensitive systems. In Proc. ACM/IEEE Design Automation Conference, pages 361-367, June 2000.
• [7] J. Carmona, J. Cortadella, M. Kishinevsky, and A. Taubin. Elastic circuits. IEEE Transactions on Computer-Aided Design, 28(10):1437-1455, Oct. 2009.
• [8] J. Carmona, J. J´ulvez, J. Cortadella, and M. Kishinevsky. Scheduling synchronous elastic design. In 9th International Conference on Application of Concurrency to System Design (ACSD 2009), pages 52-59, 2009.
• [9] M. Casu and L. Macchiarulo. A new approach to latency insensitive design. In Proc. Digital Automation Conference (DAC), pages 576-581, June 2004.
• [10] T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson. Introduction to Algorithms. McGraw-Hill Higher Education, 2001.
• [11] J. Cortadella, M. Kishinevsky, and B. Grundmann. Synthesis of synchronous elastic architectures. In Proc. ACM/IEEE Design Automation Conference, pages 657-662, July 2006.
• [12] G. Dantzig. Linear programming and extensions. Princeton University Press, Princeton NJ, 1963.
• [13] A. Dasdan and R. K. Gupta. Faster maximum and minimum mean cycle algorithms for system performance analysis. IEEE Transactions on Computer-Aided Design, 17(10):889-899, 1998.
• [14] A. Edman and C. Svensson. Timing closure through a globally synchronous, timing partitioned design methodology. In DAC, pages 71-74, 2004.
• [15] L. Khachian. A polynomial algorithm in linear programming. Soviet Math. Dokl., 20:191-194, 1979.
• [16] V. Klee and G. Minty. How good is the simplex algorithm. In Inequalities III, pages 159-172. Academic Press, New York, 1972.
• [17] J. D. C. Little. A proof of the queueing formula L= _ W. Operations Research, 9:383-387, 1961.
• [18] R. Lu and C.-K. Koh. Performance optimization of latency insensitive systems through buffer queue sizing of communication channels. In Proc. International Conf. Computer-Aided Design (ICCAD), pages 227-231,Nov. 2003.
• [19] J. B. MacQueen. Some methods for classification and analysis of multivariate observations. In Proc. of 5th Berkeley Symp. on Mathematical Statistics and Probability, volume 1, USA, 1967.
• [20] N. Megiddo. Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Comput., 12(4), 1983.
• [21] J.-V. Millo. Ordonnancements priodiques dans les rseaux de processus : Application la conception insensible aux latences. PhD thesis, Universit de Nice-Sophia Antipolis, December 2008.
• [22] T. Murata. Petri Nets: Properties, analysis and applications. Proceedings of the IEEE, pages 541-580, Apr. 1989.
• [23] C. V. Ramamoorthy and G. S. Ho. Performance evaluation of asynchronous concurrent systems using Petri nets. IEEE Trans. Software Eng., 6(5):440-449, 1980.
• [24] J. A. Roy, D. A. Papa, S. N. Adya, H. H. Chan, A. N. Ng, J. F. Lu, and I. L. Markov. Capo: robust and scalable open-source min-cut floorplacer. In ISPD '05, USA, 2005.
• [25] A. Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, 1998.
• [26] M. Silva, E. Teruel, and J. M. Colom. Linear algebraic and linear programming techniques for the analysis of place/transition net systems. In Reisig, W. and Rozenberg, G., editors, Lecture Notes in Computer Science: Lectures on Petri Nets I: Basic Models, volume 1491, pages 309-373. Springer-Verlag, 1998.
• [27] T. Villa, T. Kam, R. K. Brayton, and A. L. Sangiovanni-Vincentelli. Synthesis of Finite State Machines: Logic Optimization. Kluwer Academic Publishers, 1997