Anes Bendimerad

Jefrey Lijffijt
email: jefrey.lijffijt@ugent.be

Marc Plantevit
email: marc.plantevit@liris.cnrs.fr

Céline Robardet
email: celine.robardet@liris.cnrs.fr

Tijl De Bie
email: tijl.debie@ugent.be

Tijl De

Contrastive antichains in hierarchies

Keywords: • Mathematics of computing → Information theory, Probabilistic representations, • Computing methodologies → Knowledge representation and reasoning, Learning in probabilistic graphical models, Unsupervised learning Antichains, Subjective Interestingness, Pattern Mining Anes Bendimerad, Jefrey Lijffijt,

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION AND MOTIVATION

Humans typically understand concepts in terms of how they differ from the norm. For example, one might characterize the city of Amsterdam as a city of trams, snack places, and marihuana dispensaries. These are uniquely defining features of Amsterdam, even though it has lots of other features that are far more common (e.g. food venues) but less specific to the city. Another example would be to contrast the American with the French food culture. One might then find that popcorn and Aloe-vera-drinks are highly specific for the American food culture, with fresh foods, pies, and tabbouleh more defining for the French food culture.

In these examples, the concepts of interest (cities, food cultures) are described by values of particular positive integer-valued attributes, to which we will refer as counters. The number of facilities of various types a city has (e.g. number of bars, nightlife spots more generally, bus stops, etc.) is documented e.g. by FourSquare. The extent to which a national food culture relies on various food categories (e.g. beverages, alcoholic beverages more specifically, sugary snacks, etc.) can be found in the OpenFoodFact database.

Such data offers interesting opportunities to uniquely and objectively characterize concepts in terms of such counters. Most immediately, one could use the aggregate of these counters over all concepts, and contrast the counter of a particular concept with that average. The stronger it differs (positively or negatively), the stronger it should characterize that counter. In this way, one could obtain a set of unique aspects of each concept.

A challenge with this approach, however, is that counters are often organized in a hierarchy-a toy example is shown in Fig. 1 for illustration. Indeed, bars are examples of nightlife spots in the FourSquare taxonomy, and alcoholic beverages are particular kinds of beverages in the OpenFoodFact dataset. This means that the characterization can be highly redundant. Moreover, information about one counter can affect one's expectation about another (e.g. the fact that there are lots of bars can be explained by a high number of nightlife spots more generally), which may influence one's expectation about other counters (e.g. this may inflate one's expectation about night clubs).

Hierarchies have been extensively investigated in the literature for decades [START_REF] Aronis | Exploiting Background Knowledge in Automated Discovery[END_REF][START_REF] Dou | Semantic data mining: A survey of ontology-based approaches[END_REF][START_REF] Liu | Towards semantic data mining[END_REF][START_REF] Vavpetic | Semantic Subgroup Discovery Systems and Workflows in the SDM-Toolkit[END_REF]. Most studies have only considered hierarchies to restrain the pattern syntax (i.e., to avoid redundancy) or to take advantage of their subsumption power [START_REF] Aronis | Exploiting Background Knowledge in Automated Discovery[END_REF]. Surprisingly, there has been little discussion about the use of the hierarchical relationships for reasoning in the knowledge discovery task, especially to estimate some counters on some levels of the hierarchy knowing the values of some ancestors.

In this paper, we introduce the problem of characterizing a concept that is described in terms of a set of hierarchically-organized counters, by means of a subset of these counters with distinctive values. Hereby, distinctiveness is assessed with respect to some reference, e.g. the sum total of all concepts, or one concept in particular. To account for the dependencies between the various counters implied by the hierarchy, we propose to focus on subsets that are antichains (sets of incomparable elements) of the hierarchy, called contrastive antichains in this paper. These contrastive antichains pinpoint non-redundant concepts of the hierarchy that are at the same time compact and unexpected. In Figure 1, the set {Food, Bar} is an antichain, because none of these two items is a predecessor of the other one (they are not comparable). This antichain informs the user about the number of Food and Bar venues in the studied dataset. This antichain is informative if the number of Food and Bar venues are different from the expected values by the user.

The main contributions are as follows:

• Section 2 introduces and formalizes the problem of mining contrastive antichains in hierarchically organized sets of counters. • Section 3 formalizes the interestingness of a contrastive antichain with respect to prior beliefs about the values of these counters. These prior beliefs can be derived from a concept with which the concept under investigation needs to be contrasted, or from an aggregate count over all concepts. Section 3.3 in particular shows how the measure of interestingness can take into account the knowledge of previously found contrastive antichains, such that iteratively mined contrastive antichains can be made non-redundant. • Section 4 presents an algorithm to efficiently mine the most contrastive antichains. • Section 5 discusses the most important related work.

• Section 6 empirically evaluates the potential usefulness of contrastive antichains as a tool to gain insight into such data, and evaluate the effectiveness and scalability of the algorithm for mining them.

CONTRASTIVE ANTICHAINS

Here we define the problem setting, along the way introducing the necessary concepts and notation. First we define the kind of data considered, and then the kinds of pattern we are interested in finding in such data.

The data: concepts described as sets of hierarchically related counters

As discussed in the introduction, we consider the relatively common situation where concepts of interest are defined in terms of a set of positive integer-valued attributes, whereby these attributes are organized in a hierarchy. We refer to such attributes as counters. Indeed, often they represent a count of something in relation to that concept, e.g. the number of food venues (the attribute), in a particular city (the concept of interest).

A particular concern in this paper is the fact that these counters are often related in a hierarchy, defined as follows.

Definition 1 (Hierarchy). A hierarchy (or a tree) H is defined as a tuple H = (E, ≤, e 1 ) where:

• E = {e 1 , ..., e n } is a set of items,
• ≤ is a partial order relation defined over this set, • ∀e ∈ E : e 1 ≤ e (the item e 1 is called the root of H ), and • there is only one path from e 1 to any other item:

∀e i , e j , e k ∈ E : e i ≤ e k ∧ e j ≤ e k =⇒ e i ≤ e j ∨ e j ≤ e i .
In Figure 1, the following relations hold: e 1 ≤ e 2 , e 1 ≤ e 3 , and e 2 ≤ e 3 . If e i ≤ e j , then e i is a predecessor of e j , but e i is not necessarily the direct parent of e i . Note that a hierarchy is a special case of a partially ordered set. We assume such a hierarchy, where the items are counters, imposes certain constraints on the values these counters may have. Specifically, we assume that the value of a counter is never strictly larger than the value of a hierarchically smaller counter in the partial order.

For convenience, we introduce the following operations over a hierarchy.

Definition 2 (Basic operations). Given S ⊆ E:

• Precedessors operator ⇑, and successors operator ⇓ as:

⇑ S = {e ∈ E | ∃e ′ ∈ S : e ≤ e ′ }, ⇓ S = {e ∈ E | ∃e ′ ∈ S : e ′ ≤ e},
• Strict predecessor relation: e i < e j ⇔ e i ≤ e j ∧ e i e j , • The direct successor relation ≺ as: e i ≺ e j ⇐⇒⇓ e i ∩ ⇑ e j = {e i , e j }. Also, if e i ≺ e j , we use the notation π i = j to refer to the index of the direct parent of e i (e j = e π i ), • Direct predecessor operator ↑, and direct successors operator ↓ as:

↑ S = {e ∈ E | ∃e ′ ∈ S : e ≺ e ′ }, ↓ S = {e ∈ E | ∃e ′ ∈ S : e ′ ≺ e}, • the leaves L(H ) = {e ∈ E | ∄e ′ : e ≺ e ′ },
• The mimimum of S: min(S) = {e ∈ S | ∄e ′ ∈ S : (e ′ < e)}.

The value of each counter e i ∈ E is denoted using the variable x i , and when a particular empirical value is meant it will be denoted as xi . Note that this means that ∀i ∈ 2, n : x i ≤ x π i as well as xi ≤ xπ i .

Contrastive antichains as patterns

We aim to inform the analyst about the values of a subset of the counters of a concept. As formalized in Section 3, it is our goal to ensure that the patterns of this type are as informative to the data analyst as possible, taking into account the fact that the data analyst has certain prior beliefs about these counters, e.g. based on one or a set of other well-understood concepts with the same sets of counters. As information on a counter directly affects one's expectations about comparable (i.e. hierarchically related) counters (see Section 3 where we make this rigorous), we made the choice of including into the same pattern only non-comparable counters-i.e. no counter is a predecessor or successor of another, and the set of counters forms an antichain of the hierarchy. This ensures in a constructive manner that the information provided by the different counters in the pattern is not too redundant, and ensures that the patterns provide information about a larger part of the hierarchy.

For each counter e i ∈ P, a contrastive antichain pattern informs the data analyst about the value xi . The question arises whether it is of interest to inform the analyst about its precise value. We argue that in many practical cases the precise value gives no more insight than an order of magnitude indication (although probably more detailed than orders of 10). Thus, instead of informing the analyst about the precise value, in this paper we consider the case where the pattern describes just the scale of the count: ⌊log( xi )⌋.

A contrastive antichain pattern can thus be formally defined as: Definition 3 (Contrastive antichains). Given a concept and the value xi for each of a set of counters e i ∈ E which are organized in a hierarchy H = (E, ≤, e 1 ). A contrastive antichain pattern P is specified by a subset of the counters (P ⊆ E) which forms an antichain w.r.t. ≤, i.e., ∀e i , e j ∈ P: e i ≤ e j =⇒ e i = e j , along with the integers ⌊log( xi )⌋ describing the scale of the values of these counters.

THE INTERESTINGNESS OF A CONTRASTIVE ANTICHAIN

For a hierarchy H = (E, ≤, e 1 ), we aim to represent the prior beliefs of the user about the counters e i ∈ E. This will be represented by a probability distribution Pr for the set of random variables X i . We call this distribution the background distribution. In practice, the prior beliefs are derived from one or a number of example concepts and the values of their counters, as explained next.

The background distribution

In this study, we consider that the analyst has some reference that will determine her prior expectations about the counters for the concept under investigation. For instance, if we consider cities as concepts, a Londoner who would like to gain an understanding of the city of Amsterdam in terms of its counters, will typically have prior beliefs determined by the values of those counters in London.

More specifically, we assume that the analyst has an expectation of the value x i of each counter e i ∈ E that is equal to xi , determined by the values of the respective counter in the reference concept.

In addition, we assume that the analyst has specific expectations about the value of each counter (except for e 1 ) relative to its parent counter's value. This can be formalized using the following two types of constraints:

• Expectations: the expectation of each random variable X i is xi :

∀i ∈ 1, n :

x i Pr(x i ) • x i = xi , (1)
• Conditional expectations: The expectation of the ratio of a counter's value over the parent's counter's value, conditional on that parent counter's value, is equal to the observed ratio of these values:

∀i ∈ 2, n :

x i Pr(x i |x π i ) • x i x π i = xi xπ i . (2)
For i > 1, the second type of constraint is arguably a more accurate encoding of the analyst's prior expectations, as it explicitly encodes dependencies of counters conditioned on parent counters. For instance, for cities as concepts and the venues hierarchy, the analyst may expect that 75% of nightlife spots are bars, and knowing the number of nightlife spots will arguably affect the expectation of the number of bars. Moreover, the following property shows that the second constraint essentially subsumes the former, i.e. it is strictly stronger than the former.

Property 1. If the two following sets of conditions hold:

(1) Expectations for only the root:

x 1 Pr(x 1 ) • x 1 = x1 , (2)
Conditional expectations for other nodes: ∀i ∈ 2, n :

x i Pr(x i |x π i ) • x i x π i = xi xπ i , Then it follows that ∀i > 1, x i Pr(x i ) • x i = xi .
This property can be recursively proven, by starting from the first level (nodes e i for which e π i = e 1 ), and using the fact that

x π i Pr(x π i ) • x π i = xπ i .
The detailed proof is given in Appendix A.1 (Supplementary Materials). This means that it suffices to consider the expectation constraint for only the root, in addition to conditional expectation constraints for the other nodes.

Thus we assume that the joint distribution can be written as:

Pr(x 1 , x 2 , . . . , x n ) = Pr(x 1 ) i ∈ 2,n Pr(x i , x π i ). (3)
The constraints on the probability for x 1 and the conditional probabilities of x i conditioned on x π i do not uniquely define the joint probability distribution of all counter values. As proposed in [START_REF] De | Maximum entropy models and subjective interestingness[END_REF], we use distributions that maximize the entropy, as any other distribution effectively makes additional assumptions that reduce the entropy. This means that these marginal distributions are found as the solutions of the following optimization problem:

• For i = 1 (x i is the root): max Pr(x i ) - x i Pr(x i ) log Pr(x i ), s.t. x i Pr(x i )x i = xi , x i Pr(x i ) = 1.
• For i > 1, the distribution Pr(x i |x π i ) needs to maximize the entropy conditional on x π i . Here, we must however recognize that the value x i is derived from its parent counter x π i by determining which of the elements counted as part of x π i also contribute to x i . I.e., the prior expectation is about the tendency of any element contributing to x π i to also contribute to x i . In terms of such decisions for individual elements, there are many ways to arrive at the same count, namely Q(x i , x π i ) = x π i x i ways. Thus, we should use Q(x i , x π i ), the number of ways to realize this counter value, as a base measure, or equivalently, maximize the Kullback-Leibler divergence between the conditional probability Pr(x i |x π i ) and Q(x i , x π i ):

max Pr(x i |x π i ) - x i Pr(x i |x π i ) log Pr(x i |x π i ) Q(x i , x π i ) , s.t. x i Pr(x i |x π i )x i = xi xπ i • x π i , x i Pr(x i |x π i ) = 1.
The solution to the first problem is a geometric distribution [START_REF] De | Maximum entropy models and subjective interestingness[END_REF] having an expectation equal to x1 :

Pr(x 1 ) = 1 - 1 1 + x1 x 1 • 1 1 + x1 = (1 -p 1 ) x 1 • p 1 , with p 1 = 1 1+ x1 .
The solution to the second problem for the other random variables x i (i > 1), is a binomial distribution with an average xi

xπ i • x π i [12]: Pr(x i |x π i ) = x π i x i • xi xπ i x i • 1 - xi xπ i x π i -x i = x π i x i •b x i i •(1-b i ) x π i -x i , where b i = xi xπ i
is the binomial parameter.

Property 2. The marginal distribution for each random variable x i is geometric, and it is:

Pr(x i ) = 1 - 1 1 + xi x i • 1 1 + xi .
We give the proof of Property 2 in Appendix A.1 (Supplementary Materials).

The interestingness of an antichain

We use the framework of subjective interestingness SI proposed in [START_REF] De | Maximum entropy models and subjective interestingness[END_REF], that defines SI (P) as the ratio between the informativeness of a pattern and its description length (cost of communication to the user):

SI (P) = IC(P) DL(P) .
Information content IC: The information carried by a pattern is quantified by the information content [START_REF] De | Maximum entropy models and subjective interestingness[END_REF], a quantity also known as the self-information or surprisal [START_REF] Thomas | Entropy, relative entropy and mutual information[END_REF]. In particular, it is equal to the reduction of uncertainty about the data caused by the knowledge of the pattern, and is defined as follows:

IC(P) = -log(Pr(P)).
As previously discussed, the information content of a pattern is shared with the user by transmitting the scales of the counts appearing in the pattern, instead of the exact values, which can be overwhelming and difficult to remember. Let us define the random variable Y i = ⌊log(X i )⌋, whose true value is ŷi = ⌊log( xi )⌋. The probability associated to a pattern P is thus:

) = e i ∈P Pr(2 ŷi ≤ x i < 2 ŷi +1 ), = e i ∈P (1 -p i ) 2 ŷi -(1 -p i ) 2 ŷi +1 .
Description length DL: The description length measures the complexity of communicating a pattern P to the user. In general, the closer an item e ∈ E is to the root, the more likely the user is to know it. For example in Foursquare hierarchy, it is simpler to communicate the node "Asian Restaurant" (2 nd level) than "Acehnese Restaurant" (4 th level) which is a successor of "Indonesian Restaurant". The idea behind the formulation of DL(P) is to measure the length of the encodings of paths from the root to items e ∈ P such that (1) these paths cover as few as possible items that are not in P, and (2) the paths are as short as possible. To construct the set of paths, we start from the root node e 1 and recursively move to the node children until reaching each item of P. Let S be the set of nodes of the paths. The cost associated to an item e i ∈ S is computed as follows:

