# Variability Fault Localization: A Benchmark

Kien-Tuan Ngo, Thu-Trang Nguyen, Son Nguyen, and Hieu Dinh Vo  tuanngokien,
trang.nguyen, sonnguyen<EMAIL_ADDRESS>Faculty of Information Technology,
VNU University of Engineering and Technology, Vietnam

(2021)

###### Abstract.

Software fault localization is one of the most expensive, tedious, and time-
consuming activities in program debugging. This activity becomes even much
more challenging in Software Product Line (SPL) systems due to the variability
of failures in SPL systems. These unexpected behaviors are caused by
variability faults which can only be exposed under some combinations of system
features. Although localizing bugs in non-configurable code has been
investigated in-depth, variability fault localization in SPL systems still
remains mostly unexplored. To approach this challenge, we propose a benchmark
for variability fault localization with a large set of 1,570 buggy versions of
six SPL systems and baseline variability fault localization performance
results. Our hope is to engage the community to propose new and better
approaches to the problem of variability fault localization in SPL systems.

variability bug, variability fault localization, benchmark

††journalyear: 2021††copyright: acmcopyright††conference: 25th ACM
International Systems and Software Product Line Conference - Volume A;
September 6–11, 2021; Leicester, United Kingdom††booktitle: 25th ACM
International Systems and Software Product Line Conference - Volume A (SPLC
’21), September 6–11, 2021, Leicester, United Kingdom††price: 15.00††doi:
10.1145/3461001.3473058††isbn: 978-1-4503-8469-8/21/09††ccs: Software and its
engineering Software product lines

##  1\. Introduction

A Software Product Line (SPL) is the highly configurable system that enables
developers to tailor the family of products from reusable software assets
(Apel et al., 2013a). This can be done by offering numerous features
controlled by options. In Linux Kernel, there are +12K features, which is able
to generate billions of scenarios. Basically, a feature is defined as a unit
of functionality additional to the base software. A set of selections of all
the features (configurations) defines a product. The presence or absence of
some features might require or preclude other features. Feature dependencies
are specified in a feature model which constraints over features and defines
valid configurations (Apel et al., 2013a).

In practice, to verify an SPL system, a subset of all of its valid products is
selected for testing. In order to systematically test a system, various
configuration sampling strategies have been proposed. Some popular sampling
algorithms such as Combinatorial Interaction Testing (Johansen et al., 2012),
One-enabled (Abal et al., 2014), and One-disabled (Abal et al., 2014) can be
used for the configuration selection process. For each selected product, a
test suite is generated to verify its behaviors.

However, the variability that is inherent to SPL systems challenges quality
assurance (QA) (Garvin and Cohen, 2011; Medeiros et al., 2016; Nguyen et al.,
2019). In comparison with non-configurable code, finding bugs through testing
in SPL systems is more problematic as a bug can be variable (so-called
variability bug), which can only be exposed under some combinations of
features (Garvin and Cohen, 2011; Meinicke et al., 2016). In other words, a
system contains variability bugs if among the sampled products, some products
pass all their tests while the others fail. Hence, the buggy statements can
only expose their bugginess in some particular products, yet cannot in others.

Despite the importance of finding variability bugs, the existing fault
localization (FL) approaches are still limited. It is because these techniques
are designed to find bugs in a particular product. To isolate the bugs causing
failures in multiple products of an SPL system, the slice-based methods (Wong
et al., 2016) could be used to identify the failure-related slices for each
product independently of others. Consequently, there are a large number of
statements in the whole system that need to be examined to find the bugs. This
makes the slice-based methods become more impractical in SPL systems (Wong et
al., 2016).

In addition, the state-of-the-art FL technique, Spectrum-Based Fault
Localization (SBFL) (Pearson et al., 2017; Abreu et al., 2007; Keller et al.,
2017) cannot be directly applied for locating variability bugs. Indeed, SBFL
assigns the suspiciousness scores to the statements based on the test
execution information of each product independently of the others. For each
product, it produces a ranked list of statements. As a result, there are
multiple ranked lists for a single system which is failed by variability bugs.
From these lists, developers cannot determine the right starting point to
diagnose the root causes of the system failures.

