Parallel Inference Machines (Panel)

PANEL ON PARALLEL INFERENCE MACHINES

W. Bibel

lnatitut fiir Informatik, TU Miinchcn, Po.tfach 202420, D-8000 Miinchcn 2

The quest for ever more powerful computers has bumped up hard against the limits Imposed by nature such as speed of light and electrons. However, scientists and Industry agree that there Is still a great potential for further speed-up by distributing computations among many processors rather than a single one. This Is apparent for problems that can easily be broken down Into many independent parts such as those to be tackled In graphics, signal processing (which Includes radar, speech and vision analysis), structural analysis, fluid-flow dynamics, particle physics, and many others. First experiences with the new breed of parallel computers justify this optimism.

It is less obvious whether a multi-processor would bring a significant improvement in performance for prob­ lems such as lnferenclng. Finding a correct chain of Infer­ ences requires searching through a space of different pos­ sible chains, a problem known to be hard (NP-complete) and requiring exponential recources In worst cases according to our present knowledge. Therefore one might argue that one thousand processors would provide rela­ tively little improvement over a single one In worst (exponential) cases. From a more practical point of view, experiments seem to Indicate that the possibilities for exploiting parallelism In rule-based systems might be rather limited.

There are more problems of detail arising In an attempt to parallelize lnferenclng. The different possible chains in the search space partially coincide In a way not known at compile time hence making It difficult to break the whole task down into many parts and distribute these in a well-balanced way. Also (but not only) because of this overlap It seems attractive to exploit the parallelism inherent in each of these chains. But at present it Is not clear at all whether this really pays since It might cause too much overhead in communication and anyway might have only a marginal effect In view of ·the more severe problem of NP-completeness mentioned above.

Some even put forward reasonable arguments to the effect that inferencing in practice is not needed at all. Part of it could be substituted by exploiting data-base techniques even in the presence of recursion. Or, machine reasoning could be founded on episodes from the past stored In a massively parallel memory rather than on rules and facts thus leading to a memory-based reasoning with a parallelism radically different from the one discussed above; with this remark we scratch on the current discus­ sion about connectionism.

Much of what was pointed out above reflects the spirit of classical reasoning or even more specifically Horn-clause (or production-rule-based) reasoning. As we know human reasoning has many flavors that might still cause (at least practical) problems with their Integration into this classical deduction scheme. Non-monotonic, pro­ babilistic, inductive reasoning are some of the keywords pointing to such additional aspects. Little has been done in view of parallelizing such more complicated (though essential) inference techniques.

Another controverse discussion is lead on the ques­ tion to what extent the user should control the task­ partitioning and thus the parallelism. More generally, how should we program a machine with say 64K processors that operate in an asynchronous way (because of the differences in the various parts a synchronous behavior seems to be unrealistic). There is a whole spectrum of opinions on these programming language aspects that might reflect the different possible user levels, ranging from the software engineer to the casual user.

Given so many questions about the nature of the task of inferencing in general and Its Inherent parallelism in particular, it is no surprise that we still lack a convincing proposal for an architecture of a parallel Inference machine. What should be its topology, the power of Its processors, the mechanisms of Its communications, syn­ chronization, and load-balancing, these are some of the questions that are currently studied in many laboratories around the world.

In this situation It was thought that a panel discussion would provide the appropriate forum to serve a number of functions. It might give a feel for the relevance of each of the controverse discussions mentioned above and the dif­ ferent standpoints taken In them. At best, It might even help to provide some answers to the questions of concern. In any case it will Inform the AI-community that much more is going on In this promising area than one might think from the relatively sparse publications, which Is typical for any field during its Initial phase of experimen­ tation.