descript.txt

用c＋＋写的用于FPGA设计中布图布线的工具源码

  unused variables, etc.  Also slightly altered the header structure
  of the program to better check function definitions against 
  function declarations in util.c and graphics.c.  Someday I should
  make all local functions static and put declarations for all functions
  called across modules in header files.  Added an ARCH_TYPE flag
  to the makefile so that machine dependent code (random number 
  generator right now) is altered merely by changing the makefile.
  This version should now work fine on both SUN and HP.

- Fixed a minor error message bug Guy found.

- When there is only 1 location for a clb (nx = ny = 1, with 1 clb) 
  the placer goes into an infinite loop trying to move the block.
  Added a check for this so it now just refuses to place the circuit.

- Added an option to specify FPGA size (-nx and -ny) on the command line
  for Guy.  ny can now be bigger than nx, so I had to change a couple
  of things in the range limiter routines.

- Added -aspect_ratio option to allow simulation of nonsquare FPGAs.
  Cleaned up a few bits of ugly code I found while checking that I always
  used nx and ny properly.  Had to change the range limiter routine to
  make nonsquare FPGAs work properly.

Version 3.21

- Added delta channel width description function.  Makes only one channel
  extra wide (or narrow).

- Changed channel width code so that io channel widths are no longer 
  tied to the maximum channel width in the rest of the array.

- Added -fixed_pins option to lock the pins in their initial random
  positions.

Version 3.20

- Added nonlinear congestion option to the placer.  Can either replace
  the circuit for every channel width or just place once to a suggested
  width.

- Changed the router so that it only resets the pathcost element of 
  channel segments that were reached in the last routing phase.  This only
  sped up the router by 5% -- rather disappointing.

- Added code to recompute the cost (quickly) after each placement temp.
  is finished so the check_cost checks won't fail due to round off
  accumulation.


Version 3.13

- Fixed bug in netlist parser that went into an infinite loop if a global
  net was not the first item in it's hash table entry.

- Added -place_cost_exp option to set the exponent to which we take the
  average number of tracks per channel factor in the cost function.  Setting
  this option to be greater than 1 allows more sever penalization of narrow
  channels during placement.

- Made Pathfinder algorithm with init_pres_fac = 0.5 and acc_fac_mult
  = 0.2 the default for the router.  Gives about 9% better results than 
  the old router options.

- Changed the -pin_block_update_type option to -block_update_type and
  allowed it to take a value of "pathfinder".  This invokes a true
  Pathfinder algorithm, where some costs are updated immediately and
  others are updated after all nets are routed.  This Pathfinder 
  algorithm is new this version.

- Fixed a minor bug in the placer cost function that led to incorrect
  bounding boxes (and hence costs) of nets that had more than one pin
  connected to the same block.  The initial bounding box set up
  overcounted the number of blocks on the bb edges.  This bug caused
  an error message in Mike's big run of vpr on all mcnc circuits.


Version 3.12

- Added a new option, -pin_block_update_type, to allow selection of a
  mixed Pathfinder, immediate-update algorithm where pin costs are updated
  immediately and channel costs are updated in the Pathfinder manner.

- Now computes and prints out routed wirelength statistics (requested by 
  Mike). 

- Fixed a minor bug in the routine that counted the number of bends in
  the routed circuit.  The bug counted an extra bend in rare cases 
  (specifically when wires came out of an OPIN into more than one channel),
  causing the bend numbers to be about 1% higher than they should have 
  been.
  

Version 3.11

- Added a few more routing options.  Set a couple of defaults to what
  I've determined to be better values.  I compute statistics on how
  many bends there are per net.  This version is going to Jonathan.


Version 3.10

- Changed the bounding box update method so that large nets have their
  bounding boxes incrementally updated whenever possible.  This has
  sped up the bounding box calculation for bigkey_mod by a 
  factor of about 34.  For other netlists with fewer high fanout nets
  the improvement is smaller, but still significant.

- Changed the cost function calculation so that as much data as possible
  is precomputed.  This and the bounding box change together speed 
  up placement of small circuits (e64) by 2x, and large circuits (alu4)
  by 15x.

- Added more options to allow more control over the router.


Code maintenance changes:

  Restructured the options parser to make it more modular.  Added checks
  to determine that the parameters supplied for each option are of the
  correct (integer, float or string) type.

 
Version 3.02

