7 July 005 n SSP n n SSP SSP SSP n n. Selected Sequence-PairSSP. Sequence-PairSeq-Pair sequence-pair ) seq-pair n Γ + Γ (Γ + ;Γ ) n (n!) Γ + (i) Γ + i

Size: px

Start display at page:

Download "7 July 005 n SSP n n SSP SSP SSP n n. Selected Sequence-PairSSP. Sequence-PairSeq-Pair sequence-pair ) seq-pair n Γ + Γ (Γ + ;Γ ) n (n!) Γ + (i) Γ + i"

せぴあつつの
5 years ago
Views:

1 Vol. 6 No. 7 July 005 Selected Sequence-Pair n n sequence-pair n n selected sequence-pair sequence-pair Simulated Annealing selected sequence-pair An Efficient MOVE Operation for Selected Sequence-Pair Kunihiro Fujiyoshi, Chikaaki Kodama and Koji Kiyota Recently selected sequence-pair was proposed, which is a sequence-pair with n n or less sub-sequences called adjacent cross (n is the number of rectangles). In addition to the merit that it can represent any packing, it has a superior feature that a bottom left corner packing can be obtained under the constraints imposed by itself in linear time of the number of rectangles. However, as a method of generating adjacent solution was not proposed, it was impossible to use selected sequence-pair for search of packing by combining with Simulated Annealing, etc. In this paper, we propose adjacent solution which can guarantee reachability in selected sequence-pair and a procedure to generate an adjacent solution and then we confirm its efficiency by experiments.. VLSI Murata sequence-pair ) sequence-pair n O(n ) sequence-pair ) sequence-pair ) IP ) ) Tokyo University of Agriculture and Technology 5) sequence-pair n n selected sequence-pair SSP 6) sequence-pair O-tree 7),8) SSP n sequence-pair 9) sequence-pair n sequence-pair (n )/ (n )/ 5) sequence-pair n SSP Simulated Annealing SA n n SSP 7

2 7 July 005 n SSP n n SSP SSP SSP n n. Selected Sequence-PairSSP. Sequence-PairSeq-Pair sequence-pair ) seq-pair n Γ + Γ (Γ + ;Γ ) n (n!) Γ + (i) Γ + i Γ + (a) Γ + a Γ seq-pair Γ + Γ a b Γ + (a) < Γ + (b) (a) < Γ (b) a b Γ + a b Γ a b Γ + (a)<γ + (b) Γ (a)>γ (b) a b seq-pair seq-pair O(n log log n) 0) Γ + =( n) Γ Γ Γ Γ + seq-pair (abcdef; bfdcae) Γ (65) Γ + (56) n +5 n L + (),L + (),,L + (n) X 5 n L (),L (),,L (n)x n seq-pair S = (Γ + ;Γ ) n i L + (Γ + (i)) L (Γ (i)) S seqpair S S S a 90 S a. n {M,M,,M n } M,M,,M n n / T ) n. seq-pair S a, b, c, d S =( a bc d ; c ad b ) S =( a bc d ; b da c ) S Γ + Γ / b, c/a, d b, c/d, a Γ + bc Γ ad 7 (b) n seq-pair n n seq-pair (n )/ (n )/ 5) seq-pair (;) seq-pair (;) Fig. Rectangular dissection corresponding to seq-pair (;).

