Marc D Diamond

US Patent:

55176542, May 14, 1996

Filed:

May 26, 1992

Appl. No.:

7/888936

Inventors:

Jeffrey C. Kimbel - Forest Lake MN
Marc D. Diamond - Inver Grove Heights MN
Stephen E. Ross - Minneapolis MN
Charles L. Rennolet - St. Paul MN

Assignee:

FMC Corp. - Chicago IL

International Classification:

G06F 1518
G06F 1516

US Classification:

395800

Abstract:

The method and apparatus disclosed herein relates to parallel implementation of a combinatorial optimization in a multiprocessor network. The system operates as an intermediary between a root processor and a multiprocessor network. The system generates shadow nodes which are used to occupy idle capacity available within the multiprocessor network. Particularly, the shadow nodes are used to refine solutions for enumerative problems, search graph and the like while providing a near 100% utilization of a processor time in a multiprocessor network. The system provides a fully asynchronous and homogenous system design to enable the creation of locally ordered expansion queues.

US Patent:

55375936, Jul 16, 1996

Filed:

May 24, 1993

Appl. No.:

8/065505

Inventors:

Marc D. Diamond - Golden Valley MN
Jeffrey C. Kimbel - Forest Lake MN

Assignee:

FMC Corporation - Chicago IL

International Classification:

G06F 15163

US Classification:

395650

Abstract:

A method and apparatus for solving enumerative search, graph search or combinatorial optimization problems using parallel digital processors. Various nodes, representing decision points in the problem, are distributed among a plurality of digital processors. The nodes are expanded and bound values for the nodes are communicated among the processors. Non-productive solution parts are pruned to eliminate unnecessary expansion of the state space. Updated bound values are communicated in both directions along the search graph and a plurality of messages are developed to provide communication in a loosely coupled processor environment.