SASIMI 2024 Proceedings

R1-10

A Fast Three-layer Bottleneck Channel Track Assignment
with Layout Constraints using ILP
Kazuya TANIGUCHI Satoshi TAYU
Atsushi TAKAHASHI

Mathieu MOLONGO Makoto MINAMI
Katsuya NISHIOKA

Department of Information and Communications Engineering
Tokyo Institute of Technology
2-12-1 S3-58 Ookayama, Meguro-ku, Tokyo 152–8550, Japan{taniguchi@eda., tayu@, atsushi@}ict.e.titech.ac.jp

Jedat1-1-12, Minato, Chuo-ku, Tokyo 104–0043, Japan{molongo.mathieu, minami.makoto,nishioka.katsuya}@jedat.co.jp

Abstract— An algorithm for a bottleneck channelrouting problem that uses ILP is proposed. The proposed algorithm determines the track and layer assignment of nets for three-layer bottleneck channel routing
problem with layout constraints in which pins of eachnet are placed on the upper boundary of the adjacentregions on both sides of the bottleneck channel. The
proposed algorithm restricts the routing pattern ofeach net to one of three patterns by taking feasibility
into account, and outputs a solution in a few seconds
when the number of nets is 300.

I.

Introduction

The analog layout design is required not to deteriorate
the circuit performance. On the other hand, it is important to realize a layout in a small area to reduce manufacturing costs. The objective of our research is to develop
a routing framework that enables us to layout a circuit insmall area while meeting performance speciﬁcations.
In this paper, a routing problem on the bottleneck routing region where performance speciﬁcations are not violated even if multiple wires go through a track is discussed.
For routing problems which contain layout constraints,
it is not easy to construct constructive algorithms thatconsider all constraints. If the routing problem can be formulated as an Integer Linear Programming (ILP), layout
constraints can be considered more easily than constructive algorithms. However, ILP is generally NP-hard andoften diﬃcult to solve in practical time, even for smallscale problems.
In cell-based design [1], the routing area is partitioned
into small routing regions, and various routing algorithms
for such regions have been proposed. For example, channel routing algorithms were proposed in [2, 3]. Track assignment procedure considering cross-talk minimization
was proposed in [4]. A design ﬂow without repeating design is preferred [5, 6, 7]. A routing design ﬂow with
HV routing without repeating routing design has been
established. However, the obtained layout may contain a(a) HV Routing(b) Bottleneck Channel Routing
Fig. 1. Circuit layouts without and with bottleneck channelrouting region which is a bottleneck for area reduction(Fig. 1(a)). In order to resolve bottleneck, Bottleneck
channel routing (Fig. 1(b)) is proposed in [8].
In this paper, we propose U3TLA-ILP3.0 that determines the track and layer assignment of nets by using
ILP for U-shaped three-layer bottleneck channel routing
problem (U3BCRP). A layout pattern obtained by using
U3TLA-ILP3.0 will be utilized as an initial solution to explore a detailed routing in bottleneck region with layout
constraints eﬃciently.
U3TLA-ILP3.0 restricts the routing pattern of each
net to one of three patterns by taking feasibility into
account. In U3TLA-ILP3.0, decision variables are used
to determine the pattern used by each net, the trackand layer assignment is determined according to the decision variables, and the routing pattern is determined.
U3TLA-ILP3.0 outputs solutions in a few seconds for
medium-scale problems about 300 nets. The routing pattern that satisﬁes layout constraints can be obtained in ashort time by U3TLA-ILP3.0.

II.

Bottleneck Channel Routing Problem

A routing problem is to ﬁnd a better routing patternthat satisﬁes the connection requirement under the design
rule. The connection requirement among pins is called anet. Among routing patterns which satisfy connection
requirement, a routing pattern is infeasible if there is a

- 50 -

