Navegar

Colección

Datos Estadísticas

Artículo

Clauss, P.; Fernández, F.J.; Garbervetsky, D.; Verdoolaege, S. "Symbolic polynomial maximization over convex sets and its application to memory requirement estimation" (2009) IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 17(8):983-996
La versión final de este artículo es de uso interno de la institución.
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Memory requirement estimation is an important issue in the development of embedded systems, since memory directly influences performance, cost and power consumption. It is therefore crucial to have tools that automatically compute accurate estimates of the memory requirements of programs to better control the development process and avoid some catastrophic execution exceptions. Many important memory issues can be expressed as the problem of maximizing a parametric polynomial defined over a parametric convex domain. Bernstein expansion is a technique that has been used to compute upper bounds on polynomials defined over intervals and parametric boxes. In this paper, we propose an extension of this theory to more general parametric convex domains and illustrate its applicability to the resolution of memory issues with several application examples. © 2006 IEEE.

Registro:

Documento: Artículo
Título:Symbolic polynomial maximization over convex sets and its application to memory requirement estimation
Autor:Clauss, P.; Fernández, F.J.; Garbervetsky, D.; Verdoolaege, S.
Filiación:Laboratory ICPS-LSIIT, Université Louis Pasteur, 67400 Illkirch, France
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Leiden Institute of Advanced Computer Science, Universiteit Leiden, 2333 CA Leiden, Netherlands
Department of Computer Science, Katholieke Universiteit Leuven, Leuven, Belgium
Palabras clave:Bernstein expansion; Convex polytopes; Memory requirement; Program optimization; Static program analysis; Bernstein expansion; Convex polytopes; Memory requirement; Program optimization; Static program analysis; Amber; Embedded systems; Optimization; Polynomials; Set theory; Topology; Convex optimization
Año:2009
Volumen:17
Número:8
Página de inicio:983
Página de fin:996
DOI: http://dx.doi.org/10.1109/TVLSI.2008.2002049
Título revista:IEEE Transactions on Very Large Scale Integration (VLSI) Systems
Título revista abreviado:IEEE Trans Very Large Scale Integr VLSI Syst
ISSN:10638210
CODEN:IEVSE
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_10638210_v17_n8_p983_Clauss

