Pattern-Based FPC Routing Algorithm for Optimized Flexible PCB Design(Part II)

Continued part I…

› Cost-Based Allocation of Routing Layers

In practice, routing often involves multiple layers. Using only a single layer would result in a severe shortage of routing resources and overlook the fact that via placement is permitted in fan-out regions.

Multi-Layer Routing Considerations

Considering that routing paths on different layers have varying routing parameters and different impacts on other networks, a cost system has been designed to evaluate the routing results of each network on a specific layer.

Finally, the optimal result across all layers is selected as the layer assignment for that network. The cost function is as follows:

Formula 1

Routing Cost Components and Blocking Effect

In the formula, n_length represents the path length of a single wire mesh. n_via represents the number of vias for a single wire mesh; this is determined by whether the routing path is on the same layer as the pin's starting layer.

If they are not on the same layer, a via is required; each wire mesh within a single fan-out area will have at most one via. n_trap represents the blocking cost, indicating the number of unrouted traces blocked by a single trace during routing.

Since the routing order is predetermined, if the position of a candidate via is inappropriate, it will cause several subsequent traces in the routing sequence to be blocked on this layer, preventing them from being routed through.

Figure 6 shows the right fan-out region of the Left Up mode in Figure 5.

The routing order is 7, 8, 5, 6, 3, 4, 1, 2. Since the routing order of network 6 follows that of network 8, the candidate crossing point for network 6 must be located below network 8.

The same applies to Line 3 and Line 5; thus, Line 8 blocks Line 6, and Line 5 blocks Line 3. The parameters used in the experiments in this paper

are: α = 1, β = 100, and γ = 200.

Fig.6 Right pin area with blocking in Left Up pattern

• Fan-out Mode

In this paper, a fan-out mode refers to a set of modes that coordinate the order in which fan-out regions are selected across multiple fan-out regions.

Since routing planning is based on the coordinated consideration of two fan-out regions, a set of strategies is required to ensure that, while completing the routing for all fan-out regions, as many routing solutions as possible are explored.

Furthermore, since the FPC channel area requires a non-intersecting topology during routing to ensure that the theoretically optimal routing result does not result in holes, the fan-out mode must constrain the order of node positions along the partition lines while simulating as many routing results as possible.

› Topological Non-Crossing Constraints in the Channel Area

To ensure that no holes are created during routing within the channel area after layering, it is necessary to ensure that the crossing order of the two fan-out regions corresponds on each layer.

This guarantees that topologically non-crossing routing paths can be established within the channel area without the need for backward routing.

By applying the concept of eliminating identical terms in the DPS sequence using the referenced literature, we can determine whether a topologically non-crossing structure exists, thereby reducing the problem size.

Opposite Fan-Out Ordering and Non-Crossing Principle

Ensuring topological non-intersection in the channel region essentially involves reversing the order of node traversal in the reference fan-out regions after unfolding them into a ring.

That is, if the clockwise order of the right fan-out region after unfolding is from top to bottom, then the order of node traversal in the left fan-out region should be from bottom to top.

Using this theorem, we can derive the crossing order on the partition lines of the opposite fan-out region that ensures the channel region has no topological crossings, thereby aiding in the selection of crossing positions during the routing phase of the opposite fan-out region.

Clockwise Traversal and Fan-Out Region Relationships

In actual FPCs, clock relationships must be determined by unfolding along the edge chain. That is, select a starting point on the channel edge chain and traverse it in a clockwise or counterclockwise direction.

The sequence of fan-out regions traversed corresponds to the aforementioned unfolded circular clock order.

Typically, a channel zone may connect to multiple fan-out zones.

Bus Topology Constraints in Channel Routing

The connection between FPC fan-out zones is similar to the concept of a bus in a PCB; a bus essentially refers to a bundle of traces that must be adjacent to each other during routing.

Since FPC channel zones require orderly routing of trace networks and cannot have holes, all trace networks connecting one fan-out zone to another must be spatially adjacent; trace networks from other zones cannot be interspersed between them.

At the same time, the clock relationships described above must still be satisfied between regions to ensure that routing does not cross over between regions.

