LSI フロアプランニングに対する遺伝的アルゴリズムとタブー探索に基づく並列アルゴリズムとその PC クラスタ上での実現

全文

(1)2007- S L DM-128 ( 6 ). IPSJ SIG Technical Reports. 2007/1/17. t JEftma*¥1**»¥«. T 731-3194 JAftTla^femK^S* 3-4-1. E-mail: {wakaba,s_naga}@ce.hiroshima-cu.ac.jp. It. A Parallel Algorithm Based on Genetic Algorithm and Tabu Search for. LSI Floorplanning and Its Implementation on a PC Cluster Takayoshi SHIMAZUf, Shin'ichi WAKABAYASHit, and Shinobu NAGAYAMAt f Faculty of Information Sciences, Hiroshima City University 3-4-1, Ozuka-higashi, Asaminami-ku, Hiroshima 731-3194, Japan. E-mail: {wakaba,s_naga}©ce.hiroshima-cu.ac.jp Abstract. This paper proposes a parallel floorplanning algorithm for VLSI floorplanning, which was based on genetic algo. rithm (GA) and tabu search (TS). The proposed method consists of three phases. In the first phase, solutions were globally. searched by GA on each PC independently. In the second pahse, from good solutions found in the first phase, further search was performed based on GA in each PC, with interchanging solutions among PCs. In the last phase, TS was executed in each. PC to improve the best solutions found in the second phase to get a final solution. The proposed method was implemented with the MPI (Message Passing Interface) library on a PC cluster. Experimental results show the effectiveness of the proposed method.. Key words. genetic algorithm, tabu search, LSI floorplanning, parallel algorithm. -31-.

(2) 5. 1112. 6. 13. |e|c|ald|f|b|f|c|b|e|a|d|flc|b|e|a|d|. r+. r. (a). e. chromosome 11. r.. 0. 9 y\ 2 r+. . r+, r_ \Z&*:z {b). floorplan. (c). oblique-grid notation. rj«90. 3. fc GA l:. , MPI(Af«jflge Ptissing Interface, MPI) £ffl -5.. It^n/t^vrL-. 2.2. A (geneticalgorithm, GA) \Zt. TS. 3.1. X. 7x-X 1 TTte, 2.3. v-<T. {Sequence-Pair, SP) $fflU5 [5]. H GA (I . 7x-. (2)7x-X2(GA2) -32-.

(3) lelclaldlft^flcNIelald1!-116'9^-0 r+. (a). r.. sequence-pair. ^c. (b). oblique-grid notation. mi. r+,. ifi. m. r_. 7]. Bl 2 Cx-. (/,c,6,e,a,d)l vrL-Jl/ b. 7x-X fib, 7x-X (3)7x-X3(TS). 3.2. 7x-X I,. 7x-Xl,. = W x. Id. 7x-X I. & Li. -33-. [(e,c,a,d,/,6), b. fc 5 f.

(4) Gamma-. jjclaldEgblflclbEiialdl Gamma+. Gamma-. 1-l.rA ^. ^. Mlc|a|d|Mb«c|bM|a|d| Gamma+. Gamma-. start. (a)H constraint graph. (b)V constraint graph. lcMa«d|b|c|b|«aWHd| Gamma+. Icjjajjdlblclbilaliidl. Gamma-. Gamma+. 0 5. Gamma-. CTPX (DM. w Gamma+. Gamma—. Ic —dlblclbHWWdl. Parent2. Gamma+. lekldlalflblflclbleldlal Gamma+. Gamma-. Gamma-. ID 6. PPEX (Dfi\. (longest common subsequence, LCS) f. (a:f) = i4i + A: x Nt. l, lcs iz. 3.3. Bl 5 ^^kT. HI 5 Ttt a, 6, c,. GA. v^l-;|/H LC5 fC. GA1,. ommon Topology Preserving. Crossover, CTPX) [6] £#Jffl-f 5. GA2 Ttt CTPX ch->-^. -^, PPEX \t CTPX OJ; -5JC j/-. 5C.5L (Placement - based Partially Exchanging Crossover,. .. PPEX. H 6 Ttt parentl C. ^l-;!/ a,e,/ * parent2 T(Dt±i31Jl r_ \z. -34-. . offspringl.

(5) [mm2](rv h* X^-X [%]), [sec]. 4.. H. I. 4.1. mmmm. f GAI,. ft. %mZ CPU & Pentium4 3.4GHz,. 1GB <D PCI ft,. ±351* 3GB <D PC6 tit CPU3.2GHz,. <D PC7 ftO. fh 14 ft<7) PC £ IGbit/sec <ZH—tf* v. -*«; GA1. GA. 14. ax & GAlmax. 100000, 50000,. 25,. ioo,. 0.005. 100,. 200 tft^,. il, GA2 JC. PPEX ch CTPX (DM. 14. 1. Lft. 4.2. Hift-r-^tt GSRC ^ l&:200,. ^. ~35-.

(6) [mm^tfv H X^-. ^D-feXffc 5 iC. mm2](T7 K 7^-. [mm]. [mm]. 5.. te *> y \z , LSI. [1]. C.Chu, Y.-C.Wong: "Fast and accurate rectilinear Steiner minimal. tree algorithm for VLSI design," Proc.ISPD 2005, pp.28-35, 2005. [2]. Kalyanmoy Deb, Samir Arawal, Amrit Pratap, T. Meyarivan: "A fast elitist non-dodminated sorting genetic algorithm for multiobjective optimization : NSGA-II," Parallel Problem Solving from. T,. Nature-PPSN VI, Proc. 6th International Conference 2000, pp.849-. GA+TS. 858, 2000. [3]. Fred Glover, Manuel Laguna: Tabu Search, Kluwer Academic Pub. [4]. David E. Goldberg: Genetic Algorithm in Search, Optimnization and. lishers, 1997.. Machine Learning, Addison-Wesley, 1989. [5]. H. Murata, S. Nakatake, K. Fujiyoshi, and Y. Kajitani: "VLSI mod ule placement based on rectangle-packing by the sequence-pair," IEEE Trans, on Computer-Aided Design of Integrated Circuit and. ch TS. Systems,Vo\. 15, No. 12, pp. 1518-1524, Dec. 1996. vlsi. g£, Vol.43, No.5, pp. 1361-1371, 2002. [7]. P. S. Pacheco W (8c*WW): MPI 2001.. [8]. Takayoshi Shimazu,. Shin'ichi Wakabayashi,. Shinobu. Nagayama: "A parallel implementation of a genetic algorithm-based. floorplanninng method on PC clusters," Proc.SASIMI2006, pp.404411,2006. [9]. Xioping Tang, Ruiqi Tian, D.F.Wong: "Fast evaluation of sequence pair in block placement by longest common subsequence computa tion,. " IEEE Transactions on Computer-Aided Design of Integrated. Circuits and Systems, [ 10]. GSRC/benchl.html. -36-. Vol.20,. No. 12.. http://www.cse.ucsc.edu/research/surf/. pp.1406-1413,. 2001..

(7)