Module placement with boundary constraints using B*-trees
Journal
IEE Proceedings: Circuits, Devices and Systems
Journal Volume
149
Journal Issue
4
Pages
251-256
Date Issued
2002
Author(s)
Abstract
The module placement problem is to determine the co-ordinates of logic modules in a chip such that no two modules overlap and some cost (e.g. silicon area, interconnection length, etc.) is optimised. To shorten connections between inputs and outputs and/or make related modules adjacent, it is desired to place some modules along the specific boundaries of a chip. To deal with such boundary constraints, we explore the feasibility conditions of a B*-tree with boundary constraints and develop a simulated annealing-based algorithm using B*-trees. Unlike most previous work, the proposed algorithm guarantees a feasible B*-tree with boundary constraints for each perturbation. Experimental results show that the algorithm can obtain a smaller silicon area than the most recent work based on sequence pairs.
Other Subjects
Algorithms; Boundary conditions; Constraint theory; Logic design; Perturbation techniques; Simulated annealing; Trees (mathematics); B-trees; Boundary constraint; Logic modules; Module placement; Simulated annealing algorithm; Multichip modules
Type
journal article