Ensemble Boost: Greedy Selection for Superior Recommender Systems

Zainil Mehta
Matriculation Number: 1634574
University of Siegen
Chair: Intelligent Systems Group (ISG)
Supervisor: Prof. Dr.-Ing. Joeran Beel
Advisor: Mr. Tobias Vente
March 2024

###### Abstract

Ensemble techniques have demonstrated remarkable success in improving
predictive performance across various domains by aggregating predictions from
multiple models [1]. In the realm of recommender systems, this research
explores the application of ensemble technique to enhance recommendation
quality. Specifically, we propose a novel approach to combine top-k
recommendations from ten diverse recommendation models resulting in superior
top-n recommendations using this novel ensemble technique. Our method
leverages a Greedy Ensemble Selection(GES) strategy, effectively harnessing
the collective intelligence of multiple models. We conduct experiments on five
distinct datasets to evaluate the effectiveness of our approach. Evaluation
across five folds using the NDCG metric reveals significant improvements in
recommendation accuracy across all datasets compared to single best performing
model. Furthermore, comprehensive comparisons against existing models
underscore the efficacy of our ensemble approach in enhancing recommendation
quality. Our ensemble approach yielded an average improvement of 21.67% across
different NDCG@N metrics and the five datasets, compared to single best model.
The popularity recommendation model serves as the baseline for comparison.
This research contributes to the advancement of ensemble-based recommender
systems, offering insights into the potential of combining diverse
recommendation strategies to enhance user experience and satisfaction. By
presenting a novel approach and demonstrating its superiority over existing
methods, we aim to inspire further exploration and innovation in this domain.

Keywords: Recommender System, Ensembles, Greedy Ensemble Selection, Top-N
recommendations

##  1 Introduction

With the expanding usage of the Internet, individuals face the challenge of
information overflow, characterized by an overwhelming surplus of data that
often leaves users overwhelmed and unable to effectively utilize the available
information to their advantage [5]. Since recommender systems have emerged, it
has revolutionized the way users interact with online platforms. These systems
have become indispensable tools for navigating through immense volume of
information available on the internet, helping users in discovering relevant
information tailored to their preferences and needs [3]. These systems, found
across diverse platform from e-commerce to streaming services, rely on
advanced models to analyze user behavior and provide personalized
recommendations [6]. By analyzing user behavior and historical data,
recommender systems aim to predict items that users are likely to be
interested in, thus facilitating decision-making and enhancing user
experience. Over the years, a range of recommendation technique have been
developed, each with its own strengths and limitations.

However, traditional recommender systems face several challenges that hinder
their effectiveness in delivering personalized recommendations. These
challenges include cold start problems, where new users or items lack
sufficient historical data for accurate recommendations, scalability issues
when dealing with large datasets, and the inability to effectively capture
user preferences in dynamic environments [7]. These limitations underscore the
need for innovative approaches to enhance recommendation quality and address
the evolving needs of users.

Ensembling techniques have emerged as powerful method for improving predictive
performance across various machine learning domains [1]. It involves combining
prediction from various models to produce a more robust and accurate
prediction. By leveraging the diversity of different models and learning
algorithms, ensembles can often outperform best performing individual models,
leading to significant improvement in prediction accuracy and generalization
performance. Many researches now exists showing that ensemble learning often
increases performance [2]. While ensembling has been studied extensively in
classification and regression, its application in recommender system remains
relatively unexplored. This research seeks to bridge this gap by investigating
the integration of ensemble techniques into recommender systems to enhance
recommendation quality.

Therefore, in this paper we investigate the usage of ensemble techniques into
recommeder systems, with a goal of not only enhancing the quality of
recommendations but also diversity of recommendations offered to users through
the utilization of different combinations of recommendation models. An
essential component of ensembles is the combination method, which plays a
pivotal role in combining predictions from multiple models. This method
employs weighted ranking to create the final recommendation list. The method
used here is tested on five datasets namely MovieLens-100k, MovieLens-1m,
ciaodvd, hetrec-lastfm, and citeulike-a. The ten recommendation models are
implicit-matrix factorization, user-knn, item-knn, alternating-least-squares,
bayesian-personalized-ranking, logistic-matrix factorization, item-item-
cosine, item-item-tfidf, item-item-bm25, and popularity.

The approach utilizes Forward Greedy Ensemble Selection [9] to identify the
optimal ensemble combination, aiming to surpass the performance of any
singular recommendation model employed. Each individual recommendation model,
as well as the resulting ensemble, is evaluated and compared on the test
dataset using the NDCG(Normalized-Discounted Cummulative Gain) metric. It is a
widely adopted metric in the field of information retrieval and recommendation
systems [4]. It quantifies the effectiveness of a ranked list by considering
both the relevance of items and their positions in the list. NDCG provides a
normalized measure that ranges between 0 and 1, where higher values indicate
better alignment with user preferences.