- Changed the cost function's for the router.  Pins that are not 
  oversubscribed now have a cost of 0., not 1.  The costs of all pins
  should be 1 less than in version 3.01.  Channels are penalized for
  overuse via formulae like cost = 1. + (chan_occ - chan_width) * fac
  rather than the old cost = 1. + (chan_occ / chan_width - 1.) * fac.
  This new cost penalizes absolute rather than relative overuse, and
  should be faster to compute and lead to larger penalties (regardless
  of channel width) with smaller penalty factors, fac.  It's magnitude
  should be more in line with that of the pin overuse cost.

  The one drawback is that the relative overuse cost considered using
  11 tracks in a 10 track channel to be less severe than using 2 tracks
  in a 1 track channel, which is probably the way it should be.


Version 3.01

- Allocated small chunks of memory with calls to my_small_malloc instead
  of my_malloc.  My_small_malloc is my custom memory handler that 
  avoids the 8-byte or so storage overhead of malloc, at the cost of not
  keeping enough information to free the data structures.

- Removed the temporary code from the routing serial number generator, 
  routing print routine, and channel cost and occupancy dumping routine
  that allowed direct comparison with Version 2.22a's results.  All 
  information is now printed with the true (new) pin numbering scheme.

- Removed temporary code that set CLB's opin cost to 0.  Now it is 1;
  it shouldn't make much difference.


Version 3.00

This version evolved from Version 2.22, not 2.22a.  The changes are:

- Input netlist format changed from blif to that produced by blifmap (.net).

- Architecture description file is changed to allow the definition of more
  arbitrary clbs, with general classes of logically equivalent pins.

- The entire program has been altered to place and route general clbs rather
  than just LUTs with one output.

- The program allows global nets to be flagged via .global statements in the
  input netlist file.  These nets are ignored in all subsequent place and 
  route steps by the program, but the blocks they must connect are listed
  in the final routing output.

- The routing output now goes to a file, which is specified on the command
  line.

- Added two new command line options -route_only and -place_only.  If 
  -route_only is specified, an existing placement is read in from the
  place_file and is routed.  If -place_only is specified, the program
  quits after writing out the final placement of a circuit (no routing is
  done).


Bug Fixes and minor alterations:

- Changed the chan_y.occ vs. chan_width_y check in check_routing.  It 
  had the wrong subscript (this would have been bad!).

- Changed the placement output file to include subblock information for IOs.

- Increased the input buffer size for all parsers and added a check for 
  lines so long that they overflow the input buffer (motivated by J.P.).

- Changed binary search for minimum necessary track width so that tiny 
  circuits that succeed with a width_factor of 0 are properly handled 
  (motivated by J.P.).

- Fixed minor mistake drawing to the OPINs of IO blocks.

- Partially fixed the inaccurate drawing problem caused by X Windows' 
  apparent inability to handle coordinates outside the range -15000 to 
  15000.  I clip point by point to the -15000 to 15000 range.  This means
  drawrect, fillrect and drawtext will always work properly.  Drawline
  (fillpoly) will always work for horizontal or vertical lines (polygon edges)
  but will be incorrect for extremely zoomed diagonal ones.  Drawarc will
  also be incorrect at extreme zooms.  The PostScript output always looks
  correct.  The only complete fix for this problem is for me to write my
  own clipping routines.  This is a lot of code, and will hurt performance
  since I'll be duplicating X Windows' own checks.  I don't think it's 
  worthwhile to overcome a problem that only shows up when people zoom
  in on the graphics absurdly (like a bored Steve, who found the inaccurate
  drawing).

- Routing serial number generator now only considers the pin numbers of 
  traceback segments that are of type OPIN or IPIN.


Version 2.22a

Made some minor changes to Version 2.22 to allow this program's output to
be compared to that of Version 3.0 in order to be sure the programs work
the same way.  Fixed a nasty bug in check_routing where the chan_width_y
not exceeded check was incorrect.  Changed the serial number generation
to avoid taking the pin numbers of things that were not IPINS or OPINs.

Version 2.22

Same as version 2.21 with a few changes to make util.c and util.h a bit
more modular.


Version 2.21

Updated the router graphics, and fixed the unsaved routing bug, and
the improper abort sequence when the PostScript file can't be opened.
This version is fully functional, but can handle only clbs with 1 LUT
in them.


Version 2.20

This version correctly routes nets and updates the cost functions.  It
is a complete place and route tool.  The router graphics have now been
implemented, and all graphics allow a text message and selection of clbs.