3 Vol. 6 No. 7 Selected Sequence-Pair 7. Selected Sequence-PairSSP 6) n seq-pair n n selected sequence-pair SSP n n n seq-pair ).. SSP 6) k n SSP O(n+k) SSP k O(n) O(n) 6) Step SSP S k O(n+k) Step k O(n+k) SSP S k n+k Step S O(n+k).. Step k n seq-pair Adjcross List O(n+k) 6) Γ (65) Adjcross List (a) 5 (b) (c) 6 7 (d), 5/6,, /6, (e) (f) 5 6, /, 6, 5/6, Adjcross List Γ p p = 0; foreach (p =Γ ){ if (p < p p ) foreach(k = p p p ) k, k+ /p p,p ; p p = p; if ((p ) &&(Γ (p+) > Γ (p))) // p+ p if ((p > ) &&(Γ (p ) < Γ (p))) // p p } p p = 0; foreach (p =Γ ){ if (p < p p ) foreach(k = p p p ) k, k+ /p,p p ; p p = p; if ((p ) &&(Γ (p+) < Γ (p))) // p+ p if ((p > ) &&(Γ (p ) > Γ (p))) // p p } ( Adjcross List ) Adjcross List Fig. Algorithm Adjcross List., /6,, /, 6. ( a bc d ; c ad b ) ( a bc d ; b da c ) b, c/a, d Γ + Γ + (b)<γ + (c) Γ (b)>γ (c) b c Γ Γ + (a)<γ + (d) Γ (a) < Γ (d) d a b, c/d, a Γ + Γ + (b)<γ + (c) Γ (b)<γ (c) b c Γ Γ + (a) < Γ + (d) Γ (a) > Γ (d) d a b c Γ + Γ a d Γ + Γ b c Γ + Γ a d Γ + Γ Γ (65), /, 6 (h), /6,, 5/6, (g) Γ

4 7 July 005 (a) (b) (c) 6 (d) (e) (f) Γ Γ Γ Γ 6 6 (g) Γ (65) (h) Γ (65), /6,, 5/6,, /, 6 Adjcross List Γ (65) Fig. An example of Adjcross List for normalized Γ (65). Γ Γ + Γ + (g) Γ (h).. n n seqpair SSP SA SA MOVE perturb SA SSP SSP SSP SSP Γ + Γ seq-pair ).. seqpair ) a a SSP SSP n SSP SSP P B seq-pair (P B ; P B ) SSP SSP (P + ; P ) (P B ; P B ) SSP (P + ; P ) Step SSP (P B ; P B ) Γ + Γ insertion sort (P + ; P + ) Step SSP (P + ; P + ) Γ P (P + ; P ) SSP (P B ; P B ) (P + ; P + ) (P + ; P ) (P B ; P B ) = (abcde ; abcde) (P + ; P )=(bcead ; eacdb) Step (n ) Γ + Γ seq-pair S abcd seq-pair Γ + =( a bc d ) Γ =( b da c ) Γ = ( c ad b ) Γ ba

5 Vol. 6 No. 7 Selected Sequence-Pair 75 Step (P B ; P B )=(abcde; abcde) (bacde; abcde) (bacde; bacde) (bcade; bacde) (bcade; bcade) (bcade; bcade) (bcade; bcade) (bcead; bcade) (P + ; P + )=(bcead; bcead) Step (P + ; P + )=(bcead; bcead) (bcead; cbead) (bcead; ecbad) (bcead; eacbd) (P + ; P )=(bcead; eacdb) SSP (P B ; P B ) = (abcde; abcde) (P + ; P ) = (bcead; eacdb) Fig. An example of converting from SSP (P B ; P B ) to (P + ; P ). Elements lined below were already sorted. dc Γ ca db Γ + S Step (n ) Step Γ + Γ seq-pair Γ + Γ P B Γ + Γ (n ) Step n n (n ) Step Step abcd Γ + =( a bc d ) Γ =( c ad b ) Γ =( b da c ) Step SSP (P + ; P + ) Step abcd Γ d b c Step b c d d d abcd P Step Γ a d x x P + d x abcd abcx Step Step n n (n ) (P + ; P ) P + Γ (n ) 6(n ) SSP (P+; P ) SSP (P+; P ) P B P+ (P+; P ) (P+; P+) (P+; P+) (P+; P ) (n ) (P +; P ) (P+; P+) Step n n. () () () ) () )

6 76 July Seq-pair SSP 7 seq-pair seq-pair Fig. 5 The ratio of SSP to a variety of seq-pair. () ()SA () a b b a () SSP seq-pair 5 () ()() () SSP SSP ) ().. ) Γ (965078) 6 Γ Γ Γ Γ Γ (965078) ) Γ Γ Fig. 6 Conceptual diagram of table for normalized Γ (965078). Γ (965078) seq-pair Γ + Γ n ) SSP SA SSP SSP SSP O(n) Γ + Γ 6 7