A naive solution to adapt SBFL for variability bugs in a system is that one
can treat the whole system as a non-configurable code. This can be done by
refactoring the mechanism controlling features in the system (e.g., #ifdef) to
the corresponding if-then statements. By this adaptation, for a faulty system,
a single ranked list of the suspicious statements can be produced according to
their suspiciousness scores. The score of each statement is measured based on
the total number of the passing and failing tests executed by the statement in
all the products. However, this adaptation has two key problems which are
caused by the incompatibility in testing of the different products. First, in
an SPL system, since the roles of a statement in different products are
different, the statement behaves and is expected to behave differently in
these products. Hence, the tests in a product, which are designed to verify
the behaviors of the specific statements in this product, could not be used to
verify the behaviors of those statements yet in another product. Consequently,
counting all the tests in the different products to measure the suspiciousness
of a statement could cause inaccurate assessments. Secondly, for a product
having more tests, it will have more impact on the suspiciousness scores of
the statements in the whole system. This bias increases more clearly for the
cases when the numbers of tests in the products are significantly different.
It is because the total number of the tests used to measure the suspiciousness
of statements in the system is counted from all the products. As a result, the
suspiciousness of a statement in the whole system might not be holistically
measured. Thus, these two problems of this adaptation might cause the
ineffectiveness of SBFL in localizing variability bugs.

To encourage the researchers and practitioners to propose better solutions for
variability fault localization, we contribute a dataset including 1,570 buggy
versions of 6 SPL systems with extensive test suites. In this dataset, there
are 338 versions contain a single bug each and 1,232 versions contain multiple
bugs. The proposed techniques should be evaluated using the following standard
metrics: Rank, EXAM (Wong et al., 2008), Recall at Top-$N$ (Lou et al., 2020),
and PBL (Keller et al., 2017), which are widely applied in the existing FL
studies (Keller et al., 2017; Pearson et al., 2017; Wong et al., 2016; Abreu
et al., 2007; Wong et al., 2008).

namelabel Variability Fault Localization Challenge: Given a faulty SPL system
containing variability bug(s) and a set of its sampled products with the test
suites and test execution data, participants must propose new FL techniques to
locate the buggy statement(s) in the system. The proposed techniques must be
better than our baseline on the standard metrics in FL.

Our benchmark can be found at:

namelabel https://tuanngokien.github.io/splc2021/

##  2\. A Dataset of Variability Faults

Since constructing a dataset of the real variability bugs with corresponding
tests is a considerable task, until now there is no such public dataset. The
available datasets of variability bugs (Abal et al., 2014; Mordahl et al.,
2019; Abal et al., 2018) often lack of test information. Thus, they cannot be
used to evaluate FL techniques which require test execution information.
Additionally, Just et al. (Just et al., 2014) has shown that the performance
of FL techniques on real bugs can be estimated based on their performance on
artificial bugs. That motivates us to propose a dataset of the artificial
variability bugs with the corresponding tests which are systematically
generated. Furthermore, we categorize our dataset by different dimensions of
bugs. Based on that, the proposed FL techniques could be evaluated in some
different circumstances.

###  2.1. Subject Systems

We collected 6 Java SPL systems in SPL2Go 111 http://spl2go.cs.ovgu.de/, which
are widely used in the existing studies about configurable code (Apel et al.,
2013b; Meinicke et al., 2016; Apel et al., 2011), to construct our dataset
(Table 1). In addition, the products of each system are composed by
FeatureHouse (Apel et al., 2011), a popular automated software composer.
Indeed, there are some other systems in SPL2Go, but they raise some errors
while composing and compiling their products. Thus, they cannot be used in our
dataset.

###  2.2. Single Variability Bug Generation

We design a process to systematically generate variability bugs, including
three main steps as shown in Figure 1: Product Sampling and Test Generating,
Bug Seeding, and Variability Bug Verifying.

Step 1 - Product Sampling and Test Generating. Firstly, for an SPL system, a
set of the products of the system is systematically sampled by the existing
techniques (Medeiros et al., 2016; Johansen et al., 2012). Particularly, we
sample a set of valid configurations based on the system’s feature model with
$4$-wise coverage by using SPLCA (Johansen et al., 2012). For each
configuration, a corresponding product is composed from the implementation of
all the enabled features by using FeatureHouse (Apel et al., 2011). For each
product $p$, a test suite is automatically generated using an existing test
generation technique, Evosuite (Fraser and Arcuri, 2011), to capture the
original behaviors of $p$. For each test of $p$, the output will be recorded
and used as the test oracle of the corresponding test in the product having
the same configuration as $p$ in the mutated system in Step 2.

Step 2 - Bug Seeding. To inject a fault into an SPL system, we randomly apply
a modification to the original source code of the system by using a mutation
operator. In essence, the operator changes the original behaviors of several
sampled products. The changes are expected to be captured by the products’
generated tests. In other words, these products produce output that is
different from the output recorded in Step 1. Particularly, we use $\mu$Java
tool (Ma et al., 2006) to create mutants at the statement-level of the
system’s source code. We do not apply any operator which deletes a whole code
statement. Since when the whole statement is removed from the original code,
the buggy statement which is expected to be localized by a FL technique might
not be determined. Hence, we only use the operators modifying or deleting a
part of a statement.

Step 3 - Variability Bug Verifying. In this step, we verify each generated bug
to ensure that the fault is a variability bug and caught by the tests.
Particularly, for each mutated system, the collection of products, which are
corresponding to the same set of the configurations sampled in Step 1, are
composed. After that, we run each of these products against its generated test
suite. A product is considered as a passing product if it passes all the
tests. In contrast, a product, which fails at least one test, is classified as
a failing product. A bug is considered as a variability bug if it causes
failures in certain sampled products. In other words, after testing, among the
sampled products, there are both passing and failing products. Besides, during
the testing process, test execution information will be recorded by a code
coverage tool, OpenClover 222https://openclover.org.

###  2.3. Multiple Variability Bugs Generation

For a more challenging setting, we create a dataset of the buggy systems which
contain multiple variability bugs. Particularly, we extend Step 2 and Step 3
in Figure 1 to generate such dataset:

Multiple Bugs Seeding. In Step 2, instead of applying a single modification, a
random number, $n>1$, of mutation operators are continuously used to mutate
the source code of an SPL system.

Variability Bugs Verifying. In Step 3, all the bugs need to be verified to
ensure that they are variability bugs. Particularly, when one or more bugs are
fixed, the remaining bugs still cause failures in certain products. In other
words, unless all the bugs are fixed, there still exists both the passing and
failing products. We aim to simulate the bug-fixing process in practice. For
each case, we gradually fix each bug by reverting the modification to the
original state and do regression testing. The case would be accepted if there
still exists both the passing and failing products until all the bugs are
fixed.

Figure 1. Bug-Generating Process Overview Table 1. Dataset Statistics System | Details | Test info | Bug info
---|---|---|---
#LOC | #F | #SP | #Tests | Cov | #V | #IF
ZipMe | 3460 | 13 | 25 | 255.0 | 42.9 | 304 | 2.7
GPL | 1944 | 27 | 99 | 86.9 | 99.4 | 372 | 13.0
Elevator-FH-JML | 854 | 6 | 18 | 166.0 | 92.9 | 122 | 3.6
ExamDB | 513 | 8 | 8 | 133.3 | 99.5 | 263 | 1.1
Email-FH-JML | 439 | 9 | 27 | 86.0 | 97.7 | 126 | 4.1
BankAccountTP | 143 | 8 | 34 | 19.8 | 99.9 | 383 | 4.8
#F and #SP stand for the number of features and the average sample size.
Cov and #V stand for the statement coverage (%) and the number of buggy
versions.
#IF stands for the average number of the involving features.

###  2.4. Dataset of Variability Bugs

Table 1 provides the general information of our dataset. For each system, a
set of products are sampled with 4-wise coverage. In general, for an SPL
system, the number of the sampled products depends not only on the number of
features but also the feature model of the system. For instance, although
ExamDB and BankAccountTP have the same number of features, to achieve 4-wise
coverage by sampling technique, BankAccountTP needs to generate 34 products
while this figure for ExamDB is only 8 products.

For generating tests, Table 1 shows that the sizes of the generated test
suites in different systems are different. For example, more than 8.5K test
cases are created for GPL in total. In our dataset, there are 5/6 systems
whose generated test suite reaches +90% statement coverage. Moreover, three of
them almost reach 100% statement coverage. Especially due to a large code
base, ZipMe has 255 tests per product, but its statement coverage only stays
at 42.9%.

As seen in Table 2, we generated 1,570 buggy versions of the subject systems.
Among them, 338 versions contain a single bug each, while 1,232 versions have
two or more bugs. In the dataset, the number of bugs might not be proportional
to the size of systems. For instance, ZipMe contains a larger number of
statements and has more features than ExamDB. However, there are more bugs
generated in ExamDB. The reason is, the number of mutation operators
applicable to ExamDB is greater. Thus, there are more mutants and variability
bugs that can be generated in ExamDB than in ZipMe. Moreover, the quality of
test suite also plays a critical role in generating variability bugs. The test
suite with higher statement coverage is more effective in detecting the
unexpected behaviors caused by the seeded bugs in the system. Hence, for a
system with a better test suite, there might be more variability bugs
accepted.

Figure 2. Variability Bugs by Applied Mutation Operators

Variability Bugs by Applied Mutation Operators. Figure 2 shows the proportions
of the bugs categorized by the groups of mutation operators (Ma and Offutt,
2005). As seen, there are more than haft of them generated by using Arithmetic
group. The reason is, comparing to the other groups, Arithmetic group contains
more mutation operators, such as AODS, AODU, AOIS, AOIU, and AORS (Ma and
Offutt, 2005), that are applicable for mutating the source code of our
selected systems.

Variability Bugs by Code Elements. Figure 3 shows the proportions of the bugs
classified by code element types (Sobreira et al., 2018). As seen, groups of
Conditional and Assignment contain more bugs than the others. These
proportions are similar to the distribution reported by the prior study on the
popular real-fault repository (Sobreira et al., 2018).

Figure 3. Variability Bugs by Code Elements

Variability Bugs by Involving Features. Furthermore, for a specific SPL
system, the performance of FL techniques might be influenced by the number of
features which must be actually enabled/disabled to reveal the bugs (involving
features). In this work, a feature is an involving feature to a variability
bug if from a failing product, when switching its current selection (the state
of being on or off) makes the resulting product pass all its tests. If the
resulting product has not been sampled, we additionally compose the product
and generate its tests. For a system containing multiple bugs, since the
failures in the sampled products are caused by various bugs, detecting the
involving features for each bug in this case might be impossible. For a
particular bug, when one of its involving features is switched, the resulting
product might still fail because of the other bugs. Thus, in our dataset, we
only categorized the buggy versions containing a single bug by the number of
involving features. In our dataset, the number of involving features is in the
range of [1, 25], about 76% of the cases are less than or equal to 7.

Table 2. Buggy versions categorized by number of contained bugs System | Single-Bug | 2-Bug | 3-Bug
---|---|---|---
ZipMe | 55 | 120 | 129
GPL | 105 | 190 | 77
Elevator-FH-JML | 20 | 41 | 61
ExamDB | 49 | 126 | 88
Email-FH-JML | 36 | 34 | 56
BankAccountTP | 73 | 238 | 72

###  2.5. Description of Dataset Artifacts

Our dataset is published on our website with all required information to
evaluate participants’ solutions. In particular, all the cases are organized
in different folders and each represents a version of the entire SPL system.
In each case, artifact structure is as below:

  * •

Feature Model: The feature model is in GUIDSL format (Batory, 2005).

  * •

Sampled Configurations: A set of configurations with $4$-wise coverage which
are saved in different files.

  * •

Source Code: The system and all the composed products. Note that each product
is composed based on feature superimposition mechanism of FeatureHouse (Apel
et al., 2011). For remapping purposes, the link between each code statement in
a product and the corresponding statement in the system is recorded.

  * •

Test Cases: All the generated test cases of each sampled product.

  * •

Bug Report: The locations of modified statements in the system.

  * •

Test Execution: This data is supplied in the execution log, informs how many
times each statement is executed for each test.

##  3\. Solution Evaluation

This section describes several standard metrics to evaluate FL techniques for
variability bugs in SPL systems. Furthermore, we present the results of the
naive adaptation of SBFL technique on the proposed dataset as the baseline
results of this challenge.

###  3.1. Evaluation Metrics

The main focus of FL is to help developers find a good starting point to
inspect and initiate the bug-fixing process. Therefore, the effectiveness of
FL technique generally based on the percentage of code that needs to be
examined until the first faulty location is found. In this challenge, we apply
the standard metrics which are widely used in evaluating FL techniques (Keller
et al., 2017; Pearson et al., 2017; Wong et al., 2016; Abreu et al., 2007;
Wong et al., 2008; Lou et al., 2020).

Rank. The lower Rank, the better approach. If there are multiple statements
having the same scores, buggy statements are ranked last among them. For the
cases of multiple bugs, we measured Rank by the position of the first bug in
the ranked lists.

EXAM. EXAM (Wong et al., 2008) is the percentage of the statements that must
be examined until the first faulty statement is reached:

$EXAM=\frac{\text{Number of examined statements}}{\text{Total number of
statements}}\times 100\%$

Recall at Top-$N$ (Top-$N$). Top-$N$ (Lou et al., 2020) was devised to report
the number of cases that at least one bug was found after examining $N$
statements in the ranked list.

Proportion of Bugs Localized (PBL). PBL (Keller et al., 2017) measures the
proportion of the bugs which are detected after examining a certain number of
the statements in the system.

###  3.2. Baseline Results

To construct baseline results, we conducted several experiments with the naive
adaption of SBFL which considers the whole SPL system as a non-configurable
code. The suspiciousness score of a statement is measured based on the tests
counted from all the products. We use this adaption with different SBFL
metrics (Wong et al., 2016; Abreu et al., 2007) to evaluate the baseline
performance on localizing variability bugs in both single-bug and multiple-bug
settings.

####  3.2.1. Performance in localizing single bug

Table 3. SBFL Performance in Single-bug Setting Metric | ZipMe | GPL | Elevator | ExamDB | Email | BankAccountTP
---|---|---|---|---|---|---
Rank | EXAM | Rank | EXAM | Rank | EXAM | Rank | EXAM | Rank | EXAM | Rank | EXAM
Taratula | 23.98 | 1.03 | 10.36 | 1.07 | 18.40 | 4.11 | 5.61 | 2.24 | 13.81 | 5.59 | 5.53 | 7.23
Ochiai | 18.40 | 0.79 | 9.09 | 0.94 | 8.55 | 1.91 | 3.31 | 1.32 | 4.56 | 1.84 | 3.95 | 5.15
Op2 | 12.67 | 0.55 | 8.86 | 0.92 | 4.25 | 0.95 | 3.24 | 1.29 | 4.03 | 1.63 | 3.58 | 4.66
Barinel | 23.98 | 1.03 | 10.36 | 1.07 | 18.40 | 4.11 | 5.61 | 2.24 | 13.81 | 5.59 | 5.55 | 7.24
Dstar | 18.20 | 0.78 | 9.09 | 0.94 | 8.40 | 1.88 | 3.29 | 1.31 | 4.61 | 1.87 | 3.92 | 5.11
Elevator, Email are the abbreviations for Elevator-FH-JML and Email-FH-JML
systems, respectively.

In this experiment, we use different SBFL metrics to localize the buggy
statements in 338 cases where each case contains only one bug. Table 3 shows
the average Rank and EXAM of SBFL using the 5 most popular SBFL metrics. The
results of other SBFL metrics can be found on our website (web, [n.d.]). As
seen, there are several SBFL metrics that obtained quite similar performance,
such as Tarantula and Barinel, Ochiai and Dstar, etc. Op2 is the most
effective metric which achieves significantly better performance in both Rank
and EXAM compared to the others’ results. Interestingly, the average Rank with
Op2 in most of the systems is around $6^{th}$. Meanwhile, the average Rank in
ZipMe is about $13^{th}$, perhaps because of the low-quality test suites.
Particularly, the average test coverage of a variant in this system is only
about 43% (Table 1). Although the baseline performance with Op2 in the system
ZipMe is worse than in the other systems, it is still better than other SBFL
metrics in ZipMe.

The baseline performance with Op2 in Top-$N$ is illustrated in Figure 4.
Overall, 71 bugs (about 21% of the bugs) are correctly ranked at Top-$1$. In
addition, the number of the detected bugs gradually increases when more
statements in the ranked lists are examined, about 82% of the bugs are ranked
at Top-$5$ accuracy. Interestingly, there are more bugs correctly ranked at
the Top-$1$ positions in GPL than in the other systems (Figure 5). This is
because, for GPL, there is a large number of the sampled products, which
provides more information to locate the bugs. Indeed, among the 71 bugs
correctly ranked first, there are 36 cases are buggy versions of GPL.

Figure 4. Top-$N$, $N\in[1,5]$ of SBFL with Op2 in Single-bug Setting Figure
5. Top-1 of SBFL with Op2 in Single-bug Setting

####  3.2.2. Performance in localizing multiple bugs

We conducted an experiment on 1,232 cases where each buggy version contains
$n$ bugs, $n>1$. Table 4 shows that Ochiai is the most effective metric for
localizing multiple bugs in our dataset. On average, with Ochiai, developers
only need to investigate about 4 statements in the ranked lists to find the
first buggy statement of a faulty system. Meanwhile, this figure with other
SBFL metrics is much worse, e.g., with Op2, which is about 13 statements.

In addition, the performance with Ochiai on Top-$N$ in the multiple-bug
setting is shown in Figure 6 and Figure 7. Overall, about 17% and 92% of the
cases have at least one bug ranked at the Top-$1$ and Top-$5$ positions,
respectively. Among the subject systems, Email is the system in which SBFL
with Ochiai achieved the lowest performance in Top-$1$ (Figure 7). Especially,
by examining the first statement, there is only one case that found the bug.

Furthermore, the average proportion of bugs that are localized in each case by
SBFL with Ochiai is shown in Figure 8. On average, only 7% of the bugs can be
found after examining the first statement. Moreover, by investigating the
first 5 statements in the ranked lists, developers can find 46% of the bugs in
a system. Additionally, in order to find about 80% of the bugs, they need to
examine up to 30 statements in the ranked lists.

Table 4. SBFL Performance in Multiple-bug Setting Metric | ZipMe | GPL | Elevator | ExamDB | Email | BankAccountTP
---|---|---|---|---|---|---
Rank | EXAM | Rank | EXAM | Rank | EXAM | Rank | EXAM | Rank | EXAM | Rank | EXAM
Taratula | 9.04 | 0.39 | 4.08 | 0.42 | 7.98 | 1.78 | 8.21 | 3.27 | 3.53 | 1.43 | 4.92 | 6.36
Ochiai | 5.07 | 0.22 | 2.76 | 0.29 | 4.84 | 1.08 | 2.75 | 1.09 | 3.10 | 1.26 | 2.58 | 3.34
Op2 | 19.91 | 0.85 | 4.60 | 0.48 | 15.93 | 3.56 | 11.48 | 4.57 | 11.73 | 4.75 | 4.24 | 5.48
Barinel | 9.04 | 0.39 | 4.11 | 0.43 | 7.98 | 1.78 | 8.21 | 3.27 | 3.53 | 1.43 | 4.93 | 6.36
Dstar | 7.58 | 0.32 | 2.79 | 0.29 | 4.78 | 1.07 | 2.74 | 1.09 | 2.99 | 1.21 | 2.65 | 3.44
Elevator, Email are the abbreviations for Elevator-FH-JML and Email-FH-JML
systems, respectively.
Figure 6. Top-$N$, $N\in[1,5]$ of SBFL with Ochiai in Multiple-bug Setting
Figure 7. Top-1 of SBFL with Ochiai in Multiple-bug Setting Figure 8. PBL of
SBFL with Ochiai in Multiple-bug Setting

##  4\. Summary

We present a variability fault localization benchmark with a dataset of 1,570
buggy versions of 6 widely-used SPL systems. In our dataset, there are 338
cases of single-bug and 1,232 cases of multiple-bug. The variability bugs in
the benchmark are systematically generated by diverse mutation operators,
numerous code elements, and different numbers of involving features. We also
provide several standard metrics which are broadly applied in evaluating FL
techniques. Furthermore, a naive solution adapting SBFL for variability fault
localization is evaluated to present the baseline results. We hope that our
benchmark can be a common point of comparison for variability fault
localization techniques and encourage the researchers to propose better
solutions for the challenge case.

###### Acknowledgements.

In this work, Kien-Tuan Ngo was funded by Vingroup Joint Stock Company and
supported by the Domestic Master/ PhD Scholarship Programme of Vingroup
Innovation Foundation (VINIF), Vingroup Big Data Institute (VINBIGDATA), code
VINIF.2020.ThS.04. This work has been supported by Vietnam National
University, Hanoi (VNU), under Project No. QG.18.61.

## References

  * (1)
  * web ([n.d.]) [n.d.].  https://tuanngokien.github.io/splc2021/
  * Abal et al. (2014) Iago Abal, Claus Brabrand, and Andrzej Wasowski. 2014\.  42 variability bugs in the linux kernel: a qualitative analysis. In _Proceedings of the 29th ACM/IEEE international conference on Automated software engineering_. 421–432.
  * Abal et al. (2018) Iago Abal, Jean Melo, Ştefan Stănciulescu, Claus Brabrand, Márcio Ribeiro, and Andrzej Wasowski. 2018.  Variability bugs in highly configurable systems: A qualitative analysis.  _ACM Transactions on Software Engineering and Methodology (TOSEM)_ 26, 3 (2018), 1–34.
  * Abreu et al. (2007) Rui Abreu, Peter Zoeteweij, and Arjan JC Van Gemund. 2007\.  On the accuracy of spectrum-based fault localization. In _Testing: Academic and industrial conference practice and research techniques-MUTATION_. IEEE, 89–98.
  * Apel et al. (2013a) Sven Apel, Don Batory, Christian Kstner, and Gunter Saake. 2013a.  _Feature-Oriented Software Product Lines: Concepts and Implementation_.  Springer Publishing Company, Incorporated.
  * Apel et al. (2011) Sven Apel, Christian Kästner, and Christian Lengauer. 2011\.  Language-independent and automated software composition: The FeatureHouse experience.  _IEEE Transactions on Software Engineering_ 39, 1 (2011), 63–79.
  * Apel et al. (2013b) Sven Apel, Alexander Von Rhein, Philipp Wendler, Armin Größlinger, and Dirk Beyer. 2013b.  Strategies for product-line verification: case studies and experiments. In _2013 35th International Conference on Software Engineering_. IEEE, 482–491.
  * Batory (2005) Don Batory. 2005\.  Feature models, grammars, and propositional formulas. In _International Conference on Software Product Lines_. Springer, 7–20.
  * Fraser and Arcuri (2011) Gordon Fraser and Andrea Arcuri. 2011.  Evosuite: automatic test suite generation for object-oriented software. In _Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering_. 416–419.
  * Garvin and Cohen (2011) Brady J Garvin and Myra B Cohen. 2011.  Feature interaction faults revisited: An exploratory study. In _2011 IEEE 22nd International Symposium on Software Reliability Engineering_. IEEE, 90–99.
  * Johansen et al. (2012) Martin Fagereng Johansen, Øystein Haugen, and Franck Fleurey. 2012\.  An algorithm for generating t-wise covering arrays from large feature models. In _Proceedings of the 16th International Software Product Line Conference-Volume 1_. 46–55.
  * Just et al. (2014) René Just, Darioush Jalali, Laura Inozemtseva, Michael D Ernst, Reid Holmes, and Gordon Fraser. 2014.  Are mutants a valid substitute for real faults in software testing?. In _Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering_. 654–665.
  * Keller et al. (2017) Fabian Keller, Lars Grunske, Simon Heiden, Antonio Filieri, Andre van Hoorn, and David Lo. 2017\.  A critical evaluation of spectrum-based fault localization techniques on a large-scale software system. In _2017 IEEE International Conference on Software Quality, Reliability and Security (QRS)_. IEEE, 114–125.
  * Lou et al. (2020) Yiling Lou, Ali Ghanbari, Xia Li, Lingming Zhang, Haotian Zhang, Dan Hao, and Lu Zhang. 2020.  Can automated program repair refine fault localization? a unified debugging approach. In _Proceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis_. 75–87.
  * Ma and Offutt (2005) Yu-Seung Ma and Jeff Offutt. 2005.  Description of method-level mutation operators for java.  _Electronics and Telecommunications Research Institute, Korea, Tech. Rep_ (2005).
  * Ma et al. (2006) Yu-Seung Ma, Jeff Offutt, and Yong-Rae Kwon. 2006.  MuJava: a mutation system for Java. In _Proceedings of the 28th international conference on Software engineering_. 827–830.
  * Medeiros et al. (2016) Flávio Medeiros, Christian Kästner, Márcio Ribeiro, Rohit Gheyi, and Sven Apel. 2016\.  A comparison of 10 sampling algorithms for configurable systems. In _2016 IEEE/ACM 38th International Conference on Software Engineering_. IEEE, 643–654.
  * Meinicke et al. (2016) Jens Meinicke, Chu-Pan Wong, Christian Kästner, Thomas Thüm, and Gunter Saake. 2016\.  On essential configuration complexity: measuring interactions in highly-configurable systems. In _Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering_. 483–494.
  * Mordahl et al. (2019) Austin Mordahl, Jeho Oh, Ugur Koc, Shiyi Wei, and Paul Gazzillo. 2019.  An empirical study of real-world variability bugs detected by variability-oblivious tools. In _Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. 50–61.
  * Nguyen et al. (2019) Son Nguyen, Hoan Nguyen, Ngoc Tran, Hieu Tran, and Tien Nguyen. 2019.  Feature-interaction aware configuration prioritization for configurable code. In _2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 489–501.
  * Pearson et al. (2017) Spencer Pearson, José Campos, René Just, Gordon Fraser, Rui Abreu, Michael D Ernst, Deric Pang, and Benjamin Keller. 2017\.  Evaluating and improving fault localization. In _2017 IEEE/ACM 39th International Conference on Software Engineering (ICSE)_. IEEE, 609–620.
  * Sobreira et al. (2018) Victor Sobreira, Thomas Durieux, Fernanda Madeiral, Martin Monperrus, and Marcelo de Almeida Maia. 2018\.  Dissection of a bug dataset: Anatomy of 395 patches from defects4j. In _2018 IEEE 25th International Conference on Software Analysis, Evolution and Reengineering (SANER)_. IEEE, 130–140.
  * Wong et al. (2008) Eric Wong, Tingting Wei, Yu Qi, and Lei Zhao. 2008\.  A crosstab-based statistical method for effective fault localization. In _2008 1st international conference on software testing, verification, and validation_. IEEE, 42–51.
  * Wong et al. (2016) W Eric Wong, Ruizhi Gao, Yihao Li, Rui Abreu, and Franz Wotawa. 2016.  A survey on software fault localization.  _IEEE Transactions on Software Engineering_ 42, 8 (2016), 707–740.


cited

# Bridging the Gap: FPGAs as Programmable Switches

Thomas Luinaud, Thibaut Stimpfling, Jeferson Santiago da Silva ,
Yvon Savaria,and J.M. Pierre Langlois,
Polytechnique Montréal, Canada
<EMAIL_ADDRESS>First three authors have equally contributed
to this work.This research was partially funded by Mitacs/Canada and
CPNq/Brazil.

###### Abstract

The emergence of P4, a domain specific language, coupled to PISA, a domain
specific architecture, is revolutionizing the networking field. P4 allows to
describe how packets are processed by a programmable data plane, spanning
ASICs and CPUs, implementing PISA. Because the processing flexibility can be
limited on ASICs, while the CPUs performance for networking tasks lag behind,
recent works have proposed to implement PISA on FPGAs. However, little effort
has been dedicated to analyze whether FPGAs are good candidates to implement
PISA.

In this work, we take a step back and evaluate the micro-architecture
efficiency of various PISA blocks. We demonstrate, supported by a theoretical
and experimental analysis, that the performance of a few PISA blocks is
severely limited by the current FPGA architectures. Specifically, we show that
match tables and programmable packet schedulers represent the main performance
bottlenecks for FPGA-based programmable switches. Thus, we explore two avenues
to alleviate these shortcomings. First, we identify network applications well
tailored to current FPGAs. Second, to support a wider range of networking
applications, we propose modifications to the FPGA architectures which can
also be of interest out of the networking field.

###### Index Terms:

FPGA, PISA, P4 language, in-network computing.

##  I Introduction

The P4 language [1] and the Protocol Independent Switch Architecture (PISA)
[2] have paved the road for high performance configurable data planes. P4 is a
domain specific language (DSL) designed to describe how packets are forwarded
on a data plane. PISA, a domain specific architecture associated to P4,
provides a common abstraction to configurable data planes. Figure 1 presents
PISA, a pipeline of configurable blocks (§II-B).

However, current implementations of PISA switches limit the innovation
potential of network architects. Several network applications are difficult to
implement in PISA switches, due to hardware constraints (stateful applications
often require large shared embedded memory) or architectural rigidity (fixed-
function packet scheduler).

Recently, FPGAs have emerged as a platform to accelerate network and server
applications in data centers. As an example, Microsoft has deployed FPGAs in
its data centers [3]. In-network computing has also attracted attention of
FPGA enthusiasts [4].

Following this trend, recent research [5, 6] has also proposed mapping PISA to
FPGAs. The goal is to exploit the inherent FPGA reconfigurability to implement
network applications as new P4 programs can be deployed by simply
reconfiguring the FPGA bitstream. Yet, the performance of FPGA-based PISA
switches are, at best, one order of magnitude lower than that of their ASIC
counterparts.

In this work, we take a step back and we thoroughly analyze how PISA blocks
are implemented in FPGAs to identify the strengths and weaknesses of such
mapping. These theoretical and experimental analyses have led to two major
conclusions. First, some network applications are intrinsically good matches
for FPGA implementation. Second, FPGA devices need to be reengineered to
better support networking applications.

In summary, our contributions are as follows:

  1. 1.

We analyze the mapping of PISA blocks to FPGAs, highlighting the pros and cons
(§III);

  2. 2.

We evaluate, analytically and experimentally, the performance of FPGA-based
PISA switches (§IV);

  3. 3.

We identify which applications are well suited for current FPGAs (§V); and

  4. 4.

We propose the specialization of the FPGA architecture for the network domain
(§VI).

##  II Background

A generic FPGA architecture is first presented. Then, the configurable blocks
of PISA are introduced.

###  II-A FPGA architecture

As shown in Figure 2, FPGAs are structured as an array of blocks
interconnected by a routing fabric. The routing fabric allows to route signals
between the FPGA blocks.

To communicate off-chip, FPGAs integrate configurable Input/Output (I/O)
blocks and dedicated high-speed transceiver pins. Hard-wired PCIe blocks and
MAC blocks, connected to the high-speed transceivers pins, are also integrated
in modern FPGAs.

Logic operations are implemented by Configurable Logic Blocks (CLBs),
distributed over slices. A slice comprises lookup tables (LUTs), which
implement logic functions, and flip-flops (FFs) used to synchronize signals
between logic functions.

In addition, specialized blocks are also hard-wired into FPGAs, such as
Digital Signal Processing (DSP) blocks and Block RAM (BRAM). DSPs perform
arithmetical operations, while BRAMs are width-configurable SRAMs. Hard-wired
blocks avoid wasting CLBs and allow higher clock frequencies.

###  II-B Protocol Independent Switch Architecture

Historically, network switches have been build upon fixed function ASICs as
packets undergo similar and straightforward processing in switch devices.
However, the advent of Software-Defined Networking (SDN) has changed this
state of affairs as it mandates for network programmability.

In this context, the PISA architecture [2] was the first proposal to support
programmable protocol-agnostic packet forwarding. PISA comprises a
programmable parser, a programmable pipeline of match-action tables, a fixed
function packet scheduler, and a configurable deparser. PISA is illustrated in
Figure 1, where blue rectangles are match tables and yellow trapeziums are
Arithmetic and Logical Units (ALUs) implementing actions.

Programmable Parser Packet Scheduler Deparser Figure 1: Reference PISA switch
model

A parser extracts header fields that are used to build lookup keys for the
match-action stages. A key is matched against rules stored in a match table.
The lookup result, an action and an associated data, is executed by an action
stage. A packet scheduler reorders the packet according to a scheduling
algorithm. Finally, a deparser reassembles the updated packet headers and
emits the packet.

##  III Mapping PISA to FPGAs

A typical implementation of PISA on FPGA follows a dataflow architecture,
where the processing is laid out spatially on a pipeline. That is, the
processing is divided into a sequence of operations, where each operation is
mapped onto a portion of the FPGA. Packets are streamed on a data bus
throughout the PISA components. Because a packet size can be larger than the
bus width, a packet can be segmented over the data bus, and can require
multiple clock cycles to traverse a PISA component.

In the next sections, we describe the key components of the PISA architecture
and we discuss their micro-architecture efficiency when implemented on FPGAs.

$\times$$\times$$\times$$\times$Crossbar Routing Fabric DSPBRAMSliceI/O Figure
2: Considered FPGA architecture

###  III-A Programmable Parser

The packet parser extracts header fields to be matched in the match-action
stages, and determines the stack of valid protocols in a switch [7]. The
common approach to implement packet parsers is through an abstract state
machine. The state machine can be represented as a Directed Acyclic Graph
(DAG) in which nodes are protocols and edges indicate protocol transitions.

DAGs are a good fit to FPGAs due to their embarrassingly pipeline-able
characteristic. Also, data flow architectures can be leveraged by the
intrinsic of the FPGA fabric, where logic elements are tightly coupled to
registers improving the pipeline efficiency. In addition, nodes of a packet
parser DAG are compact data structures that easily fit in on-chip memories or
registers. As a result, multiple high-performance programmable packet parsers
have been implemented on FPGAs [8, 9, 10].

###  III-B Match Stage

A match table is an abstract container, holding a collection of keys, actions
and data, addressed by a lookup key. In P4, a match table can be configured
for exact match, ternary match or longest prefix match.

Exact Match (EM). EM is traditionally implemented with content addressable
memory (CAM). A CAM memory is associative array used to find if an exact key
value is stored into a table. Such CAM memories are no longer integrated as
hard blocks in FPGAs and must be emulated.

One approach to CAM emulation is transposed memories, where the lookup key is
used as an address. The memory stores for each lookup key a bitmap of the
matched keys. The transposed approach typically yields a memory efficiency
less than 10% [11, 12].

An efficient approach to implement exact match operations exploits a hash
table combined with Cuckoo hashing for collision resolution, yielding a memory
efficiency higher than 80% [2, 13]. Thus, EM implementation on FPGAs can be
efficient using on-chip memories.

Ternary Match. TCAM are traditionally used for ternary matches. Hardware TCAM
comprises a memory with a match circuitry, to store a ternary rule and match
it against a lookup key and a priority encoder, which returns the matched rule
index with the highest priority. Similarly to CAMs, TCAMs are emulated on
FPGAs.

A memory efficient approach to emulate a TCAM of width $W$ and depth $N$ is to
build $P$ smaller TCAMs using the transposed memory approach. Still, the
memory overhead is $2^{w}/w$, with $w=W/P$.Hence, the overhead is minimal for
a TCAM where $w=1$ or $w=2$, which translates to a depth of 2 or 4. In
practice, this overhead ranges from $8.4\times$ to $65\times$, since current
FPGA memories have a minimum depth of 32 (LUT RAMs) and 512 (BRAMs).

[14] propose to represent ternary rules as logic functions [14], which are
synthesized in LUTs (§ II-A). However, this approach yields a memory
efficiency similar with the transposed memory approach, because a LUT is a
small SRAM that records one result for each possible input. Hence,
implementation of efficient TCAMs on FPGAs remains an open question.

Longest Prefix Match (LPM). LPM is a sub-case of ternary match with two
differences: 1) the mask applies on a contiguous segment of bits, starting
from the least significant bit, 2) when multiple objects match a lookup key,
only the longest prefix matched is returned. Thus, LPM implemented with TCAMs
[15] are achieving a low memory efficiency on FPGAs (§ III-B).

