Event driven blackboard processing system that provides dynamic load balancing and shared data between knowledge source processors

• US 5,506,999 A
• Filed: 09/22/1994
• Issued: 04/09/1996
• Est. Priority Date: 01/22/1992
• Status: Expired due to Fees

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Boland, Arthur J., Skillman, Thomas L., Ling, Yong-Long C., Blair, Richard N., Pier, Richard M.
• Primary Examiner(s): GECKIL, MEHMET B
• Application Number:
  US08/310,931
• Time in Patent Office: 565 Days
• Field of Search: 395/800, 395/200, 395/53, 395/54, 395/84, 395/11, 395/650, 395/700
• US Class Current: 718/105
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

A blackboard parallel processing system for carrying out a general processing task using a plurality of parallel processors. In one application of the blackboard processing system, a workstation (102), which is part of an an automated workstation manufacturing system (AWMS), includes a blackboard control unit (BCU) (106) on which four separate functions are implemented in separate identical modules. The BCU includes a database module (34) having access to a global database, which is available to each of the plurality of parallel processors, referred to as knowledge source processors (KSPs) (40). A trigger module (46) includes trigger patterns that are compared to the data developed from messages transmitted by the KSPs to initiate specific tasks according to a predefined sequence. A scheduler module (42) responds to the trigger signals, by transmitting a signal to initiate each task, either by a specified KSP or by the KSP that is the least loaded with previously assigned processing task. A communication module (38) serves as an interface between knowledge source operating systems in each of the KSPs. Applications running in each KSP are initiated in response to the signals provided by the BCU, producing data and using data available to each of the KSPs on the global database.

Claims

1. A blackboard processing system, comprising:

a plurality of knowledge source processors that are configured for parallel processing of computational tasks, so that while one knowledge source processor carries out one computational task, another knowledge source processor carries out another computational task;

a blackboard control unit, physically separate and distinct from said plurality of knowledge source processors, coupled in communication with said plurality of knowledge source processors, said blackboard control unit including a plurality of functional hardware modules, each of said functional hardware modules including a central processing unit, an electronic memory and a communication interface, said plurality of functional hardware modules including;

database means, coupled in communication with the knowledge source processors, for storing and retrieving data received from the knowledge source processors;

communication means, coupled in communication with the knowledge source processors and to the database means, for conveying data to and from specific knowledge source processors and to and from the database means, and for transmitting instructions to the knowledge source processors;

trigger means, coupled in communication with the database means and responsive to data presented to and stored by the database means, for producing a trigger signal upon the occurrence of a predefined condition indicated by that data; and

scheduler means, coupled in communication with the knowledge source processors through the communication means and connected to the trigger means to receive the trigger signal produced by the trigger means, for transmitting the instructions through the communication means to the knowledge source processors, the instructions causing a selected knowledge source processor to carry out a specific computational task.

2. The blackboard processing system of claim 1, wherein the scheduler means are further operative to cause data required by the selected knowledge source processor for carrying out the specific computational task to be transmitted through the communication means to the selected knowledge source processor.

3. The blackboard processing system of claim 1, wherein the database means respond to requests for data received from the knowledge source processors through the communication means, and in response to the requests, retrieve data for transmission back to the knowledge source processors that made the requests.

4. The blackboard processing system of claim 1, wherein the functional hardware modules comprising the database means, the communication means, the trigger means, and the scheduler means are interchangeable.

5. The blackboard processing system of claim 1, wherein functions performed by any of the database means, the communication means, the trigger means, and the scheduler means are effected by a plurality of the functional hardware modules to accommodate higher levels of activity for such functions.

6. The blackboard processing system of claim 1, wherein the functional hardware modules are interconnected by a plurality of serial data links to facilitate high-speed data interchange between the functional hardware modules.

7. The blackboard processing system of claim 1, wherein the electronic memory of the functional hardware modules comprise a high-speed random access memory circuit.