(1) If e i is an internal node of the hierarchy and the end-point of a path, its encoding cost is log(α 1 ), with α 1 is the probability that the path "stops" on that node. We encode with the value log(1 -α 1 ) the fact that e i is an internal node of a path. (2) Let α 2 be the probability that e i ∈ P and 1-α 2 the probability that e i is not in P. In the case where e i ∈ P we must also encode the value ŷi . This requires log(A) bits, where A ≥ ŷ1 is an upper bound on values ŷi . By multiplying these quantities with the respective cardinalities (| ⇑ P \ P | for the number of internal nodes of paths and | ↓ (↑ P)| for the end-points of the paths), the total encoding cost of P is: In what follows, we detail, as an example, the computation of DL({e 4 , e 5 , e 6 }) given in Figure 2: • Starting from the root e 1 , we explore its children {e 2 , e 6 , e 9 }.

DL(P) = -| ⇑ P \ P | • log(1 -α 1 ) -| ↓ (↑ P) \ L(H )| • log(α 1 ) -| ↓ (↑ P) \ P | • log(1 -α 2 ) -|P | • (log(α 2 ) + log(A)) .
Then, we consider the node e 2 and explore its children. This requires a cost of -2×log(1-α 1 ) since there are two internal nodes on these paths.

• At that time, the description covers the items {e 3 , e 4 , e 5 , e 6 , e 9 } and thus contains P. Since e 6 and e 9 are not leaves, we need to specify that we stop on them. This takes a cost of -2×log(α 1 ). • We also specify that e 3 , e 9 do not belong to P (with a cost of -2 × log(1 -α 2 )) and that e 4 , e 5 , e 6 belong to P (with a cost of -3 × log(α 2 )). Finally, we add the cost to communicate the ŷi values for each item of P (with a cost of 3 × log(A)).

The overal description length of P is then: Pr(P |O) is the probability that P is present in the data given that the scales of items e i ∈ O are equal to their observed values ŷi :

DL(P) = -2 × log(1 - α 1 ) -2 × log(α 1 ) -2 × log(1 -α 2 ) -3 × (log(α 2 ) + log(A)).

Updating the background knowledge

Pr(P |O) = e i ∈P Pr( ŷi | e j ∈ O ŷj ).
The conditional probabilities Pr( ŷi | e j ∈ O ŷj ) can be computed using the conditional constraints between each x i and its direct ancestor x π i , as expressed by Equation 2. These dependencies between variables Y i constitute a Bayesian tree (i.e., a graphical model representation [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF]) which states that the joint probability between two values of the tree is independent conditionally to the value of their direct ancestor. The probability of a given state (y 1 , ..., y n ) is thus:

Pr(y 1 , ..., y n ) = i ∈ 1,n Pr(y i |y π i ).
The sum-product inference algorithm [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF] can be used to update the background model. In order to use this algorithm, we first need to derive the corresponding factor graph. This can be constructed by making a factor function f 1 defined on Y 1 , and a factor function f i,π i for each pair (y i ,y π i ). The values of these functions are: f 1 (y 1 ) = Pr(y 1 ), and f i,π i (y i , y π i ) = Pr(y i |y π i ) for each (y i , y π i ). Then, the probability of a given state (y 1 , ..., y n ) of this graph is: The sum-product algorithm works only when the random variables have a finite number of states, while in our case y i take their values in N. To make the use of sum-product possible, we can limit the values of x i to an upper bound A > max( x1 , x1 ). If we set A = 2 20 , x i can variate from 0 to 2 20 , and y i from 0 to 20. For example, if values of xi and xi are all lower than 2 15 , it can be sufficient to set A = 2 20 , since Pr (y i > 20) will be extremely small and negligible. Before running sum-product, we prepare the values of f 1 for each y 1 ∈ 0, log(A) , and the value of each f i,π i for each (y i , y π i ) ∈ 0, log(A) 2 :

Pr(y 1 , ..., y n ) = f 1 (y 1 ) • i ∈ 2,n f i,π i (y i , y π i ).
• For the factor f 1 , the computation can be done in constant time using the CDF of the geometric distribution:

f 1 (y 1 ) = Pr(2 y 1 ≤ x 1 < 2 y 1 +1 ) = (1 -p 1 ) 2 y 1 -(1 -p 1 ) 2 y 1 +1 .
• For the other factor functions, we have:

f i,π i (y i , y π i ) =Pr(y i |y π i ) = Pr(y i ∧ y π i ) Pr(y π i ) , = 2 yπ i +1 -1 x π i =2 yπ i Pr(x π i ) • Pr(2 y i ≤ x i < 2 y i +1 |x π i ) Pr(2 y π i ≤ x π i < 2 y π i +1
) .

And:

Pr(2 y π i ≤ x π i < 2 y π i +1 ) = (1 -p i ) 2 y i -(1 -p i ) 2 y i +1 , Pr(2 y i ≤ x i < 2 y i +1 |x π i ) = I 1-b i (x π i -2 y i +1 -1, 2 y i +1 ) -I 1-b i (x π i -2 y i -1, 2 y i ),
with I α (m -k, k + 1) is the regularized incomplete beta function which can be efficiently approximated [START_REF] Smith | Algorithm 814: Fortran 90 software for floating-point multiple precision arithmetic, gamma and related functions[END_REF].

The complexity for computing all the factor function values is in O(|E|•A•log(A)), and the memory complexity is O(|E|•log(A) 2 ). The computation of factor functions can be done once for the studied hierarchy, in order to be used repeatedly by sum-product each time we need to update the model. Sum-product can be applied as explained in [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF]. The time complexity of this algorithm is O(|E| • log(A) 2 ), we recall that |E| is the number of random variables Y i , and log(A) 2 is the number of possible values of each pair (y i , y π i ).

FINDING THE MOST INTERESTING CONTRASTIVE ANTICHAINS

