Memory management optimization problems for integrated circuit simulators Export

@article{citeulike:1560088, abstract = {In hardware design, it is necessary to simulate the anticipated behavior of the integrated circuit before it is actually cast in silicon. As simulation procedures are long due to the great number of tests to be performed, optimization of the simulation code is of prime importance. This paper describes two mathematical models for the minimization of the memory access times for a cycle-based simulator. An integrated circuit being viewed as a directed acyclic graph, the problem consists in building a graph order on the vertices, compatible with the relation order induced by the graph, in order to minimize a cost function that represents the memory access time. For both proposed cost functions, we show that the corresponding problems are NP-complete. However, we show that the special cases where the graphs are in-trees or out-trees can be solved in polynomial time.}, author = {Bossart, Timothee and Kordon, Alix M. and Sourd, Francis}, booktitle = {3rd Cologne/ Twente Workshop on Graphs and Combinatorial Optimization - CTW2004}, citeulike-article-id = {1560088}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.dam.2007.03.019}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6TYW-4NC38MD-6/2/ca59b6f792e5d1a249a8859166475f3d}, day = {1}, doi = {10.1016/j.dam.2007.03.019}, journal = {Discrete Applied Mathematics}, keywords = {algorithm, combinatorics}, month = {September}, number = {14}, pages = {1795--1811}, posted-at = {2007-08-14 12:15:11}, priority = {4}, title = {Memory management optimization problems for integrated circuit simulators}, url = {http://dx.doi.org/10.1016/j.dam.2007.03.019}, volume = {155}, year = {2007} }

TY - JOUR ID - citeulike:1560088 L3 - citeulike-article-id:1560088 N2 - In hardware design, it is necessary to simulate the anticipated behavior of the integrated circuit before it is actually cast in silicon. As simulation procedures are long due to the great number of tests to be performed, optimization of the simulation code is of prime importance. This paper describes two mathematical models for the minimization of the memory access times for a cycle-based simulator. An integrated circuit being viewed as a directed acyclic graph, the problem consists in building a graph order on the vertices, compatible with the relation order induced by the graph, in order to minimize a cost function that represents the memory access time. For both proposed cost functions, we show that the corresponding problems are NP-complete. However, we show that the special cases where the graphs are in-trees or out-trees can be solved in polynomial time. IS - 14 JF - Discrete Applied Mathematics EP - 1811 TI - Memory management optimization problems for integrated circuit simulators VL - 155 T2 - 3rd Cologne/ Twente Workshop on Graphs and Combinatorial Optimization - CTW2004 SP - 1795 KW - algorithm KW - combinatorics AU - Bossart, Timothee AU - Kordon, Alix AU - Sourd, Francis PY - 2007/09/01/ UR - http://dx.doi.org/10.1016/j.dam.2007.03.019 ER -