A characterization of data mining algorithms on a modern processor
Amol Ghoting, Gregory Buehrer, Srinivasan Parthasarathy, Daehyun Kim, Anthony D. Nguyen, Yen-Kuang Chen, Pradeep Kumar Dubey · 2005
In this paper, we characterize the performance and memory access behavior of several data mining algorithms. Specifically, we consider algorithms for frequent itemset mining, sequence mining, graph mining, clustering, outlier detection, and decision tree induction. Our study reveals that data mining algorithms are compute and memory intensive. Furthermore, some algorithms have poor spatial locality, while most algorithms have poor temporal locality. Hardware prefetching helps the algorithms with good spatial locality, but most algorithms are unable to leverage simultaneous multithreading because of their memory intensive nature. Consequently, all these algorithms grossly under-utilize a modern day processor. Using the knowledge gleaned in this investigation, we briefly show how we improve the performance of a frequent itemset mining algorithm, FPGrowth, on a modern processor. Our study suggests that a specialized memory system with several thread contexts per processor is needed to allow these algorithms to scale on future microprocessors. 1.