Forest Packing: Fast Parallel, Decision Forests
Forest Packing: Fast Parallel, Decision Forests
复制标题
森林包装：快速并行、决策森林
DOI：
10.1137/1.9781611975673.6
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
James Browne, Disa Mhembere
中科院分区：
文献类型：
--
作者：
James Browne, Disa Mhembere
决策森林是一种流行的机器学习技术，可以帮助科学家从海量数据集中提取知识。这类工具仍然很受欢迎，因为它们的可解释性和易用性，不像其他现代机器学习方法，如内核机器和深度学习。决策森林也可以很好地扩展用于大数据，因为训练和运行时操作是可并行的，允许高推理吞吐量。这些森林的一个负面方面，以及许多真实的应用程序的一个站不住脚的属性，是由大模型大小与随机存储器访问模式的组合引起的高推理延迟。我们提出的内存包装技术和一种新的树遍历方法，以克服这一不足。我们的系统的结果是一组树成一个层次结构。在低层，我们将多棵树的节点打包到连续的内存块中，这样每次内存访问都会为多棵树获取数据。在更高的层次上，我们使用叶基数来识别通过树的最流行的路径，并将这些路径配置在连续的缓存行中。我们扩展这种布局与重新排序的树遍历算法，以利用无序执行和高速缓存行预取提供的内存吞吐量增加。总之，这些优化将集成分类的性能和并行可扩展性提高了10倍，超过了优化的C++实现和流行的R语言实现。
Decision Forests are popular machine learning techniques that assist scientists to extract knowledge from massive data sets. This class of tool remains popular because of their interpretability and ease of use, unlike other modern machine learning methods, such as kernel machines and deep learning. Decision forests also scale well for use with large data because training and run time operations are trivially parallelizable allowing for high inference throughputs. A negative aspect of these forests, and an untenable property for many real time applications, is their high inference latency caused by the combination of large model sizes with random memory access patterns. We present memory packing techniques and a novel tree traversal method to overcome this deficiency. The result of our system is a grouping of trees into a hierarchical structure. At low levels, we pack the nodes of multiple trees into contiguous memory blocks so that each memory access fetches data for multiple trees. At higher levels, we use leaf cardinality to identify the most popular paths through a tree and collocate those paths in contiguous cache lines. We extend this layout with a re-ordering of the tree traversal algorithm to take advantage of the increased memory throughput provided by out-of-order execution and cache-line prefetching. Together, these optimizations increase the performance and parallel scalability of classification in ensembles by a factor of ten over an optimized C++ implementation and a popular R-language implementation.