Each model has been fine-tuned for specific top-N111N refers to the ndcg@N,
for which the model is optimized  recommendations. Consequently, the ensemble
technique comprises varying top-k222k refers to top-k recommendation taken
into consideration recommendations across different models, but ultimately
considers only the top-N items in the ensemble. The NDCG scores of the
ensemble are assessed for different top-k recommendations, revealing
performance enhancements across almost all scenarios as the k value increases.

The paper is structured as follows: Section 2 provides a review of the related
literature concerning Ensembling and Recommender Systems. In Section 3, we
detail the methodology, focusing on the approach to ensemble combination.
Sections 4 encompass the presentation and discussion of results and
experiments, followed by conlusion of the research in Section 5 .

##  2 Related Work

Ensembling techniques have gained significant attention in various domains for
their ability to enhance predictive performance by combining multiple models
[3]. Caruana et al. [2] demonstrated the effectiveness of ensemble selection
in improving predictive accuracy across diverse datasets. Their work
emphasized the importance of selecting an optimal ensemble of models to
maximize performance. Forouzandeh et al. [3] applied ensemble learning to
recommender systems, specifically focusing on MovieLens dataset. They utilized
graph embedding techniques in conjunction with ensemble learning to improve
recommendation quality. While their approach showcased promising results, it
primarily focused on a specific dataset, leaving room for exploration across
broader datasets and ensemble methods.

Evaluation metrics play a crucial role in assessing the effectiveness of
recommendation algorithms and ensembles. Järvelin and Kekäläinen [4]
introduced the Non-Discounted Cumulative Gain (NDCG) metric, which measures
the relevance of recommended items in ranked lists. This metric has become
widely adopted in evaluating recommendation systems.

In the realm of automated recommender systems, various ensembling techniques
have been explored to enhance the performance of recommendation models. One
notable approach is presented by Vente et al. [9] [8], who introduced LensKit-
Auto, an experimental toolkit within the LensKit framework. Their work
highlights the use of greedy ensemble selection, a method that iteratively
selects the best-performing models to create an ensemble that maximizes
overall recommendation quality. This approach demonstrates significant
improvements in recommendation performance by leveraging the strengths of
multiple algorithms, making it highly relevant to our research on ensembling
techniques in recommender systems.

While existing literature provides insights into ensembling techniques and
their application in recommender systems, our research contributes to this
field by proposing a ensembling approach to combine recommendation algorithms
and its recommendations using GES. Through extensive experimentation on
multiple datasets, we evaluate the effectiveness of our ensemble method in
improving recommendation quality and diversity. By leveraging prior research
and employing ensemble selection strategies, our work contributes to the
ongoing exploration of ensemble-based recommender systems.

##  3 Method

###  3.1 Datasets and Dataset Partitioning

The study utilized five datasets: MovieLens-100k, MovieLens-1m, ciaodvd,
hetrec-lastfm, and citeulike-a, each varying in size. A prediction matrix was
constructed, containing user-item interactions along with the predictions
generated by the various algorithms utilized in the study. Each entry in the
matrix represents the prediction score generated by a specific model for a
given user. The prediction matrix serves as the foundation for evaluating the
performance of individual recommendation algorithms and ensemble technique.

Each dataset is partitioned in five folds and each fold has its training
(60%),validation(20%) and testing subset(20%). The overall performance of each
model and ensembles were then averaged across all folds for each dataset.
Moreover, the prediction matrices were optimized for NDCG@5, NDCG@10, and
NDCG@20 for each dataset. This approach ensured comprehensive assessment
across different subsets of the data, minimizing the risk of overfitting.

###  3.2 Models

Ten recommendation models were employed to generate recommendations tailored
to the characteristics of each dataset. These models included Implicit Matrix
Factorization(I-MF), User-based knn(U-KNN), Item-based knn(I-KNN), Alternating
Least Squares(ALS), Bayesian Personalized Ranking(BPR), Logistic Matrix
Factorization(L-MF), Item-Item-Cosine Similarity(I-I-COSINE), Item-Item-tfidf
Similarity(I-I-TFIDF), Item-Item-BM25 Similarity(I-I-BM25), and Popularity-
based(PPL) Recommender. These models were further used to form ensembles.

###  3.3 Ensemble Method: Weighted Ranking Method

The prediction score of an item assigned by a model estimates the likelihood
or relevance of an item to a given user. A higher prediction score indicates a
higher rank in the recommendation list for that user. The proposed ensemble
technique utilizes a weighted ranking method to combine the predictions of
individual model effectively. This method is based on the principle that
algorithms that performs well, as well as frequently recommended items by
these models, are assigned higher weights in the ensemble.

