PowerPoint プレゼンテーション

Title and Authors
EQ-Sequences for
Coding Floorplans
1
1. Introduction -1
A floorplan is a dissection of a rectangle called
chip into smaller rectangles called rooms by
horizontal and vertical line segments, which meet
in T-junctions.
1
2
6
4
The floorplanning contains:
 Encoding (to represent floorplans);
 Moving (to transform floorplans) ;
 Decoding (to realize floorplans).
3
7
5
8
2
1. Introduction -2
In order to generate and evaluate candidate
floorplans to determine the best floorplan
encountered so far, floorplans should be
represented by codes that satisfy the
followings:
Any feasible floorplan can be represented by an
unique code;
The code is decoded to one and only one floorplan;
Code moving can be efficiently implemented;
Abutment relationships of two rooms can be
checked out before decoding or while moving.
3
1. Introduction -3
In this paper, we propose a new code for
representing a floorplan called EQ-sequence, which
can be considered as an Extension of a Q-sequence.
The advantages of EQ-sequence:
 Any
floorplan
with
different
adjacent
relationships of rooms can be encoded by a unique
EQ-sequence and an EQ-sequence can be decoded
to a unique floorplan, both are in O(n) time.
 Whether two rooms is connected (abut) or not
can be checked while moving the EQ-sequences.
4
2. BASIC CONCEPTS-1 (Walls and Prime Seg)
The segments enclosing the
chip as walls particularly are
called right-wall(WR), left-wall
(WL), top-wall (WT ) and bottomwall (WB).
WT
p1
1
p3
WL
3
2
p2
4
5
6
p4
p5
8
WB
p6
7
p7
WR
For any room r, two segs meet at
the right-bottom corner of r and one
ends there forming a T-junction.
The seg that ends at the T-junction
is called the prime seg of r, denoted
by pr. Note that the right-bottom
room has not a prime seg.
5
2. Basic Concepts-2 (Q-sequence)
Q-sequence: is a concatenation
of the states of rooms (WL or WT),
represented by a sequence Q(r)
(Q(WL) or Q(WT)).
WT
p1
1
p3
WL
3
2
p2
4
5
6
p4
p5
8
WB
p6
7
p7
WR
Q(r) (Q(WL) or Q(WT)) has the
one of the patterns (a>b>c… >d).
r(WL)RaRbRc…Rd
or
r(WT)BaBbBc…Bd
The Q-sequence of the floorplan is:
WLR3R1 WTB6B2B1 1R2 2B4B3 3R8R5R4 4B5 5R7R6
6B7 7B8 8
6
2. Basic Concepts-3 (adjacent relationships )
22
1
1
55
22
55
55
6
66
3
4
3
4
7
7
(b)
66
……
7
4
3
8
8
8
(a)
22
1
6
(c)
The floorplans (a) (b) and (c) are equivalent under
Q-sequence representations. It is evident that the
adjacent relationships of rooms are different.
In order to represent the adjacent relationships of
rooms in a floorplan, we extend the Q-sequence to
propose a new code called EQ-sequence.
7
3. EQ-Sequence Encoding-1 (Def. of Adjacent number )
For defining the EQ-sequence, we give the concept of
adjacent number of every room.
S2
WT
p1
1
S1
2
p2
S
4 4
p3
WL
p4
3
S3
5
S5
WB
p5
8
6
p6
7
p7
S6
WR
S7
Definition 3.1: Let i be a room
except for the right-bottom room,
if the prime seg pi is vertical
(horizontal), the number of the
rooms which are below (right-of)
i and adjacent to i is called
adjacent number of i, denoted
by Si. If the below (right-of) of i
is wall, Si =0.
The adjacent numbers of each room are S1=1, S2=1,
S3=0, S4=2, S5=1, S6=0 and S7=0.
8
3. EQ-Sequence Encoding-2 (Def. of Ai , Ii )
For giving the properties of EQ-sequence, the following
definitions are very important.
r1
R1
r2
R2
rk
……
R 3 …… R m
r1
r2
R1
r3 R2
prime seg prk
R3
……
……
rk
Rm
Definition 3.4: Let rk be a room
except for the right-bottom room,
the rooms adjacent to the prime
seg prk on the opposite side of rk
form an associated room set of rk,
denoted by Ark. Moreover, when
the prime seg prk is either
horizontal or vertical, all of the
rooms adjacent to prk on the same
side of rk form an inside room
set of rk, denoted by Irk.
Ark = {R1, R2, R3, …, Rm}, Irk ={r1, r2, r3, …, rk}
9
3. EQ-Sequence Encoding-3 (Adjacent number constrain)
Sr1 Sr2
r1
R1
r2
R2
Srk-1
…… rk
R3 ……Rm
There are k rooms
There are m rooms
Lemma 3.1: The adjacent numbers of each prime seg prk
satisfy the following constraint:
Sr1+Sr2+Sr3+……+Sr k-1 k+m–2
It is very important to understand Lemma 3.1
in an EQ-sequence.
10
3. EQ-Sequence Encoding-4 ( Def. of EQ-S)
S1
WL
Definition 3.2: For a room r, its
WT
S2
state EQ(r) is rNS
NSr RaRbRc…Rd or
S
6
1 p1
2 p2
rNS
Similarly,
NSrBaBbBc…Bd.
6
S
EQ(WL)= WLN0
N0RaRbRc…Rd and
4 4 p6
p3
p4
WR EQ(W )= W N0
T
TN0BaBbBc…Bd
3
7
S7 Definition 3.3: An EQ-sequence
5 p5
p7
for a floorplan of n rooms is a
S3
S5 8
concatenation of the states:
WB
(EQ(WL)EQ(WT)EQ(1)EQ(2)
……EQ(n)).
The EQ-sequence of the floorplan is:
WLN0R3R1 WTN0B6B2B1 1N1R2 2N1B4B3 3N0R8R5R4
4N2B5 5N1R7R6 6N0B7 7N0B8 8
11
3. EQ-Sequence Encoding-5 (How to obtain Ai , CBi and CRi)
Algorithm 3.1: Finding all inside room sets in a
Q-sequence of n rooms.
Algorithm 3.2: Finding all associated room sets in
a Q-sequence of n rooms.
The computation complexities of them are O(n).
12

