Comparison of Three Algorithms for Ensuring Serializable Executions in Parallel Production Systems

Problem Solving

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 10

Problem Solving: Real-Time

To speed up production systems, researchers have developed parallel algorithms that execute multiple instantiations simultaneously. Unfortunately, without special controls, such systems can produce results that could not have been produced by any serial execution. We present and compare three different algorithms that guarantee a serializable result in such systems. Our goal is to analyze the overhead that serialization incurs. All three algorithms perform synchronization at the level of instantiations, not rules, and are targeted for shared-memory machines. One algorithm operates synchronously while the other two operate asynchronously. Of the latter two, one synchronizes instantiations using compiled tests that were determined from an offline analysis while the other uses a novel locking scheme that requires no such analysis. Our examination of performance shows that asynchronous execution is clearly faster than synchronous execution and that the locking method is somewhat faster than the method using compiled tests. Moreover, we predict that the synchronization and/or locking needed to guarantee serializability will limit speedup no matter how many processors are used.