Figure 7 shows a schematic diagram of a non-crossing bus topology within a channel connecting multiple fan-out regions.

Fig. 7 Example of bus connections in a channel connecting multiple pin areas without topological crossing

Bus Ordering and Routing Space Mapping

Assuming U is the bus in the FPC, the unique clockwise sequence after the fan-out regions are laid out in a ring is , with PA₁ as the

reference fan-out region. the clockwise order of the remaining fan-out zones connected to PA₁ is .

Based on these connection relationships, this is converted to the clockwise bus order . Since there are no other bus networks within the bus, this sequence can be further converted into the routing space position sequence on the partition line of fan-out zone 1.

That is, all crossings of the wiring network belonging to bus U₄ must be located entirely to the right of bus U₃; this requirement must be satisfied on every layer; the same applies to other fan-out zones.

Finally, we obtain the routing space sequence along the partition line for each fan-out zone shown in Figure 7.

This sequence is a strong constraint that ensures no holes are drilled in the channel area.

Routing Modes and Directional Scanning

For fan-out region PA₁, the Down mode (clockwise direction) scans from left to right, and the sequence of routing space positions along the partition line is ; the Up mode (counterclockwise direction) scans from right to left, and the sequence of routing space positions on the partition line is ; the same applies to other fan-out regions.

For bus U₃, when PA₁ is used as the reference fan-out area, its routing mode can be analogous to the Left Down or Left Up modes described in Section 2.1.1, depending on the selected clock direction.

When PA₅ is used as the reference fan-out area, its routing mode can be analogous to the Right Down or Right Up mode.

Global Reordering of Bus Routing Sequence

The order within the routing mode is re-sorted globally in this step based on the bus routing sequence.

The internal order within the bus remains according to the routing mode sequence, while the order between buses is re-sorted according to the current fan-out area routing space order and the current clock direction mode.

For example, if the current routing order is , where ∈ U₁ and ∈ U₂, and the routing space order on this fan-out area is , the intra-bus order remains unchanged according to the original routing order, while the inter-bus order is rearranged; the final routing order is .

› Order of Fan-Out Region Selection

In routing mode design, the selection of left and right fan-out regions differs, and the routing results also differ.

This is because the routing resources for fan-out regions vary; using only the routing order and crossing order of a single fan-out region as a standard may lead to suboptimal results. Furthermore, there may be multiple buses within the same fan-out region.

Although the bus order on the partition line is unique, the routing order within the bus network is not unique.

Permutation Complexity and Optimization Strategy

Assuming there are n fan-out regions in the current channel, if all possible permutations and combinations of fan-out regions are fully considered, the set formed by these choices is a complete permutation combination, f(n) = n!.

However, when n is large, the number of permutations becomes excessive, and due to constraints on the spatial order of routing along the partition lines, there will be many duplicate combinations.

Therefore, we simplify this by taking each fan-out region as a vertex, and at each point, expand the circular sequence clockwise and counterclockwise as a permutation.

The set of all permutations of fan-out regions and clock directions serves as the final set of permutations for selecting the order of fan-out regions.

Thus, the final number of permutations is f(n) = 2*n.

Coverage of Simplified Permutation Model

The simplified set of permutations and combinations omits only a few cases of bus routing sequences, while covering all selection scenarios involving fan-out regions. Taking bus U2 in the channel shown in Figure 7 as an example, it still retains the four routing modes described in the previous section:

Example Routing Modes in Fan-Out Regions

① Left-Down Mode (Clockwise from PA1)

Use PA1 as the reference fan-out area, with the clock direction set to clockwise (Left-Down).

In this case, the fan-out selection order is .

With PA₁ as the reference fan-out area, bus U₁ is at the front of the routing space sequence for both PA₁ and PA₄, so it can be routed; the same applies to bus U₂.

② Left-Up Mode (Counterclockwise from PA1)

With PA₁ as the reference fan-out area, the clock direction is counterclockwise (Left-Up).

In this case, the fan-out zone selection order must be . First, use PA₅ as the reference fan-out zone route bus U₅.

