Incremental Learning for Real-time Partitioning for FPGA Applications

Belhedi Wiem, Kammoun Ahmed and Hireche Chabha

Department of Research, Altran Technologies, Rennes, France

Keywords: Hardware/Software Partitioning, Incremental Learning, Classification, Incremental Kernel SVM (InKSVM),
Online Learning.

Abstract: The co-design approach consists in defining all the sub-tasks of an application to be integrated and distributed
on software or hardware targets. The introduction of conventional cognitive reasoning can solve several prob-
lems such as real-time hardware/software classification for FPGA-based applications. However, this requires
the availability of large databases, which may conflict with real-time applications.
The proposed method is based on the Incremental Kernel SVM (InKSVM) model. InKSVM learns incremen-
tally, as new data becomes available over time, in order to efficiently process large, dynamic data and reduce
computation time. As a result, it relaxes the assumption of complete data availability and provides fully au-
tonomous performance.
Hence, in this paper, an incremental learning algorithm for hardware/software partitioning is presented. Start-
ing from a real database collected from our FPGA experiments, the proposed approach uses InKSVM to
perform the task classification in hardware and software. The proposal has been evaluated in terms of classi-
fication efficiency. The performance of the proposed approach was also compared to reference works in the
literature.
The results of the evaluation consist in empirical evidence of the superiority of the InKSVM over state-of-the-
art progressive learning approaches in terms of model accuracy and complexity.

1 INTRODUCTION ware/software partitioning (Shui-sheng et al., 2006),

(Wang et al., 2016), (Zhang Tao and Zhichun, 2017),
Hardware/software partitioning consists of dividing (Ouyang et al., 2017), (Wijesundera et al., 2018),
the application’s computations between those which (Yousuf and Gordon-Ross, 2016).
will be performed by conventional software (that are All these approaches are unique in nature and
sequential instructions) and those that run parallel cir- each offers advantages of its own. However, real-
cuits which will be performed by specific hardware. time applications require unsupervised learning in or-
This is referred to as co-design, the design is twofold, der for a fully autonomous performance (Skliarova
a software design and a hardware design. The co- and Sklyarov, 2019). Hence, in this paper, we
design approach is then to define all the sub-tasks of proposed an unsupervised learning algorithm for
an application to integrate and to distribute them on hardawre/software partitioning. Starting for a real
software or hardware targets (Kammoun et al., 2018). database that was collected from our experimenta-
The automatic partitioning of a system specifica- tions on FPGA, the proposed work makes the use of
tion is a complex issue (considered as a NP-hard prob- Incremental Kernel-SVM in order to perform task-
lem) due to the high number of parameters to account classification into hardware and software. The pro-
for. In addition, it requires adapted computing pow- posal was evaluated in terms of its classification ef-
ers. The problem gets more complicated when work- ficiency and its performance was also compared to
ing on embedded systems that will be subject to real- benchmark approaches.
time constraints, surface consumption, etc. The partitioning category uses an automatic
Faced with the complexity of the software / hard- method; in this case an optimization algorithm, which
ware partitioning problem, several approaches have takes into account all the parameters of the problem,
adopted manual methods to assign each task to the will be adopted.
corresponding entity on architecture. In this work, our goal is to develop an algorithm
Others have been made in regard of hard- that will naturally group the data into two groups:

598
Wiem, B., Ahmed, K. and Chabha, H.
Incremental Learning for Real-time Partitioning for FPGA Applications.
DOI: 10.5220/0010202705980603
In Proceedings of the 13th International Conference on Agents and Artificial Intelligence (ICAART 2021) - Volume 2, pages 598-603
ISBN: 978-989-758-484-8
Copyright c 2021 by SCITEPRESS – Science and Technology Publications, Lda. All rights reserved
 Incremental Learning for Real-time Partitioning for FPGA Applications