Finding contrastive antichains is computationally hard: the number of antichains in a rooted tree of order n is at most 2 n-1 +1, as shown by Klazar in [START_REF] Klazar | Twelve countings with rooted plane trees[END_REF]. Also, the interestingness of a contrastive antichain is a ratio of two measures, IC and DL, that vary unpredictably from one pattern to another and for which it is not straightforward to derive non-trivial bounds on their values to prune some uninteresting antichains. Nonetheless, we derive MICA-Miner, a heuristic algorithm based on a greedy strategy, which has a polynomial worst case complexity (i.e., O |E| f 1 and f i,π i (for each i ∈ 2, n ) are already computed based on the approach explained in Section 3.3. MICA-Miner is an iterative algorithm that, at each iteration, updates the model using the sum-product algorithm for integrating the previously observed nodes O. It then produces an antichain P based on GreedySearch. MICA-Miner continues until GreedySearch returns an empty pattern, which means that IC(e) = 0 ∀e ∈ E.

In order to greedily build an antichain, GreedySearch starts from an empty pattern P = ∅ and a set of candidates C = E. It also uses a set Q that contains the current paths endpoints, i.e., Q contains the already known part of ↓ (↑ P), and Q will be equal to ↓ (↑ P) at the end of GreedySearch. In each step, GreedySearch chooses an item that will be added to Q and possibly to P, and removed from C (as well as its predecessors and successors). In order to decide which item to pick in each step, GreedySearch uses a heuristic IC DL where DL is defined for an antichain P and a set Q s.t. P ⊆ Q ⊆↓ (↑ P). DL is similar to DL, the difference is that DL does not account for the cost of all the paths endpoints ↓ (↑ P), but only for Q, the already known part of the final ↓ (↑ P):

DL(P, Q) = -| ⇑ P \ P | • log(1 -α 1 ) -|Q \ L(H )| • log(α 1 ) -|Q \ P | • log(1 -α 2 ) -|P | • (log(α 2 ) + log(A)) .
At each iteration, GreedySearch selects two items: e ⋆ ∈ C and f ⋆ ∈ min(C) such that regarding to I C DL : (1) e ⋆ is the best item to add to P , (2) f ⋆ is the best item to add to Q \ P (i.e., f ⋆ is the best candidate to remove from C without add it to P). From e ⋆ and f ⋆ , GreedySearch chooses the one that has the highest

IC DL

. If e ⋆ is chosen, P is extended by this item. Otherwise, f ⋆ and all its successors are removed from the set of candidates. When C becomes empty, the antichain P is returned.

RELATED WORK

The use of hierarchies (ontologies, taxonomies, etc.) in KDD tasks has been extensively studied. In [START_REF] Aronis | Exploiting Background Knowledge in Automated Discovery[END_REF], the authors explained the high and promissing utility of ontologies in different steps of the KDD process, and proposed an association mining tool that benefits from

Algorithm 2: GreedySearch

Input: H : the hierarchical dataset, values of conditional probabilities Pr( ŷi |O) for each y i Output: P: A greedily constructed antichain

1 P ← ∅, C ← E, Q ← ∅ 2 while C ∅ do 3 e ⋆ ← argmax e ∈C I C (P ∪{e }|O) D L(P ∪{e },Q ∪{e }) 4 f ⋆ ← argmax e ∈min(C ) I C (P |O) D L(P ,Q ∪{e }) 5 if I C (P ∪{e ⋆ }|O) D L(P ∪{e ⋆ },Q ∪{e ⋆ }) ≥ I C (P |O) D L(P ,Q ∪{f ⋆ }) then 6 P ← P ∪ {e ⋆ } 7 Q ← Q ∪ {e ⋆ } 8 C ← {e ∈ C | e ⪯̸ e ⋆ ∧ e ⋆ ⪯̸ e } 9 else 10 Q ← Q ∪ {f ⋆ } 11 C ← {e ∈ C | f ⋆ ⪯̸ e }
12 return P ontologies in different stages of the mining process (data understanding, task design, etc.). The generic problem of Semantic Data Mining has been defined in [START_REF] Liu | Towards semantic data mining[END_REF][START_REF] Vavpetic | Semantic Subgroup Discovery Systems and Workflows in the SDM-Toolkit[END_REF]: given a set of objects annotated with ontology terms, the goal is to find hypothesis, expressed by domain ontology terms, explaining the given empirical data. Specifically in [START_REF] Lavrac | Using Ontologies in Semantic Data Mining with SEGS and g-SEGS[END_REF][START_REF] Vavpetic | Semantic Subgroup Discovery Systems and Workflows in the SDM-Toolkit[END_REF][START_REF] Vavpetic | Semantic Data Mining of Financial News Articles[END_REF], the Semantic Subgroup Discovery problem is studied: given a dataset where each object is annotated with ontology terms and belongs to a specific class, the goal is to find a conjunction of ontology terms (a conjunctive rule) that corresponds to a set of object discriminating a specific class. To evaluate the discriminativity of a conjunctive rule, these approaches mainly use the wW RAcc heuristic based on the W RAcc1 measure. This heuristic has been initially proposed for the generic task of Subgroup Discovery [START_REF] Lavrac | Subgroup Discovery with CN2-SD[END_REF]. A similar method has been proposed in [START_REF] Aronis | Exploiting Background Knowledge in Automated Discovery[END_REF] to take benefit from ontology structures in order to optimize and reduce the redundancy in the search of conjunctive rules that satisfy some user specified constraints. In [START_REF] De Beéck | Mining Hierarchical Pathology Data Using Inductive Logic Programming[END_REF], this problem of rule learning is tackled based on ILP (Inductive Logic Programming), and ontology structures are integrated by providing additional clauses to the ILP solver. Enumerating hierarchical attributes has been also integrated in the Exceptional Model Mining problem [START_REF] Belfodil | Flash Points: Discovering Exceptional Pairwise Behaviors in Vote or Rating Data[END_REF]. The common point between these works is the use of ontologies in the rule discovery to provide conjunctive clauses which cover a part of data that satisfy some constraints. In our work, the goal is to characterize the dataset based on an antichain that does not necessarily cover the same part of the data, but provides a good characterization of the overal dataset. Another specificity of our work is the explicit use of hierarchies to represent user background knowledge and integrate it in the interestingness measure.

Several works have also used hierarchies to improve the prediction task. In [START_REF] Garriga | Feature Selection in Taxonomies with Applications to Paleontology[END_REF], the authors propose an algorithms that, given a training set of objects described with ontology concepts, allows to select an antichain whose nodes will be used as features to learn a predictive model. Other works proposed different ontology-aware classification approaches [START_REF] Desjardins | Using Feature Hierarchies in Bayesian Network Learning[END_REF][START_REF] Zhang | Learning Ontology-Aware Classifiers[END_REF][START_REF] Zhang | Learning accurate and concise naïve Bayes classifiers from attribute value taxonomies and data[END_REF] based on well known models (decision trees, bayesian networks). While these works uses ontology structures to provide better prediction models, our approach aims to provide knowledge about a dataset to a specific user. Ontology structure has been used in other KDD tasks (ontology-based clustering, information extraction, recommender systems, etc.). In the survey [START_REF] Dou | Semantic data mining: A survey of ontology-based approaches[END_REF] a large spectrum of these works is reviewed.

In this paper, we use an interestingness measure inspired by the FORSIED framework [START_REF] De | An information theoretic framework for data mining[END_REF][START_REF] De | Maximum entropy models and subjective interestingness[END_REF], which defines the SI of a pattern as the ratio between the IC and the DL. The IC is the amount of information contained in the pattern. The quantification is based on the gain from a Maximum Entropy background model that depicts the current knowledge of a user, hence it is subjective, i.e., particular to the modeled belief state. Regarding the previous studies based on FORSIED framework, the novelty of our work is the incorporation of dependencies between user expectations about different attributes, using available hierarchy structures of the data.

EMPIRICAL RESULTS

In this section, we report our experimental results. These experiments aim to evaluate the performance and the quality of results provided by MICA-Miner in real world datasets. The method was implemented in Java and the experiments were performed on a machine equipped with Intel(R) Xeon(R) CPU @ 4.00GHz, and 128GB main memory, running Debian GNU/Linux 9.6. The code and the data are available 2 . Datasets and aims. We conduct experiments in three real world datasets whose main characteristics are given in Table 1: -FV: Foursquare venues [START_REF] Le Falher | Where Is the Soho of Rome? Measures and Algorithms for Finding Similar Neighborhoods in Cities[END_REF], the nodes e i in this hierarchical dataset are categories of venues3 (food, restaurant, event, etc.). We aim to study the distribution of venue categories in Amsterdam and London, and discover which kind of categories are surprisingly frequent/rare in each of these cities. We then consider two case studies: (1) FV-Ams for Amsterdam: the observed values xi are the counters of categories in Amsterdam, (2) FV-Lon for London: the observed values xi are the counters of categories in London. For both cases, the priors xi are the aggregation of categories counters throughout 20 well known cities from Europe and USA (London, Barcelona, New York, etc.).

-OFF: Open Food Facts4 is a free food product database that gathers information and data on food products around the world. Each product is described by its food category (Plant-based food, ...) and its country. The categories represent the nodes e i of the hierarchy. We want to compare the distribution of food categories between France and USA, the two countries with the most contributions. Then, the values xi (resp. xi ) are the number of products for each category in France (resp. USA).

-EP_Abst: European Parliament5 is a dataset that depicts ballots of the European Parliament between 2014 and 2019. Each ballot is described by the corresponding topics and the votes (for, against, abstain) of each deputy, whose political groups are given. Topics are organized following a hierarchy (e.g., the topic "5.10 Economic Union" is the strict predecessor of "5.10.02 Price policy, price stabilisation"). We build a hierarchical dataset for each political group where the values xi correspond to the number of abstentions: the number of times a deputy from this group abstains in the topic e i . The priors xi are constructed from the total number of ballots by topic.

In this experimental study, we aim to answer the following questions: How much time and memory does MICA-Miner consume in practice? How does the size of the hierarchy |E| impact the performance of MICA-Miner? What is the impact of model updating on the found antichains? Are the antichains found by MICA-Miner relevant and informative? Quantitative evaluation. We study the runtime and memory consumption for (1) the computation of factor functions (see Section 3.3), and (2) MICA-Miner. We vary the number of items in the real world datasets as follows: in order to decrease the number of items, we iteratively remove leaves that are the furthest from the root, and in order to increase the number of items, we duplicate the tree as many times as we need and then we add a new root that links all the duplications. Results are given in Figure 5, column 1 for the factor functions, and column 2 for MICA-Miner. As it was theoretically expected, the computation of factors requires a time and memory that linearly increase with the number of items. Moreover, the time increases for MICA-Miner in a quadratic manner (a fitted model a • |E| 2 + b approximates the time with an average square error below 7(s 2 )), its memory consumption also follows the same quadratic trend. Comparative evaluation. There is no approach in the literature that supports the discovery of subjectively interesting antichains in hierarchies. Nevertheless, we identify some baselines that we consider in our study to highlight the characteristics of the patterns found with MICA-Miner: (1) SI without update which returns the best results according to the SI measure without updating the background knowledge model; (2)WRAcc that uses the W RAcc measure [START_REF] Lavrac | Subgroup Discovery with CN2-SD[END_REF]. This measure has been largely used in Subgroup Discovery in order to evaluate the prevalence of a given class of objects in a specific subset of data (a subgroup). We adapted it to our problem in order to evaluate the prevalence/absence of nodes e ∈ P in the studied dataset. We consider that a subgroup is defined with the antichain P, the size of positive class is xi , and the size of negative class is xi . We . -Redundancy: An important goal of the iterative updating of the model is to avoid communicating to the user similar information several times. For example, after informing the user that e i ="Restaurant" is prevalent, it is less informative to tell her that e π i ="Food" is also prevalent. We aim to measure this kind of redundancy between patterns returned by each approach based on the following measure defined for a set of patterns R: 6 reports the values of these properties in each of the three configurations (1) SI (our approach), (2) W RAcc measure, and (3) SI without update. These properties are computed based on the top 5 patterns in FV-Ams and EP-Abst, and on top 20 in OFF (since it is a much larger hierarchy). The average values of counters in W RAcc results are significantly large, its top patterns generally contains nodes with the highest counters in the dataset. However, its average contrast is remarkably low. Figure 5 shows the first pattern found by W RAcc in FV-Ams. Most of its nodes are not significantly contrastive, i.e., there is not a high difference between the observed value and the expected value. We can also notice that the values of redund are the lowest for the results of SI , and those of the W RAcc have the highest redund. The value of redund for SI is clearly lower than its value for "SI without update" in FV-Ams and EP-Abst. The difference is not remarkable for the OFF dataset, indeed, since it is a larger dataset, there is less chance to have redundancies in the results. To sum up, our method allows to discover more contrastive antichains than methods that do not take into account the prior beliefs. Furthermore, updating the background knowledge at each iteration makes it possible to provide less redundant results. Illustrative results. We report in Figure 7 the top 3 contrastive antichains discovered by MICA-Miner in FV-Ams, FV-Lon, and OFF datasets. The blue color quantifies the expected value by the user (based on her beliefs over 20 cities), and the red color is the observed counter in Amsterdam (resp. London). The first antichain in Amsterdam informs that American Restaurants, Residential Buildings, and Airports are much less frequent than expected, while Marijuana Dispensary and Tram Station are significantly over-expressed. This last type of venue is indeed characteristic of Amsterdam, because it is authorized in this city while it is generally illegal in other cities. London is characterized with a high number of Fish & Chip Shops, Portuguese Restaurants, and Pubs, and an under-expression of Residences and Airports. We point out that Airport venues can correspond to any place related to Airport (Airport Food Court, Airport Gate, Airport Tram, etc.). After assimilating this first antichain, the user will change her expectations about the rest of the data. For example, she may assume that in general there is a high presence of Food venues and Bars in London, which is also incorporated in our model using the conditional expectation. Due to this hypothesis, the second antichain will notify the user that despite of the high observed values in the first antichain, there is some specific types of Food venues and Bars that are under expressed (American Restaurant, Donut Shop, etc.). For OFF dataset, the Red color quantifies the observed counts of products from France, and blue color corresponds to the expected values derived from products distributions from USA. The first antichain can be interpreted as: From an American point of view, the French food is characterized with a high number of fresh meals, refrigerated meals, fresh foods, and a low presence of groceries and popcorn products.

redund(R) = P ,P ′ ∈R P P ′ | {e i ∈P | ∃e π i ∈P ′ : ( xi -xi )•( xπ i -xπ i )≥0} | |R |× P ∈R |P | . Figure

CONCLUSION

We have introduced the novel problem of mining contrastive antichains in hierarchically organized sets of counters. Prior beliefs are used to assess how contrastive an antichain is. Furthermore, the hierarchical relations are fully exploited to both propagate the beliefs and to update the background knowledge . We have proposed a greedy algorithm that efficiently and iteratively returns the most contrastive antichains. Extensive empirical results on several realworld datasets confirm that the contrastive antichains are intuitive and they capture insights that cannot be done with other interestingness measure or without updating the background knowledge. This paper opens up several avenues for research such as the integration of this model into the subgroup discovery / exceptional model mining framework.

A SUPPLEMENTARY MATERIALS A.1 Proofs

Proof of Property 1. We consider that x π i Pr(x π i ) • x π i = xπ i and we prove that x i Pr(x i ) • x i = xi . The complete proof can be recursively established by starting from the root (x π i = x 1 ) for which we already know that x 1 Pr(x 1 ) • x 1 = x1 .

x i Pr(x i ) • x i = x i x π i Pr(x π i ) • Pr(x i |x π i ) • x i , = x i x π i Pr(x π i ) • Pr(x i |x π i ) • x i , = x π i x i Pr(x π i ) • Pr(x i |x π i ) • x i , = x π i Pr(x π i ) • x i Pr(x i |x π i ) • x i , = x π i Pr(x π i ) • xi xπ i • x π i , = xi xπ i • x π i Pr(x π i ) • x π i , = xi xπ i • xπ i , = xi .

□

Proof of Property 2. This property states that the marginal distribution of each random variable x i is geometric and it is:

Pr(x i ) = (1 - 1 1 + xi ) x i • 1 1 + xi .
For the root x 1 , this is already the case. We then prove this property by recursion, we consider that x π i follows a geometric distribution with parameter p π i = 1 1+ xπ i and we prove that x i also follows a geometric distribution with a parameter p i = 1 1+ xi :

Pr(x i ) = +∞ x π i =x i Pr(x π i ) • Pr(x i |x π i ), (4)
= +∞ x π i =x i (1 -p π i ) x π i • p π i • x π i x i • b x i i • (1 -b i ) x π i -x i , (5)
= p π i • b x i i (1 -b i ) x i • +∞ x π i =x i x π i x i (1 -p π i )(1 -b i ) x π i , (6)
= p π i • b x i i (1 -b i ) x i • +∞ k =0 k + x i x i (1 -p π i )(1 -b i ) k +x i , (7)
= p π i • b x i i (1 -b i ) x i • (1 -p π i )(1 -b i ) x i • +∞ k=0 k + x i x i (1 -p π i )(1 -b i ) k , (8)
= p π i • b x i i • (1 -p π i ) x i • +∞ k =0 k + x i k (1 -p π i )(1 -b i ) k , (9)
The negative binomial infinite series can be simplified:

+∞ k =0 k + x i k (1 -p π i )(1 -b i ) k = 1 -(1 -p π i )(1 -b i ) -1-x i , = (b i + p π i -b i • p π i ) -1-x i , then: Pr(x i ) = p π i • b x i i • (1 -p π i ) x i • (b i + p π i -b i • p π i ) -1-x i , ( 10
) = p π i b i + p π i -b i • p π i • (1 - p π i b i + p π i -b i • p π i ) x i . ( 11
)
After substituting

p π i = 1 1+ xπ i and b i = xi xπ i
, we find that

p π i b i +p π i -b i •p π i = 1 1+
xi . This means that:

Pr(x i ) = (1 - 1 1 + xi ) x i • 1 1 + xi .
This concludes the proof. □

A.2 Theoretical complexity of MICA-Miner

We derive the worst case complexity of MICA-Miner, which depends on the complexity of sum-product and GreedySearch. As stated in Section 3.

A.3 Supplementary experiments

Quantitative evaluation. We aim to study the influence of the parameter A on the runtime and memory consumption. A is an upper bound on the value of variables x i , it needs to cover the used values xi and xi , this means that A ≥ max( xi , xi ). Figure 8 reports the results. The runtime grows linearly w.r.t A for the preprocessing step while the increasing of A does not significantly impact the runtime of MICA-Miner. The memory consumption slightly increases in general w.r.t. A in both cases.

A.4 Code and data

All code and data are available at https://tinyurl.com/y2jkmduv.

Figure 1 :

 1 Figure 1: Example of hierarchy with counts (counts of venues in a city).

Figure 2 :

 2 Figure 2: Example of an antichain pattern P = {e 4 , e 5 , e 6 }

α 1

 1 and α 2 are user specified parameters. If the user prefers to have patterns P with deeper nodes from the hierarchy (nodes which are closer to the leaves), she can decrease the value of α 1 . On the other hand, if she likes to have patterns P with larger number of items, she can increase α 2 .

  When a rational user observes some patterns, her background knowledge may change to take into account these new pieces of information. It results that the observed patterns become expected by her and the background knowledge has to be updated as well. Let us denote by O ⊆ E the set of already observed nodes. The quality of a pattern P can thus be assessed using SI (P |O), the subjective interestingness of P conditioned to the already observed values from O: SI (P |O) = IC(P |O) DL(P) = log(Pr(P |O)) DL(P) .

Figure 3

 3 Figure 3 displays the factor graph of the hierarchy from Figure 1.The sum-product algorithm works only when the random variables have a finite number of states, while in our case y i take their values in N. To make the use of sum-product possible, we can limit the values of x i to an upper bound A > max( x1 , x1 ). If we set A = 220 , x i can variate from 0 to 220 , and y i from 0 to 20. For example, if values of xi and xi are all lower than 215 , it can be sufficient to set A = 2 20 , since Pr (y i > 20) will be extremely small and negligible. Before running sum-product, we prepare the values

Figure 3 :

 3 Figure 3: Factor graph of the tree in Figure 1.

Figure 4 :

 4 Figure 4: Time (line) and memory consumption (bars) of the factor functions computation (columns 1), and MICA-Miner (columns 2) in the studied datasets w.r.t. |E|.

Figure 5 :

 5 Figure 5: Top 1 pattern based on W RAcc measure FV-Ams.

  compare the following properties computed in the top k patterns returned in each configuration: -Average normalized values of counters: we show the average values of xi x1 corresponding to nodes in the top patterns. -Average contrast: we want to evaluate how much the values of xi are contrastive comparing with their corresponding xi . We propose to use the following contrast measure defined for an antichain P ⊆ E: contrast(P) = e i ∈P max ( xi , xi )-min( xi , xi ) max ( xi , xi )

Figure 6 :Figure 7 :

 67 Figure 6: Comparison of (1) normalized supports, (2) contrast, (3) redundancy between the top antichains of the three measures: SI , W RAcc, and SI without model updating.RankFV-Ams FV-London OFF 𝑥 " # : observed values (in Amsterdam)𝑥 " $ : expected values (based on aggregations from 20 cities)

Figure 8 :

 8 Figure 8: Supplementary experiments. Time (line) and memory consumption (bars) of the factor functions computation (row 1), and MICA-Miner (row 2) in the studied datasets w.r.t. A.

  MICA-MinerInput: H : the hierarchical dataset, pre-computed values of factor functions f 1 and f i,π i for each i ∈ 2, n . Output: R: the antichains sorted based on iteratively updated SI .

	1 R ← ⟨⟩
	2 O ← ∅
	3 repeat
	4	// Update the model with the sum-product algorithm
	5	// and derive the probabilities Pr( ŷi | O) for each y i :
	6	Sum-product(H, O)
	7	// Compute an antichain with a greedy strategy:
	8	P ← GreedySearch(H)
	9	if P ∅ then
	10	R .append(P )
	11	O ← O ∪ P

2

• max(loд(A)

2

, |L(H )|) , see Appendix A.2) and whose effectiveness is demonstrated experimentally. Before running this algorithm, we consider that the factor functions Algorithm 1:

