ROLLED: Racetrack Memory Optimized Linear Layout and Efficient Decomposition of Decision Trees
ROLLED: Racetrack Memory Optimized Linear Layout and Efficient Decomposition of Decision Trees
复制标题
DOI：
10.1109/tc.2022.3197094
复制
发表时间：
2023-05
影响因子：
3.7
通讯作者：
Christian Hakert;Asif Ali Khan;Kuan-Hsun Chen;F. Hameed;J. Castrillón;Jian-Jia Chen
中科院分区：
文献类型：
--
作者：
Christian Hakert;Asif Ali Khan;Kuan-Hsun Chen;F. Hameed;J. Castrillón;Jian-Jia Chen
现代低功耗分布式系统倾向于集成机器学习算法。在资源受限的设置中，模型的执行必须针对性能和能耗进行优化。赛道内存（RTM）有望通过提供前所未有的集成密度、更小的访问延迟和更低的能耗来实现这些目标。但是，要访问RTM中的数据，需要先将数据转移到访问端口。我们研究决策树，并制定安置策略，以减少RTM的总班次。决策树允许在训练期间进行分析，从而得到树路径的访问概率。我们将树节点映射到RTM，以使移位的总数最小。具体来说，我们提出了两种不同的放置方法：1)将树节点紧密打包并均匀放置在单个RTM位置；2)将决策树节点分解为单独的RTM块。我们讨论了这两种方法的理论成本模型，我们正式证明了统一组织的上界是$4× $ 4x，分解组织的上界是$12× $ 12x。我们进行了彻底的实验评估，将我们的算法与最先进的放置策略进行比较。我们的实验评估表明，统一和分解的解决方案分别减少了58.1%和80.1%的移位次数，导致总体运行时间减少了53.8%和46.3%，能耗减少了52.6%和61.7%。
Modern low power distributed systems tend to integrate machine learning algorithms. In resource-constrained setups, the execution of the models has to be optimized for performance and energy consumption. Racetrack memory (RTM) promises to achieve these goals by offering unprecedented integration density, smaller access latency, and reduced energy consumption. However, to access data in RTM, it needs to be shifted to the access port first. We investigate decision trees and develop placement strategies to reduce the total number of shifts in RTM. Decision trees allow profiling during training, resulting in tree paths’ access probabilities. We map tree nodes to RTM so that the total number of shifts is minimal. Concretely, we present two different placement approaches: 1) where tree nodes are closely packed and placed uniformly in a single RTM location and 2) where decision tree nodes are decomposedto separate RTM blocks. We discuss theoretical cost models for both approaches, we formally prove an upper bound of $4\times$4× for the unified and an upper bound of $12\times$12× for the decomposed organization towards the optimal placement. We conduct a thorough experimental evaluation to compare our algorithms to the state-of-the-art placement strategies Our experimental evaluations show that the unified and decomposed solutions reduce the number of shifts by $58.1\%$58.1% and $80.1\%$80.1%, respectively, leading to a $53.8\%$53.8% and $46.3\%$46.3% reduction in the overall runtime and $52.6\%$52.6% and $61.7\%$61.7% reduction in the energy consumption, compared to a naive baseline.