Effects of Parallelism on Blackboard System Scheduling

1 Introduction

From the beginning the blackboard paradigm has been developed with parallelism in mind [Lesser et al., 1975]. The idea of independent Knowledge Sources (KSs) that communicate only through a shared blackboard is a model that inherently enc.ourages parallel execution. Many researchers have looked at making blackboard systems execute in parallel [Corkill, 1989, Fennell and Lesser, 1977, Rice et al., 1989].

In particular the execution of multiple Knowledge Source Instantiations (KSI) in parallel (known as knowl­ edge source parallelism) is discussed in several places in the literature. The Advanced Architectures Project at Stanford University [Rice, 1989, Rice et al., 1989] has investigated blackboard parallelism at several lev­ els of granUlarity. Their Cage architecture takes the ex­ isting AGE blackboard architecture and extends it to execute concurrently at several granularities, including knowledge source parallelism [Nii et al., 1989]. Another project that investigated knowledge source parallelism is the work by [Fennell and Lesser, 1977] to study the ef­ fects of parallelism on the Hearsay II speech understand­ ing system [Erman et al., 1980]. One major contribut~on of that project is a detailed study of blackboard locking mechanisms. An alternative method for enforcing data consistency is the use of transactions as described by [Ensor and Gabbe, 1985].

*The authors are listed in alphabetical order. This work was partly supported by the Office of Naval Research under a University Research Initiative grant number N00014-86-K0764, NSF contract CDA 8922572, ONR contract N0001489-J-1877, and a gift from Texas Instruments.

One distinguishing feature of these studies of paral­ lelism in blackboard systems is that they used simulated parallelism. Concurrently executing processes and in­ terprocess communication were simulated using complex models of parallel environments. This was the case pri­ marily because of the primitive nature of existing parallel hardware and the lack of sophisticated software develop­ ment environments. Only recently have hardware and software capabilities come together to allow the actual implementation of parallel blackboard systems [Bisiani and Forin, 1989]. Useful parallel programming environ­ ments now exist, including implementations of Lisp. The work described in this paper was done on a Sequent mul­ tiprocessor using Top Level Common ~isp 1 (a version. of Lisp that supports concurrent processmg) and a spectal version of GBB 2.0 2 that was modified to allow parallel read access to the blackboard and to allow locking only part of the blackboard on write accesses.

Along with our actual use of parallel h:Udware, a m~­ jor difference between our work and prev10us research lS our focus on how control knowledge needs to change in a parallel environment. Previous work was m~re interest.ed in investigating specific parallel models, while we are m­ terested in what new control knowledge is useful. As we show, it is not enough to just add locks to a sequential blackboard system and execute the top n KSis as rated by sequential control heuristics on n parallel processors. New heuristics need to be added that are sensitive to the requirements for effective parallel execution. Ear­ lier work on Partial Global Planning[Durfee and Lesser, 1987] showed that constructing schedules using a high­ level view of the solution space (derived by distributed agents from goal relationships) improved the utilization of distributed processors. This leads to the intuition that using goal relationships in scheduling may be helpful in a single agent, parallel-processing situation.

1 Top Level Common Lisp is a trademark of Top Level,

Inc.

2 GBB 2.0 is a trademark of Blackboard Technologies, Inc.

The next section discusses the details of our parallel architecture. Section 2.3 describes the new kinds of con­ trol knowledge that are useful in a parallel environment and identifies the kinds of data that are required to im­ plement those new kinds of knowledge. Section 3 briefly introduces the Distributed Vehicle Monitoring Testbed, the application that motivates this work, and describes the new heuristics that were added for parallelism. Sec­ tion 3.1 presents and discusses the results of the exper­ iments we pedormed on the system, including the per­ formance of the implementation and the effect of the added control heuristics. The final section summarizes the work and describes future research directions.

2 Architecture

The architecture is a straightforward extension to the BB1-strle uniprocessor blackboard architecture de­ scribed in lDecker et al., 1989, Decker et al., 1990]. In that architecture the processor takes the currently top rated KSI from the executable agenda. It executes the KSI action, which creates and modifies blackboard hy­ potheses. These hypotheses in turn stimulate goals, which trigger new KSs for execution. A scheduler or­ ders the executable agenda and the loop begins again. This low-level control loop is highly parameterized; the parameters are set by control knowledge sources.