12 until P = ∅;

Table 1 :

 1 Description of the real-world datasets.

	Datasets	|E|	| x1|	# levels branching factor
	FV-Ams 846	9030	5	13
	FV-Lon	846	25220	5	13
	OFF	2000	147,411	10	3.6
	EP_Abs	358 [7470; 30, 673]	5	5.17

  3, sum-product has a worst case complexity of O(|E| •loд(A) 2 ) where |E| is the number of items, and the parameter A > max( x1 , x1 ) is the considered number of possible values of x i . In GreedySearch, each iteration costs at most O(|E|), and the maximum number of iterations is equal to |L(H )| which is the size of the largest antichain. Thus, GreedySearch has a worst case complexity of O(|E| • |L(H )|). Since the maximum number of iterations in MICA-Miner is |E|, we conclude that its worst case complexity is O |E| 2 • max(loд(A) 2 , |L(H )|) .

W RAcc: Weighted Relative Accuracy measure

https://tinyurl.com/y2jkmduv

https://developer.foursquare.com/docs/resources/categories

https://world.openfoodfacts.org/

http://parltrack.euwiki.org/

Acknowledgements. This work was supported by the ERC under the EU's Seventh Framework Programme (FP7/2007-2013) / ERC Grant Agreement no. 615517, FWO (project no. G091017N, G0F9816N), the EU's Horizon 2020 research and innovation programme and the FWO under the Marie Skłodowska-Curie Grant Agreement no. 665501, Group Image Mining (GIM) which joins researchers of THALES Group and LIRIS Lab, and by the ACA-DEMICS grant of the IDEXLYON, project of the Université of Lyon, PIA operated by ANR-16-IDEX-0005.


Simon Rokicki

Davide Pala

Joseph Paturel

Olivier Sentieys

What You Simulate Is What You Synthesize: Designing a Processor Core from C++ Specifications Invited Paper

Designing the hardware of a processor core as well as its verification flow from a single high-level specification would provide great advantages in terms of productivity and maintainability. In this work, we highlight the gain of starting from a unique high-level synthesis and simulation C++ model to design a processor core implementing the RISC-V Instruction Set Architecture (ISA). The specification code is used to generate both the hardware target design through High-Level Synthesis as well as a fast and cycle-accurate bit-accurate simulator of the latter through software compilation. The object oriented nature of C++ greatly improves the readability and flexibility of the design description compared to classical HDL-based implementations. Therefore, the processor model can easily be modified, expanded and verified using standard software development methodologies. The main challenge is to deal with C++ based synthesizable specifications of core and uncore components, cache memory hierarchy, and synchronization. In particular, the research question is how to specify such parallel computing pipelines with high-level synthesis technology and to demonstrate that there is a potential high gain in design time without jeopardizing performance and cost. Our experiments demonstrate that the core frequency and area of the generated hardware are comparable to existing RTL implementations.

I. INTRODUCTION

Since decades software and hardware have shared a symbiotic relationship -a situation where both elements support and need each other to thrive and progress. Innovations in hardware architecture are leading to better processors which can support the complex software applications being developed today. Similarly, software and programming languages have made it easier to prototype, simulate and even synthesize hardware, for example the creation of High-Level Synthesis (HLS) tools. HLS is a hardware design technique where an algorithm written in a high-level language like C or C++ is interpreted to create digital hardware which implements the same functionality. HLS tools are very useful for designing complex controllers or accelerators, as they allow engineers to focus simply on functionality, without worrying about architectural details too much.

Standard development flows for processor architecture are based around the development and maintenance of a hardware model for synthesis, and a software model (i.e. an instructionset simulator) to validate the applications that will run on the design. Those two models have to be verified independently. High-level synthesis would also be considerably useful to cut down the complexity of the hardware development in a processor design methodology. As shown in Figure 1, HLS enables the use of a single behavioral model of the simulator, which is compiled into a cycle-accurate bit-accurate simulator by standard compilers and also synthesized into a hardware component through HLS. It is also possible to debug the behavioral model at the C/C++ level and to simply validate the behavior of the generated hardware through co-simulation and standard software development tools. Although high-level synthesis is making huge progress in dealing with complex structures, how far can these tools go? Can they be used to design something as complex as a microprocessor? In particular how to specify such parallel computing pipelines (e.g., core pipeline stages, cache hierarchy, communications with uncore components) with the HLS technology and to demonstrate that there is a potential high gain in design time, without jeopardizing performance and cost.