3. EQ-Sequence Encoding-6
For a given Q-sequence with n rooms, we make an
E-sequence by inserting N0 behind WL and WT, and
NSi behind room label i for room 1 to n-1 in the Qsequence.
Theorem 3.1: An E-sequence is an EQ-sequence if
and only if all inserted numbers Si in the E-sequence
satisfy Lemma 3.1.
Lamme 3.1:
For each prime seg prk, let Irk be {r1, r2,…, rk}, Ark={R1,
R2,…, Rm} the adjacent numbers of room r1, r2, …, rk-1 be Sr1,
Sr2, …, Srk-1 and, the following inequality holds.
Sr1+Sr2+Sr3+……+Srk-1  kk+m–2
m
13

3. EQ-Sequence Encoding-6 （Example）
WT
p1
1
p3
WL
3
By Theorem 3.1:
2
(Sr1+Sr2+Sr3+……+Srk-1  k+m–2)
p2
4
5
6
p4
p5
8
p6
7
p7
WR
For p2, I2= {1, 2}, i.e. k=2,
A2={3, 4}, i.e. m=2 and S1=1,
so the inequality
S1  2+2–2=2
holds well.
WB
Unique-Symbol and Parenthesis:
WLN0R3R1 WTN0B6B2B1 1N1R2 2N1B4B3 3N0R8R5R4 4N2B5 5N1R7R6 6N0B7 7N0B8 8
14

