An Efficient and Scalable Memory Allocator for Multithreaded Tabled Evaluation of Logic Programs
Miguel Areias and Ricardo Rocha
December 2012
Abstract
Despite the availability of both multithreading and tabling in some
Prolog systems, the implementation of these two features, such that
they work together, implies complex ties to one another and to the
underlying engine. In recent work, we have proposed an approach to
combine multithreading with tabling, implemented on top of the Yap
Prolog system, whose primary goal was to reduce memory usage for the
table space. Regarding the execution times, we observed some problems
related to Yap's memory allocator, which is based on the operating
system's default memory allocator, when running programs that allocate
a higher number of data structures in the table space.
In this paper, we propose a more efficient and scalable memory
allocator for multithreaded tabled evaluation of logic programs. Our
goal is to minimize the performance degradation that the system
suffers when it is exposed to simultaneous memory requests made by
multiple threads. For that, we propose a memory allocator based on
local and global pages, to split memory among specific data structures
and different threads, together with a strategy where data structures
of the same type are pre-allocated within a page. Experimental results
show that our new memory allocator can effectively reduce the
execution time and scale better, when increasing the number of
threads, than the original allocator.
Bibtex
@InProceedings{areias-icpads12,
author = {M. Areias and R. Rocha},
title = {{An Efficient and Scalable Memory Allocator for Multithreaded Tabled
Evaluation of Logic Programs}},
booktitle = {Proceedings of the 18th International Conference on Parallel and
Distributed Systems (ICPADS 2012)},
pages = {636--643},
publisher = {IEEE Computer Society},
editor = {X. Tang and Cheng-Zhong Xu},
month = {December},
year = {2012},
address = {Singapore},
}
Download Paper
PDF file
IEEE Computer Society