Each recommender model assigns scores to items for a specific user, with the
score range normalized between 0 and 1 for all models. Additionally, each
model’s performance is measured using NDCG scores on the validation dataset.
NDCG score is the ratio of Discounted Cumulative Gain (DCG) and Ideal
Discounted Cumulative Gain (IDCG) [10]. For each user, if the item is present
in the validation dataset, it has a numerator of 1 and 0 otherwise in the DCG
formula. IDCG is calculated by assuming all items recommended are present in
the validation dataset. The NDCG score of the models is the average of the
NDCG of individual users. The model’s NDCG scores for each fold are further
stored in a dataframe.

$NDCG=\frac{DCG}{IDCG}$

Where:

$DCG=\sum_{i=1}^{n}\frac{{rel_{i}}}{\log_{2}(i+1)}$
$IDCG=\sum_{i=1}^{n}\frac{1}{\log_{2}(i+1)}$

Here, $rel_{i}$ is equal to 1 if the item is in validation dataset and 0
otherwise , and $n$ denotes the total number of items considered.

To prioritize the contribution of each models in the ensemble, models are
arranged in descending order of their NDCG scores, assigning higher weightage
to models with higher performance.

Figure 1: Steps to generate ensembled list of recommendations of each user

For each user and a specific k in the top-k recommendation list, the weighted
ranking score is calculated by multiplying the normalized prediction score of
each model by its overall NDCG score on the validation subset that is stored
in the dataframe. This process is repeated for all ten models. The
recommendation list of top k items, for each model is taken into
consideration. If an item appears in multiple recommendation lists of
different models, its scores are summed up to reflect its collective relevance
across models, which result in assigning higher overall scores to items that
are consistently recommended across multiple models. All unique items receive
scores and are then arranged in descending order of the new weighted ranking
score.

Subsequently, only the top-N333Note: The algorithms used in ensembling have
been optimized for the NDCG@N metric. Considering a larger number of items in
the recommendation list of each model may alter the overall ranking in the
ensemble list. Therefore, we first compile a list of top-k recommendations and
subsequently evaluate only the top-N items for assessment. items, optimized
for specific NDCG@N metrics, are selected to comprise the final ensemble list
for each algorithm. (Figure 1 shows the overview of the ensembling method)

Next, the ensemble list of recommendations for all users is combined, and the
ensemble score is calculated using the NDCG metrics. This novel ensemble
technique aims to leverage the strengths of individual algorithms while
mitigating their weaknesses, ultimately enhancing the quality and diversity of
recommendations provided to users.

###  3.4 Selecting best performing ensemble

Forward Greedy Ensemble Selection (GES) is employed to combine recommendations
from the ten models. Initially, pairs of each models are combined, followed by
combinations of three, four, five, and so on until all models are covered.
Each ensemble is evaluated with the NDCG score using the test subset.

The process of Forward GES is illustrated in Figure 2, which provides an
example of its application with four different models. This iterative approach
allows us to explore a wide range of ensemble combinations systematically.

Figure 2: Example of Forward Greedy Ensemble Selection on four models

Throughout our research, we retain all generated ensemble combinations and
assess their performance individually, which requires considerable
computational resources. This iterative process is repeated across all five
folds of the dataset. The final NDCG score on test subset for each model and
various ensemble combinations is then averaged across all five folds for a
specific dataset.

The ensemble that yields the highest NDCG score represents the outcome of our
ensemble selection method employing Forward Greedy Ensemble Selection. This
approach enables us to identify the most effective combination of models for
generating recommendation lists with enhanced quality and relevance.

###  3.5 Experimental setup

Ensembling is a post processing step, combining strengths and weakness of
different models. The experiments are run on the OMNI cluster of University of
Siegen. The code is written in Python and the main libraries used are pandas,
numpy, and sklearn. A JSON file is used to configure the settings of the
experiment. S-Batch script is used to submit jobs to the cluster. The code is
hosted on the github.

##  4 Results and Discussion

As mentioned before the prediction matrices used for ensebmling have been
optimized for N=5, 10, and 20 in NDCG@N. Here, we undertake a comparative
analysis focusing on the NDCG scores of the top ensemble model against those
of the best-performing individual model. However, it’s imperative to present
results across all models, as their performance may vary across different
datasets. The experimental findings yeilds the following results upon applying
the ensemble method across diverse datasets:

ciaodvd citeulike-a hetrec-lastfm ml-1m ml-100k across-all-datasets % relative
to PPL ALS 0.023 0.076 0.175 0.256 0.253 0.1566 88% BPR 0.013 0.064 0.099 0.11
0.146 0.0864 4% I-MF 0.025 0.126 0.184 0.203 0.193 0.1462 76% I-I-BM25 0.027
0.124 0.199 0.256 0.246 0.1704 105% I-I-COSINE 0.012 0.095 0.201 0.236 0.229
0.1546 86% I-I-TFIDF 0.019 0.109 0.201 0.247 0.236 0.1624 95% I-KNN 0.015 0.11
0.207 0.24 0.236 0.1616 94% L-MF 0.02 0.064 0.155 0.171 0.205 0.123 48% PPL
0.019 0.01 0.079 0.155 0.153 0.0832 0% U-KNN 0.03 0.13 0.184 0.258 0.25 0.1704
105% Ensemble-Method 0.036 0.136 0.215 0.269 0.271 0.1854 123%