4. Module Placements-1 (Moving)
2
1
Homomorphic moving
6
2
1
3
5
3
4
(b)
5
1
4
2
6
Homomorphic moving
(Q-Seq. is unchanged)
and
Hetermorphic moving
(This is a question of
moving Q-Seq.)
5
3
(a)
6
4
(c)
Hetermorphic moving
2
1
2
1
3
3
6
4
5
(e)
4
6
2
1
(d)
Homomorphic moving
5
3
5
6
4
(f)
15

4. Module Placements-2 (Moving)
Input an EQ-s
Moving
Hetermorphic
moving ?
y
The method of
moving between
EQ-sequences can
be explained by the
chart.
EQ-s
Q-s
Hetermorphic
moving
Q-s
Algorithm 4.1
EQ*-s
Homomorphic
moving
Satisfy
abutment
constraints?
y
Decode
Algorithm 4.2
Algorithm 4.3
Algorithm 5.1
Evaluate
OK
Output Solution
Algorithm 5.2
16

4. Module Placements-3 (Moving)
Algorithm 4.1: Hetermorphic Moving
Input: a Q-sequence of n rooms
Output: a moved Q-sequence
Step 1: Choose a room state of Q(i)= iBaBbBc…Bd
(iRaRbRc…Rd) where |{BaBbBc…Bd }|>1, or
|{ RaRbRc…Rd}|>1.
Step 2: When 1< i <n, Ba(Ra) can be moved to the
front of Bi(Ri), or when 1  i <n-2 and after i is B
(R), Bk(Rk) in the front of Bi(Rk) can be moved to the
rear of room i.
This method is called Position Moving in a Qsequece moving [paper 15]
17

4.
Module Placements-3 (Example of Hetermorphic moving )
Algorithm4.1
2
1
WLR4R3R1 WTB2B1 1R2 2B5B3 3B4 4R6R5 5B6 6
3
5
4
6
Move B5 to the front of B2
WLR4R3R1 WTB5B2B1 1R2 2B3 3B4 4R6R5 5B6 6
2
1
3
5
4
6
Move R3 to the rear of room 1
WLR4R1 WTB5B2B1 1R3R2 2B3 3B4 4R6R5 5B6
6
18

4. Module Placements-4 (Moving)
Algorithm 4.2: Homomorphic moving
Input: An EQ-sequence or a Q-sequence of n rooms
Output: A moved EQ-sequence
Step 1: Finding all inside room sets and all associated room sets of
the EQ-sequence or Q-sequence by the algorithm 3.1 and 3.2.
Step 2: Initialize Sj=0, 1 j  n-1.
Step 3: For a prime seg prk whose |Irk|>1, let Irk = {r1, r2, r3, …, rk}
and Ark ={R1, R2, R3,…, Rm}. If m=1, then let Sr1=Sr2=Sr3=…=Srk1=1; If m>1, generating random numbers x1, x2, x3, …,xk which are
in (0, 1), each adjacent number Sri (1 i  k-1) can be given by


xi
Sri  
m
S  1.234   2
x

x

x



x
 1 2 3

k
so that a moved EQ-Sequence can be gotten.
19

4. Module Placements-5 (Moving)
Example of Homomorphic moving
p2
1
1
2
6
S1
4
3
5
p5
7
S1=2, S2=1 and S4=1
3
8
2
4
S2
S4
5
6
7
8
WLN0R3R1 WTN0B6B2B1 1N1R2 2N1B4B3 3N0R8R5R4 4N2B5 5N1R7R6 6N0B7 7N0B8 8
WLN0R3R1 WTN0B6B2B1 1N2R2 2N1B4B3 3N0R8R5R4 4N1B5 5N1R7R6 6N0B7 7N0B8 8
For p2 , I2={1, 2} and A2={3, 4} where k=2 and m=2, x1=0.922 and x2=0.374,
we have


x1
0.922
  1.422  2
S1  
m  

2




x

x
0
.
922

0
.
374


 1

2
For p5 , I5={2, 4, 5} and A5={6, 7} where k=3, m=2, x1=0.300 and x2=0.345,
x3=0.302, we have
 x
 
