Return to CLIP Main Page

Parallelization: Correctness and Efficiency

• Correctness: same solutions as sequential execution.
• Efficiency: taking a shorter or equal execution time (speedup) or, at least, no-slowdown over state-of-the-art sequential systems.
• Imperative (a), functional (b), constraint logic programming (c):
  

  Y := W+2; (+ (+ W 2) Y = W+2,

  X := Y+Z; Z) X = Y+Z,

  (a) (b) (c)

  
  
• Constraint programming (with choices): 0.430.43 p(X) :- X=a.
  q(X) :- X=b, large computation.
  q(X) :- X=a.
  
• Fundamental issue: p affects q (prunes its choices); q ahead of p is speculative.
• q(X) = { if X=b then large computation else if X=a then true else fail }