Otherwise, LPM can be emulated with data structures such as binary trees as in
the Xilinx LPM IP. Not only both the memory efficiency and frequency are
improved by 2$\times$, but the resource consumption is reduced by an order of
magnitude over transposed memory. However, the update latency grows linearly
with the number of keys.

Several other data structures proposed in the literature [16, 17], exploit
specific characteristics of the stored key to improve memory efficiency.
However, these methods can hardly be used in systems configured with P4 since
the characteristics of the content of match tables are unknown a priori.

###  III-C Action Stage

Primitive actions are operations natively supported in P4, comprising
arithmetic, logic, bit shifts, and conditional operations.

Arithmetic and logic operations. These operations are, except for the
division, efficiently mapped to the FPGA fabric. Indeed the ALU found in a CPU
is efficiently implemented on FPGA [11]. In addition, modern FPGAs supports
fast multiplications and multiply-and-accumulate operations, as well as adders
with DSPs and hard-wired carry chains. However, division operations on FPGAs
are costly in terms of logic resources, but are quite uncommon in packet
processing. Complex actions combining multiple primitives are well supported
when laid out in a pipeline.

In addition, the reconfiguration capability of FPGAs allow supporting almost
any combination of actions.

Conditional operations. Conditions described in P4 are translated at the
architectural level into multiplexers that select one operation, or result,
out of multiple inputs. While an FPGA slice can be configured as a 16 to 1
multiplexer, very wide multiplexers must be distributed over multiple slices,
which degrades performance with the number of conditions.