0.300
S 
m  
 2  0.633  1
1
 x1  x2  x3   0.300  0.345  0.302 
 x2

0.345
S4  
m  
 2  0.728  1
 x1  x2  x3   0.300  0.345  0.302 
2
20

4. Module Placements-6 (Abutment Judgment of Two Rooms)
Theorem 4.1: Let a and b (a<b) be two rooms indicated by
Abe order in a floorplan, the condition that a and b abut
each other is as follows.
(1) If a and b are in the same inside room set or the same
associated room set and there is no room c between a and b,
then a and b abut each other.
(2) If a is the i-th room in Irk={r1, r2, r3,…, rk} and b is the j-th
room in Ark={R1, R2, R3,…, Rm}, and the adjacent numbers
of rooms r1, r2, r3,…, rk -1 be Sr1, Sr2, Sr3, …, Srk-1. When one
of the following inequalities is satisfied
 i=1, 1jSr1,
 1<i<k, Sr1 + …+ Sri-1–i+2 j Sr1 + …+ Sri–i+1,
 i= k, Sr1+Sr2+ …+ Srk-1–k+2 j m,
then a and b abut each other.
21

4. Module Placements-7 (Judging two rooms abutment)
WT
p1
1
2
p3
WL
3
Judge the adjacent relationships
between room 4 and 6, 5 and 6.
p2
Firstly, room 4 and 6 , 5 and 6 join
6
p6
with p5 on the different sides.
4
p4
WR Then, I ={2, 4, 5} and A ={6, 7},
5
5
7
k=3, m=2, and S2=1, S4=2. Room 4 is
5 p5
p7
the 2nd and room 6 is the 1st room in
8
A5. room 5 are 3rd room in I5.
WB
For room 4 and 6, we have i =2<k, j =1 and S2 –i +2= 1, S2+
S4–i +1= 2, the inequality S2 –i +2=1 j  S2+ S4–i +1= 2 is
satisfied. According to Theorem 4.1, room 4 and 6 abut.
For room 5 and 6, we have i =3=k, j =1 and S2+ S4–i +2= 2, it
is not satisfy S2+S4–k+2 j m, room 5 and 6 do not abut.
22
5. EQ-SEQUENCE DECODING -1
EQ-sequence
Constraint relations table
Constraint Graphs
(horizontal constraint graph
and
vertical constraint graph)
Grid
Floorplan
23
5. EQ-SEQUENCE DECODING -2
The constraint relations table
pi or Wj
Ai
Ii
Vertex
Type
p1
2
1
V1
V
p2
3, 4
1, 2
V2
H
p3
4, 5, 8
3
V3
V
p4
5
4
V4
H
p5
6, 7
2, 4, 5
V5
V
p6
7
6
V6
H
p7
8
5, 7
V7
H
3, 8
VB
H
VT
H
VR
V
VL
V
WB
WT
WR
6, 7, 8
WL
1
WT
p1 2 p2
4
WL
p6 6
p3 p4
WR
3
7
5 p5
p
7
8
WB
The relationships between
rooms and H-type vertexes.
HRV table
room vertex
1
2
3
4
5
6
7
8
V2
V2
VB
V4
V7
V6
V7
VB
VRV table
room vertex
The relationships between
rooms and V-type vertexes.
1
2
3
4
5
6
7
8
V1
V5
V3
V5
V5
VR
VR
VR
24
5. EQ-SEQUENCE DECODING -3
How to obtain B-partial graph (Vertical constraint graph)
VT
1
V2
2
6
4
3
V4
5 V
7
V6
7
Vertex generating: Each horizontal prime seg
pi is corresponding to vertex Vi; WT and WB
are corresponding to VT and VB..
Edge generating:
(1) For each B pattern state EQ(r)=rNSrBaBb…Bd,
(EQ(WT)=WTN0BaBb…Bd), consider each room
8
ri{a, b, …, d}, we draw an edge from vertex Vp
HRV table V
to Vr, where Vp is corresponding to ri and Vr is
B
room vertex
corresponding to r in the HRV table.
1
V2
For the EQ-sequence : WLN0R3R1 WTN0B6B2B1 1N1R2 2N1B4B3
2
V2
3N0R8R5R4 4N2B5 5N1R7R6 6N0B7 7N0B8 8
3
VB
VB
4
5
6
7
8
V4
V7
V6
V7
VB
For WTN0B6B2B1, we draw the edges e6, e2 and e1 from V6 to VT, V2 to
VT and V2 to VT because room 6 is corresponding to V6 and room 2 is
corresponding to V2 and room 1 is corresponding to V2 in HRV table.
25
5. EQ-SEQUENCE DECODING -3
VT
1
VV22
VT
2
1
VV22
4
3
6
V6
4
V4
7
5 V7
3
V6
V4
7
5 V7
8
Quasidual
graphs
The above-below
constraint relation
on opposite sides of
vertical prime seg
2
6
8
VB
VB
B-partial graph and Vertical constraint graph
V1
V1
1
2
1
6
2
6
4
4
VR
VL
3
V5
5
V3
7
VR
VL
3
V5
5
7
V3
8
8
R-partial graph and Horizontal constraint graph
26
5. EQ-SEQUENCE DECODING -4
Decoding by a grid
On a grid, using the algorithm of Depth-First search sorting
algorithm , to get the order of all vertexes in the constraint graphs,
the relative positions of prime segs can be obtained.
VT
VH1
VH2
…
VHn
VB
VL
VV1
VV2 … VVm
VR
27
5. EQ-SEQUENCE DECODING –5 (Example)
VT (WT)
V2 (p2)
V6 (p6)
V4 (p4)
V7 (p7)
VB (WB)
VL (WL) V1 (p1) V3 (p3) V5 (p5) VR (WR)
pi or Wj
Ai
Ii
Vertex
Type
…
…
…
…
…
p5
6, 7
2, 4, 5
V5
V
p7
8
5, 7
V7
H
…
…
…
…
…
VT
H
WT
We want to find the two
endpoints of the prime seg.
For example, consider V5 ( p5 )
which is a V-type vertex, I5= {2, 4,
5}, from the EQ-sequence, we
can find a state WTN0B6B2B1 that
contains B2. Thus, one endpoint
corresponding to p5 is VT.
Then, we find the other inside
room set {5, 7} containing 5.
Because the vertex corresponding to
this set is V7, the other endpoint is
V7.
By the same method, we can determine the two endpoints of the other prime segs.28