Table 1: Comparison of NDCG@5 scores of Individual model and Ensemble Method
across various datasets

ciaodvd citeulike-a hetrec-lastfm ml-1m ml-100k across-all-datasets % relative
to popularity ALS 0.02 0.066 0.147 0.234 0.232 0.1398 84% BPR 0.013 0.027
0.082 0.119 0.173 0.0828 9% I-MF 0.022 0.109 0.159 0.189 0.184 0.1326 75% I-I-
BM25 0.024 0.106 0.168 0.234 0.221 0.1506 99% I-I-COSINE 0.01 0.082 0.169
0.217 0.21 0.1376 82% I-I-TFIDF 0.016 0.094 0.168 0.225 0.218 0.1442 90% I-KNN
0.013 0.096 0.175 0.216 0.212 0.1424 88% L-MF 0.018 0.058 0.135 0.161 0.191
0.1126 49% PPL 0.016 0.009 0.07 0.142 0.142 0.0758 0% U-KNN 0.026 0.112 0.157
0.235 0.225 0.151 99% Ensemble-Method 0.03 0.117 0.183 0.247 0.243 0.164 116%

Table 2: Comparison of NDCG@10 scores of Individual model and Ensemble Method
across various datasets

ciaodvd citeulike-a hetrec-lastfm ml-1m ml-100k across-all-datasets % relative
to PPL ALS 0.016 0.052 0.108 0.199 0.193 0.1136 79% BPR 0.012 0.026 0.078
0.103 0.125 0.0688 9% I-MF 0.018 0.085 0.123 0.167 0.161 0.1108 75% I-I-BM25
0.02 0.08 0.123 0.195 0.186 0.1208 91% I-I-COSINE 0.008 0.063 0.123 0.182
0.173 0.1098 73% I-I-TFIDF 0.013 0.071 0.124 0.188 0.182 0.1156 82% I-KNN
0.011 0.073 0.128 0.176 0.172 0.112 77% L-MF 0.015 0.045 0.102 0.143 0.164
0.0938 48% PPL 0.013 0.007 0.054 0.123 0.12 0.0634 0% U-KNN 0.02 0.084 0.115
0.195 0.187 0.1202 90% Ensemble-Method 0.024 0.097 0.148 0.219 0.211 0.1398
121%

Table 3: Comparison of NDCG@20 scores of Individual model and Ensemble Method
across various datasets

(a) ml-100k

(b) ciaodvd

(c) hetrec-fm

(d) ml-1m

(e) citeulike-a

Figure 3: ”NDCG(@5) Score vs k” across different datasets

(a) ml-100k

(b) ciaodvd

(c) hetrec-fm

(d) ml-1m

(e) citeulike-a

Figure 4: ”NDCG(@10) Score vs k” across different datasets

(a) ml-100k

(b) ciaodvd

(c) hetrec-fm

(d) ml-1m

(e) citeulike-a

Figure 5: ”NDCG(@20) Score vs k” across different datasets

Table 1 2 3 provides a comparison of the NDCG scores for individual algorithms
(optimized specifically for NDCG@5, NDCG@10, and NDCG@20 respectively) and the
ensemble method across the five datasets, along with the average performance
across all datasets and the relative performance compared to a popularity-
based recommender. In the tables, cells highlighted in blue indicate the best-
performing individual model for each dataset, while cells highlighted in green
represent the best-performing model across all models, including the ensemble
method. The Popularity model serves as the baseline. Notably, the Ensemble
method consistently outperforms the best individual model across all datasets,
demonstrating an average improvement of 18% for NDCG@5, 17% for NDCG@10, and
30% for NDCG@20.

In the NDCG@5 table1, the ensemble technique achieves an impressive
performance, outperforming all individual models across the datasets.
Particularly noteworthy is its substantial improvement over the popularity-
based recommender, with a relative performance of 123%. This indicates that
the ensemble method successfully leverages the strengths of individual models
to provide more accurate and relevant recommendations, as evidenced by the
significant increase in NDCG scores across all datasets.

Moving on to the NDCG@10 table2, similar trends are observed, with the
ensemble technique consistently surpassing individual models and demonstrating
a relative performance of 116% compared to the popularity-based recommender.
This further reinforces the effectiveness of the ensemble approach in
enhancing recommendation quality across diverse datasets.

