This paper presents a process model, based on the OR-forest description, for the parallel execution of logic programs. In the PSOF model, the parallel execution of a program is realized by the parallel search of the u...This paper presents a process model, based on the OR-forest description, for the parallel execution of logic programs. In the PSOF model, the parallel execution of a program is realized by the parallel search of the unique OR-forest for the program: an OR-parallel execution of a goal is carried out by successor processes simultaneously searching multiple branches, and all the processes searching the same tree are logically independent and need not communicating; AND-parallel execution of a goal is practised by slave processes simultaneously searching multiple trees. A slave process sends a message to its master process only when it reaches a leaf node. The subject of the automatic partition of sub-goals in the framework of OR-forest is also discussed in this paper.展开更多
An environment-sharing scheme for both AND- and OR-parallel executions o?logic programs is presented in this paper. In this scheme, an environment consists of binding records for storing binding values o?variables. A ...An environment-sharing scheme for both AND- and OR-parallel executions o?logic programs is presented in this paper. In this scheme, an environment consists of binding records for storing binding values o?variables. A binding record contains only the values of instantiated variables. Unbound variables never occur in binding records. Therefore, binding records of a process can be safely shared by its successor/slave processes, overcoming the drawback of checking and copying "uncommitted context" in OR-parallel environment-sharing scheme.A 2-level storage structure for environment storage and procedures for creating, accessing and updating the environment are defined in this paper. This scheme, including all the procedures, has been implemented in PROLOG and tested by running a number of benchmarks.展开更多
In order to implement Prolog efficiently, Prolog-oriented processors and VLSI chips have been proposed and designed. However, most of the Prolog machines and processors emerged recently suffer from two weaknesses: the...In order to implement Prolog efficiently, Prolog-oriented processors and VLSI chips have been proposed and designed. However, most of the Prolog machines and processors emerged recently suffer from two weaknesses: they cannot implement Prolog database operations or cannot perform numerical evaluations at high speed. In this psper, the architecture of a Prolog machine GKD-PLM is presented. Based on the WAM-PLUS which is an execution model for sequential Prolog, the GKD-PLM can not only execute Prolog code rapidly, but also support database operations and numerical evaluations. First, the characteristics of the machine are described, followed by the description of the instruction set, the data representations, and the hardware structures of the execution unit and the microprogram control unit of the Prolog processor SPP. The performance of the machine is estimated.展开更多
First, a model of static data flow computer and a model of data flow graph are pro-posed; then a model of system is presented to calculate practical parallelism degree withoverhead of instruction execution on data flo...First, a model of static data flow computer and a model of data flow graph are pro-posed; then a model of system is presented to calculate practical parallelism degree withoverhead of instruction execution on data flow computers as its parameter. From the compu-tation, the maximum practical parallelism degree of a program running on a static dataflow computer is determined with MP/OH (MP is the mean parallelism degree of a program,OH is the overhead of instruction execution on the computer). Therefore the overhead hasgreat influence on the performance of a data flow computer.展开更多
The Warren Abstract Machine is an efficient execution model for Prolog,which has become the basis of many high performance Prolog systems.However.little support for the implementation of the non-logical components of ...The Warren Abstract Machine is an efficient execution model for Prolog,which has become the basis of many high performance Prolog systems.However.little support for the implementation of the non-logical components of Prolog is provided in the WAM.The original Warren code is not modifiable.In this paper,we show how static modifications of Warren code can be achieved by adding a few instructions and a little extra information to the code.The implementation of the code manager is discussed.Algorithms for some basic operations are given.展开更多
In this paper,we present an approximate formula for calculating th speedup of a concurrent non-DO loop.The execution pattern of a concurrent non-Do loop is analyzed.As a result,the optimal concurrent step for a non-DO...In this paper,we present an approximate formula for calculating th speedup of a concurrent non-DO loop.The execution pattern of a concurrent non-Do loop is analyzed.As a result,the optimal concurrent step for a non-DO loop is presened and proved.With the analysis of the speedup of a concurrent non-DO loop,a simple and useful approximate formula is deduced,which is just the mathematical limit of speedup when the number of iterations is approaching infinity.展开更多
文摘This paper presents a process model, based on the OR-forest description, for the parallel execution of logic programs. In the PSOF model, the parallel execution of a program is realized by the parallel search of the unique OR-forest for the program: an OR-parallel execution of a goal is carried out by successor processes simultaneously searching multiple branches, and all the processes searching the same tree are logically independent and need not communicating; AND-parallel execution of a goal is practised by slave processes simultaneously searching multiple trees. A slave process sends a message to its master process only when it reaches a leaf node. The subject of the automatic partition of sub-goals in the framework of OR-forest is also discussed in this paper.
文摘An environment-sharing scheme for both AND- and OR-parallel executions o?logic programs is presented in this paper. In this scheme, an environment consists of binding records for storing binding values o?variables. A binding record contains only the values of instantiated variables. Unbound variables never occur in binding records. Therefore, binding records of a process can be safely shared by its successor/slave processes, overcoming the drawback of checking and copying "uncommitted context" in OR-parallel environment-sharing scheme.A 2-level storage structure for environment storage and procedures for creating, accessing and updating the environment are defined in this paper. This scheme, including all the procedures, has been implemented in PROLOG and tested by running a number of benchmarks.
基金Project partly supported by the National Natural Science Foundation of China.
文摘In order to implement Prolog efficiently, Prolog-oriented processors and VLSI chips have been proposed and designed. However, most of the Prolog machines and processors emerged recently suffer from two weaknesses: they cannot implement Prolog database operations or cannot perform numerical evaluations at high speed. In this psper, the architecture of a Prolog machine GKD-PLM is presented. Based on the WAM-PLUS which is an execution model for sequential Prolog, the GKD-PLM can not only execute Prolog code rapidly, but also support database operations and numerical evaluations. First, the characteristics of the machine are described, followed by the description of the instruction set, the data representations, and the hardware structures of the execution unit and the microprogram control unit of the Prolog processor SPP. The performance of the machine is estimated.
文摘First, a model of static data flow computer and a model of data flow graph are pro-posed; then a model of system is presented to calculate practical parallelism degree withoverhead of instruction execution on data flow computers as its parameter. From the compu-tation, the maximum practical parallelism degree of a program running on a static dataflow computer is determined with MP/OH (MP is the mean parallelism degree of a program,OH is the overhead of instruction execution on the computer). Therefore the overhead hasgreat influence on the performance of a data flow computer.
文摘The Warren Abstract Machine is an efficient execution model for Prolog,which has become the basis of many high performance Prolog systems.However.little support for the implementation of the non-logical components of Prolog is provided in the WAM.The original Warren code is not modifiable.In this paper,we show how static modifications of Warren code can be achieved by adding a few instructions and a little extra information to the code.The implementation of the code manager is discussed.Algorithms for some basic operations are given.
文摘In this paper,we present an approximate formula for calculating th speedup of a concurrent non-DO loop.The execution pattern of a concurrent non-Do loop is analyzed.As a result,the optimal concurrent step for a non-DO loop is presened and proved.With the analysis of the speedup of a concurrent non-DO loop,a simple and useful approximate formula is deduced,which is just the mathematical limit of speedup when the number of iterations is approaching infinity.
