A. Montone & M.D. Santambrogio
Dipartimento di Elettronica e Informazione
Politecnico di Milano

Overview
Today’s Field Programmable Gate Arrays (FPGAs) are among the most adopted solutions for embedded systems implementations. Since their introduction in the mid ‘80s, FPGAs have provided new challenges to the existing VLSI design automation algorithms. FPGAs are no longer considered only as devices for prototyping, but they are also becoming companions to ASICs. For example, cutting-edge systems are built pairing an ASIC with an FPGA that can be configured in order to implement a desired circuit depending on application needs [1]. One of the most studied advantages of FPGAs deals with their reconfiguration capability, i.e. the ability to change the architecture or the application implemented on the FPGA without any mechanical action applied to the device [2, 3, 4]. One cutting-edge application deals with dynamic or partial reconfigurability. According to this methodology, a modular architecture may change at runtime (without having a disruption of provided functionality) a subset of its modules in order to improve or change its own behavior. Reconfigurability therefore introduces time as a new variable inside the floorplanning and placement formulation.

In such a scenario, it is possible to define a reconfigurable functional unit (RFU) as a synthesized and technology-mapped module that can be configured inside a portion of the FPGA. The identification of the floorplanning and placement constraints for the RFUs is an important problem that needs to be addressed. Currently one of the most interesting research topics, both in academia [5] and industry [6, 7], deals with the relationship between floorplanning and reconfigurability.

The determination of floorplanning constraints is required regardless of whether an FPGA is configured statically or dynamically.  However dynamic or partial configuration provides an especially compelling reason for such constraints. Identification of area constraints is much more critical in dynamically configurable systems because the same chip area may be used by several RFUs.  The aim of this work is the definition of an objective function to evaluate the quality  of an area assigned to a given RFU. We based our objective function on wirelength, introducing a novel way to estimate wirelength based on the interpolation of output data coming from synthesis and technology mapping algorithms. The proposed methodology has been validated using Synplicity’s Synplify Pro® software [6].  The advanced area optimization technology used in the Synplify Pro tool gives one the capability to pack the designs into smaller FPGAs without impacting performance. Furthermore, Synplicity provides advanced synthesis technology to support modular design methodologies [8].

In the next section a detailed description of the proposed metric is provided.

Metric for area constraint evaluation
Several metrics can be used in order to rate the area () where a RFU () is placed and consequently to evaluate the global placement of a set of modules. In [9] the following values have been taken into account to evaluate the placement of  inside area  (referred to as ):

• The fragmentation factor (where  is the total number of resources of type t provided by area ,  is the total number of resources of type t required by , and  is the target FPGA’s spatial density¹ of resources of type t  inside area  )

• The length of critical path  
• The average length of the 10 longest paths  

The following objective function has been defined:

where A is a number, while B and C are frequencies and belongs to the same order of magnitude of the longest path of the considered design. Hence, scaling critical path and the 10 longest paths using B and C with respect to the longest path of the design results in  being the sum of parts belonging to the interval [0,1]. Hence if the considered module is responsible for the longest critical path then  will have a normalized path components equal to 1, and any variation to the critical path due to the placement will be emphasized more than any other improvement obtained i.e., decreasing fragmentation.  The square power is used to assign a higher weight to higher components, i.e. it is better to gain a decrease of a long data path than a decrease of a low fragmentation rate. Furthermore, parameters A, B and C can be specified in order to better weight importance of each component.  Given an RFU placed into ,  can be easily computed, but the exact value of   and   can be obtained only by performing placement and routing of  inside.

The novelty introduced here is the approximation of path components through paraboli-like functions of:

•  aspect ratio of  the ratio between height and width of , i.e. an aspect ratio equal to 2 means having an assigned area whose height is twice the width 
•  area ratio of  with respect to  requirements, the ratio between the area (expressed in CLB2) of and the minimum area required by , i.e. an area ratio equal to 2 means having assigned an area twice the minimum required 

Hence  and  can be expressed as quadratic functions of , .  Figure 1 shows a simple example of how an assigned-area’s aspect ratio and critical path are related, resulting in an RFU with an area aspect ratio too high (or too low) and therefore a longer critical path.

Figure 1:Example of the relationship between assigned area (grey square) aspect ratio and longest path (red line)