hardware tasks and software tasks. Fore this, we use A predefined number of trees grows continuously
in incremental Kernel SVM (InKSVM) to perform the by adding splits whenever enough samples are gath-
task classification in hardware and software. ered within one leaf. Tree ensembles are very popular,
The overall organization of the paper is as follows. due to their high accuracy, simplicity and paralleliza-
After the introduction, we present the various Incre- tion capability.
mental learning methods algorithms that were used In fact, instead of using a predetermined set of
for real-time classification applications in section 2. data at the start, the ORF injects new data during
In section 3, the proposed learning strategy of unsu- the process. It works by creating new trees when-
pervised hardawre/software partitioning is presented. ever there are enough sample based on the result of
In Section 4, experimental results of the proposed ap- existing trees and adds those to the forest.
proach are presented and compared to those given by Incremental Learning Vector Quantization (ILVQ)
benchmark approaches. In Section 5, we summarize (Shui-sheng et al., 2006) extends the Generalized
results from different perspectives and we conclude Learning Vector Quantization (GLVQ) to a dynami-
the paper. cally growing model by continuous insertion of new
prototypes. The (GLVQ)(Liang et al., 2006) is an im-
provement of the basic method in which reference
2 RELATED WORK: vectors are updated based on the steepest descent
method in order to minimize the cost function. The
INCREMENTAL LEARNING cost function is determined so that the obtained learn-
METHODS FOR REAL-TIME ing rule satisfies the convergence condition.
CLASSIFICATION Learn++ (LPP) (Polikar et al., 2001) utilizes an
ensemble of classifiers by generating multiple hy-
Artificial intelligence has drawn great attention in re- potheses using training data sampled according to
cent years and it can be found in many practical ap- carefully tailored distributions. The outputs of the re-
plications, such as (Belhedi and Hannachi, 2020). sulting classifiers are combined using a weighted ma-
However, in real world problems, not all the jority voting procedure. In essence, both Learn++ and
data is always always available at the very begin- AdaBoost which is it inspired by generating an en-
ning. For instance, this is the case for autonomous semble of weak classifiers, each trained using a dif-
systems(e.g.,autonomous driving and robotics) which ferent distribution of training samples. The outputs of
need a continuous adjustment, as new data is avail- these classifiers are then combined using Littlestone’s
able. Moreover, other systems need human feed- majority-voting scheme to obtain the final classifica-
back. In such situations, classic or batch models re- tion rule.
train from scratch, which requires high computational Stochastic Gradient Descent (SGD) (Bottou,
complexity and training time. 2010) As the data size and means of stocking it had
Hence incremental-learning-based algorithms gone up over the last decade, the SGD is an attempt to
were proposed in the literature in order to solve help processing these faster and thus reduces the com-
real-time challenges. puting time, which is the limiting factor in the current
More precisely, for the sake of solving classifica- statistical machine learning methods. A more precise
tion problems for non-linearly separable data, many analysis uncovers qualitatively different tradeoffs for
incremental classifiers have been proposed in the lit- the case of small-scale and large-scale learning prob-
erature. The rest of this section reviews and discusses lems. The large-scale case involves the computational
a selection of Incremental classifiers that are namely: complexity of the underlying optimization algorithm
Online Random Forest (ORF)(Lakshminarayanan in non-trivial ways. Unlikely optimization algorithms
et al., 2014), incremental Learning Vector Quan- such as stochastic gradient descent show amazing per-
tization (ILVQ)(Shui-sheng et al., 2006), Learn++ formance for large-scale problems. In particular, sec-
(LPP)(Polikar et al., 2001), Stochastic Gradient De- ond order stochastic gradient and averaged stochas-
scent (SGD)(Bottou, 2010), and Incremental Extreme tic gradient are asymptotically efficient after a single
Learning Machine (IELM). A performance compara- pass on the training set.
ison of these classifiers with respect to the proposed Incremental Extreme Learning Machine (IELM)
approach is presented in section 4 (Liang et al., 2006) is a variant of the ELM algorithm,
Online Random Forest (ORF) (Lakshminarayanan which are feedforward neural networks for classifica-
et al., 2014) is an incremental version of the Extreme tion and feature learning with a single layer or mul-
Random Forest. In fact, it goes a step further in order tiple layers of hidden nodes, where the parameters of
to refine the prediction. hidden nodes (not just the weights connecting inputs

599
ICAART 2021 - 13th International Conference on Agents and Artificial Intelligence

to hidden nodes) need not be tuned. In OS-ELM, the where αc is the coefficient being incremented of the
parameters of hidden nodes (the input weights and bi- new data point xc outside the initial database. Since
ases of additive nodes or the centers and impact fac- gi = 0 for the margin vectors inside S, the equation 4
tors of RBF nodes) are randomly selected and the out- can be rewritten in matrix form as:
put weights are analytically determined based on the 
∆gc
 
