B.L.O.: Grounding Decision Trees for Maximum Efficiency on Racetrack Memory

TL;DR

Deploying Machine Learning on the edge requires more than just efficient algorithms; it requires hardware-aware data structures. This paper presents B.L.O. (Bidirectional Linear Ordering), a memory layout technique specifically designed for Decision Trees (DTs) on Racetrack Memory (RTM). By aligning the physical layout of the tree with its probabilistic execution path, the authors reduce memory shift overhead by over 50%, significantly extending the battery life of embedded sensors.

The "Shift" Problem in Racetrack Memory

Racetrack Memory (RTM) is a promising Non-Volatile Memory (NVM) that offers high density and low power. However, it has a unique physical constraint: data is stored on a "track" (nanowire) and must be shifted to a fixed access port before being read.

The performance penalty is proportional to the shift distance. While general heuristics like ShiftsReduce exist, they don't understand the "Rules of the Game" for Decision Trees—namely, that execution always flows from parents to children and then resets to the root for the next sample.

Methodology: Bidirectional Linear Ordering (B.L.O.)

The researchers recognized that Decision Tree execution is a directed traversal. If you place a tree "linearly" (unidirectionally), you might minimize the distance from parent to child, but the jump from a leaf back to the root (for the next inference) becomes massive.

1. The 4x Approximation Guardrail

The authors formally prove that by treating the DT as a rooted tree and applying an Optimal Linear Ordering (O.L.O.) algorithm, the resulting shift count is guaranteed to be no worse than 4 times the theoretical optimum.

2. The Bidirectional Insight

Instead of a simple linear list, B.L.O. splits the tree's left and right subtrees.

• The Left Subtree is reversed.
• The Root is placed in the center.
• The Right Subtree follows in standard order.

This "Bidirectional" placement ensures that regardless of which branch the inference takes, the average distance back to the root is halved compared to a naive start-to-finish layout.

Fig 1: Correction of suboptimal placement by moving the root to a central, bidirectional position.

Experimental Results

The authors tested B.L.O. against standard BFS layouts and the state-of-the-art ShiftsReduce across 8 UCI datasets (e.g., MNIST, Adult, Spambase).

• Shift Reduction: B.L.O. achieved a 65.9% reduction in shifts compared to naive layouts.
• vs. SOTA: It outperformed ShiftsReduce by 54.7% in total shifts for realistic DT configurations.
• Energy & Latency: The hardware-level efficiency translated directly to a 19.2% improvement in both runtime and energy consumption.

Fig 2: Comparison of total shifts across different datasets. B.L.O. consistently stays near the theoretical MIP (Mixed Integer Programming) optimum.

Critical Insight & Conclusion

The genius of B.L.O. lies in its simplicity. By converting a complex hardware placement problem into a classical graph theory problem (O.L.O.) and adding a "bidirectional" mirror, the authors solved a major bottleneck in NVM-based edge computing.

Takeaway: As we move toward AI-on-the-edge, the "Abstract Data Type" and the "Physical Storage Layout" can no longer be decoupled. B.L.O. proves that domain-specific knowledge of an algorithm's traversal pattern is the key to unlocking the true potential of emerging memory technologies like Racetrack Memory.

Limitations

The current approach assumes the tree fits within a single Domain Block Cluster (DBC). For massive trees spanning multiple clusters, the inter-cluster latency might introduce new complexities not fully covered in this bidirectional model.