Floor planning

Floorplanning (English for floor plan ) denotes an optimization problem , are to be arranged at the functional groups or components in a system so that possible short connection, transport or signal paths arise. Floor planning plays a major role today in the creation of layouts in chip design , where individual subcircuits are to be arranged within an overall circuit.

description

The optimization goal in floor planning is to minimize the connection, transport or signal paths, usually in order to optimize the speed or size of an electronic circuit. examples are

Arrangement of the circuit blocks on a circuit board ,
Arrangement of sub-circuits in an integrated circuit ,
Installation of the machines in a factory hall for a production process (original origin of the term) and
Placement of the shelves and goods on the shelves in a retail facility.

Since many of these subtasks are NP-complete and have a large amount of solutions , it is not possible to calculate optimal solutions in a reasonable time. Therefore approximation algorithms and heuristics are used.

Floor planning in chip design

After the behavior and structure design, partitioning and floor planning initiate the layout synthesis for the chip design. The task of floor planning is to prepare the result of the circuit partitioning in such a way that each block created can be placed and wired internally. The three main goals of floor planning are to determine (1) the shapes and (2) the arrangement of the circuit blocks (planning the block shapes and positions) and (3) the signal assignment of their external I / O connections (pin assignment or pin assignment ).

Individual evidence

^ B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms. 5th edition, Springer, Berlin 2012, ISBN 978-36-422-4487-2 , p. 392.
↑ J. Lienig: Layout synthesis of electronic circuits - basic algorithms for the design automation. 2nd edition, Springer, Berlin 2016, ISBN 978-36-624-9814-9 , p. 63.

literature

MF Anjos, A. Vannelli: An Attractor-Repeller Approach to Floorplanning . In: Mathematical Methods of Operations Research (ZOR) . tape 56 , no. 1 , 2002, p. 3-27 , doi : 10.1007 / s001860200197 .
J. Lienig: Layout Synthesis of Electronic Circuits - Basic Algorithms for Design Automation. 2nd edition, Springer, Berlin 2016, ISBN 978-36-624-9814-9 .

[1] B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms. 5th edition, Springer, Berlin 2012, ISBN 978-36-422-4487-2 , p. 392.

[2] J. Lienig: Layout synthesis of electronic circuits - basic algorithms for the design automation. 2nd edition, Springer, Berlin 2016, ISBN 978-36-624-9814-9 , p. 63.