In the NDCG@20 table3, once again, the ensemble technique stands out as the
top performer, showcasing a relative performance of 121% compared to the
popularity-based recommender. This consistent trend across different
evaluation metrics and datasets underscores the robustness and reliability of
the ensemble technique in improving recommendation quality.

Overall, the results highlight the significant impact of the ensemble
technique utilizing the weighted ranking method in enhancing recommendation
quality, showcasing its superiority over best individual model across all
evaluated metrics and datasets.

The ensemble list of recommendations consists of only top N items, which is
derived from top-k list of recommendation of each model. As the ensemble
method is based on weighted ranking score considering different values of k
might alter the ranking of the items for each, resulting in different top-N
list and therefore effecting the NDCG-score.

For instance, when considering N=5, the top-k items (k=5, 10, 15, 25, 50, 75,
100, 125, and 150) refer to recommendation lists containing k items for a
specific user. Each model produces such a list, which is considered during the
ensemble creation process. This process generates a list of k items arranged
in descending order of the new weighted ranking score for each item(blue line
in Figure 3 ). However, since N=5, only the top-5 items are considered, and
the NDCG value is evaluated. This value is then compared to the best-
performing individual model optimized for NDCG@5(yellow line in Figure 3),
forming the basis for comparison.

In each graph representing NDCG@5, NDCG@10, and NDCG@20, the yellow line
corresponds to the NDCG score of the best-performing individual model for the
respective NDCG@N across the dataset. Conversely, the blue line illustrates
the variation of NDCG scores achieved by the ensemble method as k, the number
of recommended items, varies. The shaded band surrounding the lines represents
the confidence interval (95%) for the NDCG scores across the five folds of the
dataset, with its size decreasing proportionally with the dataset’s
magnitude444Size of the dataset: ml-100k <ciaodvd <hetrec-fm <ml-1m
<citeulike-a, indicating higher confidence in the NDCG scores for larger
datasets.

For NDCG@5 figure 3, the graph showcases the fluctuation of NDCG scores across
different values of k for each dataset. The comparison between the
ensemble’s(blue line) and the best-performing individual model’s(yellow line)
NDCG@5 score reveals that the ensemble outperforms the individual model,
highlighting the effectiveness of the ensemble approach in improving
recommendation quality.

Similarly, in the case of NDCG@10 figure 4, a similar trend is observed, with
the variation of NDCG scores depicted across different values of k for each
dataset. Once again, the comparison between the ensemble and the best-
performing individual model underscores instances where the ensemble achieves
superior performance, emphasizing its effectiveness in enhancing
recommendation quality.

Lastly, for NDCG@20 figure 5, once again the comparison between the ensemble
and the best-performing individual model reveals scenarios where the ensemble
outperforms the individual model, further underscoring the effectiveness of
the ensemble approach in augmenting recommendation quality.

These detailed analyses provide valuable insights into the performance of the
ensemble method across different NDCG values and dataset sizes, showcasing its
robustness and superiority over individual models. Through meticulous
evaluation and comparison, we highlight the significance of the ensemble
approach in optimizing recommendation quality, thus contributing to the
advancement of recommender system research and practice.

##  5 Conclusion

This research aimed to explore the efficacy of ensembling techniques in
recommender systems, specifically focusing on devising novel ensemble methods
to outperform the best-performing individual models, along with conducting a
comparative analysis against them. The methodology employed a weighted ranking
approach, aggregating different lists of top-N recommendations to generate a
final ensemble recommendation list.

Results consistently indicate that the ensemble method surpasses the
performance of individual models across all datasets. Moreover, it was
observed that the confidence band of the ensemble method decreases with an
increase in the dataset size. These findings underscore the potential of
ensemble techniques to enhance recommendation systems, similar to their
effectiveness in regression and classification tasks.

The research highlights the importance of applying ensembling in
recommendation systems and its ability to improve results. However, it also
acknowledges the computational intensity of the weighted ranking method, which
necessitates significant time for experimentation.

Our study represents an important step forward in the application of ensemble
techniques to recommender systems. By demonstrating the superiority of
ensembles over individual models, we lay the groundwork for future research
endeavors aimed at enhancing recommendation systems. Our findings underscore
the transformative potential of ensemble techniques in reshaping
recommendation landscapes, providing users with recommendations that align
closely with their preferences and needs.