yc Qc,s
  T 
Qc,c
sequentially arriving data. One of the main strength
 
 ∆gs   ys Qs,s  ∆b  QTc,s 
of IELM is its versatility, as it can both handle data  ∆g0  =  y0 Q0,s  ∆αs +∆αc  QT 
c,0
arriving one by one or chunk-by-chunk with varying 0 0 yTs yc
chunk size. (5)
Hence, in equilibrium:
∆b = β∆αc (6)
3 PROPOSED APPROACH
and
Let xi be the training vectors and yi = ±1 are their ∆α j = β j ∆α j , ∀ j ∈ D (7)
corresponding labels. The goal of the SVM-based where the sensitivity coefficients are give by
classification is to find the optimal separating func-
yc
   
tion that reduces to a linear combination of kernels on β
the training data as follows:  βs1   Qs1c 
 .  = −A  .  (8)
N  .   . 
. .
f (x) = ∑ α j K(x j , x) + b (1) βsls Qsls c
j=1

The coefficients α j are obtained by minimizing the Where A = Q−1 and β j = 0 for all j outside S. Hence,
following quadratic objective function subject to the according to the equation 4, the margin change ac-
lagrange multiplier (b) and with the symmetric posi- cording to:
tive definite matrix (Q) constrains: ∆gi = γi ∆αc , ∀i ∈ ∪{c} (9)
min0≤α j ≥C : W = ∑ αi Qi j α j − ∑ αi + b ∑ yi αi (2) where the margin sensitivity γi is expressed as:
i, j i i

Hence, as Q = yi y j K(xi , x j ) is positive definite, and γi = Qic + ∑ Qi j β j + yi β, ∀i ∈

/S (10)
j∈S
K are positive-definite, then the Karush-Kuhn-Tucker
(KKT) condition on the loss function W are sufficient γi = 0 for all i in S.
for optimality and are written as: Hence, IKSVM efficiently updates the previously
≥ 0, i f αi = 0 trained model.
 
 
= 0,
 
dW
gi = = ∑i Qi j α j + yi f (xi ) − 1

dαi
 i f 0 < αi < C

 ≤ 0, otherwise
4 EVALUATION

dW

db = ∑i y j α j = 0 (3)
Hence, the KKT condition divides the dataset into
three sets as:
4.1 Comparison with Incremental
• The first set, S, consists of support vectors that are
Learning Methods
strictly located on the margin (yi f (xi ) = 1).
In order to provide empirical evidence of the supe-
• The second set consists of error support vectors riority of the proposed model, several experiments
that exceed the margin. are conducted. First we have compared it with state-
• The third set consists of non-support vectors. of-the-art incremental learning approaches in terms
Before a new data is added, the KKT condition is sat- of accuracy and model complexity. This experiment
isfied for all the training samples. The key idea is shows the advantages of incremental learning over
to maintain equilibrium on all data points by updating batch learning. For this experiment, tests were con-
the Lagrange multiplier αi in order to satisfy the KKT ducted using several artificial databases whose de-
condition that can be also expressed as: scriptions are reported in Table 1. According to Fig-
ure 1 and Figure 2, the proposed approach provides
∆gi = Qic ∆αc + ∑ j∈S Qi j ∆ j + yi ∆b,
(
better accuracy compared to batch in terms of accu-
∀i ∈ {1, ..., l} ∪ {c} (4) racy values, since incremental models yield a cleaner
∆ dW
db = yc ∆αc + ∑ j∈S ∆α j = 0 solution.

600
 Incremental Learning for Real-time Partitioning for FPGA Applications

In addition, the proposed method is applied for Energy, Allocation, and type (Hardware or Software).
solving industry applications: hardawre/software par- The allocation step is one of the most important
titioning for FPGA-based applications. For this, the in the partitioning process. In fact, by definition, the
database is of a collection of experiments that were Allocation is to find the best set of components which
conducted in Altran Technologies. allows to implement the functionalities of a given sys-
The studied incremental methods are namely: tem. However, the sheer number of available software
Online Random Forest (ORF), Incremental Learn- and hardware makes the task extremely complex.
ing Vector Quantization (ILVQ), Learn++ (LPP), In-
cremental Extreme Learning Machine (IELM) and 4.2.2 Comparison of Partitioning Results with
Stochastic Gradient Descent (SGD). Conventional Approaches

Table 1: Evaluated datasets. The comparison of partitioning results with respect

Incremental Method Description to conventional Approaches is illustrated in Table 2.
Train Test Features Classes
Border 4000 1000 2 3
Results are reported for the proposed method as well
Overlap 3960 990 2 4 as 1)Lee(Lee et al., 2007), 2)Lin(Lin et al., 2006),
Letter 16000 4000 16 26
DNA 1400 1186 180 3 3)GHO(Lee et al., 2009), 4)GA(Zou et al., 2004), as
well as the Hardware orient partition (HOP).
The results illustrated in Table 2 show the superi-
ority of the proposed approach in terms of both accu-
racy and execution time.

