PPoPP 2008 START Conference Manager    

An Adaptive Memory Conscious Approach for Mining Frequent Trees: Implications for Multi-core Architectures (poster presentation)

Shirish Tatikonda and Srinivasan Parthasarathy

The 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2008)
Salt Lake City, Utah, February 20-23, 2008


In this article we present algorithms for frequent tree mining targeting emerging single-chip multiprocessor architectures. We explore algorithmic designs that improve the memory performance of such algorithms, both in terms of alleviating latency to memory as well as in terms of reducing the pressure on the front side bus (of specific importance for such architectures). We then explore adaptive task-parallel and data-parallel design strategies which facilitate effective parallelization even in the presence of data and workload skew while minimizing parallelization overheads. We perform a detailed characterization of the employed optimizations on real data that demonstrates that our algorithm keeps a small working set while reducing the overall runtime and alleviating the bandwidth pressure on the front side bus. We also show that our adaptive parallelization strategy achieves a speedup of up to $13$ times on $16$ processors.

START Conference Manager (V2.54.5)