{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,6]],"date-time":"2023-01-06T05:40:36Z","timestamp":1672983636994},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2004,7]]},"abstract":"Placement is key issue of integrated circuit physical design. There exist some techniques inspired in thermodynamics coping with this problem as Simulated Annealing. In this article, we present a combinatorial optimization method directly derived from both Thermodynamics and Information Theory. In TCO (Thermodynamic Combinatorial Optimization), two kinds of processes are considered: microstate and macrostate transformations. Applying the Shannon's definition of entropy to reversible microstate transformations, a probability of acceptance based on Fermi--Dirac statistics is derived. On the other hand, applying thermodynamic laws to macrostate transformations, an efficient annealing schedule is provided. TCO has been compared with a custom Simulated Annealing (SA) tool on a set of benchmark circuits for the FPGA (Field Programmable Gate Arrays) placement problem. TCO has provided the high-quality results of SA, while inheriting the adaptive properties of Natural Optimization (NO).<\/jats:p>","DOI":"10.1145\/1013948.1013951","type":"journal-article","created":{"date-parts":[[2004,10,7]],"date-time":"2004-10-07T17:38:56Z","timestamp":1097170736000},"page":"310-332","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Annealing placement by thermodynamic combinatorial optimization"],"prefix":"10.1145","volume":"9","author":[{"given":"Juan D","family":"Vicente","sequence":"first","affiliation":[{"name":"CIEMAT (Laboratorio General de Electr\u00f3nica), Madrid, Spain"}]},{"given":"Juan","family":"Lanchares","sequence":"additional","affiliation":[{"name":"Universidad Complutense de Madrid (Spain), Madrid, Spain"}]},{"given":"Rom\u00e1n","family":"Hermida","sequence":"additional","affiliation":[{"name":"Universidad Complutense de Madrid (Spain), Madrid, Spain"}]}],"member":"320","published-online":{"date-parts":[[2004,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aarts E. and Korst J. 1989. Simulated Annealing and Boltzmann Machines A Stochastic Approach to Combinatorial Optimization and Neural Computing. Wiley New York. Aarts E. and Korst J. 1989. Simulated Annealing and Boltzmann Machines A Stochastic Approach to Combinatorial Optimization and Neural Computing. Wiley New York."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications (FPL)","author":"Betz V.","unstructured":"Betz , V. and Rose , J. , Eds . 1997. VPR: A new packing, placement and routing tools for FPGA research . In Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications (FPL) ( Oxford, UK. Sept). Springer-Verlag, New York, 213--222. Betz, V. and Rose, J., Eds. 1997. VPR: A new packing, placement and routing tools for FPGA research. In Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications (FPL) (Oxford, UK. Sept). Springer-Verlag, New York, 213--222."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.711315"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the ACM\/IEEE DAC, 284--290","author":"Breuer M. A.","year":"1977","unstructured":"Breuer , M. A. 1977 . A class of min-cut placement algorithms . In Proceedings of the ACM\/IEEE DAC, 284--290 . Breuer, M. A. 1977. A class of min-cut placement algorithms. In Proceedings of the ACM\/IEEE DAC, 284--290."},{"key":"e_1_2_1_5_1","unstructured":"Callen H. B. 1960. Thermodynamics. Willey New York. Callen H. B. 1960. Thermodynamics. Willey New York."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design","author":"Cheng C. E.","year":"1994","unstructured":"Cheng , C. E. 1994 . RISA: Accurate and efficient placement routability modeling . In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design ( San Jose, Calif., Nov.). ACM, New York, 690--695. Cheng, C. E. 1994. RISA: Accurate and efficient placement routability modeling. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (San Jose, Calif., Nov.). ACM, New York, 690--695."},{"key":"e_1_2_1_7_1","volume-title":"Genetic Placement. Proc. IEEE ICCAD","author":"Cohoon J. P.","unstructured":"Cohoon , J. P. and Paris , W . 1986 . Genetic Placement. Proc. IEEE ICCAD . Washington, DC, United States, 422--425. Cohoon, J. P. and Paris, W. 1986. Genetic Placement. Proc. IEEE ICCAD. Washington, DC, United States, 422--425."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 24th Euromicro Conference","author":"de Vicente J.","unstructured":"de Vicente , J. , Lanchares , J. , and Hermida R . 1998. RSR: A new rectilinear steiner minimum tree approximation for FPGA placement and global routing . In Proceedings of the 24th Euromicro Conference ( V\u00e4steras, Sweden). 192--195. de Vicente, J., Lanchares, J., and Hermida R. 1998. RSR: A new rectilinear steiner minimum tree approximation for FPGA placement and global routing. In Proceedings of the 24th Euromicro Conference (V\u00e4steras, Sweden). 192--195."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the International Workshop on Field Programmable Logic and Applications (FPL), (Glasgow). Lecture Notes in Computer Science","volume":"1673","author":"de Vicente J.","unstructured":"de Vicente , J. , Lanchares , J. , and Hermida R . 1999. Placement optimization based on global routing updating for system partitioning onto multi-FPGA mesh topologies . In Proceedings of the International Workshop on Field Programmable Logic and Applications (FPL), (Glasgow). Lecture Notes in Computer Science , vol. 1673 . Springer-Verlag, New York, 91--100. de Vicente, J., Lanchares, J., and Hermida R. 1999. Placement optimization based on global routing updating for system partitioning onto multi-FPGA mesh topologies. In Proceedings of the International Workshop on Field Programmable Logic and Applications (FPL), (Glasgow). Lecture Notes in Computer Science, vol. 1673. Springer-Verlag, New York, 91--100."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 11th IEEE International Workshop on Rapid System Prototyping. IEEE Computer Society Press, Los Alamitos, Calif., 188--193","author":"de Vicente J.","unstructured":"de Vicente , J. , Lanchares , J. , and Hermida R . 2000. Adaptive placement by natural optimization . In Proceedings of the 11th IEEE International Workshop on Rapid System Prototyping. IEEE Computer Society Press, Los Alamitos, Calif., 188--193 . de Vicente, J., Lanchares, J., and Hermida R. 2000. Adaptive placement by natural optimization. In Proceedings of the 11th IEEE International Workshop on Rapid System Prototyping. IEEE Computer Society Press, Los Alamitos, Calif., 188--193."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1109\/TPAMI.1984.4767596","article-title":"Stochastic relaxation, Gibbs distribution and the Bayesian restoration in images","volume":"6","author":"Geman S.","year":"1984","unstructured":"Geman S. and Geman , D. 1984 . Stochastic relaxation, Gibbs distribution and the Bayesian restoration in images . IEEE Trans. Patt. Anal. Mac. Int. 6 , 6, 721 -- 741 . Geman S. and Geman, D. 1984. Stochastic relaxation, Gibbs distribution and the Bayesian restoration in images. IEEE Trans. Patt. Anal. Mac. Int. 6, 6, 721--741.","journal-title":"IEEE Trans. Patt. Anal. Mac. Int."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.13.2.311"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1016\/0895-7177(89)90202-1","article-title":"Very fast simulated re-annealing","volume":"12","author":"Ingber L.","year":"1989","unstructured":"Ingber , L. 1989 . Very fast simulated re-annealing . Math. Comput. Model. 12 , 967 -- 973 . Ingber, L. 1989. Very fast simulated re-annealing. Math. Comput. Model. 12, 967--973.","journal-title":"Math. Comput. Model."},{"key":"e_1_2_1_14_1","first-page":"33","article-title":"Adaptive simulated annealing (ASA): Lesson learned","volume":"25","author":"Ingber L.","year":"1996","unstructured":"Ingber , L. 1996 . Adaptive simulated annealing (ASA): Lesson learned . Control Cybernet. 25 , 33 -- 54 . Ingber, L. 1996. Adaptive simulated annealing (ASA): Lesson learned. Control Cybernet. 25, 33--54.","journal-title":"Control Cybernet."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.2307\/1269076"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatric S.","year":"1983","unstructured":"Kirkpatric , S. , Gelatt , C. D. , and Vecchi , M. P. 1983 . Optimization by simulated annealing . Science 220 , 671 -- 680 . Kirkpatric, S., Gelatt, C. D., and Vecchi, M. P. 1983. Optimization by simulated annealing. Science 220, 671--680.","journal-title":"Science"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1109\/43.67789","article-title":"GORDIAN: VLSI placement by quadratic programming and slicing optimization","volume":"10","author":"Kleinhans J. M.","year":"1991","unstructured":"Kleinhans , J. M. , Sigl , G. , and Johannes , F. M. , and Antreich , K. J. 1991 . GORDIAN: VLSI placement by quadratic programming and slicing optimization . IEEE Trans. CAD Integ. Circ. Syst. 10 , 356 -- 365 . Kleinhans, J. M., Sigl, G., and Johannes, F. M., and Antreich, K. J.1991. GORDIAN: VLSI placement by quadratic programming and slicing optimization. IEEE Trans. CAD Integ. Circ. Syst. 10, 356--365.","journal-title":"IEEE Trans. CAD Integ. Circ. Syst."},{"key":"e_1_2_1_18_1","volume-title":"The Annealing Algorithm","author":"Otten R. H. J. M.","unstructured":"Otten , R. H. J. M. and van Ginneken L. P. P. P. 1989. The Annealing Algorithm . Kluwer . Otten, R. H. J. M. and van Ginneken L. P. P. P. 1989. The Annealing Algorithm. Kluwer."},{"key":"e_1_2_1_19_1","article-title":"A force directed component placement procedure for printed circuit boards","author":"Quinn N. R.","year":"1979","unstructured":"Quinn , N. R. and Breuer , M. A. 1979 . A force directed component placement procedure for printed circuit boards . IEEE Trans. Circ. Syst. CAS-26, 377--388. Quinn, N. R. and Breuer, M. A. 1979. A force directed component placement procedure for printed circuit boards. IEEE Trans. Circ. Syst. CAS-26, 377--388.","journal-title":"IEEE Trans. Circ. Syst. CAS-26, 377--388."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1109\/43.46801","article-title":"Temperature measurement and equilibrium dynamics of simulated annealing placement","volume":"9","author":"Rose J.","year":"1990","unstructured":"Rose , J. , Klebsch , W. , and Wolf , J. 1990 . Temperature measurement and equilibrium dynamics of simulated annealing placement . IEEE Trans. CAD 9 , 253 -- 259 . Rose, J., Klebsch, W., and Wolf, J. 1990. Temperature measurement and equilibrium dynamics of simulated annealing placement. IEEE Trans. CAD 9, 253--259.","journal-title":"IEEE Trans. CAD"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of IEEE, 1013--1029","author":"Rose J.","unstructured":"Rose , J. , el Gamal , A. , and Sangiovanni-Vincentelli , A . 1993. Architecture of FPGAs . In Proceedings of IEEE, 1013--1029 . Rose, J., el Gamal, A., and Sangiovanni-Vincentelli, A. 1993. Architecture of FPGAs. In Proceedings of IEEE, 1013--1029."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Custom Integrated Circuit Conference (Rochester, N.Y.). 522--527","author":"Sechen C.","unstructured":"Sechen , C. and Sangiovanni-Vincentelli , A . 1984. The TimberWolf placement and routing package . In Proceedings of the Custom Integrated Circuit Conference (Rochester, N.Y.). 522--527 . Sechen, C. and Sangiovanni-Vincentelli, A. 1984. The TimberWolf placement and routing package. In Proceedings of the Custom Integrated Circuit Conference (Rochester, N.Y.). 522--527."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A mathematical theory of communication","volume":"27","author":"Shannon C. E.","year":"1948","unstructured":"Shannon , C. E. 1948 . A mathematical theory of communication . I & II. Bell Syst. Tech. J. , 27 , 379 -- 423 , 623--656. Shannon, C. E. 1948. A mathematical theory of communication. I & II. Bell Syst. Tech. J., 27, 379--423, 623--656.","journal-title":"I & II. Bell Syst. Tech. J."},{"key":"e_1_2_1_24_1","volume-title":"Algorithms for VLSI Physical Design Automation","author":"Sherwani N. A.","unstructured":"Sherwani , N. A. 1999. Algorithms for VLSI Physical Design Automation . Kluwer Academic Publishers . Sherwani, N. A. 1999. Algorithms for VLSI Physical Design Automation. Kluwer Academic Publishers."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1109\/TCAD.1987.1270265","article-title":"Thermodynamic optimization of block placement","volume":"6","author":"Siarry P.","year":"1987","unstructured":"Siarry , P. , Bergonzi , L. , and Dreyfus G. 1987 . Thermodynamic optimization of block placement . IEEE Trans. CAD 6 , 211 -- 221 . Siarry, P., Bergonzi, L., and Dreyfus G. 1987. Thermodynamic optimization of block placement. IEEE Trans. CAD 6, 211--221.","journal-title":"IEEE Trans. CAD"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0375-9601(87)90796-1","article-title":"Fast simulated annealing","volume":"122","author":"Szu H.","year":"1987","unstructured":"Szu H. and Hartley , R. 1987 . Fast simulated annealing . Phys. Lett. A 122 , 157 -- 162 . Szu H. and Hartley, R. 1987. Fast simulated annealing. Phys. Lett. A 122, 157--162.","journal-title":"Phys. Lett. A"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Wong D. F. Leong H. W. and Liu C. L. 1988. Simulated Annealing for VLSI Desing. Kluwer. Wong D. F. Leong H. W. and Liu C. L. 1988. Simulated Annealing for VLSI Desing. Kluwer.","DOI":"10.1007\/978-1-4613-1677-0"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 23rd ACM\/IEEE Design Automation Conference (Las Vegas, Nev.). ACM","author":"Wong D. F.","unstructured":"Wong , D. F. and Liu , C. L . 1986. A new algorithm for floorplan design . In Proceedings of the 23rd ACM\/IEEE Design Automation Conference (Las Vegas, Nev.). ACM , New York, 101--107. (RSP), (Paris, France). IEEE Computer Society, Press, Los Alamitos, Calif., 188--193. Wong, D. F. and Liu, C. L. 1986. A new algorithm for floorplan design. In Proceedings of the 23rd ACM\/IEEE Design Automation Conference (Las Vegas, Nev.). ACM, New York, 101--107. (RSP), (Paris, France). IEEE Computer Society, Press, Los Alamitos, Calif., 188--193."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1013948.1013951","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T15:59:04Z","timestamp":1672243144000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1013948.1013951"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,7]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,7]]}},"alternative-id":["10.1145\/1013948.1013951"],"URL":"http:\/\/dx.doi.org\/10.1145\/1013948.1013951","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,7]]},"assertion":[{"value":"2004-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}