Evaluating parallel logic programming systems on scalable multiprocessors
Vı́tor Santos Costa, Ricardo Bianchini, Inês Dutra · 1997
Parallel logic programming systems are soph~ticated examples of symbolic computing systems.They address problems such as dynamic memory allocation, scheduling irregular execution patterns, and managing Werent types of implicit parallelism.Most parallel logic programming systems have been developed for bus-based shared-memory architectures.The complexity of parallel logic programming systems and the large amount of data they process raises the question of whether logic programming systems can still obtain good performance on scalable architectures, such as distributed shared-memory systems.In this work we use execution-driven simulation to investigate the access patterns and caching behaviour exhibited by a parallel logic programming system, Andorrt+I.We show that the system obtains reasonable performance, but that it does not scale well.By studying the behaviour of the major data structures in Andorr*I in detail, we conclude that this result is lrwgely a consequence of the scheduling and work manipulation implementation used in the system.We also show that the Andorr~I's data structure exhibit widely-varying memory access patterns and caching behaviour, which not only depend on the number of processors, but also on the amount and type of parallelism available in the application program.Some of these data structures clearly favour invahdate-based cache coherence protocols, while others favour update-baaed protocols.Since moat of Andorra-I's data structures are common to other parallel logic programming systems, we believe that these systems can greatly benefit from flexible coherence schemes where either the compiler can specify the protocol to be used for each data structure or the protocol can adapt to varying memory access patterns.