## References

  * [1] Frank Acito.  Ensemble Models, pages 255–265.  Springer Nature Switzerland, 11 2023.
  * [2] Rich Caruana, Art Munson, and Alexandru Niculescu-Mizil.  Getting the most out of ensemble selection.  In Sixth International Conference on Data Mining (ICDM’06), pages 828–833, 2006.
  * [3] Saman Forouzandeh, Kamal Berahmand, and Mehrdad Rostami.  Presentation of a recommender system with ensemble learning and graph embedding: a case on movielens.  Multimedia Tools Appl., 80(5):7805–7832, feb 2021.
  * [4] Kalervo Järvelin and Jaana Kekäläinen.  Cumulated gain-based evaluation of ir techniques.  ACM Trans. Inf. Syst., 20(4):422–446, oct 2002.
  * [5] Zhixin Pu and Michael A. Beam.  Information overload and user satisfaction: Balance between reliance on recommendations and deliberate news selection, 2021.
  * [6] Francesco Ricci, Lior Rokach, and Bracha Shapira.  Introduction to Recommender Systems Handbook, pages 1–35.  Springer US, Boston, MA, 2011.
  * [7] Andrew I. Schein, Alexandrin Popescul, Lyle H. Ungar, and David M. Pennock.  Methods and metrics for cold-start recommendations.  In Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’02, page 253–260, New York, NY, USA, 2002. Association for Computing Machinery.
  * [8] Tobias Vente, Michael Ekstrand, and Joeran Beel.  Introducing lenskit-auto, an experimental automated recommender system (autorecsys) toolkit.  In Proceedings of the 17th ACM Conference on Recommender Systems, RecSys ’23, page 1212–1216, New York, NY, USA, 2023. Association for Computing Machinery.
  * [9] Tobias Vente, Lennart Purucker, and Joeran Beel.  The feasibility of greedy ensemble selection for automated recommender systems.  COSEAL Workshop 2022, 2022.
  * [10] Yining Wang, Liwei Wang, Yuanzhi Li, Di He, Tie-Yan Liu, and Wei Chen.  A theoretical analysis of ndcg type ranking measures.  Journal of Machine Learning Research, 30, 04 2013.


# Embedded software developments in KM3NeT phase I

V. van Beveren,11footnotetext: Corresponding author. D. Real  T. Chiarusi  D.
Calvo  S. Mastroianni  P. Musico  G. Pellegrini  P. Jansweijer  S. Colonges
C. Bozza  F. Filippini  C. Nicolau  A. Díaz

###### Abstract

The KM3NeT Collaboration has already produced more than one thousand
acquisition boards, used for building two deep-sea neutrino detectors at the
bottom of the Mediterranean Sea, with the aim of instrumenting a volume of
several cubic kilometers with light sensors to detect the Cherenkov radiation
produced in neutrino interactions. The the so-called Digital Optical Modules,
house the PMTs and the acquisition and control electronics of the module, the
Central Logic Board, which includes a Xilinx FPGA and embedded soft processor.
The present work presents the architecture and functionalities of the software
embedded in the soft processor of the Central Logic Board.

## Acronyms

AES

    Audio Engineering Society
ARP

    Address Resolution Protocol
CLB

    Central Logic Board
DAQ

    Data AcQuisition
DHCP

    Dynamic Host Configuration Protocol
DOM

    Digital Optical Module
FPGA

    Field Programmable Gate Array
HDL

    Hardware Description Language
ICMP

    Internet Control Message Protocol
LM32

    LatticeMico32
MAC

    Media Access Control
MCF

    Message Container Format
PMT

    Photo Multiplier Tube
PTP

    Precision Timing Protocol
SRP

    Simple Retransmission Protocol
TDC

    Time to Digital Converter
UDP

    User Datagram Protocol

##  1 Embedded software in the KM3NeT detector

The KM3NeT detector currently being constructed in the Mediterranean Sea[1],
consists of various modules which need to be actively controlled. For this
purpose the Central Logic Board (CLB) and its firmware has been designed
during the first phase (Phase I[2]) of detector construction and deployment.
The CLB is an electronics board with a Xilinx Kintex 7 Field Programmable Gate
Array (FPGA) as central controller. Additionally, it contains an optical
transceiver for network connectivity and, various sensors and connectors for
attaching data acquisition hardware and instrumentation. The design of the CLB
is primarily driven by the need to fit into a KM3NeT Digital Optical Module
(DOM), but it is not specific to it. The CLB is also used as the main
controller in Detector Unit Base (DU-Base), and the Calibration Unit Base (CU-
Base). Depending in which module the CLB is located different firmware can be
loaded, specific to its purpose.

The FPGA firmware contains all digital logic required to perform its function
and is a composition of gateware and embedded software. Gateware is the logic
present inside the programmable logic of the FPGA fabric and generally written
in a hardware description language, while the embedded software is written in
a programming language and running on a processor. The gateware contains three
DAQ units: The Time to Digital Converter (TDC) receiving pulses from the Photo
Multiplier Tubes (PMTs) and conditioning hardware, the Audio Engineering
Society (AES)-standard encoder receiving data from the acoustic sensor (a
hydrophone), and finally MONitoring, which generates run-time performance
metrics each time-slice, a $10\,$ms interval. The Data AcQuisition (DAQ)
modules stream data into the HWStateMachine, which subsequently annotates and
frames the data with each time-slice and finally forwards the data from each
DAQ module to the IPMux in using round-robin scheduler. The IPMux wraps the
annotated data into User Datagram Protocol (UDP) packets and dispatches them
through the WhiteRabbit Precision Timing Protocol (PTP)-core Media Access
Control (MAC) over the seafloor network to the shore data processing facility.
To prevent loss of data buffers are placed in the data-path which fit even the
maximum possible data-rates. In addition to MAC-functions, the WhiteRabbit
core is responsible for providing a detector-wide synchronized clock[3].