5 CONCLUSIONS AND FUTURE

WORK
The problem of software / hardware partitioning is
Figure 1: Comparison against incremental learning meth- approached in many ways depending on the applica-
ods in terms of accuracy. tion and architecture models considered. In this pa-
per, this problem was effectively solved based on AI
algorithms.
In this paper, IKSVM was used. In fact, InKSVM
learns incrementally, as new data becomes available
over time, in order to efficiently process large, dy-
namic data and reduce computation time. As a result,
it relaxes the assumption of complete data availabil-
ity and provides fully autonomous performance as it
efficiently updates the previously trained model.
In order to provide empirical evidence of the su-
periority of the proposed model, several experiments
Figure 2: Comparison against incremental learning meth- are conducted. First we have compared it with state-
ods in terms of model complexity. of-the-art incremental learning approaches in terms
of accuracy and model complexity. This experiment
4.2 Application of Real-time shows the advantages of incremental learning over
batch learning. For this experiment, tests were con-
Hardawre/Software Partitioning for
ducted using several artificial databases whose de-
FPGA-based Applications (Wiem scriptions are reported in Table 1. According to Fig-
et al., 2018) ures 1 and 2, the proposal provides better accuracy
compared to batch in terms of accuracy values, since
4.2.1 Database incremental models yield a cleaner solution.
In addition, the proposed method is applied for
The database is of a collection of experiments that solving industry applications: hardawre/software par-
were conducted in Altran Technologies. As described titioning for FPGA-based applications. For this, the
in (Belhedi and Hannachi, 2020), it consists of sev- database is of a collection of experiments that were
eral tasks with their respective Execution time (ET), conducted in Altran Technologies.

601
ICAART 2021 - 13th International Conference on Agents and Artificial Intelligence

Table 2: Comparison of partitioning results against conventional Approaches.

Exec time (us)

20021.60
20022.26
20151.58
20021.66
20111.26
20066.64
T22
-1

-1
-1
1
1
1
T21

-1
1
1

1
1
1
T20

-1

-1
1
1

1
T19

-1
1
1

1
1
1
T18
-1
-1
-1

-1
1
1
T17

-1
1
1

1
1
1
T16
-1

-1

-1
-1
1

1
T15

-1
1
1

1
1
1
T14

-1
1
1

1
1
1
Partitioning results
T13

-1
-1
-1
1
1

1
T12

-1

-1
1
1

1
1
T11

-1
1
1

1
1
1
T10
-1

-1

-1
1

1
1
-1
-1

-1
T9
1

1
-1
T8
1
1

1
1
1
-1

-1
T7
1
1

1
-1
T6
1
1

1
1
1
-1

-1
T5
1
1

1
-1

-1
-1
-1
-1
T4

1
-1
-1
-1

-1
T3

1
1
-1
-1
-1
-1
T2
1

1
-1

-1
-1
T1
1
1

1
GHO(Lee et al., 2009)
GA(Zou et al., 2004)
Lee(Lee et al., 2007)
Lin(Lin et al., 2006)
Proposed
Methods

HOP

As future work, InKSVM will be implemented on REFERENCES

FPGA for a fully autonomous real-time HW/SW par-
titioning. Belhedi, W. and Hannachi, M. (2020). Supervised hardware
software partitioning algorithms for fpga based appli-
cations. the 12th International Conference on Agents

602
 Incremental Learning for Real-time Partitioning for FPGA Applications

