Title :
FTS-a new algorithm for optimal row-placement
Author :
Doerffer, Karol ; Téby, Attila T. ; Anton, Oskar ; Mlynski, Dieter A.
Author_Institution :
Inst. fur Theor. Elektrotech. und Messtech., Karlsruhe Univ., Germany
Abstract :
The paper presents two new placement algorithms applied in automatic generation of functional cells. Both algorithms can be used for any problem consisting in finding the optimal permutation of a given set of elements with respect to a given objective or cost function. The first one-Wide Track Search (WTS) gives good results for problems of any size, but cannot guarantee the global optimality of solution. The second one-Full Track Search (FTS) can be applied to smaller problems (up to ~20 elements) and finds the optimal solution. Due to its smallest known computational complexity (compared to other algorithms which find global optimum) FTS can find the optimal solutions of problems, which had so far not been optimally solved because of their size
Keywords :
Boolean functions; CMOS logic circuits; cellular arrays; circuit layout CAD; circuit optimisation; computational complexity; logic CAD; network routing; Boolean function; CMOS static cells; FTS; automatic generation; computational complexity; cost function; full track search; functional cells; optimal permutation; optimal row-placement; placement algorithms; Boolean functions; Circuits; Computational complexity; Cost function; NP-hard problem; Scheduling algorithm; Wires;
Conference_Titel :
Circuits and Systems, 1994., Proceedings of the 37th Midwest Symposium on
Conference_Location :
Lafayette, LA
Print_ISBN :
0-7803-2428-5
DOI :
10.1109/MWSCAS.1994.519258