U3BCRP
Input:• net set N = {n1 , n2 , . . . , nk } (k > 0)
• right sequence R = (r1 , r2 , . . . , rk )• the number of tracks T ∈ N+
Output:• track assignment of nets
AT : N → {1, 2, . . . , T }• layer assignment of segments of nets
AL : N → {1, 2, 3} (left vertical)
AM : N → {1, 2, 3} (horizontal)
AR : N → {1, 2, 3} (right vertical)

Fig. 2. Bottleneck channel routing

design rule violation, feasible otherwise.
In grid based design, the wires of diﬀerent nets havea conﬂict if they share the same coordinate in the samelayer. In grid based design, a solution which satisﬁes connection requirement and have no conﬂicts is feasible. The
solution of a routing problem must be feasible and mustmeet layout constraints.
Three-layer bottleneck channel routing problem is deﬁned on routing area that consists of a bottleneck channel
and adjacent regions on both sides as shown in Fig. 2.
A wire which connects pins of a net goes through a
track in the bottleneck channel. A set of two-pin nets
N = {n1 , n2 , . . . , nk } is given as an input. Pins of eachnet are placed on the boundary of left and right adjacent regions. The left sequence L = (l1 , l2 , . . . , lk ) whereli ∈ N is deﬁned as the sequence of nets whose pins
are aligned counterclockwise order on the boundary of
the left-adjacent region. Similarly, the right sequence
R = (r1 , r2 , . . . , rk ) where ri ∈ N is deﬁned as the sequence of nets whose pins are aligned clockwise order on
the boundary of the right-adjacent region. N l (n) andN r (n) are the sets of nets whose left and right pins are
before the left pin and the right pin of net n in the left andright sequences, respectively. That is, they are deﬁned as
N l (n) = {li | i < j, n = lj },N r (n) = {ri | i < j, n = rj }.

(1)
(2)

In this paper, U-shaped three-layer bottleneck channelrouting problem (U3BCRP) shown in Fig. 3 which is themost basic three-layer bottleneck channel routing problem is formulated. In U3BCRP, routing area Gk,T for k
two-pin nets and T tracks is modeled by the routing grid(−k ≤ x ≤ k, 0 ≤ y ≤ T ) as shown in Fig. 4 where they-axis corresponds to the degenerated bottleneck channel, the region x < 0 corresponds to the left-adjacentregion, and the region x > 0 corresponds to the rightadjacent region. Left pin of net li and right pin of net
rj are placed at grid point (−i, 0) and (j, 0), respectively.
Track t (1 ≤ t ≤ T ) is the grid line connecting (−k, t) and(k, t).
Wires of at most three nets can go through a single
track. In the following, we assume that an input which
satisﬁesk ≤ 3T(3)
is given. Also, we assume, without loss of generality, thatleft sequence L is ﬁxed as li = ni for any net ni ∈ N .

Fig. 3. U-shaped three-layer bottleneck channel routing problem

Fig. 4. Routing area Gk,T , tracks, and pins

Fig. 5. A routing pattern for R = (n4 , n9 , n3 , n7 , n8 , n1 , n6 , n5 , n2 )Therefore, right sequence R is given as input. In addition,
we assume that layout constraints may be given, such as
wires of two speciﬁed nets must not be close to each other.
In U3BCRP, an output routing pattern has to satisfy
the following four conditions.
• Pin of all nets are connected by wire.
• Wires of diﬀerent nets have no conﬂicts.
• The wire of each net consists of one horizontal andtwo vertical segments.
• Each segment is assigned to either layer 1, 2, or 3.
The wire of a net consists of two vertical segments andone horizontal segment which is assigned to a track.
Output of the problem is the track assignment AT andthe layer assignment of three segments AL , AM , and AR .
The routing pattern is uniquely determined under the four
conditions above if the track and layer assignment is determined. If the wires of diﬀerent nets share the same
coordinate, they must be assigned to the diﬀerent layer
to avoid conﬂicts.
Once the track assignment AT (n) is determined, thetrack used by the horizontal segment of net n and thelength of the vertical segments of net n are determined,
and the routing shape of net n is determined.
Fig. 5 shows an example of routing pattern. The black,
red, and blue line segments represent the wires on layer 1,
layer 2, and layer 3, respectively.