5.
EQ-SEQUENCE DECODING -6
Algorithm5.1
Algorithm 5.1: Decoding of EQ-sequences
Input: an EQ-sequence
Output: a floorplan corresponding to the EQ-sequence
Step 1: Establishing the constraint relations table.
Step 2: Making the vertical constraint graph and the
horizontal constraint graph.
Step 3: Sorting the position relation of vertexes in the
vertical constraint graph (horizontal constraint graph) by
the algorithm of Depth-First search sorting algorithm ,
and generating a grid.
Step 4: Determining two endpoints of each prime seg in
the grid.
29

6.
Conclusion
Algorithm5.1
The contribution of the EQ-sequence is to develop the Qsequence. Any floorplan of n rooms is uniquely encoded
by an EQ-sequence and any EQ-sequence is uniquely
decoded to a floorplan, both are in O(n) time.
1. Abutment constraints of rooms. When moving, some
rooms are needed to abut walls or some rooms are
desired to abut each other.
2. To calculate the chip area roughly. It is possible to get
the maximum size of the floorplan after decoding.
3. In floorplanning, the relationships of placement and
routing should be considered.
30

Algorithm5.1
END
Thank you!
ご静聴、ありがとうございます！
謝謝！
Please give us some suggestions.
ご意見を聞かせてください．
請多提宝貴意見
31

Download Report