Procedure for optimizing mergeability and datapath widths of data flow graphs
AssigneeCadence Design Systems, Inc.
InventorsSanjeev Saluja, Anmol Mathur
Life of this patent
Estimating the term…
Abstract
Required precision and information content of datapath signals are used to define functionally safe transformations on data flow graphs. These transformations reduce widths of datapath operators and edges and enhance the mergeability of operators. An algorithm for optimally balancing data flow graph topology to further reduce the data path widths and further enhance mergeability is combined with the above in an iterative algorithm for optimizing DFGs.
Claims12
A method of optimizing a computer model of a digital circuit, said model including a data flow graph (DFG), comprising:
- (a) determining a minimum bitwidth required for at least a portion of a directed path of said DFG responsively to a width of an output port of at least one operator, where said portion is in a fan-out direction relative to said output port;
- (b) determining information content of inputs of an operator of said DFG;
- (c) determining information content of an output port of said operator responsively to said information content of said inputs;
- (d) reducing a bitwidth of a portion of said DFG responsively to said information content of inputs and said information content of the output port.
A method of optimizing a data flow graph representing a logical circuit design, comprising:
- (a) reducing bitwidths of data flow paths responsively to required precision of outputs of operators of said DFG;
- (b) reducing bitwidths of operators and outputs responsively to information content of inputs of said operators;
- (c) merging operators of said DFG responsively to said first and second reducing to generate definitions of clusters;
- (d) calculating information content upper bound for outputs of said clusters;
- reducing bitwidths of said DFG responsively to said step of calculating;
- and
- (e) repeating said reducing bitwidths of operators and outputs.
A computer readable medium encoding instructions which, when executed, cause a processor to perform a method of optimizing a computer model of a digital circuit, said model including a data flow graph (DFG), comprising:
- (a) determining a minimum bitwidth required for at least a portion of a directed path of said DFG responsively to a width of an output port of at least one operator, where said portion is in a fan-out direction relative to said output port;
- (b) determining information content of inputs of an operator of said DFG;
- (c) determining information content of an output port of said operator responsively to said information content of said inputs;
- (d) reducing a bitwidth of a portion of said DFG responsively to said information content of inputs and said information content of the output port.
A computer readable medium encoding instructions which, when executed, cause a processor to perform a method of optimizing a data flow graph representing a logical circuit design, comprising:
- (a) reducing bitwidths of data flow paths responsively to required precision of outputs of operators of said DFG;
- (b) reducing bitwidths of operators and outputs responsively to information content of inputs of said operators;
- (c) merging operators of said DFG responsively to said first and second reducing to generate definitions of clusters;
- (d) calculating information content upper bound for outputs of said clusters;
- (e) reducing bitwidths of said DFG responsively to said calculating;
- and
- (f) repeating said second reducing.
Dependencies are inferred from the claim text.