In this work, we present an attempt to answer these questions with the design of Comet, a five-stage pipelined processor implementing the RISC-V Instruction Set Architecture (ISA). Comet is fully synthesized from a unique C/C++ model using state-of-the-art HLS tools. To measure the quality of the generated hardware, we compare it against other implementations based on hardware description languages. Results show that, if the C/C++ model is written using the methodology we describe in this paper, the generated hardware is comparable or even better than other implementations when targeting an ASIC 28 nm technology node. The resource footprint on FPGA targets is slightly higher but still comparable with handoptimized designs. Moreover, a fast, cycle-accurate and bitaccurate simulator of the processor can be compiled from the same C/C++ model. The resulting maximum performance of the simulator reaches 24 million cycles per second (Mcps) on integer workloads and around 15 Mcps on average, when executing floating-point and integer workloads. The object oriented nature of C++ also greatly improves the readability and flexibility of the design description compared to classical HDL-based implementations. Therefore, the processor model can easily be modified, expanded and verified using standard software development methodologies.

The rest of this paper is organized as follows. Section II provides the background on HLS needed to understand the challenges involved in designing a processor core using HLS. In Section III, we describe how the C/C++ models have to be designed in order to be correctly synthesized by the HLS tool. In Section IV and Section V, we present the experimental results and their discussion before to draw some conclusions and perspectives in the last section.

II. BACKGROUND ON HIGH-LEVEL SYNTHESIS

The principle of high-level synthesis is to generate hardware components from functional representations using high-level languages (typically C/C++). While HLS could be seen as a compilation of software to generate hardware, it has to face several different challenges. For example, the tool can allocate computing units and hardware resources to exploit operator-level parallelism. HLS also needs to meet designer constraints such as target operating frequency and maximum allowed area or resource usage. The first behavioral synthesis methodologies and tools date back to the 1990s [START_REF] Martin | Gaut: An architectural synthesis tool for dedicated signal processors[END_REF]. However, until the 2000s, those tools were commercial failures due to the quality of the generated hardware [START_REF] Martin | High-level synthesis: Past, present, and future[END_REF] not being high enough to compete with handcrafted designs. However, more recent commercial tools like Catapult HLS from Mentor Graphics [START_REF] Fingeroff | High-Level Synthesis Blue Book[END_REF], [START_REF] Bollaert | Catapult Synthesis: A Practical Introduction to Interactive C Synthesis[END_REF], [START_REF]Catapult C synthesis[END_REF] and Vivado HLS from Xilinx [START_REF] Feist | Vivado Design Suite[END_REF] generate efficient hardware for a broad set of applications. Nevertheless, HLS is still aimed at generating hardware accelerators for computeintensive applications and is less capable when dealing with control-dominated tasks.

HLS flows are organized around two main steps. First, the tool allocates hardware components to the different operations found in the functional representation. Then, during the second step, the tool schedules the operations. The allocation and the scheduling problems are joined: allocating fewer resources to save area results may lead to a longer schedule, thus reducing the speed or the throughput of the synthesized hardware. Consequently, those two problems are often solved at the same time [START_REF] Kollig | Simultaneous scheduling, allocation and binding in high level synthesis[END_REF].

HLS tools also have to efficiently handle loops. This can be done through loop pipelining. The idea is to begin a new iteration of the loop before the completion of the current one. Loop pipelining is characterized by the Initiation Interval (II) achieved, which is the time between two iteration starts. Ideally, a loop is pipelined with an II of one, which means that a new iteration starts every cycle. However an II of one can be difficult to obtain as the II is constrained by both available resources and inter-iteration dependencies.

III. DESIGNING A PROCESSOR WITH HLS

In this section, we present how to efficiently synthesize a processor using a behavioral description (i.e., a simulator). We first explain why HLS tools cannot generate efficient hardware from an Instruction Set Simulator. Then, we present our explicitly pipelined simulator and how to integrate multicycle operators (e.g. integer division, floating-point unit).

A. Synthesis from an Instruction Set Simulator

The most intuitive way to synthesize a processor from a C/C++ description is to express the ISA execution as in an Instruction Set Simulator (ISS). An ISS is a simple way to express the functionalities of the processor organized around an infinite loop implementing the ISA. At each iteration of the loop, an instruction is fetched, its fields are decoded and a switch/case statement modifies the simulator's state function of the current instruction definition. Finally, the Program Counter (PC) is incremented and the next instruction can be executed at the next iteration.

Algorithm 1 is a simple ISS example: we can see the main parts of the simulator (the infinite while loop and the switch/case). If we consider the case corresponding to the addition (ADD), the simulator simply reads the two operand registers, executes the addition and writes the result in the register file. Similarly, the case corresponding to the load instruction (LD) computes the address, accesses the memory and writes the result on the register file. Thanks to their simple operating logic, Instruction Set Simulators are often used to provide the first simulator of an ISA. Moreover, studies from Rohou et al. demonstrated that thanks to modern branch predictors, such simulators deliver good simulation performance without needing complex optimizations [START_REF] Rohou | Branch Prediction and the Performance of Interpreters: Don'T Trust Folklore[END_REF]. Among RISC-V simulators, SWERV-ISS [START_REF] Rahmeh | Western Digital's Open Source RISC-V SweRV Instruction Set Simulator[END_REF] from Western Digital is based on this idea. The Spike simulator [START_REF] Waterman | Spike, a RISC-V ISA Simulator[END_REF] is more complex and provides higher performance, but remains based on a similar switch/case structure.

To synthesize an efficient hardware component from an ISS, some transformations need to be applied to the functional description. As Algorithm 1 shows, an addition operator is used in different cases of the switch statement (the LD and ADD cases in this example), since a single opcode is evaluated at each loop iteration, The two operators are never solicited simultaneously and a unique addition operator instance and some multiplexers can be shared between the different execution paths. This transformation is known as datapathmerging [START_REF] Moreano | Efficient datapath merging for partially reconfigurable architectures[END_REF]. If the considered operator's inputs/outputs are different in different datapaths, it might be more or less interesting resource-wise to apply the merging transformation. Similarly, all the read and write operations to the register file could be merged into one or two accesses. This transformation allows for the design size to be reduced.

To gain on the performance front, the infinite while loop of the ISS can be pipelined, hence reducing the length of the critical path and thus allowing for higher throughput to be achieved. Unfortunately, current HLS tools cannot achieve an II of 1 with such an ISS-like processor description. Indeed, several dependencies would be detected by the compiler:

• The Read After Write (RAW) dependency on the register file: when executing a load instruction, the value to write in the register file has to be fetched from memory at an address that is stored in the register file itself. If the previously executed instruction modified the register that contains the target address, its complete execution is required before the current instruction can be evaluated and the memory can be accessed. As HLS tools always schedule for the worst case, they will not be able to reach an Initiation Interval of 1 on their own. • The next PC value: the PC value for the next loop iteration can come from different paths. If the current instruction is a conditional branch, the condition has to be evaluated (which often needs register file accesses and integer comparisons). Therefore, depending on this condition, an immediate value may be added to the current PC to obtain the next value. Also, when executing an indirect branch, the next PC value comes from the register file. Because of this dependency on the PC value, HLS tools determine the following PC value at the end of the longest path, which is the conditional branch. This leads to an Initiation Interval greater or equal to 3, depending on the number of pipeline stages of the processor.

The first dependency could be handled by HLS tools if they were capable of scheduling for the most probable path, stalling the pipeline when necessary. The dependency related to the next PC value requires to generate a speculative pipeline: starting an iteration with the most probable PC value (which is often an increment of the current value, pointing to the next instruction in memory) and canceling the execution if the prediction turned out to be wrong. These two transformations could be handled by the HLS tools and represent interesting research directions. It is also noteworthy that, if the tools were capable of generating such schedules, we would get a pipelined processor that resembles the ones that are manually designed.

To summarize, synthesizing a processor core from an In-struction Set Simulator would lead to very low performance as current HLS tools are not capable of efficiently pipelining and breaking dependency in such specifications. Consequently, to develop a processor core using HLS, we need to write a simulator where the pipeline structure is explicitly encoded at the specification level.

B. Explicitly Pipelined Simulator

As explained in the previous section, current HLS tools are not capable of generating efficient pipelines for processors, that is to generate pipelines which speculate on the next value of the PC and capable of handling stall and forwarding mechanisms automatically. As we want to design a core with a performance level close to what is achievable with an HDL, we designed an explicitly pipelined simulator. In this simulator, the structure of the pipeline, as well as all the control mechanisms (stall and forward), are specified at the C/C++ level. As described in Figure 2, our simulator uses a 5-stage pipeline (Fetch, Decode, Execute, Memory and Write Back), with a forwarding mechanism from the output of the Execute and Memory stages to the input of the Execute stage. Figure 2 also represents data and instruction caches, as well as multi-cycle operators. The design of these latter components is discussed in Section III-C.

Algorithm 2 represents the high-level description of Comet, our processor core with the explicit pipeline structure. The different pipeline registers are defined as struct variables (e.g., ftodc represents the pipeline register between the Fetch and Decode stages), these variables are declared outside the scope of the main execution loop and will hence retain their values between iterations. Each iteration of the infinite loop executes the functions of all the pipeline stages on their respective input registers. Each pipeline stage function writes its output in a temporary register (that is not synthesized) that represents the data present at the input of the following physical pipeline registers. Note that five different instructions are alive in the simulator at the same time, one for each pipeline stage.