Bit-shift operations. Common fixed bit shifts represent no hardware cost when
implemented in FPGA because the shift values are known at compile time, hence,
they are hardwired into the FPGA fabric. Likewise, barrel shifters are poorly
mapped in FPGAs as they are commonly implemented using a chain a muxes. These,
in turn, are uncommon operations in packet processing, therefore, when used,
barrel shifters can be implemented using hard DSP block.

###  III-D Packet Scheduler

A packet scheduler decides at what times and in what orders are packets sent.

The push-in-first-out (PIFO) queue [18] was recently proposed as an
abstraction upon which a programmable packet schedulers can be built. However
the PIFO architecture maps poorly to an FPGA, because a range-search CAM is
required, which can only be emulated either with flip-flops, or with the
transposed memory approach (§III-B).

Alternatively, [19] have proposed a priority queue that better fits to the
FPGA architecture [19]. It exploits the intrinsic parallelism of FPGAs to sort
the packet ranks using a systolic priority queue. However, this work does not
provide the programmability supported by the PIFO.

In addition, a packet buffer is required to store packets while they are
scheduled. Assuming a typical data center
$100\text{\,}\mathrm{\SIUnitSymbolMicro s}$ RTT and one
$100\text{\,}\mathrm{G}\mathrm{bit}\mathrm{/}\mathrm{s}$ interface, an
$1.2\text{\,}\mathrm{M}$B buffer is required. Hence, assuming an FPGA with
12$\times$$100\text{\,}\mathrm{G}\mathrm{bit}\mathrm{/}\mathrm{s}$ interfaces,
a $12\text{\,}\mathrm{M}$B buffer would be required, which would use one
fourth of the on-chip memories available on the largest FPGAs and would stress
the FPGA internal routing fabric (§IV).

