《A heterogeneous parallel deduction system.docx》由会员分享，可在线阅读，更多相关《A heterogeneous parallel deduction system.docx（25页珍藏版）》请在三一文库上搜索。
1、A heterogeneous parallel deduction systemA Heterogeneous Parallel Deduction SystemGeoff SutcliffeDept of Computer Science, Edith Cowan University &Dept of Computer Science, The University of Western AustraliaPerth, Western Australia geoffhttp:/ paper describes the architecture, implementation and pe
2、rformance, of a heterogeneous parallel deduction system (HPDS). The HPDS uses multiple deduction components, each of which attempts to find a refutation of the same input set, but using different deduction formats. The components cooperate by distributing clauses they generate to other components. T
3、he HPDS has been implemented in Prolog-D-Linda. Prolog-D-Linda provides appropriate data transfer and synchronisation facilities for implementing parallel deduction systems. The performance of the HPDS has been investigated.Parallel Deduction SystemsA parallel deduction system is one in which multip
4、le deduction components run in parallel on separate processors. This is distinct from those deduction systems which run multiple deduction components alternately, such as the unit preference system Wos, Carlson & Robinson?G.A.,?1964, and those which are only conceptually parallel systems. Parallel d
5、eduction systems can be categorised along three axes.Homogeneous or Heterogeneous? In a homogeneous system the multiple deduction components all use the same deduction format. Homogeneous systems do not change the search space of the underlying deduction format. Rather they take advantage of added c
6、omputing power to distribute the work of searching that space. An example of such a system is ROO Lusk, Slaney & McCune,?1991. In a heterogeneous system the multiple deduction components use different deduction formats. The advantage of heterogeneity is that each deduction component has a different
7、search space. Further, it is necessary for only one of the components to use a complete deduction format. This feature permits incomplete formats, which are fast on average, to be used as part of complete parallel deduction system. An example of such a system is GLD|UR Sutcliffe,?1991. Between homog
8、eneous and heterogeneous are the pseudo heterogeneous systems. The components of these systems all use the same deduction format, but each component has different set-up parameters. Each component will thus have a similar search space, but will search the space in a different manner. An example of s
9、uch a system is Ertels Random Competition system Ertel,?1991.Common or Separate input sets? To implement a common input set for multiple deduction components, some kind of shared memory architecture is necessary. On the other hand, if each component maintains its own copy of the input set then more
10、common computer architectures can be used. ROO is an example of a system that uses a common input set, while the RandomCompetition system is one that uses separate input sets. An approximation of a common input set can be implemented by using separate input sets which are updated in parallel. The ap
11、proximation can be implemented provided there is some form of inter-component communication mechanism. This approach is taken in GLD|UR.Homogeneous systems require a common input set, for otherwise the components will duplicate each others search. In a heterogeneous system it is ok to have separate
12、input sets, as the components do different things naturally. However, there is an advantage to having a common input set in a heterogeneous system. As each component has a different search space, the clauses created in each component may not be created in others. By making all clauses available to a
13、ll components, cross fertilisation is achieved. Although hard to quantify, this effect has the potential to significantly affect a parallel systems performance. Further, if the parallel update approach is used, the distribution of clauses can be controlled so that different components sets are updat
14、ed differently.Synchronous or Asynchronous? An asynchronous system has the advantage that components do not have to wait for each other, and greater use is made of the available computing power. On the other hand, there may be advantage to be had in making the multiple components aware of and suppor
15、tive of each others activities.This paper introduces a heterogeneous parallel deduction system (HPDS), employing a chain format linear deduction component, a UR-deduction component, and a hyper-resolution component. The HPDS is the logical successor of GLD|UR. The components of the HPDS each maintai
16、n their own copy of the input set. Each input set is updated with clauses created locally and with clauses created in the other components. The components run asynchronously. The Parallel Implementation EnvironmentA prerequisite to the implementation of a parallel deduction system is to decide upon
17、and, if necessary, develop an appropriate parallel programming environment. The HPDS has been implemented using Prolog-D-Linda Sutcliffe & Pinakis?1991. Linda is a programming framework of language-independent operators which may be injected into existing programming languages, resulting in new para
18、llel programming languages. Linda permits cooperation between parallel processes by controlling access to a shared data structure called a tuple space. Manipulation of a tuple space is only possible using Linda operators (out, in and rd). Parallel execution is provided by an operator (eval) which st
19、arts new processes. Generically, Prolog-Linda is the extension of Prolog that supports a tuple space and the Linda operators. Prolog-D-Linda is our implementation of Prolog-Linda. Prolog-D-Linda is built on top of SICStus Prolog. It runs on a network of SUN SPARC workstations running SUN OS 4.0.3, c
20、onnected by Ethernet.In Prolog-D-Linda the tuple space is distributed (hence Prolog-Distributed-Linda). The tuple space and associated operations are implemented in server processes. The distribution of tuples across the servers is determined by a user supplied Prolog program. Linda operations in cl
21、ientprocesses are translated into requests which are passed to the appropriate server. One server is designated the eval-server, and is responsible for starting client processes requested in eval operations. The servers are started by a controller process. After starting the servers, the controller
22、works as the standard input and output device for all the servers, and for clients that are started via an eval request. This feature enables servers and clients, that are not associated with a terminal, to have user interaction.The HPDS ArchitectureThe deduction components of the HPDS are Guided Li
23、near Deduction (GLD) Sutcliffe,?1992 (GLD is a chain format linear deduction system), a UR-deduction Overbeek, McCharen & Wos,?1976 component, and a hyper-resolution Robinson J.A.,?1965 component. Each component maintains its own input set, asynchronously updating it with clauses created in the othe
24、r components at a time convenient to itself. All of the components have been implemented in Prolog. Common features of the components are?:?All use the chain format for clauses. They all use the same code for their deduction operations, processing of clauses created, and manipulation of their input
25、sets. This makes it easy to distribute the clauses that each creates.?Each component creates clauses that can be used by the others. All the components apply back and forward subsumption to all clauses that they create. The subsumption checks are applied before the clauses are distributed to the oth
26、er components. Information indicating which clauses are subsumed accompanies each clause that is distributed.?Each component uses a consecutively bounded search as its overall search strategy.Although the value bounded is different in each component, the same implementation is used in each component
27、. If a new clause is added to the input set in a search iteration, the the bound value is increased only minimally at the end of the iteration. Further, another iteration is always executed if a new clause has been added to the input set in the iteration. In the HPDS these features are affected not
28、only by clauses created locally, but also by clauses received from the other components.The GLD ComponentGLD is based on Shostaks Graph Construction (GC) procedure Shostak,?1976, but also incorporates features from other chain format linear deduction systems. In particular, GLD has a combined lemma/
29、C-literal mechanism, which improves on the original separate mechanisms in Lovelands Model Elimination (ME) procedure Loveland,?1969 and the GC procedure. The lemmas created by this mechanism are the clauses that are distributed to the hyper-resolution and UR components. GLD uses an extended unit pr
30、eference strategy in all extension operations, and thus productively uses the unit clauses which it receives from the UR component. GLD does not accept clauses created in the hyper-resolution component, as it was found that the large number of clauses created by hyper-resolution caused an unacceptab
31、le increase in the size of the GLD search space.The UR ComponentThe UR components strength lies in its ability to solve many Horn problems very quickly. The UR component is a useful adjunct to the complete GLD and hyper-resolution components. The clauses created in the two complete components are us
32、ed as nuclei in the UR component. This leads to the UR component reporting refutations for problems that it cannot solve independently.The Hyper-resolution ComponentThe hyper-resolution component of the HPDS implements positive hyper-resolution. Non-factored hyper-resolvants are distributed to the o
33、ther components. Like the GLD component, the hyper-resolution component benefits from using the unit clauses produced by the UR component. There is some possibility of an overlap between the clauses created in this component and those created in the GLD and UR components. However, GLD is a back chai
34、ning system, while hyper-resolution is forward chaining. Thus the searches of these two components are in the opposite direction. Thus each should benefit from the work that the other does at the other end of the general search space. The overlap with the UR component is dealt with by the subsumptio
35、n checks.The CombinationThe completeness of the HPDS is assured by the completeness of GLD and hyper-resolution. The difference between these components running independently and running in the HPDS, is the addition of new input clauses created in the other components. Such clauses are subject to th
36、e same subsumption checks as those created locally. By having the consecutively bounded search run another iteration whenever any new clause is added to the input set, both the GLD component and the hyper-resolution component remain complete within the HPDS.The HPDS ImplementationEach deduction comp
37、onent of the HPDS runs as a client process in Prolog-D-Linda. The deduction components do not communicate with each other directly, but rather via a deduction controller (also a Prolog-D-Linda client). The deduction controller is responsible for starting the deduction components, and for controlling
38、 the distribution of clauses created in the deduction components. Communication between the deduction components and the controller is via the Prolog-D-Linda tuple space. When a deduction component wishes to pass any data to the controller, it out s a tuple of the form controller(,). The is the name
39、 of the deduction component which produced the tuple. The field indicates the type of the . There are four possible values?: clause, stop, io and statistics. The controller retrieves these tuples from the tuple space using the in operation. Similarly, the controller passes data to the deduction comp
40、onents by placing tuples of the form (controller,) into the tuple space.When the deduction controller is started, it collects information about each of the deduction components from the user. This includes the name of components source code file, the Prolog query required to start the component, and
41、 a flag indicating whether or not the component is complete. Each deduction component is then started using the eval operation. The task of the controller is then to continuously retrieve its message tuples from the tuple space and to deal with the data according to the value of the The deduction co
42、mponents, as well as executing their deductions appropriately, must check the tuple space at regular intervals for messages from the controller. Again, these messages are dealt with according to their Within each deduction component, each clause that is created is passed to a clause control module i
43、n the component. The clause control module implements the subsumption checks, removes subsumed input clauses from the local input set, adds the new clause to the local input set, and transmits both the new clause and subsumed clauses identifiers to the controller. The The stop message type is used w
44、hen a deduction component either finds a refutation, or completes the search of its search space. If a deduction component finds a refutation it sends a stop message to the controller, with a value of success. The successful component then proceeds to terminate. The controller forwards the stop mess
45、age to the other deduction components. Upon receipt of these messages the deduction components proceed to terminate. If a deduction component completes the search of its search space without finding a refutation, it sends a stop message to the controller with a value of failure. If the failing compo
46、nent has a complete deduction format then it proceeds to terminate, and the controller forwards the stop message to the other deduction components. If the failing component is incomplete, then the stop message is ignored by the controller as a refutation could still be found. The failing component d
47、oes not terminate is this situation, as it could receive a clause from another deduction component hence opening up another piece of search space. Therefore incomplete deduction components, that have completed their search, wait for further messages from the controller.The io message type allows the
48、 deduction components to output data at the controllers terminal. This is useful for tracking the progress of the HPDS. Whenever the controller receives an io message, the When a deduction component proceeds to terminate, it determines the number of deduction operations it has performed and the amou
49、nt of CPU time it has used. These figures are sent to the controller in a statistics message. After the controller has sent a stop message to each deduction component, it collects the statistics messages and outputs appropriate statistics. The final task of the controller after this is to remove any messages left in the tuple space. TestingTo evaluate a parallel deduction system, it is important to state UNA