After executing all the pipeline stages, the simulator handles the stall and forward logic. First, a stall signal is computed for each pipeline stage. If a stage is not stalled, the temporary values that represent its output will be copied over to the physical registers. Stall signals can be activated if an external global stall signal is set, when a cache miss occurs or when a Read After Write dependency that cannot be solved with forwarding, is detected. With the latter stall source, only the two first pipeline stages are inhibited while the Execute, Memory and Write-Back stages keep committing their results. Forward mechanisms simply compare source and destination registers and trigger a forward bit. If this bit is set, one of the input values of the Execute stage is modified with the result of the Execute or the Memory stage to avoid stalling the pipeline and wait for the value to be written in the register file.

The simulator described in Algorithm 2 has therefore no inter-loop dependencies and can hence start the execution of a new instruction at every clock cycle, leading to an II of one. It is also interesting to note that the explicit pipelining transformation (effectively removing all the timing flexibility of the HLS compiler) makes the simulator cycle-accurate bitaccurate, unlike a standard solution based on an ISS.

C. Handling Multi-Cycle Operators and Caches

The simulator described in the previous section has only one pipeline stage dedicated to execution. While this is enough for most of the instruction of the base RISC-V ISA, some extensions introduce operations requiring a longer execution time (e.g., the integer division of the M extension of the ISA). If the instruction is simply added into the simulator described on Algorithm 2 in a new case statement using a normal division operator, the synthesized design will see its critical paths greatly increased and therefore its operating frequency lowered accordingly. To counter this side effect, the division needs to be broken down into small control steps. An implementation based on a for loop is not suitable, as HLS compilers always schedule for the worst case and will hence lower the II of the pipeline to the number of iterations needed to fully execute the division algorithm.

To solve this issue, multi-cycle operations are expressed as Finite State Machines (FSM) and the execution stage is stalled when a multi-cycle opcode is detected. Each state of the FSM corresponds to a computation cycle. In the case of the division, there is a state for each bit in the operand (groups of bits can be processed together using loop unrolling techniques to increase performance). When a multi-cycle opcode enters the execution stage, the pipeline will be stalled until the opcode FSM has reached its final state and a result has been produced. All the commit and forwarding logic is kept from the original pipeline.

As multi-cycle operators are synthesized alongside the processor, HLS tools can perform some resource sharing between the normal mono-cycle operations and the multi-cycle ones. For example, the division is implemented using successive subtractions. The HLS tools allow for the subtractor circuit of the Arithmetic and Logic Unit (ALU) to be re-used in the execution of the division. The drawback of this approach is that the computation of the multi-cycle operators has to be split into atomic pieces that can be executed in one cycle and the designer has to encode a state machine that guides the execution of the algorithm and generates the stall signal. This solution has been used to implement the division instruction as well as the Floating-Point Unit (FPU) of the Comet processor.

Less intuitively, we used a similar mechanism to handle associative data and instruction caches. Caches load the tags associated to the requested address. If there is a match, they return the corresponding value. If no match is detected, the caches stall the core while a line is freed and populated with values from the next memory level in the hierarchy. These two match/miss possibilities, and the processing associated to each, are sequenced using an explicit state-machine. Because of the different memory accesses, synthesizing this part is challenging. We used HLS directives to ignore some of the dependencies detected by the tool when we knew that conflicts never occur.

To illustrate the usage of the previously exposed optimization techniques, we present in the next section Comet, a RISC-V compatible 32-bit CPU based on the microarchitectural features illustrated in Figure 2.

IV. DESIGN OF THE COMET PROCESSOR CORE

In this section, we describe the experimental study conducted and the main results obtained. This study aims to: i) evaluate the quality of the generated hardware and compare it with existing RISC-V cores; ii) measure the performance of the simulator; iii) demonstrate how HLS improves the maintainability and the extensibility of a processor core design.

A. Quality of the Generated Hardware

The first part of the study is focused on measuring the quality of the generated hardware. Indeed, current HLS tools are not built for control-flow dominated C++ code such as a processor core simulator. To ensure that the synthesized core is competitive, we compare its characteristics against other similar cores.

The Comet core has been synthesized with different configurations: i) based on the rv32i that only supports basic instructions; ii) based on rv32im that has additional support for 32×32 integer multiplication and division, and iii) based on rv32imf that supports all the 32-bit single-precision floatingpoint instructions. Note that this last configuration also adds 32 32-bit floating-point registers. All those three different versions of Comet are synthesized with Mentor Graphics Catapult HLS (V10.3a), and then synthesized with Synopsys Design Compiler (P-2018.06-SP5). Each configuration targets an operating frequency of 700 MHz and the 28 nm FDSOI technology node from ST Microelectronics, using a V dd =1V, 25 • C corner.

As baselines, we used several other cores written with more standard hardware description languages. The Rocket core [START_REF] Asanović | The Rocket Chip Generator[END_REF] is a 5-stage pipelined core developed at Berkeley using the Chisel HDL [START_REF] Bachrach | Chisel: Constructing Hardware in a Scala Embedded Language[END_REF]. Its micro-architecture is close to the one of Comet but it also supports additional RISC-V extensions (compressed and atomic instructions), which may slightly impact its area results. As the Rocket core is fully configurable, we generated three versions comparable to the three Comet configurations. PicoRV is a size-optimized RISC-V core: it has no barrel shifter and only supports the rv32i ISA. PicoRV is written using Verilog HDL. Those different cores were synthesized using the same synthesis flow and technology parameters.

Table I contains the synthesis results for the different cores. For the rv32i configurations, our implementation is larger than the size-optimized PicoRV but smaller than the Rocket core. Once support for the M-extension added, Comet becomes smaller than PicoRV and Rocket, even though the difference is less significant. The addition of the floating-point extension changes this tendency, the Rocket core for rv32imf being slightly smaller than its equivalent for Comet. However, the important conclusion in this study is that the use of HLS does not significantly impact the area and frequency of the synthesized core, even when compared to an optimized version designed at the RT level.

To investigate the impact of the floating-point extension, sub-parts of the Comet core have been synthesized separately: the FPU and the core alone (note that the core still contains the 32 floating-point registers). The results of this experiment are given in Table II. Intuitively, synthesizing sub-parts of the design separately should lead to a larger design, as the HLS tool would no longer perform resource-sharing optimizations between those different parts. However, the results in Table II show the opposite: synthesizing the FPU and the core separately leads to better results. This counter-intuitive result seems to point out that we are reaching the limits of what current HLS tools can perform. As the control-flow grows in complexity with the addition of an FPU, the optimization algorithms of the HLS tool are not capable of optimizing the design as much as if it was split into smaller and simpler subdesigns. This hypothesis also holds if we measure the time spent by the HLS tool to synthesize the design. For the full core with the FPU, the compilation time reaches 23 minutes, whereas the synthesis of the core and FPU alone took two minutes each. Another advantage of HLS is its ability to synthesize a hardware design specialized for various technology targets. As an example, we synthesized Comet as a soft core embedded into a Xilinx Artix 7 FPGA (XC7A12T). The core itself is still synthesized using Catapult HLS (V10.3a) and the RTL code is then synthesized and placed and routed using Vivado 2018.3. Table III summarizes results in terms of area and maximal frequency for different RISC-V cores. Area is expressed as the number of Look-Up Tables (LUT), Flip-Flops (FF), Multiplexers (Mux), and arithmetic (DSP) blocks used in the FPGA fabric. Even if the comparison between Rocket and Comet is more difficult on FPGA, the area and frequency of the synthesized designs are comparable. We can notice that Comet uses more multiplexers and arithmetic blocks than Rocket for each configuration. On the other side, PicoRV is far smaller than Comet and operates at a higher frequency. The manually optimized FPGA design of PicoRV is much more efficient than both Rocket and Comet designs. It is however important to notice that the micro-architecture of PicoRV is completely different and the performance level of Comet is higher, PicoRV being optimized for frequency and area. Indeed, when executing a Dhrystone benchmark, Comet exhibits a Cycles Per Instruction (CPI) of 1.9, whereas the best performing configuration of PicoRV only reaches a CPI of 4.1. Note that the CPI of Comet and Rocket is similar.

B. Simulator Performance

As already stated, Comet is also a cycle-accurate and bitaccurate simulator of the processor. The simulator contains code that does not aim to be synthesized, which constitutes a wrapper around the core. It allows for the execution of standard elf files, solves systems calls (without the need of additional code within the executed binary), and implements code instrumentation facilities. Consequently, a broad range of bare metal and OS supported applications can be executed by the simulator.

To measure simulation performance, several applications from the MiBench benchmark suite have been selected (the set of workloads has been picked from all the categories of the suite). Simulator performance has been evaluated using different configurations of the target system: support for the base ISA and/or the M and F extensions as well as the presence or not of L1 caches. Applications from the MiBench suite have been executed on the simulator on a host workstation equipped with an 8th-generation Intel Core i7 CPU running at 3.9GHz.

In Table IV, we can observe a peak performance at 23.6 million cycles per second (Mcps) average when the core is set up to only support the base ISA and no caches are used. As expected the performance numbers dip as the number of supported features and system complexity increase. The lowest performance figure of 11.6 Mcps is obtained when the core supports both the M and F extensions and when L1 caches are in use. The average performance of the simulator is around 15 Mcps, when executing floating-point and integer workloads.

