| VLSI design has entered the deep sub-micron (DSM)
era, and feature sizes shrink constantly. The decrease in
feature sizes has two effects: 1-more complex circuits
can be packed on silicon, and 2-factors that were
traditionally ignored in VLSI-CAD, like cross-talk,
inductance, heat dissipation, etc., should now be
accounted for in designs. These factors cannot be computed or accurately estimated until the floorplanning stage is done. On the other hand, floorplanning cannot be started until all the modules in the library are designed (because the width/height information of the modules is needed in floorplanning). Unfortunately, the complexity of the circuits leads to long design cycles, currently a few years (e.g. for processors), and hence the traditional VLSI-CAD methods cannot guarantee reasonable time-to-market. In most of the circuits, designers extensively reuse their modules from previous projects. These modules are either used as is, or improved to fullfil requirements of the current project. Given the fact that shape information of most of the modules in the design is known at the early stages of the design, it might be possible to start the floorplanning process with the partial information on the final library. For example, suppose we had used a filter in our previous design with area A, and we are going to use a more complex filter in the new project. We might be able to estimate the area of the new filter as 1.2A with 70% probability and 1.3A with 30% probability. Based on the above idea, we have proposed a new Wong-Liu-based floorplanner called Nostradamus, which starts the floorplanning stage before the modules are completely designed. Instead of exact dimensions of the modules, the input to Nostradamus is lists of probabilistic width/height pairs for modules. To highlight the difference between our floorplanning and the traditional floorplanning problem, consider the following example:  If two modules are combined by a vertical cut to form a larger module (in the sizing tree hierarchy), the dimensions of the new module is calculated as show in the figure on the right.However, if the height information of the two modules is probabilistic, then the height of the new module will be probabilistic as well. The following figure shows an example. Note that if the height of module 1 in the figure below was fixed (i.e., not probabilistic), and greater than all probabilistic height values of module 2 (i.e., 4 and 6), then the height of the combined module would not be probabilistic. In this case, module 1 hides the probability of module 2.
The sizing process in Nostradamus is similar to the calculation of the height of the module above. Hence, the area of a floorplan generated by Nostradamus will not be a simple width x height, instead, the area will be a probability distribution function (pdf). The two figures below show examples of output floorplan's width pdf. Note the difference between variances.
If the variance of area pdf is high (e.g., C4 output
pdf above), the floorplan is not reliable: the final
floorplan, generated after all modules are designed,
might be very different than the one generated here.
Different floorplans generated by Nostradamus have different expected value/variance for the area pdf. A subset of these floorplans are in expected/variance dominant set. A floorplan is in the dominant set if no other floorplan can be found whose both variance and expected area are less than the on in the dominant set. The following figure shows an example of the dominant set.
The selection of a floorplan from the dominant set is not trivial. Based on design needs, the user can trade-off between more reliable (i.e., less variance in the final shape's dimensions) and more compact (i.e., less expected values for width/height) designs. |
