| 1. |
- Ali, Khayri Mohammed
(author)
-
A method for implementing out in parallel execution of Prolog
- 1987. - 1
-
Reports (other academic/artistic)abstract
- A method for implementing cut in parallel execution of Prolog is presented. It takes advantages of the efficient implementation of cut in the sequential WAM. It restricts the parallelism, however, it is simple and adds a small extra overhead over the sequential scheme. The method can be used in parallel execution of Prolog on shared amd nonshared memory multiprocessors.
|
|
| 2. |
|
|
| 3. |
- Ali, Khayri Mohammed, et al.
(author)
-
An investigation of an OR parallel execution model for horn clause programs
- 1988. - 1
-
Reports (other academic/artistic)abstract
- We present a model for OR parallel execution of Horn clause programs on a combined local and shared memory multiprocessor system. In this model, the shared memory only contains control information that guides processors requesting a job to independently construct the environment required to get a new job. Each processor has a local memory containing its own binding environment. This reduces the traffic to the shared memory and allows each processor to process its job with high performance. Each processor is almost the same as Warren's Abstract Machine (WAM). A method for nonshared memory multiprocessor architectures is outlined. We also present some preliminary results of an experimental investigation of the model.
|
|
| 4. |
- Ali, Khayri Mohammed, et al.
(author)
-
Global garbage collection for distributed heap storage systems
- 1987. - 1
-
Reports (other academic/artistic)abstract
- We present a garbage-collection algorithm, suitable for loosely-coupled multiprocessor systems, in which the processing elements (PE's) share only the communication medium. The algorithm is global, i.e. it involves all the PE's in the system. It allows space compaction, and it uses a system-wide marking phase to mark all accessible objects where a combination of parallel breadth-first/depth-first strategies is used for tracing the object-graphs according to a decentralized credit mechanism that regulates the number of garbage collection messages in the system. The credit mechanism is crucial for determining the space requirement of the garbage-collection messages. Also a variation of the above algorithm is presented for systems with high locality of reference. It allows each PE to perform first its local garbage collection and only invokes the global garbage collection when the freed space by the local collector is insufficient.
|
|
| 5. |
- Ali, Khayri Mohammed
(author)
-
OR parallel execution of horn clause programs based on WAM and shared control information
- 1988. - 1
-
Reports (other academic/artistic)abstract
- A method for OR parallel execution of Horn clause programs on a shared memory multiprocessor is presented. The shared memory contains only control information that guide processors requesting a job to independently construct the environment required to get a new job from the other processors without degrading the performance. Each processor has a local memory containing its own binding environment. This reduces the traffic to the shared memory and allows each processor to process its job with high performance. Each processor is almost the same as the Warren Abstract Machine (WAM). Modification to the WAM for supporting the method is described in detail. A method for nonshared memory multiprocessor architecture is outlined.
|
|
| 6. |
- Ali, Khayri Mohammed
(author)
-
OR-Parallel Execution of Prolog on a Multi-Sequential Machine
- 1986. - 1
-
Reports (peer-reviewed)abstract
- Based on extending the sequential execution model of Prolog to include parallel execution, we present a method for OR-parallel execution of Prolog on a multiprocessor system. The method reduces the overhead incurred by parallel processing. It allows many processing elements (PEs) to process simultaneously a common branch of a search tree, and each of these PEs creates its local environment and selects a subtree for processing without communication. The run-time overhead is small: simple and efficient operations for selecting the proper subtree. Communication is necessary only when some PEs have exhausted their search spaces and there are others still searching for solutions. The method is able to utilize most of the technology devised for sequential implementation of Prolog. It is optimized for an architecture which supports broadcast copying.
|
|
| 7. |
- Ali, Khayri Mohammed
(author)
-
OR parallel execution of Prolog on BC-machine
- 1988. - 1
-
Reports (other academic/artistic)abstract
- We present the principles of OR-parallel execution of Prolog on a special parallel inference machine, named BC-machine. The machine is a combined local and shared memory multiprocessor with a special interconnection network. The network allows write operations of an active processor to be broadcasted to several idle processors simultaneously. The shared memory is mainly used for sharing some control information among processors in the system. The amount of shared control information is small and accessed relatively seldom. The execution model is based on the local address space approach. It allows all the technology developed for standard Prolog to be used without loss of efficiency. We expect that the model substantially reduces the copying overhead in comparision with all previous related models. This reduction is due to our new idea of dynamic load balancing and the broadcast mechanism supported by the network. A prototype system of 9 processors is under construction at the Swedish Institute of Computer Science in Stockholm.
|
|
| 8. |
- Ali, Khayri Mohammed, et al.
(author)
-
Performance of Muse on Switch-Based Multiprocesor Machines
- 1992. - 1
-
Reports (other academic/artistic)abstract
- The Muse (multiple sequential Prolog engines) approach has been used to make a simple and efficient OR-parallel implementation of the full Prolog language. The performance results of the Muse system on bus-based multiprocessor machines have been presented in previous chapters, papers. This chapter paper discusses the implementation and performance results of the Muse system on switch-based multiprocessors (the BBN Butterfly GP1000 and TC2000). The results of Muse execution show that high real speedups can be achieved for Prolog programs that exhibit coarse-grained parallelism. The scheduling overhead is equivalent to around 8 -- 26 Prolog procedure calls per task on the TC2000. The chapter paper also compares the Muse results with corresponding results for the Aurora OR-parallel Prolog system. For a large set of benchmarks, the results are in favor of the Muse system.
|
|
| 9. |
- Ali, Khayri Mohammed, et al.
(author)
-
The Engine-Scheduler Interface used in the Muse OR-parallel Prolog System
- 1992. - 1
-
Reports (other academic/artistic)abstract
- Almost any sequential Prolog system is in principle easy to extend for OR-parallelism, using the Muse execution model. To reduce your programming effort we have implemented the Muse scheduler, with a clean interface to the Prolog sequential engine. This interface is implemented as a set of C macros. The sequential Prolog system to be parallelized uses some of those macros provided by the Muse scheduler and must also provide some macros for the Muse scheduler. This chapter paper contains a definition and description of the required macros, emphasizing information needed by the Prolog engine programmer.
|
|
| 10. |
- Gupta, Gopal, et al.
(author)
-
Parallel execution of Prolog programs
- 2001. - 1
-
In: ACM Transactions on Programming Languages and Systems. - : Association for Computing Machinery (ACM). - 0164-0925 .- 1558-4593. ; 23:4, s. 472-602
-
Journal article (peer-reviewed)abstract
- Since the early days of logic programming, researchers in the field realised the potential for exploitation of parallelism present in the execution of logic programs. Their high-level nature, the presence of non-determinism, and their referential transparency, among other characteristics, make logic programs interesting candidates for obtaining speedups through parallel execution. At the same time, the fact that the typical applications of logic programming frequently involve irregular computations, make heavy use of dynamic data structures with logical variables, and involve search and speculation, makes the techniques used in the corresponding parallelizing compilers and run-time systems potentially interesting even outside the field. The objective of this paper is to provide a comprehensive survey of the issues arising in parallel execution of logic programming languages along with the most relevant approaches explored to date in the field. Focus is mostly given to the challenges emerging from the parallel execution of Prolog programs. The paper describes the major techniques used for shared memory implementation of Or-parallelism, And-parallelism, and combinations of the two. We also explore some related issues, such as memory management, compile-time analysis, and execution visualisation.
|
|
