\n");
(void) fprintf(vis_stderr, "\t\tReplace and remove wires simultaneously?\n");
return 1; /* error exit */
} /* End of CommandSpfdNetworkOptimize */
/**Function********************************************************************
Synopsis [Implements SPFD-based simultaneous placement and logic
optimization command, spfd_pdlo, for combinational circuits mapped
to LUT-based FPGAs.]
CommandName [spfd_pdlo]
CommandSynopsis [Perform SPFD-based simultaneous placement and
logic optimization.]
CommandArguments [\[-D <depth>\] \[-h\] \[-n <file>\]
\[-r\] \[-t <sec>\] \[-v <n>\] \[-w <file>\]
net_file arch_file place_file route_file]
CommandDescription [This command performs SPFD-based combined logic
and placement optimization of combinational circuits mapped to
LUT-based FPGAs to improve circuit area and speed. The
flexibilities in the circuit are represented by SPFDs. The
following references explain in detail the theory behind SPFDs.
S. Yamashita, H. Sawada, and A. Nagoya. A new method to express
functional permissibilities for LUT based FPGAs and its
applications. In International Conference on Computer Aided Design,
pages 254-261, 1996.
Subarnarekha Sinha and Robert K. Brayton. Implementation and use of
SPFDs in optimizaing Boolean networks. In International Conference
on Computer Aided Design, 1998.
The command implements a technique that tightly links the logic
and placement optimization steps. The algorithm is based on
simulated annealing. Two types of moves, directed towards global
reduction in the cost function (total wire length), are accepted by
the simulated annealing algorithm: (1) wire removal/replacement,
and (2) swapping of a pair of blocks in the FPGA. Feedback from
placement is valuable in making an informed choice of a target wire
during logic optimization moves. The logic optimization steps
performed are similar to those of spfd_pilo, except that the
placement information is now used instead of the fanout count.
More information on this technique can be found in :
Balakrishna Kumthekar and Fabio Somenzi. Power and delay reduction
via simultaneous logic and placement optimization in FPGAs. In Design,
Automation and Test in Europe, 2000.
The command produces a placement file which is used by VPR for
routing.
This command can be used only if VIS is linked with VPR 4.22
(Versatile Place and Route), the FPGA place and route tool VPR,
from the University of Toronto. Please follow the instructions
provided in the release notes to use VPR with VIS. You can also
contact kumtheka@avanticorp.com if you need more help.
Before calling this command a network should be created for the
design (use flatten_hierarchy) and MDD ids for every node in the
network should be created (static_order -o all -n append). Dynamic
variable ordering (dvo -e sift) can be enabled to reduce BDD sizes.
Command options:
- -D <depth>
- A cluster is computed which includes nodes within the specified
'depth'. The default value is 1.
- -n <file>
- File to output the optimized circuit in VPR's .net format.
- -r
- Do not reprogram LUTs if no structural changes have been
performed with in the cluster, i.e., if no nodes or wires have been
removed do not change the local implementation of LUTs even if
alternate implementations are availabe from SPFD information. The
default is to reprogram.
- -t <sec>
- Time in seconds allowed to complete the command. If the
computation time goes above that limit, the process is is aborted.
The default is no limit.
- -v <n>
- Verbosity level.
- -w <file>
- File to output final optimized circuit.
The following is needed by VPR:
- net_file
- The description of the circuit in the .net format. Logic
optimization uses the circuit described in .BLIF format whereas VPR
needs the same circuit described in .net format. VPack (which comes
with VPR) converts a .BLIF format into a .net format.
- arch_file
- Architecture description file for FPGAs. More information can be
found in VPR's manual.
- place_file
- File to dump placement information.
- route_file
- File to dump routing information.
Relevant flags to be set by the set command:
- spfd_pdlo_logic_move_freq "r1 m1 r2 m2 ..."
- Perform m1 logic moves whenever the rate of acceptance during
simulated annealing is greater than or equal to r1, and so on. r1,
r2, r3 ... should be monotonically decreasing, else the results would
be unpredictable. 0 <= ri <= 1.0. For example:
set spfd_pdlo_logic_move_freq "0.8 0 0.5 5 0.2 10"
In the above logic schedule, zero logic moves per temperature will
be performed when the rate of acceptance is above 0.8, 5 logic
moves between 0.8 and 0.5, 10 moves between 0.5 and 0.2. As no
value is specified for acceptance rate close to 0.0, by default, 1
logic move per temperature will be performed. In this example it
will be 1 logic move between 0.2 and 0.0.
The quotes around the schedule are necessary.
- spfd_repl_rem
- If no, the logic optimization performs only wire
removal. If yes, both wire replacement and removal are performed.
- spfd_pdlo_timing
- If set, use timing driven method to remove or replace wires on the
critical path. If not set, use bounding box of the wires as the
cost function.
- spfd_pdlo_timing_nodeorwire
- Remove/replace all the wires belonging to the most critical
net. If not set, attempt to remove/replace only the most critical
wire.
- spfd_pdlo_out_crit_nets_first
- Output the circuit in VPR's .net format with the nets
appearing in the increasing order of their slack. If not set, the
initial net order specified in the original circuit's .net file is
used. The file is specified with
-n option. This
variable is valid only if spfd_pdlo_timing is set.
- spfd_pdlo_remap_clb_array
- During logic optimization, due to the removal of nodes in the
network, the current size of FPGA might be bigger than it is
necessary. In such cases, if this variable is set, the size of the
FPGA is reduced to fit the current logic network.
Relevant flags that are options to VPR:
For detailed information on the following options please refer to
the manual that accompanies VPR source distribution.
- vpr_nodisp
- vpr_fix_pins
- vpr_nx
- vpr_ny
- vpr_fast
- vpr_init_t
- vpr_alpha_t
- vpr_exit_t
- vpr_inner_num
- vpr_seet
- vpr_place_cost_exp
- vpr_place_chan_width
]
SideEffects [The network is changed to reflect the wires/nodes
removed or replaced. The internal function of the nodes is also
changed. The partition attached to the network is changed
accordingly.]
******************************************************************************/
static int
CommandSpfdPlaceOptimize(
Hrc_Manager_t **hmgr,
int argc,
char **argv)
{
#ifndef USE_VPR
(void) fprintf(vis_stdout,"** spfd info: This command requires VPR "
"(Versatile Place and Route)\n");
(void) fprintf(vis_stdout,"** spfd info: See \'help spfd_pdlo\' for more "
"information\n");
(void) fprintf(vis_stdout,"** spfd info: on how to compile VIS with VPR.\n");
(void) fprintf(vis_stdout,"** spfd info: Exiting calmly ...\n");
return 0;
#else
Ntk_Network_t *network;
graph_t *simPart;
int status,regionDepth;
int c;
long timeOutPeriod,initialTime,finalTime;
char *writeFile;
char *netFile,*archFile,*placeFile,*routeFile;
char *netOutFile;
FILE *fp = NIL(FILE);
/* These are the default values. */
spfdCreatedPart = 0; /* Do not create a new partition */
timeOutPeriod = 0;
spfdVerbose = 0; /* verbosity */
regionDepth = 1; /* Depth of cluster */
writeFile = NIL(char); /* File to output final optimized ckt. */
spfdNtkChanged = FALSE;
spfdReprogNoWire = TRUE;
netFile = archFile = NIL(char); /* Circuit specified in VPR's .net
format and FPGA architecture file */
placeFile = routeFile = NIL(char); /* File to store placement and
routing information */
spfdWiresAdded = 0;
spfdNumWiresRem = 0;
netOutFile = NIL(char); /* File to output the optimized circuit in
.net format */
status = FALSE;
if (bdd_get_package_name() != CUDD) {
(void) fprintf(vis_stderr,
"** spfd error: The spfd package can be used "
"only with CUDD package\n");
(void) fprintf(vis_stderr,
"** spfd error: Please link with CUDD package\n");
return 0;
}
util_getopt_reset();
while((c = util_getopt(argc, argv, "D:hn:rt:v:w:")) != EOF) {
switch(c) {
case 'D':
regionDepth = atoi(util_optarg);
break;
case 'h':
goto usage;
case 'n':
netOutFile = util_strsav(util_optarg);
break;
case 'r':
spfdReprogNoWire = FALSE;
break;
case 't':
timeOutPeriod = atoi(util_optarg);
break;
case 'v':
spfdVerbose = atoi(util_optarg);
break;
case 'w':
writeFile = util_strsav(util_optarg);
if ((fp = Cmd_FileOpen(writeFile,"w",NIL(char *),1)) == NIL(FILE)) {
(void) fprintf(vis_stderr,
"** spfd error: Could not open %s for writing.\n",
writeFile);
goto endgame;
} else {
fclose(fp);
}
break;
default:
goto usage;
}
}
/* netFile, archFile, and placeFile are essential. The user can
specify /dev/null for routeFile if they don't want to store the
routing information */
if (argc < 5 || argc < util_optind+4)
goto usage;
/* Get the net, architecture, place and route file names */
netFile = argv[util_optind];
archFile = argv[util_optind+1];
placeFile = argv[util_optind+2];
routeFile = argv[util_optind+3];
if(Hrc_ManagerReadCurrentNode(*hmgr) == NIL(Hrc_Node_t)) {
(void) fprintf(vis_stderr,"** spfd error: The hierarchy manager is empty. "
"Read in design.\n");
goto endgame;
}
network = (Ntk_Network_t *)
Hrc_NodeReadApplInfo(Hrc_ManagerReadCurrentNode(*hmgr),
NTK_HRC_NODE_APPL_KEY);
if(network == NIL(Ntk_Network_t)) {
(void) fprintf(vis_stderr,"** spfd error: There is no network. ");
(void) fprintf(vis_stderr,"Use flatten_hierarchy.\n");
goto endgame;
}
/* Check if the current network has signals with multiple values. */
if (TestIsNetworkMultipleValued(network)) {
(void) fprintf(vis_stderr,"** spfd error: Circuit has multiple "
"valued variables.\n");
(void) fprintf(vis_stderr,"** spfd error: The algorithm applies "
"to Boolean variables only.\n");
goto endgame;
}
if(Ntk_NetworkReadNumPrimaryInputs(network) !=
Ntk_NetworkReadNumInputs(network)) {
(void) fprintf(vis_stderr,"** spfd error: Pseudo inputs present "
"in the network.\n");
(void) fprintf(vis_stderr,"** spfd error: The algorithm does not apply.\n");
goto endgame;
}
/* Access a 'total' partition */
simPart = (graph_t *) Ntk_NetworkReadApplInfo(network,
PART_NETWORK_APPL_KEY);
if (simPart == NIL(graph_t) ||
(Part_PartitionReadMethod(simPart) != Part_Total_c)) {
simPart = Part_NetworkCreatePartition(network,
NIL(Hrc_Node_t),
"dummy", (lsList) 0,
(lsList) 0, NIL(mdd_t),
Part_Total_c,
(lsList) 0,
FALSE, FALSE, TRUE);
if (simPart == NIL(graph_t)) {
(void) fprintf(vis_stderr,"** spfd error: Could not create partition.\n");
goto endgame;
}
Ntk_NetworkAddApplInfo(network,PART_NETWORK_APPL_KEY,
(Ntk_ApplInfoFreeFn)Part_PartitionFreeCallback,
(void *)simPart);
spfdCreatedPart = 1; /* Using new partition */
(void) fprintf(vis_stdout,
"** spfd info: A new partition created.\n");
}
/* Start the timer.*/
if (timeOutPeriod > 0){
(void) signal(SIGALRM, (void(*)(int))TimeOutHandle);
(void) alarm(timeOutPeriod);
if (setjmp(timeOutEnv) > 0) {
(void) fprintf(vis_stderr, "** spfd warning: Timeout occurred after ");
(void) fprintf(vis_stderr, "%ld seconds.\n", timeOutPeriod);
alarm(0);
goto endgame;
}
}
initialTime = util_cpu_time();
/* Call the optimization routine. */
status = SpfdSimultaneousPlacementAndLogicOpt(network,netFile,archFile,
placeFile,routeFile,netOutFile,
regionDepth);
finalTime = util_cpu_time();
if(status) {
(void) fprintf(vis_stdout, "%-20s%10ld\n", "** spfd info: analysis time =",
(finalTime-initialTime)/1000);
}
else {
(void) fprintf(vis_stdout, "** spfd error: Optimization failed.\n");
}
if (writeFile) {
SpfdNetworkWriteBlifFile(network,writeFile);
FREE(writeFile);
}
if (netOutFile) {
FREE(netOutFile);
}
if (spfdCreatedPart)
Ntk_NetworkFreeApplInfo(network,PART_NETWORK_APPL_KEY);
alarm(0);
return 0; /* normal exit */
endgame:
/* Clean up */
if (writeFile)
FREE(writeFile);
if (netOutFile) {
FREE(netOutFile);
}
if (spfdCreatedPart)
Ntk_NetworkFreeApplInfo(network,PART_NETWORK_APPL_KEY);
return 1; /* Error exit */
usage:
(void) fprintf(vis_stderr, "\nusage: Also see \'help spfd_pdlo\' for more details.\n\n");
(void) fprintf(vis_stderr, "spfd_pdlo [options] net_file arch_file place_file route_file\n\n");
(void) fprintf(vis_stderr, " -D \t\tConsider region upto .\n\n");
(void) fprintf(vis_stderr, " -h \t\tCommand usage.\n\n");
(void) fprintf(vis_stderr, " -n \tFile to output optimized\n");
(void) fprintf(vis_stderr, " \t\tcircuit in .net format.\n\n");
(void) fprintf(vis_stderr, " -r \t\tDo not reprogram internal nodes if there are no\n");
(void) fprintf(vis_stderr, " \t\tstructural changes in the network.\n\n");
(void) fprintf(vis_stderr, " -t \t\tTime (s) limit for the command.\n\n");
(void) fprintf(vis_stderr, " -v \t\tVerbosity level.\n\n");
(void) fprintf(vis_stderr, " -w \tFile to output final optimized circuit.\n\n");
(void) fprintf(vis_stderr, "set options: \n");
(void) fprintf(vis_stderr, "\tspfd_pdlo_logic_move_freq \"r1 m1 r2 m2 ...\"\n");
(void) fprintf(vis_stderr, "\t\tPerform m1 logic moves per temperature whenever the rate\n");
(void) fprintf(vis_stderr, "\t\tof acceptance during simulated annealing is greater than\n");
(void) fprintf(vis_stderr, "\t\tor equal to r1, and so on. r1 > r2 > r3 ... \n");
(void) fprintf(vis_stderr, "\t\tand 0 <= ri <= 1.0.\n\n");
(void) fprintf(vis_stderr, "\tspfd_repl_rem \n");
(void) fprintf(vis_stderr, "\t\tPerform both wire replacement and removal?\n\n");
(void) fprintf(vis_stderr, "\tspfd_pdlo_timing\n");
(void) fprintf(vis_stderr, "\t\tUse timing driven method.\n");
(void) fprintf(vis_stderr, "\t\tIf not set, Bounding box method is used.\n\n");
(void) fprintf(vis_stderr, "\tspfd_pdlo_timing_nodeorwire\n");
(void) fprintf(vis_stderr, "\t\tProcess the fanouts of the most tcritical node. If not set,\n");
(void) fprintf(vis_stderr, "\t\tprocess only the wires on the critical path.\n\n");
(void) fprintf(vis_stderr, "\tspfd_pdlo_out_crit_nets_first\n");
(void) fprintf(vis_stderr, "\t\tOutput the circuit in VPR\'s .net format with\n");
(void) fprintf(vis_stderr, "\t\tnets appearing in the increasing order of their slack.\n");
(void) fprintf(vis_stderr, "\t\tIf not set, the initial net order specified in the original\n");
(void) fprintf(vis_stderr, "\t\tcircuit\'s .net file is used. The file specified in -n option\n");
(void) fprintf(vis_stderr, "\t\tis used. This option is valid only if spfd_pdlo_timing is set.\n\n");
(void) fprintf(vis_stderr, "\tspfd_pdlo_remap_clb_array\n");
(void) fprintf(vis_stderr, "\t\tReduce the size of FPGA if necessary during\n");
(void) fprintf(vis_stderr, "\t\tlogic optimization.\n\n");
(void) fprintf(vis_stderr, "set options for VPR: Please see VPR's manual for more information.\n");
(void) fprintf(vis_stderr, " vpr_nodisp\n");
(void) fprintf(vis_stderr, " vpr_fix_pins\n");
(void) fprintf(vis_stderr, " vpr_nx\n");
(void) fprintf(vis_stderr, " vpr_ny\n");
(void) fprintf(vis_stderr, " vpr_fast\n");
(void) fprintf(vis_stderr, " vpr_init_t\n");
(void) fprintf(vis_stderr, " vpr_alpha_t \n");
(void) fprintf(vis_stderr, " vpr_exit_t\n");
(void) fprintf(vis_stderr, " vpr_inner_num\n");
(void) fprintf(vis_stderr, " vpr_seed\n");
(void) fprintf(vis_stderr, " vpr_place_cost_exp\n");
(void) fprintf(vis_stderr, " vpr_place_chan_width\n");
return 1; /* error exit */
#endif /* ifdef USE_VPR */
} /* End of CommandSpfdPlaceOptimize */
/**Function********************************************************************
Synopsis [Handle function for timeout.]
Description [This function is called when the time out occurs.]
SideEffects []
******************************************************************************/
static void
TimeOutHandle(void)
{
longjmp(timeOutEnv, 1);
}
/**Function********************************************************************
Synopsis [Checks whether the network has multiple valued signals.]
Description [Checks whether the network has multiple valued
signals. Returns 1 if true, else 0.]
SideEffects [None]
SeeAlso []
******************************************************************************/
static int
TestIsNetworkMultipleValued(Ntk_Network_t *network)
{
Ntk_Node_t *node;
lsGen gen;
Var_Variable_t *var;
int numValues;
Ntk_NetworkForEachNode(network,gen,node) {
var = Ntk_NodeReadVariable(node);
numValues = Var_VariableReadNumValues(var);
if (numValues > 2)
return 1;
}
return 0;
}
#ifndef USE_VPR
/**Function********************************************************************
Synopsis [Dummy function]
SideEffects [None]
******************************************************************************/
static int
SpfdSimultaneousPlacementAndLogicOpt(
Ntk_Network_t *network,
char *netFile,
char *archFile,
char *placeFile,
char *routeFile,
char *netOutFile,
int regionDepth)
{
return 0;
}
#endif