- 51 -

For each net, via must be inserted to a wire when therouting layer of the wire is changed. A via placed between
layer i and layer j is called i-j via. A conﬂict occurs whena 1-3 via and a wire on layer 2 share the same coordinate.
Note that a 1-2 via can share the same coordinate with awire on layer 3 without conﬂict.
III.

U3TLA-TLLL
Decision variables

Track Assignment to avoid Conflict

Before introducing ILP formulations for U3BCRP, necessary conditions in track assignment to avoid conﬂicts
when the routing layer of each segment of nets is speciﬁed are discussed.
Let Ni,i be the set of nets whose left vertical segment
and horizontal segment both use layer i. All horizontal
segments of nets belonging to Ni,i use the layer i, and allnets belonging to Ni,i are assigned to diﬀerent tracks if
the routing pattern has no conﬂicts. Let a and b be nets
belonging to Ni,i such that a ∈ N l (b). If net a is assigned
to a track below the track to which net b is assigned, theleft vertical segment of net a and the horizontal segmentof net b intersect on the same layer, and conﬂict occurs
as shown in Fig. 6(a). To avoid the conﬂict between net
a and net b, net a must be assigned to a track above thetrack to which net b is assigned as shown in Fig. 6(b).
If a routing pattern contains no conﬂicts, all nets belonging to Ni,i ∩ N l (n) are assigned to a track above thetrack to which net n(∈ Ni,i ) is assigned. In this situation,
the following equation holds.
∀n ∈ Ni,i , AT (n) > |Ni,i ∩ N (n)|l(4)

If a track assignment satisﬁes the condition of Eq. (4),the left vertical segment and the horizontal segment ofnets belonging to Ni,i have no conﬂicts.
IV.

(a) AT (a) > AT (b) (b) AT (a) < AT (b)Fig. 6. Track assignment with and without conﬂict

xTt,n ∈ {0, 1} (∀(t, n) ∈ {1, 2, . . . , T } × N )

(5)

M
R
xL
i,n , xi,n , xi,n ∈ {0, 1} (∀(i, n) ∈ {1, 2, 3} × N )(6)Constraints· Pattern∑3L
i=1 xi,n =T
t=1 xt,n = 1 (∀n ∈ N )∑3
MR
i=1 xi,n =i=1 xi,n = 1 (∀n ∈ N )∑3· Conﬂict∑∑TTMn∈N xt,n ∧ xi,n ≤ 1 (∀t ∈ [T ], ∀i ∈ {1, 2, 3})T
t=1 t · xt,n <

(7)
(8)

(9)

∑3

∑T

T
t=1 t · xt,n′ + T (1 −′2LM
i=1 xi,n ∧ xi,n′ )l′(∀(n, n ) ∈ N , n ∈ N (n )) (10)ML
xTt,n ∧ xTt,n′ ∧ xM
2,n ∧ x1,n′ ∧ x3,n′ = 0
LM
xTt,n ∧ xTt,n′ ∧ xM
2,n ∧ x3,n′ ∧ x1,n′ = 0(∀(t, n, n′ ) ∈ [T ] × N × N, n′ ∈ N l (n)) (11)Fig. 7. ILP formulation U3TLA-TLLL

Constraint on Pattern in U3TLA-TLLL (Eqs. (7), (8)).
The conﬂicts between the wires of diﬀerent nets (Eqs.(9),(10)), and the conﬂicts between the 1-3 via and the wireon layer 2 (Eq. (11)) on left region are prohibited in theConstraint on Conﬂict in U3TLA-TLLL. The conﬂict onright region can be prohibited similarly, but the description is omitted here.

ILP Formulation which requires muchcalculation timeV.

