13.4 The Control Strategies for Blackboards

13.4 The Control Strategies for Blackboards

There are several layers of control in a blackboard implementation where the knowledge sources may be activated concurrently. At the lowest layer their synchronization schemes must protect the integrity of the blackboard. The blackboard is a critical section because it is a shared, modifiable resource. In a parallel environment the knowledge source's read and write access must be coordinated and synchronized. This coordination and synchronization can involve file locking, semaphores, mutexes , and so on. This layer of control is not directly involved in the solution the knowledge sources are working toward. This is a utility layer of control and should be independent of the problem to be solved by the blackboard. In our architectural approach, this layer of control will be implemented by interface classes like the mutex, and semaphore classes that we introduced in Chapter 11. Recall that the functionality contained in these classes is independent of the application they are used in. For concurrency implementations of blackboards, this layer selects one or more of the four types of parallel access that the knowledge source algorithms or heuristics will have to the physical implementation of the blackboard. That is, the users of the blackboard can be EREW, CREW, ERCW, or CRCW. This access determines how the synchronization primitives will be used. Table 13-1 contains the descriptions of the four types of parallel access that a model can use.

Table 13-1. Four Types of Parallel Access Used by a Model

PRAM models	Description
EREW	Exclusive Read Exclusive Write
CREW	Concurrent Read Exclusive Write
ERCW	Exclusive Read Concurrent Write
CRCW	Concurrent Read Concurrent Write

The segmentation of the blackboard into parts will determine which of the types of concurrency in Table 13-1 are appropriate. The most flexible CRCW can be achieved depending on the structure of the blackboard. For instance, if 16 knowledge sources are involved in a collaborative effort and each knowledge source accesses its own segment of the blackboard, then these knowledge sources can concurrently read and write the blackboard without data race problems.

The next layer of control involves the selection of which knowledge sources to involve in the search for the solution and which aspects of the problem to focus on. This is a focus-of-attention layer. This layer of control decides to focus on a certain area of the problem and selects knowledge sources accordingly . One of the major issues to tackle in any kind of problem solving is where to start and what kind of information is needed to solve the problem. The focus/attention layer evaluates the initial conditions of the problem and then controls which knowledge sources to use and where they will start. The available knowledge sources will be known to the blackboard and typically the knowledge source will accept messages or parameters that dictate how it should proceed or where in the solution space it should begin the search. For parallel implementations, this layer will determine the basic model of parallelism (distribution of the problem solvers). Usually for blackboards this is the Multiple Programs Multiple Data (MPMD, a.k.a. MIMD) model because each knowledge source/problem solver has its own area of speciality. However, the nature of the problem might warrant the popular Single Program Multiple Data (SPMD) model. If this model is used, the control layer will spawn N number of the same knowledge source but pass different parameters to each.

The next layer of control involves determining what to do with the solution or partial solutions written to the blackboard. This layer of control will determine whether the knowledge sources can stop work or whether the solution generated is acceptable, unacceptable, partially acceptable, and so on. This layer of control has complete visibility of the blackboard and all the partial or tentative solutions. It guides the overall problem-solving strategies of the collective. As with the layout of the blackboard and the structure of the knowledge sources, the blackboard model suggests the existence of a control component but does not specify how it should be structured. Sometimes the control component is part of the blackboard. Sometimes the control component is implemented by the knowledge sources. In some cases the control component is implemented by modules external to the blackboard. The control component can also be implemented by any combination of these. The knowledge sources collectively search for a solution to some problem. We want to emphasize a solution because many problems have more than one solution. Some solutions may be deeper in the search space than others, some may cost more to find than others, and some may be deemed not good enough. The control component helps to manage the collective search strategies of the knowledge sources and monitors the tentative or partial solutions to make sure that the knowledge sources are not pursuing an impractical search strategy. The control component looks out for any infinite loops , blind alleys, or recursive regression. Furthermore, the control component is involved in selecting the best or the most appropriate knowledge sources for the problem. As the knowledge sources make progress toward a solution, the control component may relieve some knowledge sources while assigning others. The control strategy will be closely related to the search strategies used by the knowledge sources. It is important to remember that the knowledge sources may each use different search strategies and problem-solving techniques. Although they work with a common blackboard, the knowledge sources or problem solvers are essentially autonomous and self-contained. Therefore, this layer of control has a two-way communication with the knowledge sources. Figure 13-4 shows possible control configurations and their layers in a blackboard architecture.

Figure 13-4. Control configurations and their layers in the blackboard architecture.

Note the configuration in Figure 13-4 contains the control within the blackboard as opposed to a separate module or knowledge source. In this configuration, the control is designed as part of the blackboard class. Since a two-way communication is needed in Layer 2 and Layer 3, it is convenient to have the blackboard spawn the processes or threads that will contain the knowledge sources. If the blackboard spawns the processes or threads it will have easy access to the thread ids or process ids. This will allow the blackboard to easily broadcast messages to the knowledge sources, and perform process and thread management. When the blackboard needs to terminate a knowledge source for some reason, access to the thread id or process id will make this easy. Notice if Figure 13-4 that one of the options is to have the control external to the blackboard and the knowledge sources. If this configuration is used, thread ids and process ids must be communicated explicitly to the control modules.