The gateware contains two LatticeMico32 (LM32) micro-processors[7], coded in
Hardware Description Language (HDL): the WhiteRabbit processor for timing
control, and the CLB processor for DAQ control and sensor readout. The IPMux
acts as a gateway to the detector network for the CLB LM32 software, allowing
both reception and transmission of Ethernet packets. This channel is used for
the slow-control and for network functions such as Address Resolution Protocol
(ARP), Dynamic Host Configuration Protocol (DHCP) and Internet Control Message
Protocol (ICMP). This work is mostly focused on the CLB LM32 processor, which
runs the KM3NeT specific software. For more information about electronics and
readout, the reader is referred to [4].

The KM3NeT telescope is a heterogeneous detector and there is not one firmware
which can run on all its modules. The firmware comprises of three types of
binaries:

  * •

The hardware specific FPGA bit-file, CLB v2 or CLB v4222CLB v4 is a newer
version of the CLB v2, containing some different peripheral components, due to
either deprecation or feature request..

  * •

The WhiteRabbit embedded software for either a KM3NeT custom version (denoted
as ‘broadcast’) [5], or standard WhiteRabbit.

  * •

The CLB application software which can be either DOM, DU-Base, CU-Base or
Golden, for start-up.

When building the firmware, different combinations of such three-types of
binaries are merged into a single FPGA firmware image, creating multiple
firmware products, each specific to an application and hardware version. The
CLB can store up to four different firmware images, but only two are needed:
The golden image and the run-time image. Though most firmware images are for a
specific module of the detector, the golden image is generic to all modules.
It is the first firmware image loaded after powering the detector and contains
only minimal hardware initialization. Its purpose is to boot the actual run-
time application, but also to allow firmware updates in case the application
requires updates, or is not operational. The run-time image is specific to the
module the CLB is contained in. Firmware update currently is a manual
procedure using an specific firmware update application. The application
checks compatibility before programming the updated image.

The First Generation (FG) of the KM3NeT firmware has been in development since
2012 and was deployed in the beginning of 2016. Since 2019 development of the
Next Generation (NG) Firmware has started, containing many improvements with
respect to the first generation, both in project semantics and program
architecture. Project improvements include usage of modern development
methodologies and tools such as the usage GIT with sub-modules, Continuous
Integration and Docker containers, for a consistent and reusable build
environment. Program architecture improvements include a refined software
state-machine, integration with of the current production version of
WhiteRabbit, and improved error handling. Some of these features which will be
covered in more detail ahead in the text.

##  2 Software Architecture

The KM3NeT embedded software is a bare metal application, using no preemptive
operating system due to the already limited RAM resources and absence of a
threading requirement. When compiled the total program, including runtime
memory, takes up less than $256\,$KiB, limited by available RAM blocks on the
FPGA. The application is mostly written in C with some assembly for start-up
and interrupt handling. The software is split into two main layers: the
system-software layer and the application layer. For each kind of firmware
image the system-software layer is the same. This layer contains OS-like
features, such as a simple cooperative multitasking scheduler, a firmware
update unit, various peripheral drivers, a UDP based network stack and support
utilities for logging and error handling. The application layer contains a
software state-machine and a number of subsystems, each responsible for a
different aspect of the application.

Figure 1: The Next Generation Software State Machine

The state-machine, shown in Figure 1, drives state of the application and
outside of the control of state-machine little application-level code is run.
Implementing the application software as a state-machine obligates the program
to always be in a clear and consistent state. The state-machine can be moved
by issuing events, generally driven over slow-control by the Control Unit[6]
application running on shore. Some events are issued autonomously by the
embedded software, such as when an error occurs or during system start-up. The
application code can be attached to state-machine transitions or to a timer,
which calls the code periodically. In case of software stalling a hardware
watchdog will reboot the system after $60\,$s of inactivity.

As previously mentioned, application code is grouped into _subsystems_. A
subsystem is a unit of code and data responsible for a specific aspect of CLB
operation. It controls hardware peripherals, through a driver abstraction,
associated with that aspect. The following subsystems are known to the CLB
software:

  * •

System – Application function not specific to other subsystems

  * •

Optics – Control of PMTs and TDCs (only in DOM firmware)

  * •

Acoustics – Acoustic sensor and AES control

  * •

