Implementation Details of Rule-Based Algorithms Using Dataflow

Implementation Details

The main difference between rule based algorithms and decision trees is in representation, where rule based algorithms provide IF THEN statements that are executed sequentially in order provide classification results (Del Jesus, Hoffmann, Navascués, & & Sánchez, 2004). Decision tree algorithms contain vertices with attributes where decisions lead to a particular leaf, which represents an output for a given input. Listing 1 presents a pseudocode for association rule learning algorithm. The presented algorithm is Apriori which performs data pruning by identifying the frequent individual items and extending them to be larger item sets.

Use k-1 itemsets to generate k itemsets
Getting C[k] by joining L[k-1] and L[k-1]
Prune C[k] with subset testing
Generate L[k] by extracting the itemsets in C[k] that satisfy minSup

Iterative nature of the algorithm enables dataflow accelerators utilization by using concepts of streaming data between iterations and creating cyclic execution graphs. This problem can be considered as an aggregated sum, where input from the previous iteration is necessary in the present one. In general a cycle in the dataflow execution graphs arises from a dependence from one iteration to the next one. Figure 1 illustrates the problem of dependency between iterations where the result of one iteration is input for the next iteration.

Figure 1.

An example of a cyclic execution graph where the red pipeline as output of an iteration is used as input for the next iteration.

One of the problems with cyclic graphs is that it is necessary to create pipeline buffers in order to meet deadlines for the frequency (Ali, Akesson, & Pinho, 2015). In essence, each arithmetic or logic unit in the graph takes a certain amount of time to produce the result. For example, multiplication of two floating point numbers on referent hardware could take n ticks to produce the result. Addition of two floating point numbers could take m ticks to produce the result on the same referent hardware, where m < n. If those two results present an input for the next unit it is necessary to create buffers on the output pipeline of the additional unit in order to have both results at the same time at the input of the next unit. Without buffers, one result will arrive before another one, and the result of the next unit will be invalid.

In order to meet deadlines in cyclic execution graphs, developers could create buffers for each unit. However, the compiler has a built-in feature called auto-loop offset that automatically detects offsets and creates buffers where necessary in order to achieve the lowest valid offset for the graph. Listing 2 presents method definitions for creating auto-loop offsets.

Stream.OffsetExpr makeOffsetAutoLoop(String name)
Stream.OffsetExpr makeOffsetAutoLoop(String name, int min size, int max size)
DFEVar Stream.OffsetExpr.getDFEVar(KernelLib design)