7 Vol. 6 No. 7 Selected Sequence-Pair 77 SSP Table Average number of unsuccessful times in generating adjacent solution of SSP. n SSP ( 0 ) SSP ( 0 9 ) Γ + 5 Γ 5 Γ + 5 Γ 5 5 (a) (b) 7 S = (5; 5) Fig. 7 An adjacent cross generated by moving element in S =(5; 5). 6 5 O(n) SSP n n Γ Γ Γ + =( ) Γ + Γ (5) seq-pair S 7(a) S Γ seq-pair n n Γ n n SSP Γ (597608) seq-pair Γ,,, 5 S Γ 6, 7,, 6 7 Γ (675) SSP 6 SSP 6 SSP seq-pair SSP SSP n n SSP seq-pair 5 seq-pair 7 SSP SSP seq-pair seq-pair seq-pair Γ (965078) 6 0 n n

8 78 July 005 SSP SSP.. n n Γ (5), /, 5 (5), /,, /5, a, b/c, d Γ Γ c d e a, b/e, d a, b/c, e.. a, b/c, d a bcd Γ c d c d Γ.. seq-pair O(n+k) Adjcross Listn k seq-pair a, b/c, d Γ cd Γ c x Γ + (x) < Γ + (a) Γ + (c) < Γ + (a) Γ + (x) > Γ + (a) (c) > Γ (a) c Γ + + a, b/c, d a, b/x, d c d, /5, Γ (5) 5 5, /5, Adjcross List O(n+ k).. Γ l r q q l r q a, b/l, q a, b/q, r a, b/l, r q l r l r q l q q r

9 Vol. 6 No. 7 Selected Sequence-Pair 79 5 Γ + Γ Γ + Γ Γ 6 + Γ (a) (b) (c) 6 8 Γ (65) Fig. 8 Adjacent crosses generated by moving element or 6 into inside of element and. Circled cross points show adjacent crosses generated by moving elements. q l r for (c =0, p =max(l, r); p n ; p ++){ if ( p p+ ) ++c; p + c ; } for (c =0, p =min(l, r); p>; p ){ if ( p p+ ) ++c; p c ; } Γ (65) q, /,q, /q, q, /,q, /q, 5 q, 5/,q, 5/q, Γ Γ +.. Adjcross List Γ + Γ Adjcross List Γ + p Γ + 5 Γ Γ Γ 6 8 (a) (b) 5 9 Γ + (7568;5678) Γ 5 Fig. 9 Adjacent crosses generated by moving element 5 into rightmost in Γ of normalized Γ + (7568; 5678). Circled cross points show adjacent crosses generated by moving elements. p p Γ Γ + p p p Γ + (p p)= Γ + (p) p x Γ x y Γ (y) =Γ (x)+ p p,p/x,y p p x Γ x p p z Γ (z) =Γ (x) Γ + x Γ + (z) < Γ + (x) p p,p/z,y Γ (5678) Γ Γ + (7568) Γ + Γ 5 Γ Γ Γ Γ 5,/, 5,/7,8 9 p Γ Γ + p p a p x Γ x y p, p a /x, y p a y