Instrumentation – Sensor readout, generally over the i2c bus (Temperature,
humidity, etc.)

  * •

Networking – IPMux control and WhiteRabbit monitoring

  * •

Base – DU-Base container control (only in DU-Base firmware).

By registering C-functions to state transitions a subsystem can control
hardware at specific points in the state-machine graph. For example, the start
event moves the state-machine from Ready to Running. In this transition the
data-acquisition hardware is enabled to start data taking.

The CLB slow control from remote is implemented by means of a custom protocol,
on top of UDP. The Slow-control protocol consists of three layers. The highest
layer is called the Message layer and binds to C-functions at the application
level. Messages have a type, e.g. ‘retrieve firmware version’ or ‘state-
machine event’, but also a class, being either Command, Reply, Event or Error.
The combination of type and class specifies the content format and
interpretation of the message payload. For example, the ‘retrieve firmware
version’ type has no parameters as a Command, but contains a string with the
firmware version as Reply. Slow-control messages are the primary method for
remote control and has functions for moving the software state-machine,
request or set process-variables and many others. Messages are bundled
together at the Message Container Format (MCF) layer, binding multiple
messages into a single payload for efficiency. The lowest slow-control layer
is Simple Retransmission Protocol (SRP) and is responsible for transmission
control. It implements a simple packet-based re-transmission scheme where
packet contains an identifier ordinal which must be acknowledged within a
$200\,$ms window and is otherwise re-transmitted. The message is resend, with
a small delay in between each attempt, to a maximum of 6 times if no
acknowledge is received after which it is deemed lost.

The primary way to set configuration values or get sensor data from remote is
by using the process-variable mechanism. Process-variables are defined in a
json5-formatted[8] variable dictionary file and using a code generation tool
various files representing the variable dictionary for different programming
languages can be generated. For the embedded software C-code is generated for
the defined variables, while for remote Java-code is generated. For the
embedded software all process-variables are exposed as plain-C variables and
are accessible for read and write but from remote access may be restricted
during a run, or in the case of sensor data always be read-only.

##  3 Build environment

The build environment consists of four GIT repositories:

  * •

clb-sw \- Builds program binary for different applications (DOM, DU-Base, CU-
Base and golden) and hardware versions (CLB v2 and v4, due to different
peripherals). It executes tests and builds documentation.

  * •

wrpc-sw \- A special branch of the WhiteRabbit PTP core is maintained and the
program binaries for the WhiteRabbit PTP core for both the standard and the
KM3NeT specific versions is build from this.

  * •

clb-hdl \- Builds the FPGA image binaries (gateware) for different hardware
versions (CLB v2 and v4). This project also uses parts of the WhiteRabbit
gateware respository to build the WhiteRabbit PTP core logic.

  * •

clb \- Includes all of the above projects as GIT sub-modules. It contains the
super-build script which builds all sub-projects and merges all generates
binaries into a number of application and hardware specific firmware images.

CMake is used as the primary build tool. The entire project can be build
inside Gitlab-CI, using a KM3NeT specific docker container.

##  4 Conclusions

The First Generation KM3NeT embedded software has been in development since
2012 and works reliably on the seafloor since 2016 but is now scheduled to be
superseded by the Next Generation KM3NeT firmware. The NG firmware has an
improved software design for consistent control, contains more reliability
features for robust operation and the project now uses modern development
tools for reliable and consistent builds. The NG firmware is currently being
tested and on track to be deployed fall 2021.

## References

  * [1] Adrián-Martínez, S et al., _Letter of intent for KM3NeT 2.0_ , _J. Phys. G: Nuclear and Particle Physics_ 43 (2016)
  * [2] KM3NeT collaboration, _KM3NeT Strategy Report_ (2015)
  * [3] Daniluk, G and Włostowski, T, _White Rabbit: Sub-nanosecond synchronization for embedded system_ , _PTTI_ (2011)
  * [4] Aiello, S et al., _KM3NeT front-end and readout electronics system: hardware, firmware, and software_ , _JATIS_ , 5(4) (2019) arXiv:1907.06453v2
  * [5] Pellegrino, C and Chiarusi, T on behalf of the KM3NeT Collaboration. _The Trigger and Data Acquisition System for the KM3NeT neutrino telescope_ _EPJ Web of Conferences_ 116, 05005 (2016)
  * [6] Aiello, S et al., _The Control Unit of the KM3NeT Data Acquisition System_ , _CPC_ , 256 (2020) arXiv:1910.00112v1
  * [7] LatticeMico32 Open, Free 32-Bit Soft Processor. (2021, July 1). retrieved from https://www.latticesemi.com/en/Products/DesignSoftwareAndIP/IntellectualProperty/IPCore/IPCores02/LatticeMico32.aspx
  * [8] JSON5 - JSON for Humans. (2021, July 1). retrieved from https://json5.org/