###  III-E Deparser

The deparser is a module that performs the inverse of what the parser does as
it reassembles headers in the correct order before sending the packet. Thus, a
deparser is well supported on FPGAs, and the methods used to implement a high
performance parser can be applied [9].

In P416, the deparser is described as a sequence of header emission
statements. The packet header is then recomposed by respecting the order of
valid headers in the sequence. However, the headers validity can be modified
during the match-action stages and current compilers do not lifetime header
analysis to find the smallest combination set of possible valid headers. Thus,
the deparser is more difficult to implement and it tends to have the largest
resource consumption in the P4 pipeline (§ IV-B).

##  IV Scaling the Packet Throughput

High-end FPGAs come with multiple hard-wired $100\text{\,}\mathrm{G}$ Ethernet
MACs, offering a total packet throughput at the I/O level exceeding the
$\text{\,}\mathrm{T}\mathrm{bit}\mathrm{/}\mathrm{s}$ barrier. This raises the
question whether an FPGA can in practice process packets at a
$\text{\,}\mathrm{T}\mathrm{bit}\mathrm{/}\mathrm{s}$.

Because PISA is implemented on FPGAs using a data flow architecture, the
packet throughput supported is directly the product $width_{bus}\times
frequency_{bus}$. Hence, increasing either the bus width, or the bus frequency
directly translates to a higher packet throughput. Another option to scale the
packet throughput is to use parallelism, i.e, to replicate a PISA pipeline. We
first discuss each of the three approaches. Second, based on experimentation,
we present in practice the scaling limitations on FPGAs.