10 70 July 005 Γ y z Γ + y p, p a /x, z Adjcross List Γ + Γ / O(n+k) Γ +, Γ (w) Γ (w+) foreach (p =Γ + ){ if (p < w){ p p = Γ + (Γ + (p) ); foreach (x p<x&& x<w&& x ) if (x p p ) p p p p,p / x,γ (Γ (x)+) else if (Γ + (Γ (Γ (x) )) < Γ + (x)) p p p p,p / Γ (Γ (x) ), Γ (Γ (x)+) }else if (p > w+){ p a = Γ + (Γ + (p)+); foreach (x w+ <x&& x<p&& x ) if (Γ (Γ (x)+) p a) p a p, p a /x,γ (Γ else if (Γ + (Γ (Γ (p a)+)) > Γ + (p a)) p a p, p a /x,γ (Γ } if (p && Γ + // p+ p if (Γ (p ) < Γ (x)+) (p+) > Γ + (p)) (p a)+) (p)) // p + + p } ( ) 0 Fig. 0 Algorithm of counting the number of adjacent crosses generated by MOVE operation where a move element will be one of outside elements of every new adjacent cross. Adjcross List Γ + Γ SSP SSP C () n n seq-pair seqpair SSP SSP Γ + =Γ SSP n n n/00 n n SSP SSP SSP ppbparts per billion SSP SSP ppthparts per thousand SSP seq-pair Table Average number of unsuccessful times in generating adjacent solution of SSP. SSP (n) ,0,08,096 8,9 6, ,958,969 8,0 6,9 ( 0 9 ) ( 0 )

Vol. 6 No. 7 Selected Sequence-Pair 7 Pentium IV. GHz Fig. Comparison of time to make an adjacent solution. SSP SSP n 0.99 SSP 50 5. SSPselected sequence-pair SA SSP SSP SSP SA CPU SSP ) Murata, H.

11 Vol. 6 No. 7 Selected Sequence-Pair 7 Pentium IV. GHz Fig. Comparison of time to make an adjacent solution. SSP SSP n 0.99 SSP SSPselected sequence-pair SA SSP SSP SSP SA CPU SSP ) Murata, H., Fujiyoshi, K., Nakatake, S. and Kajitani, Y.: VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair, IEEE Trans. CAD, Vol.5, No., pp.58 5 (996). ) Murata, H., Fujiyoshi, K. and Kaneko, M.: VLSI/PCB Placement with Obstacles Based on Sequence Pair, IEEE Trans. CAD, Vol.7, No., pp (998). ) Fujiyoshi, K. and Murata, H.: Arbitrary Convex and Concave Rectilinear Block Packing using Sequence-Pair, IEEE Trans. CAD, Vol.9, No., pp. (000). )Lai,J.,Lin,M.-S.,Wang,T.-C.andWang, Li-C.: Module Placement with Boundary Constraints Using the Sequence-Pair Representation, ASP-DAC, pp (00). 5) Murata, H., Fujiyoshi, K., Watanabe, T. and Kajitani, Y.: A Mapping from Sequence-Pair to Rectangular Dissection, ASP-DAC, pp.65 6 (997). 6) Kodama, C. and Fujiyoshi, K.: Selected Sequence-Pair: An efficient decodable packing representation in linear time using sequencepair, ASP-DAC, pp. 7 (00). 7) Guo, P., Cheng, C.-K. and Yoshimura, T.: An O-Tree Representation of Non-Slicing Floorplan, IEEE DAC, pp.68 7 (999). 8) Takahashi, T.: A New Encoding Scheme for Rectangle Packing Problem, ASP-DAC, pp (000). 9) Selected Sequence- Pair VLD00-0, pp.99 0 (00). 0) Tang, X. and Wong, D.F.: FAST-SP: A FAST algorithm for Block Placement based on Sequence-Pair, ASP-DAC, pp.5 56 (00). ) Stockmeyer, L.: Optimal Orientations of Cells in Slicing Floorplan Designs, Info. and Control, Vol.57, pp.9 0 (98). ) Takashima, Y. and Murata, H., The tight upper bound of the empty rooms in floorplan, SASIMI00, pp.6 7 (00). ) Simulated Annealing Sequence-Pair VLD99-8, pp.9 6 (000). ) Sequence-Pair Simulated Annealing Vol.J8-A, No.7, pp (00). ( 6 7 ) ( ) 9 VLSI IEEE

12 7 July IEEE VLSI

25 II :30 16:00 (1),. Do not open this problem booklet until the start of the examination is announced. (2) 3.. Answer the following 3 proble

25 II :30 16:00 (1),. Do not open this problem booklet until the start of the examination is announced. (2) 3.. Answer the following 3 proble 25 II 25 2 6 13:30 16:00 (1),. Do not open this problem boolet until the start of the examination is announced. (2) 3.. Answer the following 3 problems. Use the designated answer sheet for each problem.