Abstract
A layered stream is a list of data structuresH*Ts whereTs is a layered stream containing all possible tails for headH. One performance advantage is the ability toeagerly construct a partial solution by binding headH before the tailsTs are known. This increases potential parallelism. A disadvantage of this facility is that eagerly bindingH can cause consumers of the layered stream to do extra computation if in factTs isuncompletable. In addition, the layered streams can grow very large, the bulk of which is garbage. To combat this space inefficiency, eager term construction can be restricted, thereby reducing parallelism. In this paper we show the trade-offs between potential parallelism, execution time, space and time complexity, for a group of benchmarks implemented with layered streams and streams. We also compare these algorithms to the related paradigms of candidates/noncandidates and fused generate & test.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. Okumura and Y. Matsumoto Parallel Programming with Layered Streams,International Symposium on Logic Programming, San Francisco, IEEE Computer Society, pp. 224–233 (August 1987).
R. Trehan, The Behavior of Search Algorithms in a Committed Choice Framework,Proceedings of the Logic Programming Conference, Tokyo, ICOT, pp. 143–157 (1990).
M. Sato and A. Goto, Evaluation of the KL1 Parallel System on a Shared Memory Multiprocessor,IFIP Working Conference on Parallel Processing, Pisa, North Holland, pp. 305–318 (May 1988).
M. Sato,et al. KL1 Execution Model for PIM Cluster with Shared Memory,Fourth International Conference on Logic Programming, University of Melbourne, MIT Press, pp. 338–355 (May 1987).
K. Ueda, Guarded Horn Clauses,Concurrent Prolog: Collected Papers, (ed.), E. Y. Shapiro, MIT Press, Cambridge Massachusetts1:140–156 (1987).
E. Tick,Parallel Logic Programming, MIT Press, Cambridge Massachusetts, 1991.
E. Lusk,et al. The Aurora Or-Parallel Prolog System,International Conference on Fifth Generation Computer Systems, Tokyo,ICOT, pp. 819–830 (November 1988).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Tick, E. Execution characteristics of layered streams. Int J Parallel Prog 19, 425–443 (1990). https://doi.org/10.1007/BF01397626
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01397626