In our parallel system, several processors execute the low-level control loop concurrently. All of the hypothe­ ses, goals, agendas, KSs, and control parameters are posted on shared global domain and control blackboards that are accessible to each processor. This basic architec­ ture is very similar to the Cage simulations with KS-level parallelism and asynchronous control [Rice et al., 1989].

Besides executing the low-level control loop in paral­ lel, three major modifications to the existing system are made to allow effective use of parallelism. Locking mech­ anisms are provided to prevent conflicting blackboard accesses; the control knowledge sources are run sequen­ tially, but the actions of many control KSs are broken up and run in parallel; and new classes of control knowledge are identified and implemented. The next three sections describe each of these modifications in more detail.

2.1 Blackboard Locking

Various schemes for blackboard locking appear in the lit­ erature. The most detailed is that described by Fennell and Lesser, who describe a method for locking black­ boards that assures data integrity [Fennell and Lesser, 1977].

We have found that a much simpler locking mechanism is sufficient for our system. The only locking mechanism we provide is atomic read/write locks for blackboard writes. This mechanism is invoked when a blackboard write is done. It executes a read to see if the object to be written already exists. If it does, then the new object is merged with the existing object, otherwise the new ob­ ject is written. Knowledge sources are designed so that they create hypotheses one at a time. Since only one lock is ever acquired at a time, deadlock is impossible. The operating system scheduler prevents starvation.

This simple mechanism is sufficient because the system can build several, possibly conflicting, partial solutions to a problem [Lesser and Corkill, 1981]. It does not re­ quire exactly one consistent working solution, so it does not return to and delete objects that cause inconsisten­ cies. Because hypotheses are never deleted, the structure of the hypotheses on the blackboard never changes; only the beliefs in existing hypotheses may change. Changes in belief can be recognized and propagated by a separate knowledge source. If new hypotheses are created that would produce different results, then their creation will trigger new knowledge source instantiations that may be scheduled. We believe that other systems that share this characteristic will find that simple locking mechanisms are adequate. For example, the AGORA system uses "write-once" memory management where a blackboard element cannot be updated in place, but rather a copy is made [Bisiani and Forin, 1989].

Several types of locks were used in the implementa­ tion. Each blackboard level (space) is divided into a set of buclceu. A blackboard data unit is stored in a small number of buckets based on its characteristics. Each bucket is given its own lock. Thus two KSis can always write to different blackboard levels in parallel but one might block if they both write to the same bucket. Locks also control access to the KSI agenda and other inter­ nal data structures associated with the low-level control loop.

2.2 Executing the Control Knowledge Sources

Control knowledge sources change parameters that allow control over mechanisms such as filtering hypotheses or goals, merging hypotheses or goals, mapping from hy­ potheses to goals or goals to KSs, and the agenda rating mechanism. Control knowledge triggers on events on both the domain and control blackboards. In our cur­ rent system control knowledge sources are run sequen­ tially (meaning only one control KSI is executing at a time), however the actions of many of the control KSis divide up the work and execute it in parallel on several processors. In the future we would like to investigate executing the control knowledge in parallel as well.

2.3 New Classes of Control Knowledge for Parallelism

