Cell based performance optimization of combinational circuits

Performance optimization, i.e. the problem of finding an optimal investment of transistor area which meets given delay constraints, is considered from an abstract, cell based point of view which allows only solutions within a discrete solution space of coarse granularity. The main advantages of this problem modelling are the independence of the methods from concrete delay modelling (and thus from technology) and the applicability to even very restrictive design styles (as for example gate arrays or sea of gates). The paper contains a classification of the computational complexity of the performance optimization problem as well as efficient algorithms (where they exist), heuristics and experimental results