In this section, a straightforward ILP formulation for
U3BCRP is introduced. This formulation is natural andintuitive but impractical.
Fig. 7 gives a part of ILP formulation U3TLA-TLLL
for U3BCRP. Since the logical product (∧) can be converted to an equivalent linear expression using auxiliary
variables, a formulation which contains logical product isused here for clarity.
U3TLA-TLLL represents the routing of each net by using four variables deﬁned in Eqs. (5), (6) which specify
the track assignment and the layer assignment of threesegments. xTt,n speciﬁes track assignment AT . The netRM
n is assigned to track t if xTt,n = 1. xL
i,n , xi,n , and xi,nspecify layer assignment AL , AM , and AR , respectively.
For example, the left vertical segment of net n is assigned
to layer i if xL
i,n = 1.
In U3BCRP, each net is assigned to one track and eachsegment of a net uses one layer. They are forced by∑T

Proposed Method U3TLA-ILP3.0

In this section, the proposed algorithm for U3BCRP
with ILP formulation U3TLA-ILP3.0 shown in Fig. 8 isintroduced.
A.

Routing pattern

U3TLA-ILP3.0 restricts the layer assignment of each
net to three patterns shown in Fig. 9. U3TLA-ILP3.0
uses a variable that speciﬁes the pattern used by eachnet, but does not use variables for track assignment.
The variables used in U3TLA-ILP3.0 are{
1 (net n uses Pi )
i
pn :=
(12)
0 (otherwise)
where i ∈ {1, 2, 3} and n ∈ N . The net n uses Pi if pin = 1.
The Constraint on Pattern
p1n + p2n + p3n = 1(∀n ∈ N )(13)

restricts the pattern of each net to one of three patterns.

- 52 -

B. Track Assignment

Algorithm for U3BCRP
Input: N
Output: AT (N ), AL (N ), AM (N ), AR (N )***** 1. Pattern selection using ILP *****
P (p): ILP-formulation
Variables: Eq. (12)Constraints· Pattern: Eq. (13)· Tracks: Eq. (15)· Conﬂicts: Eq. (16, 17, 18)· Layout: Eq. (21)solve(P (p))
for(n ∈ N )1
 1 if pn = 1
2 if p2n = 1
p(n) :=

3 if p3n = 1
endfor***** 2. Track and layer assignment *****
for(n ∈ N )switch(p(n))
case(1):AT (n) := |{m | m ∈ N l (n), p(m) = 1}| + 1(AL (n), AM (n), AR (n)) := (1, 1, 2)case(2):AT (n) := |{m | m ∈ N r (n), p(m) = 2}| + 1(AL (n), AM (n), AR (n)) := (1, 2, 2)case(3):
AT (n) := |{m | m ∈ N l (n), p(m) = 3}| + 1(AL (n), AM (n), AR (n)) := (3, 3, 2)
endswitch
endfor

Proposed algorithm determines track assignment
according to the patterns of nets determined by
U3TLA-ILP3.0.
When all variables are determined to satisfy Eq. (13),the track assignment of net n using P1 is deﬁned as follows(see also Fig. 10).
∑
AT (n) :=p1m + 1
(14)m∈N l (n)∑Note that m∈N l (n) p1m is equal to the number of nets
which appear before n in the left-sequence L and that use
P1 . Both the left vertical segments and the horizontal
segments of nets using P1 use layer 1, and there is no conﬂict among them since the track assignments deﬁned by
Eq. (14) satisfy the condition of Eq. (4). The right vertical segments and the horizontal segments of nets using P1
have no conﬂicts among them since the former use layer 2
and the latter use layer 1. Therefore, any nets using P1
have no conﬂicts among them.
For any nets using P2 (or P3 ), the track assignments ofnets are deﬁned similarly so that they have no conﬂicts
among them. Therefore, any nets using the same pattern
have no conﬂicts.
The number of nets to be used for each pattern is lessthan or equal to the number of tracks T . The Constraint
on Tracks∑pin ≤ T (∀i ∈ {1, 2, 3})(15)

Fig. 8. Proposed Algorithm for U3BCRP

n∈N

restricts the number of nets to be used for each pattern.
C. Constraints in ILP to avoid conﬂicts
From the restriction of routing pattern and the track
assignment, any nets using the same pattern have noconﬂicts. A conﬂict occurs only if a vertical segment
and a horizontal segment belong to diﬀerent patterns.
U3TLA-ILP3.0 imposes constraints which prevent conﬂicts caused by such segments belonging to diﬀerent patterns.
For any pattern Pi , a conﬂict occurs when a verticalsegment of Pi intersects the horizontal segment of otherpattern Pj (̸= Pi ) which use the same layer. Among 12
pairs of vertical and horizontal segments belonging to different patterns, the following three are pairs of segments
which use the same layer.
• right vertical segment of P1 , horizontal segment of P2

P1 (1, 1, 2)

The intersection of segments in these three pairs are prohibited by the Constraint on Conﬂict shown below. The
variable M used in these constraints is a big-constant deﬁned as M := T + 1.

P3 (3, 3, 2)

Fig. 9. Three patterns used by U3TLA-ILP3.0

Fig. 10. Track assignment of P1

∑

p1m <

∑

p2m <

m∈N r (n)∑m∈N l (n)∑p2m + M (1 − p1n ) (∀n ∈ N ) (16)m∈N r (n)m∈N l (n)• left vertical segment of P2 , horizontal segment of P1• right vertical segment of P3 , horizontal segment of P2

P2 (1, 2, 2)∑

p1m + M (1 − p2n ) (∀n ∈ N ) (17)m∈N l (n)

p3m <

∑

p2m + M (1 − p3n ) (∀n ∈ N ) (18)m∈N r (n)In the following, we show that a conﬂict caused by segments belonging to diﬀerent patterns are prohibited either- 53 -

by Eqs. (16), (17), or (18). The value of each term in each
formula is nonnegative, and the value of the left side is at
most T in each formula. Therefore, note that an inequality is satisﬁed when pin (i = 1, 2, 3) is 0 since the value ofthe right side is at least M (= T + 1). Also, Eqs. (16),(17), and (18) may not be satisﬁed when p1n , p2n , and p3n
are 1, respectively.
Here, we show that the left vertical segment of nets
using P2 and the horizontal segments of nets using P1 do
not intersect if Eq. (17) is satisﬁed. Let’s consider a casethat net n uses pattern P2 , that is, p2n = 1. We showthat the left vertical segment of net n and the horizontal
segments of nets using P1 do not intersect if Eq. (17) issatisﬁed.
Let t be the value on the left side of Eq. (17).
∑p2m = t(19)m∈N r (n)From Eq. (14), t + 1 is equal to the track number of net n.
The left vertical segment of net n on layer 1 spans fromtrack 1 to track t + 1 as shown in Figs. 11 and 12. Let cbe the value of the ﬁrst term on the right side of Eq. (17).
∑p1m = c(20)m∈N l (n)Note that c represents the number of nets using P1 whichappear before net n in the left-sequence L. The horizontal
segments of these nets terminate to the right of the left
vertical segment of net n as shown in Figs. 11 and 12.
Note that t < c holds if Eq. (17) is satisﬁed. If t < c,the horizontal segments of all nets using P1 which areassigned to track 1 to track t + 1 terminate to the right of
the left vertical segment of net n as shown in Fig. 11. The
left vertical segment of net n and the horizontal segmentsof nets using P1 do not intersect, and no conﬂict occurs.
If t ≥ c, conﬂict may occur as shown in Fig. 12. Suppose
there exists a net n′ which appear ﬁrst in left-sequence L
among nets using P1 and whose left pin is to the left ofthat of net n. The net n′ is assigned to track c+1(≤ t+1),
and the horizontal segment of net n′ on layer 1 terminates
to the left of the left vertical segment of net n. The left
vertical segment of net n and the horizontal segments of
net n′ intersect, and conﬂict occurs.
In summary, Eq. (17) restricts to t < c, and prohibit
the intersection of the left vertical segment of nets using
P2 and the horizontal segments of nets using P1 .
It can be shown similarly that the conﬂict between P1
and P2 and the conﬂict between P3 and P2 do not occur
if Eqs. (16) and (18) are satisﬁed, respectively, but thedescription is omitted here.
D. Constraints in ILP to satisfy layout constraints
Among various types of layout constraints, ILP formulation that prevents crosstalk noise is discussed here as an
example.

Fig. 11. No conﬂict at left vertical segment of P2 (t < c)Fig. 12. Conﬂict at left vertical segment of P2 (t ≥ c)

Assume that a pair of a noise source aggressor and its
victim are given, and that the wire of the aggressor anda victim neither share the same coordinate nor adjacentis requested even if they are assigned in diﬀerent layer isgiven as constraint.
Let na be the aggressor, and let nv be the victim. If the
input satisﬁes both na ∈ N l (nv ) and nv ∈ N r (na ), thewires of na and nv must intersect and no feasible solution
exists. So we focus on the other situations. Suppose,
without loss of generality, that an input which satisﬁes
na ∈ N l (nv ) ∩ N r (nv ) is given. In order to satisfy thelayout constraints, net na must be assigned to two or more
tracks above the track to which nv is assigned, regardlessof patterns of them used.
The Constraints on Layout∑m∈Ni (na )

∑

pim ≤

m∈Nj (nv )(Ni (n) :=pjm +(M +1)(2 − pina − pjnv ) − 2{

N l (n) (i = 1, 3)
N r (n) (i = 2))(21)

where (i, j) ∈ {1, 2, 3}2 prohibit the intersection of thewires of na and nv and secure the gap between the wiresof them two tracks or more. The ﬁrst term on the left
and right sides represent the (track number)−1 of na andnv , respectively. Note that Eq. (21) for (i, j) is satisﬁed
if either pina = 0 or pjnv = 0 because of the second termon the right side.
In case that pina = 1 and pjnv = 1, the second term on
the right side of Eq. (21) is zero, and Eq. (21) forces that(track number of na ) ≤ (track number of nv ) − 2.
By the Eq. (21), net na is assigned to two or more tracks
above the track to which nv is assigned.
The Constraint on Layout given here is for a single pairof aggressor and victim, but the number of pairs is often
more than one in practice. If more than one pairs are
given, the layout constraints can be realized by adding
constraint given here for each pair. Even if any other- 54 -

layout constraint is given, a routing pattern which satisﬁes
the constraint can be obtained if the constraint can be
expressed in a linear equation.

TABLE I
Computation time

#nets
E. Proposed Algorithm

12
18
24
30
60
150
*18
*24

Propose algorithm shown in Fig. 8 ﬁrst formulates
U3BCRP as U3TLA-ILP3.0．Proposed algorithm thensolves the ILP using a solver to determine the patternof each net.
Once the pattern of each net is determined, the trackand layer assignment is determined uniquely. The tracknumber of net n is set equal to the number of nets whichappear before n in left or right sequence and which use
the same pattern with n.

VI.

time [ms]
TLLL
3.0
596
8
14145212628764
13
>1h
13
>1h
21
>1h
89
80327
11
>1h
67

TABLE II
Computation time andFeasible ratio by
U3TLA-ILP3.0

#nets
30
60
150
300
600
*60
*300

time
[ms]
12
20
78
279
1153
43
1087

ratio
[%]
97
98
100
100
100
94
98

Experimental Results

U3TLA-ILP3.0 is implemented in Python 3.10.11, andexecuted on a PC with 3.60GHz Intel Core-i5 CPU, 32GB
RAM. The solver used is IBM CPLEX 22.1.1.0.
The problem instances are randomly generated by selecting the right pin sequence among a permutation ofnets. The number of nets k is set to be three times thenumber of tracks T . The symbol ‘*’ is added when alayout constraint to prevent crosstalk in which a pair of
one aggressor and 5 victims is deﬁned is imposed to the
problem instances. A routing pattern obtained by using
U3TLA-ILP3.0 is shown in Fig. 13.
Table I shows the computation times of U3TLA-TLLL
and U3TLA-ILP3.0 for various net sizes when a feasible
solution is obtained. In table, “time” represents the computation time taken to solve the formulated ILP for one
problem instance.
Table II shows the average computation times of
U3TLA-ILP3.0 and the ratio that feasible solution is obtained among 100 problem instances for each net size. The
ratio is reasonable since U3TLA-ILP3.0 cannot obtain afeasible solution if the ﬁrst net in the right pin sequenceis n1 . Even in such cases, pre-processing, such as connecting net n1 using only layer 1, increase the ratio, forexample. A slightly smaller ratio is observed if a crosstalk
constraint is imposed.

VII.

Fig. 13. A routing pattern obtained by using U3TLA-ILP3.0.
#net= 60, (Agg, Vic)= ({37}, {15, 24, 41, 49, 58})

adapt it to the more general situations. For example,
a pattern in which all three segments use the samelayer can improve feasibility and reduce the number ofvias. The formulation of U3TLA-ILP3.0 can be easily
extended when more routing layers are available. It ischallenging to be able to handle problems where pins areplaced not only on upper boundaries.
References[1] A.Kahng, J.Lienig, I.Markov, and J.Hu, “VLSI Physical Design: From Graph Partitioning to Timing Closure,” Springer,
2011.
[2] A.Hashimoto and J.Stevens, “Wire Routing by Optimizing
Channel Assignment within Large Apertures,” Proc. 8th Design Automation Workshop, pp.155-169, 1971.
[3] T.Yoshimura and E.S.Kuh, “Eﬃcient Algorithms for Channel
Routing,” IEEE Trans. Computer-Aided Design of Integrated
Circuits and Systems, Vol.CAD-1, No.1, pp.25-35, Jan.1982.
[4] Y.Takashima, A.Takahashi, and Y.Kajitani, “Assignment ofIntervals to Parallel Tracks with Minimum Total Cross-Talk,”
IEICE Trans. Fundamentals, vol.E81-A, no.9, pp.1909-1915,
1998.
[5] Y.Kajitani, “Order of Channels for Safe Routing and Optimal Compaction of Routing Area,” IEEE Transactions on
Computer-Aided Design, Vol.CAD-2, No.4, pp.293-300, 1983.

Conclusion

In this paper, U3TLA-ILP3.0 which can consider layout constraints for three-layer bottleneck channel routing
was proposed. For U3BCRP, U3TLA-ILP3.0 obtains arouting pattern which satisﬁes the layout constraints ina short time by using ILP and by restricting the layout
patterns. A layout pattern obtained will be utilized as an
initial solution to explore a detailed routing in bottleneck
region with layout constraints eﬃciently.
Our future works include the extension of
U3TLA-ILP3.0 to adopt more routing patterns and- 55 -[6] W.M.Dai, T.Asano, and E.S.Kuh, “Routing Region Deﬁnition and Ordering Scheme for Building-Block Layout,” IEEE
Transactions on Computer-Aided Design, Vol.CAD-4, No.3,
pp.189-197, 1985.
[7] D.F.Wong and C.L.Liu, “A New Algorithm for Floorplan Designs,” Proc. 23rd ACM/IEEE Design Automation Conference, No.1586075, pp.101-107, 1986.
[8] K.Taniguchi, S.Tayu, A.Takahashi, Y.Todoroki, and
M.Minami, “Bottleneck Channel Routing to Reduce the Areaof Analog VLSI,” Proc. SASIMI 2022, pp.26-31, Hirosaki,
Japan, October 2022.