Comparatively, the verilator-based [START_REF] Snyder | Verilator and systemperl[END_REF] simulator of the Rocket chip executes three orders of magnitude slower, with approximately 0.023 Mcps. The widely used Gem5 simulator [START_REF] Binkert | The gem5 simulator[END_REF] can simulate around 0.2 Mcps. However, due to the extended control flow introduced by the explicit pipelining needed for HLS use, Comet is not as fast as an ISS. For example, SWERV-ISS [START_REF] Rahmeh | Western Digital's Open Source RISC-V SweRV Instruction Set Simulator[END_REF] can simulate up to 140 million instructions per second. Finally, the fastest way to simulate a RISC-V application is to use dynamic binary translation. For example, Qemu [START_REF] Bellard | QEMU, a Fast and Portable Dynamic Translator[END_REF] can simulate around 1.3 billion instructions per second, which is close to native performance. Note that ISS and DBT-based simulators are no longer cycle accurate. The performance of Comet (around 10 million instructions per second in average) coupled to the accurate nature of the simulator make it a good candidate for fast microarchitectural design-space exploration.

C. Example of Core Specialization

Using HLS for processor design offers as another advantage the ease of feature addition. As a demonstration of this extensibility, we have developed a custom instruction performing a Fast Fourier Transform (FFT) butterfly operation to speedup 64-point, radix 16, FFT computations. To simplify the implementation, the custom instruction can only read two 32bit registers and write in one hence avoiding the need for a second register file write port and additional forwarding mechanisms. The new instruction can be integrated into the pipeline by simply adding a case statement in the ALU of the Execute-stage and in the Decode stage function.

The custom butterfly instruction receives two 16-bit fixedpoint complex numbers represented with two 32-bit values. It performs the butterfly computation using a local array containing the twiddle factors and writes the result in the destination register. This single custom instruction performs four 16-bit multiplications and four 32-bit additions in a single clock cycle.

The custom instruction is added on top of the configuration supporting the rv32im ISA. The modification in the C++ model only represents 60 new lines added to the code. The new core is synthesized using a 28 nm technology for an operating frequency of 700 MHz. With the custom instruction, the core is 31% larger than the original Comet, which represents an area of 14 831 µm 2 . This area increase is mainly due to the added flipflops and multipliers required by our implementation. An FFT program was also modified to make use of the new custom instruction using the .instr assembly directive. The performance measurements demonstrate that the version exploiting the custom instruction executes 14× faster than the straight rv32im one. This also shows the ability of our C++ processor model to be easily and fastly extended with new functionalities.

V. DISCUSSION AND RELATED WORK Several attempts at generating processors using HLS have already been made. The objective is usually to generate an application-specific processor where some instructions are removed. In the work of Ahmed et al. [START_REF] Ahmed | Synthesizable-from-C Embedded Processor Based on MIPS-ISA and OISC[END_REF], the processor is not pipelined at all. In the work of Skalicky et al. [START_REF] Skalicky | Designing customized isa processors using high level synthesis[END_REF], the processor is pipelined using the automatic pipelining capabilities of their HLS tool, which limits the Initiation Interval to a minimum of three or four.

Experimental results show that the Comet core synthesized through HLS presents similar area and performance to other popular HDL-based solutions. In this section, we will discuss some of the advantages and drawbacks of HLS usage to design complex, control-oriented digital circuits such as processor cores.

A. Advantages of the Proposed Design Flow

As previously mentioned, the main advantage of HLS is that a single C++ model is used to generate both a high performance and accurate simulator and a functional hardware component. As C++ is a high-level language, the source is easy to read and is also small, offering great educational and maintainability advantages over standard HDLs. HLS also enables feature additions. As an example, the M ISA extension has been added to the sources and synthesized in a single day. Working with a single model for hardware and software also simplifies the debugging/testing part of the development process. Indeed, all the debugging is done at the C++ level, using dedicated tools like GDB or Valgrind. Once the simulator is thoroughly tested, the hardware is ready to be synthesized and co-simulation can be performed to ensure that the RTL representation behaves the same way than the software model. This design flow is more resilient and less error-prone than conventional hardware development flows.

Thanks to these properties, the Comet core is used to ease architectural exploration of processor core in several research projects:

• Design-space exploration of fault-tolerant CPU designs.

The core wrapper code has been modified to include fault injection facilities allowing the injection of errors in any memory point of the design (core and pipeline registers, caches and memories) at any time during the execution of a workload. Since the core code is kept the same, it is still synthesizable and each pipeline stage can be analyzed separately at the RT level or gate level using conventional fault-injection tools. Errors extracted at this low-level can then be re-injected in the simulator with the guidance of some data acquired during synthesis (area of the different pipeline stages, combinational/sequential logic ratios), hence allowing fast and accurate vulnerability analysis.

Comet is used as a testbed to characterize several faultmitigation techniques at different core locations and granularity levels. • Building a non-volatile processor. The cycle accurate and flexible nature of the Comet simulator easily allows the creation of tracing capabilities and the implementation of uncore peripherals. In the context of normally-off or intermittently-powered computing systems, memory backups need to be precisely scheduled to avoid data loss without having an important impact on power consumption. Based on the memory access traces provided by Comet, the estimation of several characteristics, e.g., the traffic generated by cache misses and fetch operations, is made easier. From these traces, an accelerator for the management of the backup into non-volatile memory can be rapidly designed and simulated. • The Hybrid-DBT project also made extensive use of HLS based processors [START_REF] Rokicki | Hybrid-DBT: Hardware/Software Dynamic Binary Translation Targeting VLIW[END_REF]. Hybrid-DBT is a system based on Dynamic Binary Translation (DBT), where RISC-V binaries are executed on a VLIW processor. Thanks to a DBT layer, RISC-V binaries are translated into the VLIW explicitly parallel ISA, before being executed. The Hybrid-DBT system is composed of two different types of cores: a small in-order core that translates and optimizes RISC-V binaries and a wider VLIW core that is used to execute the translated binaries. While Comet is used as the DBT processor, the VLIW core is also synthesized using HLS. The same principles are used to design the VLIW: the pipeline is explicitly described in the simulator. However, the VLIW is less complex as it does not use any stall or forward mechanisms. As the whole system is built around C++ models, it is straightforward to build a C++ simulator of the Hybrid-DBT system.

B. Designing a Processor with HLS has Some Limitations

If describing processors using HLS has several advantages it also has some drawbacks, they are mainly introduced because HLS tools are not designed to generate circuits from control-flow dominated specifications. As explained in Section III-A, HLS tools are not capable of generating an efficient pipeline from an ISS-like description of the core, and do not generate hardware below three cycles per instructions. This limitation is due to inter-loop dependencies on the register file and the PC value. In order to get around this limitation, Comet is synthesized from an explicitly-pipelined simulator specification. This type of simulators can be complex to read and write and over-constrain the final design. An ideal solution would be to let the HLS tool generate the pipeline, taking into account the targeted operating frequency and adjusting the pipeline depth accordingly. If the user wants the design to operate at low frequencies, the HLS tool could generate fewer pipeline stages and improve the number of cycles needed to execute a single instruction.

In a hand-made core, pipelining related dependencies are removed using simple but clever mechanisms: stall and forward mechanisms remove the inter-loop dependency on the register file; speculation and pipeline flush mechanisms remove the dependency on the next PC value. As future work, we plan to generalize those mechanisms and work on source-to-source transformations which automatically insert those mechanisms at the C++ level. With these dependencies removed, the HLS tool should be able to pipeline the ISS with an initiation interval of one.

It is also worth noting that standard ASIC fixing techniques, like metal and gate fixes, are hardly applicable to HLS-based designs. HLS tools are not able to ingest a modified gatelevel netlist and to reflect the changes back to a C/C++ based representation. It is also hard to tell the HLS compiler to make provisions of cells to create sewing kits as the timing and behavioral information of the kits need to be explicit. If this could be an issue when designing processor chips, it is however a general limitation of any HLS design.

VI. CONCLUSION

The work done around Comet highlights the benefits of using HLS to develop CPU cores since it significantly reduces development and debugging time. Moreover, this also provides a cycle-accurate and bit-accurate simulator which is, by construction, equivalent to the hardware core. This work demonstrates that HLS tools are mature enough to handle complex, control-dominated code such as pipelined cores. The resulting hardware presents a similar area and operating frequency to HDL written cores.

However, we also observed some limitations with stateof-the-art HLS tools. Indeed, we had to explicitly describe the organization of the pipeline, forwarding logic as well as the multi-cycle operators integration mechanics. We believe that this kind of optimizations could be done automatically by source-to-source transformations. As a future work on this project, we plan to develop more complex micro-architectures (ISA extensions, interrupt controller for OS support, out-oforder processor, shared-memory multiprocessor) to evaluate how far the limits of HLS can be pushed.

Comet is fully open-source and can be found at https:// gitlab.inria.fr/srokicki/Comet.

Fig. 1 .

 1 Fig. 1. Hardware processor development flow based on High-Level Synthesis.

TABLE I AREA

 I AND FREQUENCY RESULTS FOR DIFFERENT RISC-V CORES SYNTHESIZED USING A 28 NM TECHNOLOGY NODE.

	Core	ISA	freq.	Area	Lang.
			(MHz) (µm 2 )
		rv32i		8 168
	Comet [14]	rv32im		11 099	C++
		rv32imf		26 760
	Rocket [12]	rv32i rv32im	700	11 114 12 606	Chisel
		rv32imf		26 550
	PicoRV [15]	rv32i rv32im		7 747 Verilog 11 176

TABLE IV SIMULATOR

 IV PERFORMANCE AS A FUNCTION OF THE CORE CONFIGURATION. RESULTS ARE GIVEN IN MCPS WHICH STANDS FOR MILLIONS OF SIMULATED CYCLES PER SECOND.

	Supported extension	rv32i rv32im rv32imf
	Simulator perf. w/o L1 (Mcps)	23.6	18.2	15.1
	Simulator perf. w/ L1 (Mcps)	16.7	13.0	11.6

ACKNOWLEDGEMENTS

The authors thank Valentin Egloff, Edwin Mascarenhas, Lauric Desauw and Gurav Datta for their technical involvement and their contributions in the Comet project. This work was partly funded by the Rapid-DGA Flodam project.