Referencias:

  • I. M. Verbauwhede, C. J. Scheers, and J. M. Rabaey, quot;Memory estimation for high level synthesis,quot; in Proc. 31st Annu. Conf. Design Automation (DAC'94), New York, NY, 1994, pp. 143-148; P. Grun, F. Balasa, and N. Dutt, quot;Memory size estimation for multimedia applications,quot; in Proc. 6th Int. Workshop on Hardware/Software Codesign (CODES/CASHE'98), Washington, DC, 1998, pp. 145-149; Y. Zhao and S. Malik, quot;Exact memory size estimation for array computations,quot; IEEE Trans. Very Large Scale Integrat. (VLSI) Syst., 8, no. 10, pp. 517-521, Oct. 2000; J. Ramanujam, J. Hong, M. T. Kandemir, and A. Narayan, quot;Reducing memory requirements of nested loops for embedded systems,quot; in Proc. Design Automation Conf., 2001, pp. 359-364; Kjeldsberg, P.G., Catthoor, F., Aas, E.J., quot;Storage requirement estimation for optimized design of data intensive applications,quot (2004) ACM Trans. Des. Autom. Electron. Syst, 9 (2), pp. 133-158
  • H. Zhu, I. I. Luican, and F. Balasa, quot;Memory size computation for multimedia processing applications,quot; in Proc. 2006 Conf. Asia-South Pacific Design Automation (ASP-DAC'06), New York, NY, 2006, pp. 802-807; Feautrier, P., (1996) The Data Parallel Programming Model, LNCS 1132, pp. 79-100. , New York: Springer-Verlag, ch. Automatic Parallelization in the Polytope Model, pp
  • P. Clauss and I. Tchoupaeva, E. Duesterwald, Ed., quot;A symbolic approach to Bernstein expansion for program analysis and optimization,quot; in Proc. 13th Int. Conf. Compiler Construction (CC 2004), Apr. 2004, 2985, pp. 120-133; Loera, J.A.D., Hemmecke, R., Köppe, M., Weismantel, R., quot;Integer polynomial optimization in fixed dimension,quot (2006) Math. Oper. Res, 31 (1), pp. 147-153. , Feb
  • Bernstein, S., (1952) Collected Works, 1. , Moscow: USSR Academy of Sciences
  • Bernstein, S., (1954) Collected Works, 2. , Moscow: USSR Academy of Sciences
  • Berchtold, J., Bowyer, A., quot;Robust arithmetic for multivariate Bernstein-form polynomials,quot (2000) Computer-Aided Design, 32, pp. 681-689
  • Farouki, R., Rajan, V., quot;On the numerical condition of polynomials in Bernstein form,quot (1987) Computer-Aided Geometric Design, 4 (3), pp. 191-216
  • Garloff, J., Vehi, J., Sainz, M.A., Eds., quot;Application of bernstein expansion to the solution of control problems,quot (1999) Proc. Workshop on Applications of Interval Analysis to Systems and Control (MISC'99), pp. 421-430. , Girona Spain
  • J. Garloff and B. Graf, The Use of Symbolic Methods in Control System Analysis and Design. London, UK: Institution of Electrical Engineers (IEE), 1999, ch. Solving Strict Polynomial Inequalities by Bernstein Expansion, pp. 339-352; Martin, R., Shou, H., Voiculescu, I., Bowyer, A., Wang, G., quot;Comparison of interval methods for plotting algebraic curves,quot (2002) Computer Aided Geometric Design, 19, pp. 553-587
  • Pop, S., Cohen, A., Bastoul, C., Girbal, S., Jouvelot, P., Silber, G.-A., Vasilache, N., (2006) quot;Graphite: Loop optimizations based on the polyhedral model for GCC,quot; presented at the 4th GCC Developer's Summit, , Ottawa, Canada
  • E. Schweitz, R. Lethin, A. Leung, and B. Meister, quot;R-stream: A parametric high level compiler,quot; in 10th Annu. Workshop on High Performance Embedded Computing (HPEC 2006), J. Kepner, Ed., Lexington, MA, 2006; S. P. Amarasinghe, J. M. Anderson, M. S. Lam, and C. W. Tseng, quot;The suif compiler for scalable parallel machines,quot; in Proc. 7th SIAM Conf. Parallel Processing for Scientific Computing, 1995; Verdoolaege, S., Seghir, R., Beyls, K., Loechner, V., Bruynooghe, M., quot;Counting integer points in parametric polytopes using Barvinok's rational functions,quot (2007) Algorithmica, 48 (1), pp. 37-66. , Jun
  • S. Verdoolaege, K. Beyls, M. Bruynooghe, and F. Catthoor, quot;Experiences with enumeration of integer projections of parametric poly-topes,quot; in Proc. 14th Int. Conf. Compiler Construction, R. Bodík, Ed., Berlin/Heidelberg, 2005, LNCS3443, pp. 91-105; R. Seghir and V. Loechner, quot;Memory optimization by counting points in integer transformations of parametric polytopes,quot; in Proc. Int. Conf. Compilers, Architectures, and Synthesis for Embedded Systems (CASES 2006), Seoul, Korea, Oct. 2006; Clauss, P., Loechner, V., quot;Parametric analysis of polyhedral iteration spaces,quot (1998) J. VLSI Signal Process, 19
  • Meister, B., quot, Stating and manipulating periodicity in the polytope model (2004) Applications to program analysis and optimization,quot, , Ph.D. dissertation, ICPS, Université Louis Pasteur de Strasbourg, Strasbourg, France
  • Loechner, V., Polylib: A library for manipulating parameterized poly-hedra ICPS, Université Louis Pasteur de Strasbourg, France (1999), Tech. Rep, Mar; T. Rabl, quot;calculation and estimation of parameterized integer polytopes,quot; Master's thesis, Universität Passau, Germany, 2006; Ratschek, H., Rokne, J., (1984) Computer Methods for the Range of Functions, , Chicester, UK: Ellis Horwood
  • Farin, G., (1993) Curves and Surfaces in Computer Aided Geometric Design, , San Diego, CA: Academic Press
  • Zettler, M., Garloff, J., quot;Robustness analysis of polynomials with polynomial parameter dependency using Bernstein expansion,quot (1998) IEEE Trans. Autom. Contr, 43, pp. 425-431
  • Ziegler, G.M., (1995) Lectures on Polytopes, , Berlin, Germany: Springer-Verlag
  • Bauer, C., Frink, A., Kreckel, R., quot;Introduction to the GiNaC framework for symbolic computation within the C++ programming language,quot (2002) J. Symb. Comput, 33 (1), pp. 1-12
  • Haible, B., (2006) Class library for numbers, , http://www.ginac.de/CLN, CLN:, Online, Available
  • Verdoolaege, S., Barvinok, (2007) A library for counting the number of integer points in parametrized and non-parametrized polytopes, , http://freshmeat.net/projects/barvinok, Online, Available
  • Feautrier, P., quot, Dataflow analysis of array and scalar references,quot (1991) Int. J. Parallel Programm, 20 (1), pp. 23-53
  • Barthou, D., Collard, J.-F., Feautrier, P., quot;Fuzzy array dataflow analysis,quot (1997) J. Parallel Distrib. Comput, 40 (2), pp. 210-226
  • Zhu, H., quot, (2006) Computation of memory requirements for multi-dimensional signal processing applications,quot, , Ph.D. dissertation, Univ. Illinois, Chicago
  • Bastoul, C., quot, Code generation in the polyhedral model is easier than you think,quot (2004) Proc. 13th Int. Conf. Parallel Architectures and Compilation Techniques (PACT '04), pp. 7-16. , Washington, DC
  • S. Verdoolaege, H. Nikolov, and T. Stefanov, quot;PN: A tool for improved derivation of process networks,quot; EURASIP, J. Embedded Systems, Special Issue on Embedded Digital Signal Processing Systems, 2007; Clauss, P., Fernández, F.J., D.Garbervetsky, and S.Verdoolaege, quot;Symbolic polynomial maximization over convex sets and its application to memory requirement estimation,quot; Université Louis Pasteur, France ICPS Research Report, , 06-04, 2006
  • Beyls, K., D'Hollander, E., quot;Generating cache hints for improved program efficiency,quot (2005) J. Syst. Arch, 51 (4), pp. 223-250
  • S. Verdoolaege and M. Bruynooghe, M. Beck and T. Stoll, Eds., quot;Algorithms for weighted counting over parametric polytopes: A survey and a practical comparison,quot; in 2008 Int. Conf. Information Theory and Statistical Learning, Jul. 2008; Braberman, V., Garbervetsky, D., Yovine, S., quot;A static analysis for synthesizing parametric specifications of dynamic memory consumption,quot (2006) J. Object Technol, 5 (5), pp. 31-58. , Jun
  • S. Cherem and R. Rugina, quot;Region analysis and transformation for java programs,quot; in Proc. 4th Int. Symp. Memory Management (ISMM'04), New York, NY, 2004, pp. 85-96; A. Salcianu and M. Rinard, quot;Pointer and escape analysis for multithreaded programs,quot; in Proc. 8th ACM SIGPLAN Symp. Principles and Practices of Parallel Programming (PPoPP'01), 2001, pp. 12-23; V. Braberman, F. Fernández, D. Garbervetsky, and S. Yovine, quot;Parametric prediction of heap memory requirements,quot; in Proc. ACM Int. Symp. Memory Management, Jun. 2008, pp. 141-150; V. Maslov and W. Pugh, quot;Simplifying polynomial constraints over integers to make dependence analysis more precise,quot; in CONPAR 94 - VAPP VI, Int. Conf. Parallel and Vector Processing, Sep. 1994; W. Blume and R. Eigenmann, quot;Symbolic range propagation,quot; Univ of Illinois at Urbana-Champaign, Ctr. for Supercomputing Res. & Dev., Tech. Rep. 1381, 1994; Engelen, R.A.V., Gallivan, K., Walsh, B., quot;Parametric timing estimation with the Newton-Gregory formulae,quot; J (2006) Concurrency and Computation: Practice and Experience, 18 (10), pp. 1434-1464. , Sep
  • Darte, A., Schreiber, R., Villard, G., quot;Lattice-based memory allocation,quot (2005) IEEE Trans. Comput, 54, pp. 1242-1257
  • M. Hofmann and S. Jost, quot;Static prediction of heap usage for first-order functional programs,quot; in Proc. 30th ACM SIGPLAN-SIGACT Symp. Principles of Programming Languages (POPL'03), Jan. 2003, pp. 185-197; J. Hughes and L. Pareto, quot;Recursion and dynamic data-structures in bounded space: towards embedded ml programming,quot; in Proc. ICFP '99, 1999, pp. 70-81; L. Unnikrishnan, S. Stoller, and Y. Liu, quot;Optimized live heap bound analysis,quot; in Proc. VMCAI '03, Jan. 2003, 2575, pp. 70-85; W.-N. Chin, H. H. Nguyen, S. Qin, and M. C. Rinard, C. Hankin and I. Siveroni, Eds., quot;Memory usage verification for oo programs,quot; in Proc. 12th Int. Symp. Static Analysis (SAS 2005), 2005, 3672, pp. 70-86

Citas:

---------- APA ----------
Clauss, P., Fernández, F.J., Garbervetsky, D. & Verdoolaege, S. (2009) . Symbolic polynomial maximization over convex sets and its application to memory requirement estimation. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 17(8), 983-996.
http://dx.doi.org/10.1109/TVLSI.2008.2002049
---------- CHICAGO ----------
Clauss, P., Fernández, F.J., Garbervetsky, D., Verdoolaege, S. "Symbolic polynomial maximization over convex sets and its application to memory requirement estimation" . IEEE Transactions on Very Large Scale Integration (VLSI) Systems 17, no. 8 (2009) : 983-996.
http://dx.doi.org/10.1109/TVLSI.2008.2002049
---------- MLA ----------
Clauss, P., Fernández, F.J., Garbervetsky, D., Verdoolaege, S. "Symbolic polynomial maximization over convex sets and its application to memory requirement estimation" . IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 17, no. 8, 2009, pp. 983-996.
http://dx.doi.org/10.1109/TVLSI.2008.2002049
---------- VANCOUVER ----------
Clauss, P., Fernández, F.J., Garbervetsky, D., Verdoolaege, S. Symbolic polynomial maximization over convex sets and its application to memory requirement estimation. IEEE Trans Very Large Scale Integr VLSI Syst. 2009;17(8):983-996.
http://dx.doi.org/10.1109/TVLSI.2008.2002049