1、附录 A FPGA Placement Optimization Methodology Survey Sang-Joon Lee and Dr. Kaamran Raahemifar Department of Electrical and ComputerEngineeringRyersonUniversity Toronto, ON, Canada ABSTRACT Field Programmable Gate Array (FPGA) is a programmable chip that can be used to quickly implement any digital ci
2、rcuits. Placement is an important part of FPGA design step which determines physical arrangement of the logic blocks in the FPGA. The quality of placement of logic blocks determines overall performance of the logic implemented in the FPGA. In this paper, a number of placement optimization techniques
3、 are reviewed； min-cut, quadratic, simulated annealing, and a hybrid approach of using genetic algorithm with simulated annealing technique. The methodology of each optimization technique is presented and its advantages and disadvantages are evaluated. Overall, the hybrid approach of using genetic a
4、lgorithm with simulated annealing technique produces best result, reaching a global optimal solution. The hybrid approach of using genetic algorithm and simulated annealing optimization technique is implemented using MATLAB and its results are presented using a wire-lengthdriven placement as cost fu
5、nction. Index Terms Field programmable gate arrays, optimization methods, routing, quadratic programming, simulated annealing, and genetic algorithms 1.INTRODUCTION Field-Programmable gate arrays (FPGA) are reprogrammable logic chips that can be configured to implement various digital circuits. The
6、Field Programmable Gate Array (FPGA) has gained its popularity in implementing digital circuit due to its significant low cost and fast prototyping turn around time. In this survey, an island style FPGA model is considered. Island style FPGA architecture is generally characterized by its two-dimensi
7、onal symmetry. The generic structure consists of four main elements: Configurable Logic Blocks (CLB), which typically contains either combinational or sequential logic circuits, Input/Output blocks (IOB), which connects the FPGA with external devices and programmable interconnection resources and sw
8、itches. Configurable logic blocks are capable of implementing multiple logic functions. The connection block is used to connect a CLB to the routing channels via programmable connections. Similarly, the switch block is used to connect vertical and horizontal routing channels via programmable connect
9、ions. 1.1 The Placement Problem The goal of placement is to find a valid placement for each of configuration logic blocks while trying to minimize the total length of interconnect required. FPGA placement algorithm requires a net-list of logic blocks, which includes CLBs, I/O pads, and their interco
10、nnections. The result of placement is the physical assignment of all blocks and pads on the target FPGA that minimizes one or more objective cost functions. There are three common optimization criteria for placement, time-length driven placement, wirelength-driven placement and routability-driven pl
11、acement. This paper will focus on wire-length placement as the optimization criteria. 1.2 Placement Optimization Techniques There are five different classes of FPGA placement optimization techniques currently proposed, min-cut, quadratic, simulated annealing, genetic algorithm and particle swarm opt
12、imization. In this paper, four techniques, min-cut, quadratic, simulated annealing, and a hybrid genetic algorithm with simulated annealing technique will be presented and evaluated. The paper is organized as follows. In section 2, min-cut placement is presented. In section 3, the quadratic placemen
13、t technique is presented. In section 4, simulated annealing technique is presented. In section 5, a hybrid method of using genetic algorithm and simulated annealing is presented. Lastly, an implementation of hybrid method of genetic algorithm and simulated annealing optimization technique is present
14、ed. 2. MIN-CUT PLACEMENT The min-cut optimization technique uses recursive partitioning to divide a net-list of circuits into increasingly smaller sub-circuits. The following section describes the min-cut placement approach and evaluation of the placement algorithm. 2.1 Min-Cut Optimization Techniqu
15、e The min-cut optimization technique recursively apply mincut partitioning to map the net-list of the circuit into the FPGA layout region. A circuit is recursively bi-partitioned, minimizing the number of cuts of the nets that connect component between partitions, while leaving the highlyconnected b
16、locks in one partition. This recursive process is repeated until each partition contains only a few blocks to group the highly-connected blocks together in order to decrease placement cost 3. Each partition corresponds to one node in a recursive tree, in a breath first manner 2. The goal of min-cut
17、to make a division of partitions that cuts fewest wires. All edges in the net-list to be partitioned are weighted with timing criticality. The timing criticality of the edges is calculated using the timing delay values where time delay is always positive . Also, it defines criticality of a node as t
18、he maximum criticality of its incident edges. Using timing criticality as edge weight criteria disables the partitioning algorithm from cutting edges with high criticalities. Therefore, the time critical nets will be kept in same partition and the circuit will have a smaller time delay. The process
19、of delay assignment is performed at every partitioning stage. Therefore, the timing criticalities will be more accurate and better at each stage of timing-driven partitioning . 2.2. Pros and Cons The advantage of min-cut/partition based technique is that it has an open cost function which can be eit
20、her wire-lengthdriven or time-driven cost function. However, it does not reach global solution. Also, the solution may vary on how the min-cut/partition is performed. As well, as partition is performed, the information from previous step is lost； therefore, the solution may not be able to climb out
21、of a local minimum. 3. QUADRATIC PLACEMENT In this section, the quadratic optimization technique implementation for placement problem is reviewed. 3.1. Overview of Quadratic Placement The quadratic algorithm tries to minimize total squared length by solving linear equation . The cost function is the
22、 quadratic sum of the distance from source to destination of each point the path. A cost function for example shown in figure 1 is as follows: This cost function is expanded for entire circuit in the FPGA. The general cost function for quadratic placement is as follows: 222222 )43()43()32()32()21()2
23、1( yyxxyyxxyyxxc （ 1） This cost function is expanded for entire circuit in the FPGA.The generalcostfunctionforquadratic placementis asfollows: )2()()(),(,2212 ji jiji yyxxyx Where x and y are the coordinates of a logic of the net-list.Wijistheweightoftheedgethatconnectsnodes(xi,yi)and node(xj,yj). S
24、incetheinputofthequadraticplacementis usuallyrepresentedbyahyper-graph,andtwonodescanbe connectedbymorethanonenet,thegraphisconvertedtoa weighted hyper-graph, and then two models are used to convertthehyper-graphintoagraph. 3.2. OptimizationbyQuadratic Placement The following is the quadratic placement optimization technique proposed. Stage 1 Buildandsolve linearequations. Mapthe circuittothe FPGAchip. Adddummynodesandexpandthe placement. Stage 2