and Artificial Intelligence (ICAART 2020), 2:860– Wijesundera, D., Prakash, A., Perera, T., Herath, K., and
864. Srikanthan, T. (2018). Wibheda: framework for
Bottou, L. (2010). Large-scale machine learning with data dependency-aware multi-constrained hardware-
stochastic gradient descent. In Proceedings of COMP- software partitioning in fpga-based socs for iot de-
STAT’2010, pages 177–186. Springer. vices. In 2018 IEEE 26th Annual International Sym-
posium on Field-Programmable Custom Computing
Kammoun, A., Hamidouche, W., Belghith, F., Nezan, J.-F.,
Machines (FCCM), pages 213–213. IEEE.
and Masmoudi, N. (2018). Hardware design and im-
plementation of adaptive multiple transforms for the Yousuf, S. and Gordon-Ross, A. (2016). An automated
versatile video coding standard. IEEE Transactions hardware/software co-design flow for partially recon-
on Consumer Electronics, 64(4):424–432. figurable fpgas. In 2016 IEEE Computer Society
Annual Symposium on VLSI (ISVLSI), pages 30–35.
Lakshminarayanan, B., Roy, D. M., and Teh, Y. W. (2014).
IEEE.
Mondrian forests: Efficient online random forests. In
Advances in neural information processing systems, Zhang Tao, Zhao Xin, A. X. Q. H. and Zhichun,
pages 3140–3148. L. (2017). Using blind optimization algorithm
for hardware/software partitioning. IEEE Access,
Lee, T.-Y., Fan, Y.-H., Cheng, Y.-M., and Tsai, C.-C. 5:1353–1362.
(2009). Hardware-software partitioning for embed-
ded multiprocessor fpga systems. International Jour- Zou, Y., Zhuang, Z., and Chen, H. (2004). Hw-sw parti-
nal of Innovative Computing, Information and Con- tioning based on genetic algorithm. In Proceedings
trol, 5(10):3071–3083. of the 2004 Congress on Evolutionary Computation
(IEEE Cat. No. 04TH8753), volume 1, pages 628–
Lee, T.-Y., Fan, Y.-H., Cheng, Y.-M., Tsai, C.-C., and 633. IEEE.
Hsiao, R.-S. (2007). Enhancement of hardware-
software partition for embedded multiprocessor fpga
systems. In Third International Conference on In-
telligent Information Hiding and Multimedia Signal
Processing (IIH-MSP 2007), volume 1, pages 19–22.
IEEE.
Liang, N.-Y., Huang, G.-B., Saratchandran, P., and Sun-
dararajan, N. (2006). A fast and accurate online se-
quential learning algorithm for feedforward networks.
IEEE Transactions on neural networks, 17(6):1411–
1423.
Lin, T.-Y., Hung, Y.-T., and Chang, R.-G. (2006). Efficient
hardware/software partitioning approach for embed-
ded multiprocessor systems. In 2006 International
Symposium on VLSI Design, Automation and Test,
pages 1–4. IEEE.
Ouyang, A., Peng, X., Liu, J., and Sallam, A. (2017).
Hardware/software partitioning for heterogenous mp-
soc considering communication overhead. Interna-
tional Journal of Parallel Programming, 45(4):899–
922.
Polikar, R., Upda, L., Upda, S. S., and Honavar, V. (2001).
Learn++: An incremental learning algorithm for su-
pervised neural networks. IEEE transactions on sys-
tems, man, and cybernetics, part C (applications and
reviews), 31(4):497–508.
Shui-sheng, Z., Wei-wei, W., and Li-hua, Z. (2006). A new
technique for generalized learning vector quantization
algorithm. Image and Vision Computing, 24(7):649–
655.
Skliarova, I. and Sklyarov, V. (2019). Hardware/software
co-design. In FPGA-BASED Hardware Accelerators,
pages 213–241. Springer.
Wang, R., Hung, W. N., Yang, G., and Song, X. (2016). Un-
certainty model for configurable hardware/software
and resource partitioning. IEEE Transactions on Com-
puters, 65(10):3217–3223.
Wiem, B., Mowlaee, P., Aicha, B., et al. (2018). Unsuper-
vised single channel speech separation based on opti-
mized subspace separation. Speech Communication,
96:93–101.

603