A Variable Supply Model for Distributing Deductions

1. Tasks

Each task has a globally unique name. Attached pieces of information are:

1. Task Description: (PROP-SET 8-SET AU]), where PROP-SET is the set of propositions to be proved, 8-SET is the set of bindings obtained so far, and ALL? is a boolean variable that means all positive results must be found (if true) or only one positive result must be found (if false) 8 .
2. Parent Task
3. Pending Subtasks
4. Results: This is the set of results received so far for this task.

8 1n the current implementation. ALL? is always true.

1. Grabbed Timestamp: This is the timestamp 9 at which the task was grabbed. This can be revised if a future "grab" request for the same task "wins" out over a previous "grab" request. In a comparison between two "grab" requests. the one with the lower timestamp "wins".

2. Messages

Each message is Message-Typti,Arguments). required: described here with the syntax The following four message types are

1. New(Task-Name Task-Description): This is the message used to make the "Task is available" broadcast mentioned in section IV. When a processor receives a new message, the processor sets up the appropriate book-keeping information for the task name and puts the task name in the potential work set.
2. Grabbed(Task-Name Timestamp): This is the message used to make the "Task is grabbed" announcement mentioned in section IV. When a processor selects a certain task as the next current task for itself, it broadcasts a grabbed message for that task. When a grabbed message is received for a task, it is removed from the potential work set of the processor where the message is received and the book-keeping information for the task is revised (if required). If the task for which the grabbed message is received is the current task or even if the task is awaiting completion of its subtasks, then it will have to be aborted if the timestamp in the new grabbed message is lower than the previous timestamp for the task name. Aborting a task also means aborting any pending subtasks for the task. 1\ remote task is aborted by sending a kill message as explained below.
3. Kiii(Task-Name): A kill message is sent to abort tasks remotely. When a kill message is received. the task name is removed from the potential work set. In case the task in question is the current task, it is aborted and another current task is chosen. Also, if the task is awaiting completion of some of its subtasks, the subtasks are recursively aborted.
4. Done(Task-Name Binding-List): This is sent when the answer for a remotely originated task is obtained. When a done message is received. the result is reported to the parent of the task in question. The result is added to the results already obtained for the parent task name. If there are no pending subtasks for the parent task name, then the combined result for the parent task is reported to the processor that originated the parent task. 10 Again, a done message may have to be used if the originator of the parent task was a remote processor. The entire computation is

9 A timestamp is composed of the time in its higher order bits and a fixed number of bits for a unique processor number in iLc; lower order bits. A timestamp with a lower (greater) time than another timestamp is always lower (greater) than the other. When the times are equal. the timestamp with the lower numbered processor is lower.

10 For the case in which a single answer is required for the top-level deduction. a positive answer can be sent to the processor that originated the top-level deduction and the rest of the computation can be terminated. This is not done in the current implementation. however.

complete when all needed results (one or all) for the top­ level task are reported.

3. Heuristics

Several heuristics, as described below, are used to reduce computation and communication.

When it is time for a processor to select a new current task out of the potential work set, locally generated tasks are preferred: this saves on sending a done message for that task when the task is completed.

Backward-chaining within a processor is done in a depth-first fashion. This reduces thT search (compared to breadth-first) if only one positive result is desired. 1

To reduce the number of grabs for the same task. the following heuristic is used. Grabs by processors are given some arbitrary but pre-specified priority order. By watching messages on the broadcast network, processors get hints about the status of other processors. For example, if a processor sends out a grabbed message, other processors know that the processor is busy. When a new task is made available. a processor will defer grabbing to a higher-priority processor if both are free.

When deciding which tasks to move to the potential work set, the most costly is picked. Also. when deciding which task to grab out of the potential work set. the most costly is chosen. This is done so that a free processor grabs the most costly task first out of the surplus tasks available from all the processors. The effect is that, in general, processors tend to remain busy longer between grabs and this reduces the message traffic.

If no information is available about the cost of deductions. the least one can go by is that deductions higher up in the deduction tree are. on the average, more costly. Also, if the delays are not very high, all processors can be heuristically assumed to be at the same level in the tree. Therefore, the order of announcement of new tasks on the broadcast network can be heuristically assumed to be in the more costly to less costly order.

B. Domain of Application of ESP