###  IV-A Methods

Scaling the Bus Width. To simplify the discussion, we assume that the minimum
packet size is greater or equal to the bus width. Increasing the bus size
comes at the cost of a higher resource consumption and limits the maximum bus
frequency. Because the bus size is increased, more bits are synchronized and
processed, which directly increases the resource consumption. However, wide
buses ($>$512 bits) increase the routing congestion in FPGAs, leading to
longer wire delays, which directly limits the frequency.

Scaling the Bus Frequency. One method consists in increasing the depth of a
pipeline to reduce the logic delay and wire delay between two flip-fops. The
latency can increase, but the shorter clock periods can be obtained, which
increases the frequency. In theory, the parser, match action tables and
deparser can be heavily pipelined, and thus, the frequency can scale. However,
experimentally, the FPGA architecture limits the frequency scaling (§ IV-B).

Pipeline Replication. Our experiments (§ IV-B) show that the maximum practical
throughput in single pipeline is around
$800\text{\,}\mathrm{G}\mathrm{bit}\mathrm{/}\mathrm{s}$. However, State-of-
the-art FPGAs can support almost twice this throughput as hard
$100\text{\,}\mathrm{G}\mathrm{bit}\mathrm{/}\mathrm{s}$ MAC blocks.

The packet throughput can be increased linearly with the number of PISA
pipelines implemented, at the cost of a linear resource consumption growth.

To exploit the benefits of pipeline replication, a packet dispatcher is
required at both the input and output of the pipelines to distribute the
packet traffic among the pipelines. In addition, the packet dispatcher
integrates buffers in each port to prevent packet drops. The resulting buffers
complexity can be expressed as:

$\displaystyle\mathtt{BufferSize=\frac{Ports}{Pipes}\times MaxPktSize}$
$\displaystyle\mathtt{TotalBufferSize=2\times Ports\times BufferSize}$

where $\mathtt{Pipes}$ is the number of pipelines, $\mathtt{Ports}$ the number
of Ethernet ports, $\mathtt{BufferSize}$ the input/output buffer size per
port, $\mathtt{MaxPktSize}$ the maximum supported packet size, and
$\mathtt{TotalBufferSize}$ the total required buffer size.

Figure 3: FPGA results for test cases from Table I.

###  IV-B Experimental Evaluation

To characterize some FPGA performance limitations, we first evaluate the
impact of the data bus width on the clock frequency. Then, we characterize the
performance of multiple PISA blocks in terms of resource usage and clock
frequencies. The PISA block stressed and the description of each test is
presented in Table I. All the experiments were described in P4111The source
code is available at https://github.com/luinaudt/Unleashing_FPGA. The
implementation was executed with Xilinx SDNet 2017.4 combined with Vivado
2018.2 on a Xilinx Virtex Ultrascale+ FPGA (XCVU9P-flga2577-3-e) with a
targeted clock frequency of $500\text{\,}\mathrm{MHz}$.

