W. Abu-sufah, Improving the Performance of Virtual Memory Computers, 1978.

O. Azizi, J. Collins, D. Patil, H. Wang, and M. Horowitz, Processor Performance Modeling using Symbolic Simulation, ISPASS 2008, IEEE International Symposium on Performance Analysis of Systems and software, pp.127-138, 2008.
DOI : 10.1109/ISPASS.2008.4510745

R. Beigel, The polynomial method in circuit complexity, [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pp.82-95, 1993.
DOI : 10.1109/SCT.1993.336538

F. Bouchez, A. Darte, C. Guillon, and F. Rastello, Register Allocation: What does the NP-completeness Proof of Chaitin et al. Really Prove?, Fifth Annual Workshop on Duplicating, Deconstructing and Debunking (WDDD2006) (at ISCA-33), 2006.

P. Briggs, K. D. Cooper, and L. Torczon, Improvements to graph coloring register allocation, ACM Transactions on Programming Languages and Systems, vol.16, issue.3, pp.428-455, 1994.
DOI : 10.1145/177492.177575
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.253

A. E. Brown, J. P. Eckhardt, M. D. Mayo, W. A. Svarczkopf, and S. P. Gaur, Improved performance of IBM Enterprise System/9000 bipolar logic chips, IBM J. Res. Dev, vol.36, issue.5, pp.829-834, 1992.

S. Burckel, Closed iterative calculus, Theoretical Computer Science, pp.371-378, 1996.
DOI : 10.1016/0304-3975(95)00171-9
URL : http://doi.org/10.1016/0304-3975(95)00171-9

S. Burckel and E. Gioan, In Situ Design of Register Operations, 2008 IEEE Computer Society Annual Symposium on VLSI, pp.287-292, 2008.
DOI : 10.1109/ISVLSI.2008.62
URL : https://hal.archives-ouvertes.fr/lirmm-00287659

S. Burckel and M. Morillon, Three generators for minimal writing-space computations, Theoretical Informatics and Application, pp.131-138, 2000.
DOI : 10.1051/ita:2000110
URL : http://archive.numdam.org/article/ITA_2000__34_2_131_0.pdf

S. Burckel and M. Morillon, Quadratic Sequential Computations of Boolean Mappings, Theory of Computing Systems, pp.519-525, 2004.
DOI : 10.1007/s00224-003-1069-7

S. Burckel and M. Morillon, Sequential computation of linear Boolean mappings, Theoretical Computer Science, pp.287-292, 2004.
DOI : 10.1016/j.tcs.2003.11.027

H. Out-written and M. Johnson, Code optimization, 2007.

G. J. Chaitin, Register allocation & spilling via graph coloring, SIGPLAN '82: Proceedings of the 1982 SIGPLAN symposium on Compiler construction, pp.98-105, 1982.
DOI : 10.1145/800230.806984

G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins et al., Register allocation via coloring, Computer Languages, vol.6, issue.1, pp.47-57, 1981.
DOI : 10.1016/0096-0551(81)90048-5

S. Chatterjee, V. Vibhor, A. R. Jain, S. Lebeck, M. Mundhra et al., Nonlinear array layouts for hierarchical memory systems, Proceedings of the 13th international conference on Supercomputing , ICS '99, pp.444-453, 1999.
DOI : 10.1145/305138.305231

A. Church, An Unsolvable Problem of Elementary Number Theory, American Journal of Mathematics, vol.58, issue.2, pp.356-363, 1936.
DOI : 10.2307/2371045

J. Cohoon and J. Davidson, C++ Program Design: An Introduction to Programming and Object-Oriented Design, 1997.

Y. Crama and P. L. Hammer, Boolean Functions -Theory, Algorithms, and Applications, 2008.

J. Daintith, A Dictionary of Computing, 2004.
DOI : 10.1093/acref/9780199234004.001.0001

P. S. Friendly, D. , and Y. Patt, Putting the fill unit to work: dynamic optimizations for trace cache microprocessors, Proceedings. 31st Annual ACM/IEEE International Symposium on Microarchitecture, pp.173-181, 1998.
DOI : 10.1109/MICRO.1998.742779

M. Frigo, C. E. Leiserson, H. Prokop, S. Ramachandran, and Z. W. , Cache-oblivious algorithms (extended abstract), Proc. 40th Annual Symposium on Foundations of Computer Science, pp.285-397, 1999.

L. George and A. W. Appel, Iterated register coalescing, ACM Transactions on Programming Languages and Systems, vol.18, issue.3, pp.300-324, 1996.
DOI : 10.1145/229542.229546
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.4803

F. Havet, Graph colouring and applications. HabilitationàHabilitationà diriger des recherches, 2007.

K. Hoste and L. Eeckhout, Cole, Proceedings of the sixth annual IEEE/ACM international symposium on Code generation and optimization , CGO '08, 2008.
DOI : 10.1145/1356058.1356080

R. Ismail and V. M. Rooney, Microprocessor Hardware and Software Concepts, 1987.

S. Hammarling, J. Dongarra, and J. , Du Croz and I. Duff. A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software, pp.1-17, 1990.

J. Jannotti, Ars Technicia: The PC Enthusiasts Resource, 2001.

U. Meier, K. Gallivan, W. Jrdby, and A. Sameh, The impact of hierarchical memory systems on linear algebra algorithm design, 1987.

J. Keller, The 21264: a superscalar alpha processor with out-of-order execution. 9th Annual Microprocessor Forum, 1996.

]. D. König, ???ber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Mathematische Annalen, vol.15, issue.4, pp.453-465, 1916.
DOI : 10.1007/BF01456961