More than one processor can start executing a task at the same time. Therefore, either the tasks should be side-effect free as in the backward chaining case or repetitions of side-effects should be acceptable. Examples of acceptable repetitions of side-effects include l) side-effects designed only to increase efficiency but not to affect the correctness of the computation (e.g., caching of propositions in the backward chaining case) and 2) idempotent computations.

As mentioned before, ESP can handle a realistic failure set. Details of this can be found in a technical report written by the authors (Singh, 1984).

C. Comparisons with Previous Work

Contract Net (Davis, 1983) was one of the first efforts to address the problem of dynamically distributing tasks among processors. Its supply protocol uses what is called an Announcement-Bid-Award sequence. Enterprise (Malone. 1983) uses a similar supply protocol but with significant specializations. In the discussion below. ABASP stands for the Announcemenl·Bid·Award type of protocol used in the Contract Net and Enterprise.

ESP allows task execution to begin as soon as a bid is submitted (in a grabbed message). This can increase processor utilization compared to ABASP in which task execution begins only when an award message is received.

Also, no award message is required as in ABASP. Additionally, there is the potential of drastically reducing the number of grabbed messages.

1 1 This pure depth-first strategy will have to be modified if there are infinite depth paths. In the current implementation. only depth-first is used within a processor.

the equivalent of bid messages in the ABASP case. The number of grabbed messages may, in the best case, be one per new task announced. This will happen if the first grabbed message is always sufficiently early to inhibit any other processor from making an attempt to "grab" the same task. Also. recall that a heuristic to reduce the number of grabbed messages was presented earlier.

Note. however. that there is one source of extra messages in the supply-driven strategy using ESP. Multiple executions of the same task are possible. In theory, these multiple executions can create multiple sub-tasks (with extra new messages) in parallel that have to be killed off by extra kill messages. In practice, experimental results indicate that this is not a problem when delays are reasonably short and throughput is not a constraint. Short delays lead to a quick killing of replicated executions before extra sub-tasks can be generated and announced from the short-lived replicated executions. The throughput constraint case will create a problem for Enterprise and Contract Net as well but they do not propose any specific solutions. This paper. however. presents VSM to deal with that case.

Shapiro's Bagel (Shapiro, 1983) also deals with dynamic distribution of tasks in a multiprocessor system. However. Shapiro deals with syslolic problems where programmer determined mappings are possible. Similar assumptions in the present case would mean that one would know ahead of time how many subtasks were going to be generated from each task. This paper makes no such assumption.

VI A SUPPLY-DRIVEN ALLOCATION STRATEGY

Imagine for a moment that the broadcast network can allow an infinite message throughput. This assumption is, of course. not practical but it serves to illustrate the extreme of very plentiful network throughput. A supply-driven strategy, in which all newly generated tasks are announced to all processors, might be appropriate in precisely such a situation.

In the supply-driven strategy, all processors place all newly generated tasks. except one task that is chosen as the current task. in the potential work set. Of course, all tasks placed in the potential work set must be announced with new messages. A processor is allowed to grab a task from the potential work set only when it runs out of internally generated tasks. Since all surplus tasks are announced as being available, this strategy needs the highest network throughput of all strategies included in VSM.

A. Experimental Results

All results reported here were obtained by implementing VSM and ESP on a s\Tulation of the multiple processor architecture described in section Ill. The unit of time for the results reported is the time taken to do a unit backward-chaining deduction.

Figure 3 gives some information about the or deduction tree that was experimented with. The database of each processor contains the behavioral and structural description of a piece of digital hardware - a 4-bit adder. It also contains the values of its inputs. The top-level proposition is a fact to be proved about one of the outputs of the adder. It turns out that the top-level proposition has no positive answer and, therefore. the entire deduction tree is searched in trying to prove the proposition.

The time taken for 1 processor to do the adder example is 652 unit deduction time units. Figure 4 shows the results obtained for the adder example with 1 to 10 processors. For now. the reader's attention is directed to the curves labeled Supply-Driven. lnfinile Throughput.

12 The simulation was performed on a sequential processor (Symbolics 3600). A preliminary version was implemented with multiple (real) 3600's communicating over a Chaosnet to obtain the parameters for a realistic simulation. More details in (Singh. 1984).

