Component placement
methods for wiring layout
Oleg Buzovsky1, professor, D.S., & Kostiantyn Danko 1,
post graduate student
1 Computer System Department, Faculty of
Information and Computing Technique, National Technical University of Ukraine
“Kyiv Polytechnic Institute”, Address: 37, Prospect Permohy,
03056, Kyiv-56,
Development of computer-aided
design systems requires improving placement and routing methods, defining
optimal integral quality criteria, designing universal and flexible algorithms
for solving given problems.
Placement problem means search
of optimal element placement on a plane according to certain criteria.
Placement problem solution defines input data for wiring layout routing and
thus determines routing solution quality.
Large quantity of conflicting
and often mutually exclusive criteria makes it impossible to determine explicit
methods for optimal placement problem solution. Usually obtained solution is
suboptimal.
Existing methods can be
classified into two big groups that use constructive and iterative
algorithms. Constructive algorithms
disadvantages are non-optimal solutions and high probability of collisions
while placing components. Advantages include implementation simplicity and high
performance. Iterative algorithms possess larger time complexity but allow
producing significantly better layout according to specified criteria.
Results of both algorithm
groups research are presented in the report. Placement algorithm combining
constructive and iterative approaches was developed on the basis of known
placement methods analysis. Initial placement for further optimization is implemented
by constructive algorithm. Constructive approach disadvantages are eliminated
by iterative optimization of initial placement. Time complexity increase is
compensated by placement solution quality. It is noted
that time complexity of algorithm is not critical due to modern computer
systems resources.
Designed on the basis of
offered algorithms software system is flexible and configurable. Based on
common interfaces and design patterns, it allows building algorithm chains for
consecutive component placement optimization. System gives opportunity to
define strategy of combining various constructive and iterative algorithms for
solving design and research problems.
Using integrated functional
allows transforming multi-criterion problem to single-criterion. Functional
minimizes interconnection wiring lengths and optimizes wiring layout metric
properties. Designed solution significantly facilitates routing process by decreasing
occupancy of wiring layout areas intended for routing interconnections.