Normal control knowledge (as used in a sequential en­ vironment) rates KSis based on knowledge such as the belief of their input data, the potential belief in the out­ put data, the significance of the output data given the current system goals, and their efficiency or reliability. In addition to these kinds of control knowledge there are several general classes of control knowledge that can be added to more effectively execute I(Ss in parallel. These general classes of control knowledge include:

Access Collisions: To avoid excessive conflicts for blackboard access, do not schedule two KSis to work in the same part of the search space at the same time. For example, if KSI A and KSI B both write to a particular level of the blackboard, then they should not be scheduled for execution at the same time, because one of them will have to wait for the other to relinquish blackboard locks.

Task Ordering: Tasks may have absolute, unchange­ able orderings (meaning they cannot be scheduled to execute in parallel at all), or there may be in­ terdependence among tasks that lead to ordering preferences (one task provides data that will signif­ icantly affect the speed or quality of the result of another task.) For example, Task A may produce a result that makes the performance of Task B much faster. If so, Task A should be scheduled before Task B.

Task Bottlenecking: Performing certain tasks earlier in problem-solving may reduce future sequential bottlenecks. In general it is preferable to execute tasks that will allow more parallel options later. For example, there may be an absolute task order­ ing that requires that Task A be performed before Tasks B, C, and D, which can then be performed in parallel. Task A should be performed as soon as possible, because it will allow more parallelism later.

Task Invalidation: This is based on the "Competition Principle" in Hearsay-11 [Hayes-Roth and Lesser, 1977]: ·the results of some tasks may completely re­ move the need to execute other tasks.-Thus, when currently executing tasks are taken into account (as­ sumed to complete), some pending tasks will be ob­ viated. For example, Task A and Task B may per­ form the same operation, and produce the same re­ sult, in different ways. If Task A has been scheduled, then Task B should not be immediately scheduled, because it will be obviated if Task A completes suc­ cessfully.

To take these general classes of control knowledge into account the system requires particular kinds of knowl­ edge about the domain KSis. In particular, avoid­ ing acceu colli6ion.t requires knowledge about the in­ put/output characteristics of a KSI (i.e., what parts of the blackboard it accesses and modifies.) Ta6k ordering requires knowledge about task interactions. Often this knowledge is best captured through relationships among the goals of particular tasks. A voiding ta6k bottleneck­ ing requires knowledge about the probable outcomes of tasks, again often expressed through goal relationships. Ta6k invalidation uses knowledge about supergoal and subgoal relationships to understand the effect of KSI ex­ ecutions on ·other KSis' goals.

There are four general categories of goal relationships that can be used (via KSI rating heuristic functions) to schedule domain KSs [Decker and Lesser, 1990]:

Domain Relations: This set of relations is generic in that they apply to multiple domains and domain dependent in that they can be evaluated only with respect to a particular domain, e.g., inhibits, can­ cels, constrains, predicts, causes, enables, and su­ pergoalfsubgoal (from which many useful graph re­ lations can be computed, as shown below). These relations provide ta6k ordering constraints, represented by temporal relations on the goals (see be­ low).

Graph Relations: Some generic goal relations can be derived from the supergoalfsubgoal graphical struc­ ture of goals and subgoals, e.g., overlaps, necessary, sufficient, extends, subsumes, competes. The com­ pete6 relation is used to produce ta6k invalidation constraints. These relations also produce ta6k bot­ tlenecking information.

Temporal Relations: From Allen [Allen, 1984], these include before, equal, meets, overlaps, during, starts, finishes, and their inverses. They can arise from domain relations, or depend on the scheduled timing of goals - their start and finish times, esti­ mates of these, and real and estimated durations.

Non-computational Resource Constraints: A final type of relation is the use of physical, non­ computational resources. Two tasks that both use a single exclusive resource cannot execute in paral­ lel. For example, if two tasks require that a single sensor be aimed or tuned differently, they cannot execute in parallel.

For example, examine the goal structure in Figure 1 (abstracted from an actual domain goal relation graph). Assume that task TaskF is currently executing on a pro­ cessor. The arcs in the graph represent the goal/6v.bgoal domain relation on the goals 3 . From only this one do­ main relation, we can tell for example that F and G are nece66ary for D, D is nece66ary for B and C, and B is 6v.fficient for A. F and G eztend' one another, as doD and H. Goal B compete6 with C.

Thus a ta6k invalidation heuristic might avoid schedul­ ing a task that achieves goal B in parallel with one that achieves goal C. In the given situation (with TaskF ex­ ecuting, and G and H available for processing), a ta6k bottleneck heuristic might prefer to schedule a task to satisfy G, which will allow work on goals D and H in the future 5 , over a task to satisfy H, which would allow only work on goal G in the future. Of course, tasks may accomplish multiple goals, a fact that is simplified in this example. A ttuk ordering heuristic would not find any temporal relations in this example; they are induced by domain relations where goals comtrain or predict others.

3 While it looks similar, this is different from a typical data dependency diagram both in granularity and in the fact that it would be constructed dynamically during problem solving. At the present time we constructed one by hand to develop possible parallel heuristics for our domain.

*Goal 1 eztend· goal 2 if there exists a supergoal, goal 3, such that goals 1 and 2 are in the same AND conjunct.

6 Goal D would become open, since its necessary subgoals F and G would be completed; goal H already was open.

3 Experiments

Experiments were run on the Distributed Vehicle Mon­ itoring Testbed (DVMT)[Lesser and Corkill, 1983], a knowledge-based signal interpretation system. The in­ put to the DVMT is acoustic signals generated by mov­ ing vehicles and detected by acoustic sensors. The goal of the DVMT is to identify, locate and track patterns of vehicles moving through a two-dimensional space. The four main blackboard levels are: &ignal (for processing of signal data), group (for collections of signals attributed to a single vehicle), vehicle (for collections of groups that correspond to a single vehicle), and pattern (for collec­ tions of vehicles acting in a coordinated manner).

For our purposes, DVMT domain KSs can be divided into two main classes: synthesis and track extension. Synthesis KSs combine one or more related hypotheses at one level of the blackboard into a new hypothesis at the next higher level. Track extension KSs output track hypotheses, where a track is a list of sequential pieces of time-location data that identify the movements of a vehicle. The control KSs of the system can also be di­ vided into two main classes: those that implement a goal­ directed strategy and those that extend that strategy for parallel execution.

For these experiments, the DVMT processes the input data in three distinct phases. In the first phase (find ini­ tial vehicle&), an initial set of control KSs execute, con­ figuring the DVMT to perform a thorough analysis of all data at time 1. The purpose of this phase is to roughly identify the type and position of all vehicles that will be tracked in the experiment 6 · The data file we used con­ tained 12 vehicles, and we defined four possible vehicle types with some signals and groups of signals shared by multiple vehicles. After these control KSs execute, and the domain KSs process all time 1 data, more control KSs are triggered and execute, configuring the DVMT for the second phase of processing. In the second phase ( approzimate &hort track&), the DYMT pe~orm~ qui~k, approximate processing to determme the likely Identity and patterns of the vehicles being tracked. This phase ends when control KSs recognize that the DVMT has es­ tablished a pattern (or explanation) for all the vehicles, though the patterns may be uncertain. For these exper­ iments, we defined a short track to contain at least four time-location data points-thus, this phase ended after processing the time 4 data. Again, control KSs assign new values to system parameters,. and the third phase (perform pattern-directed proceuing) commences. The DVMT devotes most of its processing in this phase to tracking vehicles involved in primary patterns, while per­ forming cursory processing on vehicles involved in secondary patterns. This phase continues until all data in the input file has been processed. In these experiments, we included data until time 9.

8 We have restricted these experiments such that every ve­ hicle appears in the first set of acoustic samples, in order to simplify processing.

3.1 Examining the Basic Parallel Architecture

The first set of experiments involved ~ollecting statis­ tics on the basic parallel architecture without any added heuristics to take advantage of the parallelism. These experiments demonstrate that the locking system works, that the basic architecture provides for a good utiliza­ tion of processors, and that the domain and our problem­ solving method provide inherent parallelism.

Data for runs of the environment on 1 processor with no special parallel heuristics are summarized in Table 1. This table shows the time the single processor uses in each phase (and between phases) and the percent of the total time spent in each phase (and between phases) . This data is used in comparisons to the other experi­ ments described later. In this and all later experiments, data was collected with the locking and metering mecha­ nisms enabled. The locking mechanism itself had almost no overhead and as much of the metering as possible is , . done on a separate processor, completely outside of the processors being used for the experiment. The data col­ lected by the metering processor did not involve locking any of the target processors. All of the experiments were conducted on a 16 processor Sequent Symmetry, and all of the experiments used less than 16 available processors (so no tasks were swapped ofF a processor).

Table 2 shows the speedup resulting from 5 processors and no parallel heuristics. Phase 1 parallelism arises mostly from being able to process all the data from the sensors in parallel. The tasks in phases 1 and 2 all must be executed, which also causes a high degree of inherent parallelism.

Centralizing the meta-controller that is implemented by control KSs proved not to be a bottleneck in pro­ cessing; when not changing phases the meta-controller is almost dormant (simply checking for the end of a phase), and most of the work involved in changing ph~es (setting up new hypothesis and goal filters and runDlDg the hypotheses through them) is done in parallel. By running the low-level control loop (hyp to goal to KS mapping) in parallel we avoided the control bott!eneck observed by Rice et al. in their first Cage expenment, where a set of KSs was executed synchronously by the controller [Rice et al., 1989]. The only time that the system ever has to synchronize is at the beginning of a phase change, as the agenda from the last phase is empty and that of the next phase is still being generated. We have already begun work to eliminate this bottleneck as well, using a channelized architecture th~t gives us the ability to have different pieces of data at difFerent phases of processing simultaneously.

3.2 Examining the Parallel Heuristics

By simply allowing KSis to run in parallel, we achieved a significant improvement in the DVMT performance. However it is clear from the discussion in Section 2.3 that we 1 should be able to do better than just taking the top (single processor) rated KSI ofF of the agenda.

Four new heuristics were added to incorporate knowl­ edge about how parallelism affects scheduling. The BB1-style controller [Hayes-Roth, 1985] rates each KSI against each heuristic of each active focus. The archi­ tecture supports two types of heuristics - numeric and pass/fail. Numeric heuristics are summed to produce a rating; pass/fail heuristics must pass a KSI or it will not be executed. Either type of heuristic can also de­ cide not to rate a KSI - the effect is of a rating of 0 or 'pass' but it is recorded differently. All the previous non-parallel domain heuristics were numeric but some of the new parallel heuristics are pass/fail.

1. PD.66 Non-obviated Outpuu. Schedule KSis that will not produce output that will be obviated if the cur­ rently executing KSis complete successfully. This heuristic implements the taiJic invalidation criteria described in Section 2.3. The usefulness of this heuristic is tied to the success rate of the KSis in question - if the KSI currently executing is likely to finish successfully, then the heuristic will be likely to avoid duplicate work. This is a pass/fail heuris­ tic - if there are no tasks available that will not be obviated by existing tasks, then the processor will wait. This heuristic is not needed in the single processor case because when a KSI completes its ac­ tion, all KSis that it obviates are removed from the agenda before the next KSI is chosen.
2. PD.66 Primary PatteNU. This heuristic, which was a numeric rating heuristic in the single-processor sys­ tem, was changed to a pass/fail heuristic. It is an example of a ta61c ordering heuristic as described in Section 2.3. An implicit assumption of this heuristic is that KSs are not interruptible; so, when low pri­ ority KSis are started, later arriving higher priority KSis may not get a processor. When running an existing blackboard system in parallel, one should carefully examine the existing control heuristics to see if they will have the desired effect with mul­ tiple processors. While a high rating is sufficient in a single processor system to indicate that the KSs involved in a task are important to execute, in the multiprocessor case a decision must be made as to whether a processor should execute a KSI from a useful, but less important, task or wait idle for known important future tasks.
3. Prefer Outpuu on Different Region/J. Schedule KSis that do not access the same blackboard regions as the currently executing KSis. This heuristic imple­ ments the general acce/JIJ collillion control knowledge described in Section 2.3. In our case, only black­ board write operations need to be locked. This heuristic will be more applicable in systems such as those described by [Fennell and Lesser, 1977] that do more elaborate locking. This is a numeric preference heuristic. Obviously this heuristic is not needed in the single processor case because only one KSI is being executed, so there cannot be any blackboard access collisions.
4. Prefer Many Output Hypll. Schedule KSis that ex­ pect to produce many output hyps before those that expect to produce fewer output hyps. This heuris­ tic implements the tad: bottleneck avoidance class of heuristics described above. By preferring to produce many outputs, more possible tasks may be enabled in the future. This is a weak numeric preference heuristic. This heuristic is not needed in the sin­ gle processor case (in the DVMT domain) because the single processor will still have to execute all of the (non-obviated) KSis, no matter how long the agenda is. The purpose of this heuristic is merely to get the queue to a long length quickly, improving multiple processor performance.

Table 3 is a comparison of the system with the four heuristics and 5 processors with the 1 processor system and the 5 processor system. We did not get as much speedup over the experiment without parallel heuristics as we had hoped. A primary reason for this is that the parallel version without heuristics was developed to run as fast and as efficiently as possible with 1 or more pro­ cessors; we did not handicap it in any way. Our pa­ rameterized low-level control loop allows very few KSis through that should not be executed (i.e., very little search). This hampers the heuristics especially in phases 1 and 2, which have very tight and precise control plans.

For example, the task obviation heuristic finds very few tasks to obviate. This is because we try to iden­ tify and filter out or merge hypotheses and goals that might create redundant tasks as early as possible (be­ fore they trigger KSs to form KSis). However, this may not always be the best course to take - even our own system is being expanded to include multiple methods of achieving the same result by trading off some of the characteristics (such as precision and certainty) for time [Decker et al., 1990]. This may result in more potentially obviatable tasks on the agenda. We test this hypothesis in Section 3.2.1.

The access collision heuristic is also relatively weak. This is because, as we have previously stated, KSis sel­ dom block on writing to the same area of a blackboard level, and may read in parallel. Access collision avoid­ ance may be more important in systems that must lock objects for a long time to modify them. We tested this hypothesis in Section 3.2.2. Another problem stems from the prefer many output hyp6 heuristic; the DVMT tends to already work this way as a side effect of the domain heuristics, therefore the heuristic will not show an ap­ preciable improvement when present.

As stated previously, the agendas in phases 1 and 2 were tightly regulated - the execution of a KSI on the agenda was necessary for overall problem solving progress. KSis were not likely to be obviated by other KSis, and most KSis were involved in "good" work. However, this was not the case in phase 3. KSis were created whose output would often be subsumed by the output of another KSI if this other KSI were given an opportunity to run (the first KSI is a candidate for ob­ viation), and a fair number of secondary pattern KSis existed on the agenda at any point in time. Given these characteristics of the agenda in phase 3, 21.3% speedup over the 5 processor system to 4.8 times speedup over 1 processor was achieved. The parallel heuristics allowed processors to make intelligent decisions regarding the next KSI to execute. As a result of the parallel heuris­ tics, more KSis were obviated, and processors often de­ layed executing the next KSI if none of the KSis on the agenda appeared particularly appealing. It is also im­ portant to note that utilization was down somewhat in phase 3 because of the parallel heuristics, but the overall end-to-end processing time was reduced.

3.2.1 Testing the Task Obviation Heuristic

In order to test the tuk obviation parallel heuristic, we modified the basic parallel system by disabling the KSI­ merging feature. This results in many KSis, triggered by different data but intending to satis7 identical or simi­ lar goals, being placed on the agenda . The scenario was run once with five processors without any parallel heuris­ tics, and then again with the addition of the single task obviation heuristic. The results are shown in Table 4. Speedup was achieved particularly in phase two, when the addition of the task obviation heuristic caused a suf­ ficient number of KSis to be obviated, because KSis were executed in a data-directed manner and thus tended to obviate others upon completion.

3.2.2 Testing the .Access Collision Heuristic

In order to test the acceu colli6ion parallel heuris­ tic, we configured the DVMT to allow higher potential contention for system locks, without otherwise handi­ capping the system. Specifically, we modified the ba­ sic parallel system by disabling the KSI-merging feature and by artificially lengthening the time processors spend in the blackboard bucket locks. The first modification forces the creation of a separate KSI for each output goal (rather than merging similar goals). Since KSis that pedorm essentially the same activities tend to get rated approximately the same, a processor will select a KSI for execution that will create results that one or more other KSis running at the same time might pro­ duce. The effect of not allowing similar KSis to merge will produce a high amount of contention for blackboard regions, because similar KSis will be executing at the same time. The second modification simulates a sys­ tem that requires a larger context for KSI execution - one that keeps more of the blackboard locked for longer times. The larger the context, the higher the probability of contention. The scenario was run once without any parallel heuristics, and then again with the addition of the single access collision heuristic. Both runs were with five processors.

Adding the heuristic to avoid regions that other pro­ cessors are utilizing resulted in a significantly decreased amount of time spent in locks. A processor in the run without the access collision heuristic spent an average of 18.4% of its time in locks, while the addition of the access collision heuristic reduced this time to 11.0%.

1 A similar effect might have been achieved by activating multiple approximate processing methods, in addition to the normal precise methods, for each goal.

4 Conclusions

We investigated the effects of parallelism on blackboard scheduling. We have shown that we are able to get a speed-up for the DVMT application. We also showed that at least some of the speed-up was produced by our new heuristics that take parallel knowledge into account. It is our hypothesis that as the amount of search and interaction among search paths increases the heuristics will become more important. We are working to test this hypothesis.

As mentioned briefly in Section 3.1, we are currently investigating a channelized architecture that allows dif­ ferent vehicles to be in different phases of problem­ solving simultaneously. That is, data for different ve­ hicles can be processed using different filters, rated us­ ing different heuristics, and even use different approx­ imate processing problem-solving methods all concur­ rently. We believe this has the potential to significantly increase parallelism, both because it removes the phase­ changing bottleneck and because it clearly and simply divides up the work for parallel execution.

Acknowledgments

The authors would like to thank Kevin Q. Gallagher for his work in creating a shared memory parallel processing version of GBB 2.0.