8. The blackboard processing system of claim 1, wherein the electronic memory of each functional hardware module stores a plurality of machine instructions that determine whether the functional hardware module operates as the trigger means, the communication means, the database means, or the scheduler means.

9. The blackboard processing system of claim 1, wherein each knowledge source processor includes memory means for storing a knowledge source operating system, and wherein the knowledge source operating system interprets instructions received from the blackboard control unit so that those instructions can be run by the knowledge source processor and translates between a data format used by the knowledge source processor and a data format used by the blackboard control unit if said data formats are different from each other.

10. The blackboard processing system of claim 1, wherein the specific computational tasks that the knowledge source processors are instructed to carry out by the scheduler means each comprise a portion of an overall application that the blackboard processing system is running, and wherein the data used by the knowledge source processors in carrying out the specific computational tasks are stored by the database means so that such data are available to all of the knowledge source processors.

11. The blackboard processing system of claim 1, wherein the scheduler means at times assign a specific computational task to each knowledge source processor and at times select one of the knowledge source processors to carry out the specific computational task based on its computational capabilities and availability at the time of the selection.

12. A blackboard processing system for running an application that includes a plurality of computational processes, at least some of which can be completed in parallel, comprising:

(a) a plurality of parallel processors that carry out the computational processes included in the application; and

(b) blackboard control means, physically separate and distinct from the plurality of parallel processors, and coupled in communication with the plurality of parallel processors, said blackboard control means including a plurality of processor modules, each of said processor modules including a central processing unit, an electronic memory and a communication interface, said plurality of processor modules;

(i) providing high-speed data communication to and from the plurality of parallel processors;

(ii) storing, retrieving, and sharing data resulting from computational processes that have been completed by the plurality of parallel processors, to enable other computational processes to be completed by them;

(iii) scheduling the computational processes to run on selected parallel processors based on a capability of the selected parallel processors to carry out specific computational processes and based upon a relative computational load already imposed on the parallel processors, a parallel processor that is less heavily loaded being selected to carry out a specific computational process instead of a parallel processor that is more heavily loaded; and

(iv) detecting that a predefined event has occurred based on data supplied by at least one of the plurality of parallel processors that are indicative of such an occurrence, and upon detecting the occurrence of the predefined event, initiating running of one of the computational processes so that the plurality of computational processes are completed in response to the predefined event, the blackboard control means thus insuring that the computational processes included in the application are carried out efficiently by sharing the data and allocating the computational processes among the plurality of parallel processors.

13. The blackboard processing system of claim 12, wherein at least one of the parallel processors at times is selected to simultaneously carry out at least two of the computational processes.

14. The blackboard processing system of claim 12, wherein data required by a specific one of the parallel processors are requested from the blackboard control means, and in response, the blackboard control means retrieve such data and transfer the data to the specific one of the parallel processors that requested the data.

15. The blackboard processing system of claim 12, wherein the blackboard control means transfer data required for carrying out one of the computational processes to a parallel processor that is selected to run that computational process.

16. The blackboard processing system of claim 12, wherein each of said plurality of processor modules carries out a different set of machine instructions to perform a different function of the blackboard control means.

17. The blackboard processing system of claim 16, wherein a plurality of the processor modules are used to perform a single function of the blackboard control means to accommodate higher levels of processing activity required by said single function.

18. The blackboard processing system of claim 16, further comprising a plurality of serial data links that facilitate high-speed data communication between the processor modules.

19. The blackboard processing system of claim 16, wherein the memory circuit comprises a high-speed random access memory circuit for storing data.

20. The blackboard processing system of claim 16, wherein the processor modules are interchangeable.

21. The blackboard processing system of claim 12, wherein each parallel processor includes memory means for storing a knowledge source operating system used to interface the parallel processor to the blackboard control means.

22. The blackboard processing system of claim 21, wherein the memory means of each parallel processor also store a general operating system with which the knowledge source operating system interfaces.