Notice from the figure that initially the speedup is almost linear but it becomes less so as the number of processors increases: the speedup obtained by using ten processors (7 .01) is still substantial. Some of the less than linear speedup is due to the inter-processor message delay but some is certainly due to the fact that the deduction tree for the example does not permit very large speedup due to its shape (see figure 3 ). The deduction tree is not very wide at some depths and. therefore, all processors cannot be kept busy at all times by any possible supply protocol. A wider deduction tree for a bigger example can certainly be expected to lead to larger speedups.

The message traffic does not vary much when the number of processors is varied from l to 10. The total number of messages sent increases from 165 for l processor to 213 for lO processors.

Note that although the speedup cu.rve for the supply-driven strategy for infinite throughput looks somewhat like a logarithmic curve, it is a mistake to associate this with Mi8sky's hypothesis (of log(# of processors) speedup) (Minsky, 1970).

The results mentioned so far were obtained with an allowed throughput of infinity. It is certainly possible that the throughput is not enough to send all the messages that are queued at some time in the next unit deduction time. One might expect that with a throughput bottleneck the performance of the supply-driven strategy will degenerate. This is exactly what is observed in the simulation (as shown in the curves labeled Supply-Driven. Bollleneck Throughpul) when a fairly severe throughput limitation of 2 is imposed. The delay is one as before. The speedup for lO processors is only 2.80.

B. Conclusions

The supply-driven strategy works well when the throughput is not a bottleneck. However, the performance can be quite bad if the throughput does become a bottleneck.

13 t f communication cost is ignored as in Minsky's hypothesis. the speedup curves for the supply-driven strategy in the infinite throughput case will be asymptotically linear. as long as the size of the or deduction tree is large enough compared to the number of processors. CommuniCation cost certainly reduces speedup but there is no proof that speedups will be only logarithmic in the general case.

It is important to note here that most of the time, it was not really necessary to announce all surplus tasks when all processors were already busy. The next section offers an alternative that can reduce the amount of communication and thereby decrease overall task completion time for the throughput bottleneck case.

VII A DEMAND-DRIVEN ALLOCATION STRATEGY

The supply-driven strategy always supplies any surplus tasks and. therefore, uses up a lot of throughput. The other extreme is to supply surplus tasks only when all previously announced tasks have been grabbed. This is the demand-driven strategy. As will be shown later. this can drastically reduce message traffic and lead to faster completion of tasks when the available throughput is a bottleneck.

All ~urplus tasks are not supplied and, therefore. not placed in the potent1al work set. The surplus tasks that are not supplied are put in the actual work set. More precisely, when a processor generates more than one task, it keeps one as its next current task, supplies a task to the potential work set if the potential work set is empty, and keeps the remaining tasks in its actual work set. With this strategy, the tasks are supplied only when they are demanded (i .e., when the potential work set gets empty).

A. Comparison with Supply-Driven Allocation Strategy

Not only does the demand-driven strategy use fewer messages than the supply-driven strategy, as explained above, but in some cases the number of messages can be provably an infinitesimal fraction of the supply-driven case. One such case is when the deduction tree is a balanced, binary tree and the ratio of the number of tasks to the number of processors goes asymptotically to infinity. More details are provided in (Singh, 1984). In addition. experimental data presented later will show a dramatic reduction in messages in a practical case.

Another attractive property of the demand-driven strategy is that it requires less storage. Most tasks are kept locally whereas in the supply· driven case, all processors keep a copy of tasks not being worked on.

There is, however. a disadvantage with using the demand-driven strategy. There may be, in general, a higher delay in transferring tasks among processors. This can happen when more than one processor becomes free at the same time : one processor can grab the single task in the potential work set but the others have to wait for some surplus task to be transferred to the potential work set. An example in which the behavior of the demand-driven strategy is, in fact, unboundedly worse is where the total rate of generation of tasks is equal to the total rate of consumption of tasks and the rate of generation and consumption is not uniform over all tasks. A high delay in such a situation would further compound the problem.

B. Experimental Results

The curves labeled Demand-Driven, Infinite Throughput in figure 4 illustrate the performance of the demand·dri ven strategy for the adder example for unit delay and infinite throughput.