Bus width vs frequency. To characterize the bus width impact on the clock
period, the test T0 was implemented with a bus width ranging from 64 to 2048
bits.

As shown in Figure 4, the resource consumption is linear with the bus width,
while the maximum clock frequency decreases for bus larger than 1280 bits.
This frequency deterioration relates to routing congestion and a large net
fan-out. When a routing block is congested, signals are routed to farther
routing blocks, which increases wire delays. In addition, we observe a large
fan out in our tests that limit the maximum clock frequency, even with hyper-
pipelined data paths.

We observe a maximum throughput around
$786\text{\,}\mathrm{G}\mathrm{bit}\mathrm{/}\mathrm{s}$ per implemented
pipeline for a bus width of 2048 bits. As a result, two pipelines are required
to process the I/O bandwidth available on high-end FPGAs.

Stressing PISA. To stress the different PISA blocks, we used a bus width of
2048 bits. The implementation results are presented in Figure 3. The dotted
line shows the clock period required for a throughput of
$600\text{\,}\mathrm{G}\mathrm{bit}\mathrm{/}\mathrm{s}$ per pipeline.

We observe that T1, T2 and T5 have little impact on the clock period. Thus,
increasing the protocol stack and adding more action does not affect
throughput. By contrast, in T3 and in T4, the clock period is increased by
more than 60%. The performance deterioration for T3 does not relate to the CAM
emulation method § III-B, but to the BRAMs distribution over the FPGA fabric.
To implement larger memories, several BRAM blocks are combined. Because, BRAMs
are organized in columns (§ II-A), large memories are spread into multiple
BRAM columns, incurring long wire delays, which decrease the clock period. For
T4, the reduced performance also relates to the use of large distributed RAM
spanning over the FPGA fabric.

Finally, resource consumption increases between T0 and T1, because the
deparser uses more than 80% of all resources. The LUT and FF usage is similar
for T1, T2, T3 and T5, which demonstrates the efficiency of actions performed
on FPGAs. Compared to T1, more BRAMs are used for T3 and T4 to implement the
match tables. T4 uses a high number of LUTs and FF, because of an inefficient
TCAM implementation.

Table I: Test cases to stress the FPGA architecture. Test |  Description |  Stress
---|---|---
T0 |  3 headers, 74 bytes, no tables |  -
T1 |  T0 + 8 headers, 116 bytes |  (De)Parser
T2 |  T1 + IPv4 checksum |  Actions
T3 |  T2 + EM $64\text{\,}\mathrm{k}$ $\times$ 128 bits |  Match tables
T4 |  T2 + TCAM $4\text{\,}\mathrm{k}$ $\times$ 128 bits |  Match tables
T5 |  T2 + 4 chained conditionals |  Actions

##  V FPGAs and In-Network computing

A growing interest in the literature is shown for in-network computing. Our
thesis is that FPGAs are a key component to unlock the potential of this
paradigm. Indeed, FPGAs can support a very high packet throughput in several
cases (§ IV-B). This raises three fundamental questions:

  1. 1.

Which applications can efficiently be implemented in current FPGA?

  2. 2.

Which programming model to use?

  3. 3.

Is PISA sufficient for in-network computing?

Applications tailored to FPGAs. [20] classify in-network computing
applications in three categories: the number of operations per packet, the
number of states per packet and the packet gain [20]. Based on our
experimentations, applications tailored to FPGAs need to perform a high number
of operations per packet, have a limited number of states, but avoid match
tables.

An example of application meeting these criteria is the reduction operation in
a distributed deep neural network (DDNN) training [4]. The DDNN training
consists of computing gradients which are subsequently collected by a
parameter server (PS). The PS aggregates received values with arithmetical
operations, then updates the model and forward it back. Because the PS has a
high number of operations per packet, packets are mainly parsed and forwarded,
this application could support a higher packet throughput over the previously
reported results [4].

Figure 4: Resource consumption and clock period as function of the bus size
for the T0 benchmark.

Programming model. To enforce the abstraction layers, we argue that a network
DSL, such as P4, should be used only to describe packet manipulation, while
the remaining application processing should be expressed with a general-
purpose language. In addition, current high level synthesis tools,
synthesizing a general-purpose language for FPGAs, have shown to achieve
performance close to hand written RTL code [10].

Abusing PISA externs. On FPGAs, an in-network computing application can
consist of PISA connected to an application module. P4 externs allow to
connect external hardware modules to PISA. Hence a generic in-network
computing architecture would integrate standardized interfaces to extern
processing modules.

##  VI Specializing FPGAs

PISA efficiency and performance are currently limited by the existing FPGA
architecture. Notably, the match stages and packet scheduler are the main
performance bottlenecks.

We propose to specialize the FPGA architecture to better support PISA, while
preserving the FPGA’s flexibility for applications outside of the networking
realm.

Hard-wired TCAMs. This would increase resource efficiency and performance of a
ternary match stage.

To evaluate the benefits of hard-wired TCAMs, we analyze the number of
transistors required for a 48$\times$128 TCAM as older Lattice FPGAs had hard-
wired TCAMs using this configuration. It is well established that a single-bit
TCAM requires 16 transistors.Thus, $98\text{\,}\mathrm{k}$ transistors are
needed for the memory and match circuitry in a 48$\times$128 TCAM block. The
cost associated to the priority encoder is ignored as it is negligible.

In contrast, a 1-bit SRAM cell requires 6 transistors. Since soft-TCAMs use
SRAMs, and have a 10$\times$ memory overhead (§ III-B), a 48$\times$128 soft-
TCAM needs $368\text{\,}\mathrm{k}$ transistors. Hence, ignoring the
reconfigurability cost, a hard-wired TCAM could reduce the silicon usage by
3.8$\times$.

Determining the number of TCAM primitives to hard-wire on FPGA is left for
future work, as it relates to the FPGA thermal budget and the TCAM cells used
[2].

More flexible on-chip memory primitives can be as an alternative to hard-wired
TCAMs. The transposed memory approach would directly benefit from shallower
and wider memories. However, wider memories imply large data buses, which have
a direct impact on performance (§IV).

Hard-wired CAM. The motivation to hard-wire CAMs is to better support packet
schedulers, but not for lookup operations. Indeed, the PIFO micro-architecture
[18] requires single cycle CAMs, which are poorly emulated on FPGAs [12]. In
addition, PIFO uses range-search CAMs, where a lookup key must be enclosed in
a range. However, a hard range-search CAM is too specialized to be included as
a generic module.

Hence, we propose to hard-wire configurable CAM primitives supporting $=$, $<$
and $>$ match operations, which brings two benefits. First, multiple CAM
primitives can be combined with programmable logic to construct range search
CAMs. Second, because multiple match operations are supported, other
applications can use it. For instance, soft-CPUs can use the proposed CAM for
cache units, out-of-order scheduling , and applications using sparse matrices,
such as machine learning, to reduce memory footprint.

We now evaluate the CAM size needed for the PIFO architecture. The CAM size
derives from the number of flows and the rank size supported by a packet
scheduler. To support 1024 flows, with a rank size of 16 bits, a range-search
CAM of 1024 $\times$ (16 $\times$ 2) is required [18]. [21] [21] report an
overhead of almost 20$\times$ between a range-search CAM block and its
equivalent size SRAM. However, since the analyzed CAMs are built using flip-
flops, this overhead is over-evaluated by a factor of 3.In addition, because
high-end FPGAs pack hundreds of $\text{\,}\mathrm{Mbit}$ of SRAM, using
hundreds of $\text{\,}\mathrm{kbit}$ of SRAM for CAMs has a very limited
impact.

Dedicated Network on Chip. One solution to limit the signal congestion inside
the routing fabric is to integrate a Network on Chip (NoC). A NoC can be seen
as a grid interconnecting different blocks of the FPGA together. Because a NoC
is hard-wired, it supports high clock frequency, which in turns allows a high
packet throughput as presented by
Achronix222https://www.achronix.com/product/speedster7t/. Also, a NoC simplify
routing complexity by reducing the routing scope.

