Figure 5: The construction of the detailed routing when combining a meta-block
Because of the hierarchical construction of the individuals and the
binarity of the tree, the detailed routing on the layout
can be computed during the placement of the blocks.
Note that a meta-block is considered to be a fixed unit in the higher levels
of the tree.
When combining two blocks, all routing inside the resulting meta-block is done (cf. fig. 5).
Terminals on the outer borders are passed on as terminals to the outer border
of the meta-block.
Terminals in the channel and on the outer sides of the blocks are connected, if they
are shared by a common net.
Nets inside the channel which could not be connected or have to be connected to more terminals than
only those contained in this meta-block
are passed on as terminals to one of the borders which are adjacent to the channel.
For these nets, the direction of the way out of the channel is determined by a
top-down traversal of the tree following the bottom-up construction phase.
During this phase there is a check for each net, whether it is
included inside of one of the partial layouts which are joined in an inner node.
In this case, the net has to cross the channel and
therefore a pseudo-optimal way for this net out of the channels in both sons of this node
can be fixed (cf. fig. 6).
Figure 6: Fixing a global route by a top-down traversal (left) for the pseudo-optimal way (right)
This method achieves that the nets follow the hierarchy of the cuts defined
by the slicing tree structure.
This way is often not optimal, but during the optimization process, the
optimal structure of the slicing tree - regarding layout area and routing -
is computed.
In comparison to former experiments, where the global routes were chosen
randomly when combining the meta-blocks, here the total wirelength is
considerably reduced.
When choosing random routes for all nets out of the
channels, many nets are routed to the outer border of the layout and
have to be connected after composing the root node.
Of course it could be possible to do the optimization of these
routes by the genetic algorithm later on, but if one is able to
compute (nearly) optimal routes `by hand', there
is no need for passing this work to the genetic algorithm.