High speed path optimization co-processor
AssigneeFMC Corporation
InventorJohn M. Hansen
Life of this patent
Estimating the term…
Abstract
A data processor having a pipeline-parallel structure for rapidly solving optimization problems using relatively simple circuitry. A plurality of pipelines each have a circuit for adding a directional cost value to a directional sum value and the total value compared to an adjacent sum value to obtain an optimum value. The optimum result of each comparison in the pipelines is coupled to a processor control circuit. The process is repeated until an optimum path value is obtained.
Claims9
A data processor having a pipeline-parallel structure for rapid solving optimization problems for use with a plurality of sequentially numbered sources of directional cost values, a plurality of sources of directional sum values, and a source of center cell values, said processor comprising:
- a plurality of sequentially numbered pipeline stages, each of said pipeline stages having first, second and third input leads and first and second output leads, each of said pipeline stages having means for adding signals on said first and second input leads to produce a total signal and having means for comparing said total signal with a center cell signal on said third input lead, each of said pipeline stages having means for selecting a smaller value of signal from said total signal and said center cell signal and coupling said smaller signal to said first output lead of said pipeline stage, each of said pipeline stages having means for developing an exchange signal to indicate the result of said comparing of said total signal and said center cell signal, said exchange signal being coupled to said second output lead of said pipeline stage;
- means for coupling said first input lead of each of said sequentially numbered pipeline stages to a corresponding numbered one of said sources of directional cost values;
- means for coupling said second input lead of each of said sequentially numbered pipeline stages to one of said sources of directional sum values;
- means for coupling said third input lead of a first of said sequentially numbered pipeline stages to said source of center cell values;
- means for coupling said third input lead of each of the remainder of said sequentially numbered pipeline stages to said first output lead of an adjacent lower numbered one of said pipeline stages;
- control means for directing the flow of signals in said data processor, said control means being connected to each of said pipeline stages and to each of said sources of cost and sum values;
- and
- means for coupling said first output lead of a highest numbered pipeline stage to said source of center cell values, said exchange signals on said second output leads causing said control means to couple signals to said source of center cell values from said first output lead of said higher numbered pipeline stage.
A data processor having a pipeline-parallel structure for rapid solving optimization problems for use with a plurality of sequentially numbered sources of directional cost values, a plurality of sources of directional sum values, and a source of center cell values, said processor comprising:
- a plurality of sequentially numbered pipeline stages, each of said pipeline stages having first, second and third input leads and first and second output leads, each of said pipeline stages having means for adding signals on said first and second input leads to produce a total signal and having means for comparing said total signal with a center cell signal on said third input lead, each of said pipeline stages having means for selecting a larger value of signal from said total signal and said center cell signal and coupling said larger signal to said first output lead of said pipeline stage, each of said pipeline stages having means for developing an exchange signal to indicate the result of said comparing of said total signal and said center cell signal, said exchange signal being coupled to said second output lead of said pipeline stage;
- means for coupling said first input lead of each of said sequentially numbered pipeline stages to a corresponding numbered one of said sources of directional cost values;
- means for coupling said second input lead of each of said sequentially numbered pipeline stages to one of said sources of directional sum values;
- means for coupling said third input lead of a first of said sequentially numbered pipeline stages to said source of center cell values;
- means for coupling said third input lead of each of the remainder of said sequentially numbered pipeline stages to said first output lead of an adjacent lower numbered one of said pipeline stages;
- control means for directing the flow of signals in said data processor, said control means being connected to each of said pipeline stages and to each of said sources of cost and sum values;
- and
- means for coupling said first output lead of a highest numbered pipeline stage to said source of center cell values, said exchange signals on said second output leads causing said control means to couple signals to said source of center cell values from said first output lead of said highest numbered pipeline stage.
Dependencies are inferred from the claim text.