Hard-wired wide buses. We propose to integrate hard-wired wide buses into the
routing fabric in order to support a high packet throughput. The idea consists
in routing a n-bit bus as a single instance instead of routing individually
each bit of a n-bit bus.

The benefits are multiple. First, it would reduce the signal congestion
observed with wide buses, which limits the frequency.Second, both the
interconnection cost and the configuration memory footprint would be reduced
because a single configuration bit would control a n-bit bus. Hard-wired wide
buses would also ease the routing process for the FPGA tools.

While many applications using byte based structures would benefit from a hard-
wired wide bus, single bit routing level is still required to keep the
flexibility of today’s FPGAs.

##  VII Related Work

FPGA acceleration. FPGAs can drastically improve the CPU usage efficiency,
reduce the computation time, and increase the energy efficiency. [3] have
demonstrated the benefits of FPGAs on applications such as machine learning or
page ranking [3]. For pure network acceleration, the NetFPGA platform has been
introduced. However, it lacked support for programmable data planes. Recently,
[6] demonstrated how to extend the NetFPGA platform to implement programmable
data planes using the Xilinx SDNet compiler [6]. Moreover, many works have
proposed to use FPGAs as SmartNICs [22, 3]. However, these works connect FPGAs
to 40G/50G Ethernet links, which do not stress the FPGA architecture.

FPGA architecture for networking. While [2] highlighted that FPGAs cannot beat
a programmable ASIC because of their inefficient TCAM support and the limited
I/O bandwidth provided, the authors did not study the roots of these
inefficiencies [2]. [23] suggested augmenting the FPGA architecture with hard-
wired CAMs, but their motivation lies in supporting efficient lookup
operations, which differs from our proposal [23]. The Xilinx’s Versal ACAP
[24] architecture integrates a NoC used mainly to route data out of the
programmable logic, but its performance to route data within the programmable
logic is yet unknown.

Compiling network applications to FPGAs. Available commercial and open-source
P4 compilers compile P4 directly to RTL [5, 6]. Another avenue is to exploit a
high-level synthesis tools as an intermediate step [25]. However, none of
these works evaluated the shortcomings of the FPGA architecture for networking
applications.

##  VIII Conclusion

P4 is the language and PISA the architecture that made programmable data plane
a reality. FPGAs, in turn, have recently played an important role for servers
and network offloading in data centers. Some works have also proposed to
implement PISA on FPGAs. However, little effort has been devoted to analyze
whether FPGAs can efficiently implement PISA.

In this paper, we have studied how each PISA block is mapped to the existing
FPGA archicture. Our analysis, supported by experiments, showed that a few
PISA blocks are inefficiently implemented on FPGAs. The root of this
inefficiency lies in FPGA architectures. Still, we identified a set of
networking applications, and in-networking applications that are excellent
matches to current FPGA devices. We also proposed to integrate network
specialized hard-wired blocks, which would significantly improve performance
of FPGA-based PISA switches without sacrificing the flexibility of FPGAs.

## References

  * [1] Pat Bosshart et al.  “P4: Programming Protocol-independent Packet Processors”  In _SIGCOMM Comput. Commun. Rev._ , 2014
  * [2] Pat Bosshart et al.  “Forwarding Metamorphosis: Fast Programmable Match-action Processing in Hardware for SDN”  In _SIGCOMM Comput. Commun. Rev._ , 2013
  * [3] Adrian M Caulfield et al.  “A cloud-scale acceleration architecture”  In _The 49th Annual IEEE/ACM International Symposium on Microarchitecture_ , 2016
  * [4] Youjie Li et al.  “Accelerating Distributed Reinforcement Learning with In-switch Computing”  In _Proceedings of the 46th International Symposium on Computer Architecture_ , 2019
  * [5] Han Wang et al.  “P4FPGA: A Rapid Prototyping Framework for P4”  In _Proceedings of the Symposium on SDN Research_ , 2017
  * [6] Stephen Ibanez, Gordon Brebner, Nick McKeown and Noa Zilberman  “The P4-NetFPGA Workflow for Line-Rate Packet Processing”  In _Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays_ , FPGA ’19, 2019
  * [7] Glen Gibb, George Varghese, Mark Horowitz and Nick McKeown  “Design Principles for Packet Parsers”  In _Proceedings of the Ninth ACM/IEEE Symposium on Architectures for Networking and Communications Systems_ , 2013
  * [8] Michael Attig and Gordon Brebner  “400 Gb/s Programmable Packet Parsing on a Single FPGA”  In _Proceedings of the 2011 ACM/IEEE Seventh Symposium on Architectures for Networking and Communications Systems_ , 2011
  * [9] Pavel Benacek, Viktor Pus, Hana Kubatova and Tomas Cejka  “P4-To-VHDL: Automatic generation of high-speed input and output network blocks”  In _Microprocessors and Microsystems_ , 2018
  * [10] Jeferson Silva, François-Raymond Boyer and J.M. Pierre Langlois  “P4-Compatible High-Level Synthesis of Low Latency 100 Gb/s Streaming Packet Parsers in FPGAs”  In _Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays_ , 2018
  * [11] Henry Wong, Vaughn Betz and Jonathan Rose  “Quantifying the gap between FPGA and custom CMOS to aid microarchitectural design”  In _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , 2013
  * [12] A. M. S. Abdelhadi and G. G. F. Lemieux  “Modular SRAM-Based Binary Content-Addressable Memories”  In _IEEE 23rd Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)_ , 2015
  * [13] Adam Kirsch and Michael Mitzenmacher  “The power of one move: Hashing schemes for hardware”  In _ACM Transactions on Networking_ 18.6 IEEE, 2010
  * [14] P. Reviriego, A. Ullah and S. Pontarelli  “PR-TCAM: Efficient TCAM Emulation on Xilinx FPGAs Using Partial Reconfiguration”  In _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , 2019
  * [15] Ameer MS Abdelhadi, Guy GF Lemieux and Lesley Shannon  “Modular Block-RAM-Based Longest-Prefix Match Ternary Content-Addressable Memories”  In _2018 28th International Conference on Field Programmable Logic and Applications (FPL)_ , 2018
  * [16] Hoang Le and Viktor K Prasanna  “Scalable tree-based architectures for IPv4/v6 lookup using prefix partitioning”  In _IEEE Transactions on Computers_ , 2011
  * [17] G. Retvari et al.  “Compressing IP Forwarding Tables: Towards Entropy Bounds and Beyond”  In _IEEE/ACM Transactions on Networking_ , 2016
  * [18] Anirudh Sivaraman et al.  “Programmable Packet Scheduling at Line Rate”  In _Proceedings of the 2016 ACM SIGCOMM Conference_ , 2016
  * [19] I. Benacer, F. Boyer and Y. Savaria  “A Fast, Single-Instruction–Multiple-Data, Scalable Priority Queue”  In _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , 2018
  * [20] Dan R. K. Ports and Jacob Nelson  “When Should The Network Be The Computer?”  In _Proceedings of the Workshop on Hot Topics in Operating Systems_ , HotOS ’19  New York, NY, USA: ACM, 2019, pp. 209–215
  * [21] Anirudh Sivaraman et al.  “Towards Programmable Packet Scheduling”  In _Proceedings of the 14th ACM Workshop on Hot Topics in Networks_ , HotNets-XIV  New York, NY, USA: ACM, 2015
  * [22] Daniel Firestone et al.  “Azure Accelerated Networking: SmartNICs in the Public Cloud”  In _15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18)_ , 2018, pp. 51–66
  * [23] Adrian Caulfield, Paolo Costa and Manya Ghobadi  “Beyond SmartNICs: Towards a Fully Programmable Cloud”, 2018  URL: https://www.microsoft.com/en-us/research/uploads/prod/2018/05/beyond_smart_nics.pdf
  * [24] Ian Swarbrick et al.  “Network-on-Chip Programmable Platform in Versal TM ACAP Architecture”  In _Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays_ , 2019, pp. 212–221  ACM
  * [25] Nik Sultana et al.  “Emu: Rapid prototyping of networking services”  In _2017 USENIX Annual Technical Conference (USENIX ATC 17)_ , 2017, pp. 459–471