Since bus U₃ is not located on the far left in PA₁, it cannot be routed; any network that cannot be routed at this stage will be routed in subsequent reference fan-out area selections. Next, the reference fan-out area is PA₂; similarly, bus U₄ cannot be routed because it is positioned on the far left in PA₁ at this stage.

Finally, PA₁ is selected as the reference fan-out area; at this point, the routing proceeds in a counterclockwise direction, the bus routing order is . First, bus U4 is routed, followed by bus U₃, and then bus U₂.

③ Right-Down Mode (Counterclockwise from PA3)

Use PA₃ as the reference fan-out area, with the clock direction set to counterclockwise (Right-Down).

At this point, the fan-out zone selection order is . First, use PA₄ as the reference fan-out zone to route bus U₁, then use PA₃ as the reference fan-out zone.

At this point, bus U₂ is in PA₁ because U₁ has already been successfully routed and is at the front of the routing space sequence, so routing can proceed.

④ Right-Up Mode (Clockwise from PA3)

Using PA₃ as the reference fan-out zone, with the clock direction set to clockwise (Right-Up), the fan-out zone sequence should be .

• Optimization of Crossing Points

Once routing of all fan-out regions is complete, the use of a multi-Z-shaped pattern for routing individual wire nets and the selection of crossing points that are closely adjacent to the array result in a significant amount of unnecessary routing. Therefore, a post-processing step is necessary to optimize wire lengths.

After the current round of fan-out area routing is complete, this paper re-routes the networks by traversing the routing sequence in reverse and examining the set of available candidate points for each network, intending to minimize line length.

The results before and after optimization are shown in Figure 8.

Fig. 8 Comparison of optimization effects forchanging position of cross points

Experimental Results and Analysis

The algorithm described in this paper was implemented in C++ and tested on a Windows system with a 2.69 GHz processor and 16 GB of RAM; all use cases were derived from real-world industrial applications.

Routing planning not only requires improving the quality of detailed routing but also necessitates controlling its own performance overhead.

• Routing Planning Performance Analysis

The routing planning results of the pattern-based routing method proposed in this paper are listed in Table 1, with a fan-out region grid size of 12.

As shown in Table 1, the time complexity of the routing planning is relatively low, and the routing success rate reaches 100%, meeting design expectations.

Since the routing planning does not consider detailed routing constraints, detailed routing comparison experiments need to be conducted based on the routing planning results.

• Comparative Evaluation with Heuristic Methods

The comparison in this paper is with an FPC routing planning algorithm based on heuristic search; both methods calculate the points where the line network crosses the partition lines in the fan-out region through routing planning to achieve segmented routing of the fan-out region channels.

Since both methods ensure the routability of the channel region, this paper's experiments only compare the detailed routing results of the fan-out region.

After obtaining the intersection points of the partition lines, detailed routing was performed using the congestion-cost-based router PathFinder, and the comparison results are listed in Table 2. Here, "Time" refers to the sum of the routing planning time and the detailed routing time.

• Experimental Results and Performance Gains

The experimental results show that, compared to the reference, using the algorithm proposed in this paper for

reduces the total routing time by an average of 63.1%, the number of holes by an average of 13.7%, and the congestion level by an average of 4.4%.

Table 1 Bus planning results based on pattern routing

Table 2 Comparison of results of some test cases

Conclusion

This paper proposes an FPC routing planning algorithm based on pattern routing.

By designing routing patterns and fan-out patterns to simulate routing scenarios that may occur during actual fan-out area routing, using Dijkstra's algorithm (DPS), we determine the topologically non-intersecting routing sequence for the fan-out areas connected to the channel region.

This sequence is then used as a positioning constraint for points along the partition lines.

Finally, pattern routing is employed to achieve results as close as possible to actual routing with minimal computational cost, thereby providing a realistic evaluation of the current routing performance.

By comprehensively comparing all results, the optimal solution is selected to guide subsequent detailed routing.

Compared to existing FPC routing planning algorithms, the routing planning method proposed in this paper offers significant improvements in both the performance and results of detailed routing.