Implementation Details of Decision Tree Algorithms Using Dataflow

Algorithm

This section presents implementation details of the C4.5 algorithm (Hssina, Merbouha, Ezzikouri, & Erritali, 2014) (Dai & Ji, 2014) for decision tree construction. Listing 1 presents a pseudocode of the algorithm that utilizes information theory methods to choose the attribute of the training data that most effectively splits instances into subsets described with labels.

•	Check for the above base cases.
•	For each attribute a, find the normalized information gain ratio from splitting on a.
•	Let a_best be the attribute with the highest normalized information gain.
•	Create a decision node that splits on a_best.
•	Recurse on the sublists obtained by splitting on a_best, and add those nodes as children of node.

Figure 2 presents an example of a decision tree created by the C4.5 algorithm. According to the training data, attribute outlook has the best information gain ratio and thus is in the root of the tree. Leaves in the tree present the class or output of an algorithm which in this case predicts whether an action will be taken.

Figure 1.

An example of a decision tree which predicts whether an action will be taken according to the weather data.

Implementation Details

In order to implement such an algorithm on the dataflow accelerator, the first thing is to encode categorical values to numerical. Numerical values could be stored on the host machine either on card memory and streamed to the accelerator in order to compute information gain for each attribute.

Data streams connect two endpoints and transfer data in ticks between them (Pell, Mencer, Tsoi, & Luk, 2013). Figure 2 illustrates data streams used in the accelerators for streaming variables to the accelerator and back to the host machine or on card memory. In the first tick, the start of the stream presents number 1 while in the second tick stream shifts and next element is 2.

Figure 2.

An example of data streams in dataflow accelerators

Streams enable accessing neighbor elements relative to the head of the stream. It could be beneficial for calculating information gain to access neighbor elements in a stream in order to produce the result faster. They are used in use cases where neighbor elements are necessary for producing the result, as illustrated in Figure 3.

Figure 3.

An example of stream offsets utilization in a matrix

In order to use offsets it is important to determine what type of offsets is needed:

• •

  static offsets have a size fixed at compile-time

• •

  variable offsets have size set at run time before a stream is processed

• •

  dynamic offsets have sizes set at run time during stream processing