Figure 2 presents an example where the fragmentation factor demonstrates its effectiveness in driving the RFU placement.

Figure 2: Working in a 1D reconfigurable scenario it is possible to see how the Fragmentation Factor can be used to drive the placement of the RFUs that have to be implemented. (a) In this context we have to different Reconfigurable Areas both with a high Fragmentation Factor. (b) It presents a scenario where both the components are placed in the same are to minimize the Fragmentation Factor.

A drawback of the fragmentation factor is that it does not take into consideration important information such as the routing complexity and the corresponding wire length inside each Reconfigurable Area.  Figure 3 shows an example of this drawback, reporting the relationship between assigned-area size and complexity of the routing. Assigning a biggest area to the RFU (whose components are represented by the 4 orange squares) the components can be placed further apart; consequently more routing resources are included in the space between components (yellow area). Area assignment in Figure 3 (b) corresponds to a higher fragmentation index (the area provides more resources than the ones strictly needed by the RFU).

Figure 3: Example of the relationship between assigned area (grey rectangle) size and routing complexity.

The parameters of f can be evaluated in two ways:

• Pre-Placement and Routing: the parameters are directly estimated from data provided by the netlist.
• Post-Placement and Routing: Some placements and routings of  are performed inside different areas (characterized by different aspect ratios and dimensions), evaluating and  for such placements and routings; finally the parameters are evaluated by performing a maximum-likelihood estimation. This second method is more time-expensive, but provides much more precise results with respect to the Pre-Placement and Routing.

Figure 4: Plot of the longest paths and the critical path with respect to the assigned area aspect ratio (total area is kept fixed)

Once the parameters of quadratic function have been computed, the area assignments can be evaluated.

A validation of this approach can be seen in Figure 4, where the path delay terms derived from placement and routing experiments of a SDRAM controller are reported. It can be noticed how the path delay terms of the objective function have paraboli-like shapes. As previously described, the area ratio is measured with respect to the smallest feasible solution. It can be observed how increasing the area results in a routing becoming less knotty. However, without introducing further constraints to the placement and routing tool, the logic spreads out (due to effects resembling force directed placement), the nets become longer, and total latency increases. Table 1 presents the results of the corresponding placement and routing experiments where different area constraints have been assigned to the same SDRAM memory controller as per Figure 1.

Table 1: SDRAM memory controller placement and routing results, corresponding to different area constraints assignment

Using such coefficients the improvements given by scaling assigned area can be easily seen. Looking at the table one can be notice again how an increase in the assigned area does not always result in a better timing result, due to mapping tools that tend to spread logic along the assigned area without taking account   (unless explicitly specified) of global timing.   allows one to evaluate the quality of the placement and routing of  inside an area . In order to evaluate the quality of an entire placement,  can be evaluated for each module m assigned to the corresponding area . Consequently, an index of placement quality may be obtained by weighting the values obtained for all the modules.

Bibliography
[1]  Intel Corporation. "Intel Developer Conference." 2007.

[2]  A. Alsolaim, J. Starzyk, J. Becker, M. Glesner. "Architecture and application of a dynamically reconfigurable hardware array for future mobile communication systems." IEEE Symposium on Field-Programmable Custom Computing Machines. 2000.

[3]   R.D. Hudson, D. I. Lehn, P. M. Athanas. "A runtime reconfigurable engine for image interpolation." IEEE Symposium on Field-Programmable Custom Computing Machines. 1998.

[4]   S. Swaminathan, R. Tessier, D.Goeckel, W. Burleson. "A dynamically reconfigurable adaptive viterbi decoder." 10th International Symposium on Field Programmable Gate Arrays. 2002.

[5]   V. Betz, J. Rose. “VPR: a new packing, placement and routing tool for FPGA research.” Springer Berlin, 1997.

[7]   Xilinx Inc. http://www.xilinx.com.

[8]    Synplicity Inc. “Synplify Pro User Guide and Tutorial”

[9]  A. Montone, M.D. Santambrogio, D. Sciuto. "A design workflow for the identification of area constraints in dynamic reconfigurable systems." IEEE International Symposium on Electronic Design, Test and Applications. 2008.

1. The spatial density of resources of type t inside an area is given by the ratio between the number of contained resources of type t and the number of contained frames (i.e. the smallest portion of FPGA that can be individually configured).