Name
Abstract | ||
|---|---|---|
We present the first backtracking algorithm for stream AND-parallel logic programs. It relies on compile-time knowledge of
the dataflow graph of each clause to let it figure out efficiently which goals to kill or restart when a goal fails. This
crucial information, which we derive from mode declarations, was not available at compile-time in any previous stream AND-parallel
system.
We show that modes can increase the precision of the backtracking algorithm, though our algorithm allows this precision to
be traded off against overhead on a procedure-by-procedure and call-by-call basis. The modes also allow our algorithm to handle
efficiently programs that manipulate partially instantiated data structures and an important class of programs with circular
dependency graphs. On code that does not need backtracking, the efficiency of our algorithm approaches that of the committed-choice
languages; on code that does need backtracking its overhead is comparable to that of the independent AND-parallel backtracking
algorithms. |
Year | DOI | Venue |
|---|---|---|
1988 | 10.1007/BF02427851 | International Journal of Parallel Programming |
Keywords | Field | DocType |
backtracking algorithm,intelligent backtracking,strong and precise modes.,don't-know nondeterminism,stream and-parallel execution,stream and-parallelism,logic program,parallel systems,data structure | Graph,Data processing,Logic gate,Programming language,Computer science,Parallel processing,Parallel computing,Theoretical computer science,Dataflow,Backtracking,Mathematical logic | Journal |
Volume | Issue | ISSN |
17 | 3 | 0885-7458 |
Citations | PageRank | References |
2 | 0.40 | 26 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zoltan Somogyi | 1 | 571 | 141.85 |
| kotagiri ramamohanarao | 2 | 4716 | 993.87 |
| Jayen Vaghani | 3 | 103 | 48.51 |