A. Kumar, The HP PA-8000 RISC CPU, Hot Chips VIII, 1996.
DOI : 10.1109/40.592310

M. S. Lam, E. E. Rothberg, and M. E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pp.63-74, 1991.

V. K. Leont-'ev, Certain problems associated with boolean polynomials Computing Center, Russian academy of Sciences, ul, 1998.

E. E. Rothberg, M. S. Lam, and M. E. Wolf, The cache performance and optimization of blocked algorithms, The Sixth International Conference on Architectural Support for Programming Languages and Operating Systems, 1991.

F. J. Macwilliams, N. J. Sloane, /. J. Macwilliams, and N. J. Sloane, The theory of error correcting codes, sole distributors for the U.S.A. and Canada, 1977.

A. C. Mckeller and E. G. Coffman, Organizing matrices and matrix operations for paged memory systems, Communications of the ACM, vol.12, issue.3, pp.153-165, 1969.
DOI : 10.1145/362875.362879

J. Michael, M. Penner, K. Viktor, and . Prasanna, Optimizing graph algorithms for improved cache performance, Proc. Intl Parallel and Distributed Processing Symp, pp.769-782, 2002.

R. C. Miller and B. J. Oldfield, Producing Computer Instructions for the PACT I Compiler, Journal of the ACM, vol.3, issue.4, 1956.
DOI : 10.1145/320843.320847

J. Miranda, The Usage of Compiler Optimization by Programmers, Thesis, 2001.

N. Park, D. Kang, K. Bondalapati, and V. K. Prasanna, Dynamic data layouts for cache-conscious factorization of DFT, Proceedings 14th International Parallel and Distributed Processing Symposium. IPDPS 2000, pp.693-701, 2000.
DOI : 10.1109/IPDPS.2000.846054

S. Bennett, E. Rotenberg, and J. E. Smith, Trace cache: a low latency approach to high band-width instruction fetching, 29th International Symposium on Microarchitecture, pp.24-34, 1996.

S. Rudeanu, On the decomposition of boolean functions via boolean equations. j-jucs, pp.1294-1301, 2004.

S. Rus and L. Rauchwerger, Compiler technology for migrating sequential code to multithreaded Architectures, 2006.

K. S. Mckinley, S. Carr, and C. Tseng, Compiler optimization for improving data locality, Proceedings of the Sixth International Conference on Architectural Support for Programming Languages and Operating Systems

R. Muth, S. Debray, W. Evans, and B. D. Sutter, Compiler techniques for code compaction, ACM Trans. on Programming Languages and Systems, vol.22, issue.2, pp.378-415, 2000.

V. Sarkar, Code optimization of parallel programs, Proceedings of the sixth annual IEEE/ACM international symposium on Code generation and optimization , CGO '08, pp.1-1, 2008.
DOI : 10.1145/1356058.1356087

V. Sarkar, Challenges in Code Optimization of Parallel Programs, CC, 2009.
DOI : 10.1007/978-3-642-00722-4_1

I. L. Sayers, A. P. Robson, A. E. Adams, and E. G. Chester, Principles of microprocessors, 1991.

P. B. Schneck, A survey of compiler optimization techniques, Proceedings of the annual conference on , ACM'73, pp.106-113, 1973.
DOI : 10.1145/800192.805690

D. S. Scott and C. Strachey, Towards a mathematical semantics for computer languages, 1971.

R. Tomasulo, An Efficient Algorithm for Exploiting Multiple Arithmetic Units, IBM Journal of Research and Development, vol.11, issue.1, pp.25-233, 1967.
DOI : 10.1147/rd.111.0025

A. Turing, Computability and ??-definability, The Journal of Symbolic Logic, vol.42, issue.04, pp.153-163, 1937.
DOI : 10.2307/2371045

R. , C. Whaley, and J. J. Dongarra, Automatically tuned linear algebra software, Supercomputing '98: Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), pp.1-27, 1998.
DOI : 10.1109/sc.1998.10004
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.108.3487

M. E. Wolf and S. M. Lam, A data locality optimizing algorithm, The SIGPLAN'91 Conference on Programing Language Design and Implementation, pp.30-44, 1991.

M. J. Wolfe, More iteration space tiling, Proceedings of the 1989 ACM/IEEE conference on Supercomputing , Supercomputing '89, 1989.
DOI : 10.1145/76263.76337
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.578.5640

L. Unité-de-recherche-inria-lorraine, Technopôle de Nancy-Brabois -Campus scientifique 615, rue du Jardin Botanique -BP 101 -54602 Villers-lès-Nancy Cedex (France) Unité de recherche INRIA Futurs : Parc Club Orsay Université -ZAC des Vignes 4

I. Unité-de-recherche and . Rennes, IRISA, Campus universitaire de Beaulieu -35042 Rennes Cedex (France) Unité de recherche INRIA Rhône-Alpes : 655, avenue de l'Europe -38334 Montbonnot Saint-Ismier (France) Unité de recherche INRIA Rocquencourt : Domaine de Voluceau -Rocquencourt -BP 105 -78153 Le Chesnay Cedex (France) Unité de recherche, 2004.

I. De-voluceau-rocquencourt, BP 105 -78153 Le Chesnay Cedex (France) ?tt??????????r????r