As can be seen by comparing the curves labeled Demand-Driven. Infinite Throughput and Supply-Driven, Infinite Throughput. the time taken for lO processors with the demand-driven strategy ( 105) is slightly more that the time taken with the supply-driven strategy (93). The extra time taken is due to the extra delay in supplying tasks. However, the number of messages sent with the demand-driven strategy (90) is much lower than the number of messages sent with the supply-driven strategy (213). Therefore, it should be expected that the demand-driven strategy will not degrade as much in the presence of the same throughput limitation imposed on the supply-driven strategy. This is. in fact, the case as illustrated by the curves labeled Demand· Driven, Bollleneck Throughput. The delay is one and the maximum throughput is 2.

For 10 processors, the time taken for the demand-driven strategy only increases from 105 to 106 by changing the maximum throughput from infinity to 2. In the bottleneck case. the demand-driven strategy (with a time of 106) completely outperforms the supply-driven strategy (with a time of233).

C. Conclusions

The demand-driven strategy can perform better than the supply· driven strategy in the presence of throughput constraints because it requires fewer messages.

It is possible that the tradeoff between delay in supplying tasks (high for the demand-driven case) and the message traffic requirements (high in the supply-driven case) may not have been optimally resolved in either of the extremes. An increase in delay may also be viewed as a reduction in parallelism. VSM allows any intermediate strategy to be selected with great ease and it seems quite probable that intermediate strategies will be found useful for intermediate communication situations. However, no results are avai lable at the present time about these intermediate strategies. Moreover, no results arc avai lable on automating the selection of such a strategy.

VIII CONCLUSIONS

This section contains a description of possible extensions, future work and a summary of the paper.

A. Extensions

The variable supply idea is actually more general than what its application so far in VSM, in conjunction with ESP. might suggest. The extensions described in this section retain the essential goal of VSM. the ability to vary the supply of new tasks given that communication constraints may exist.

1. Extension to Different Task Domains

In cases where side-effects are not acceptable, one can usc a different supply protocol with VSM that does not allow multiple instances of a task to start executing. For example, one could use the announcement· bid-award supply protocol (of Contract Net or Enterprise).

2. Extension to Different Processor Interconnection Structures

It is possible to apply VSM . to cases where the interconnection structure is not a single broadcast network. Essentially, broadcasts are replaced by limited broadcasts. The subset of processors to which a limited broadcast is directed is determined solely by the originating processor of the task. More details can be found in (Singh, 1984).

3. Using Additional Information

Costs of Deductions

So far costs of deductions have not been used because it is not easy to make accurate estimates. However, if one does have a means to obtain reasonable estimates, several uses are possible.

An application of cost estimates can be to stop distribution of certain propositions if their costs are too low to justify the overhead of distribution to other processors.

Also. estimates can be used to break ties between processors with different speeds in a more efficient way than by just comparing the timestamps at which grabs take place. Timestamps based on completion time estimates will be more profitable.

Another application of estimates can be to do load balancing.

Probabilities of Proving Propositions

These probabilities, along with costs of proving those propositions, can be used to determine the best order of doing the tasks (Barnett. 1984, Simon. 1975). Further. Rosenschein and Singh (Rosenschein, 1983) place an upper bound on the amount of work that may be done to achieve the optimal order determined as above. It may be possible to generalize that upper bound result for an arbitrary number of tasks. On the other hand, the result may be more immediately useful in doing many pairwise redistributions in the hope of getting most of the power of a complete redistribution.

B. Future Work

A major effort of future work (Singh, 1985) will be to remove the two major bottlenecks present in the current method of distribution of deductions: the replicated database and the shared communication network. The architecture to be used will consist of large numbers of processors connected with local connections to neighbors (as in a hex· connected plane, for example). Each processor will have a limited amount of local memory that can only store a small part of the entire database.

And parallelism will also be taken advantage of in a limited way. Taking full advantage of and parallelism is a very difficult problem.

C. Summary

Controlling communication cost was seen to be crucial for the successful use of the multiprocessor used. ESP allows communication cost to be reduced in comparison to other task supply protocols. VSM allows an easy and powerful mechanism to choose strategies that work best under different communication constraints. The two extreme strategies were shown to be useful by theoretical and experimental results. In addition, VSM and ESP can be adapted for use with other tasks, interconnection structures. and additional information about tasks.

ACKNOWLEDGMENTS

We wish to thank Ernst Mayr for many stimulating discussions and all others that commented on earlier drafts of this paper.