Dimitri Van Landuyt

Steven Op De Beeck

Aram Hovsepyan

Sam Michiels

Wouter Joosen

Sven Meynckens

Gjalt De

Jong Melexis

Olivier Barais

Mathieu Acher

Towards Managing Variability in the Safety Design of an Automotive Hall Effect Sensor

Keywords: D.2.10 [Software Engineering]: Design-Methodologies, Representation, D.2.11 [Software Engineering]: Software Architectures-Domain-specific architectures, D.2.13 [Software Engineering]: Reusable Software-Reusable libraries, Reuse models Software product line engineering, hardware/software codesign, Safety patterns, automotive, ASIL validation

This paper discusses the merits and challenges of adopting software product line engineering (SPLE) as the main development process for an automotive Hall Effect sensor. This versatile component is integrated into a number of automotive applications with varying safety requirements (e.g., windshield wipers and brake pedals).

This paper provides a detailed explanation as to why the process of safety assessment and verification of the Hall Effect sensor is currently cumbersome and repetitive: it must be repeated entirely for every automotive application in which the sensor is to be used. In addition, no support is given to the engineer to select and configure the appropriate safety solutions and to explain the safety implications of his decisions.

To address these problems, we present a tailored SPLEbased approach that combines model-driven development with advanced model composition techniques for applying and reasoning about specific safety solutions. In addition, we provide insights about how this approach can reduce the overall complexity, improve reusability, and facilitate safety assessment of the Hall Effect sensor.

INTRODUCTION

Many software-based systems and products are designed to be versatile, i.e. they solve different problems for different customers. To accomplish this, the development addresses the superset of the requirements of sufficiently large groups of customers. Versatility is a common -yet often implicitarchitectural driver in the development of software-based systems and products because it makes production economically feasible: servicing more customers with a single product increases the return on investment of the development costs, and benefits from economies of scale [START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF].

As a downside however, it shifts some of the responsibility and complexity to the deployment and integration stages of development. In many cases, it is left to the customer to customize the product to his needs as part of a system integration project and this requires a deeper understanding of the product and its many possible configurations.

The above applies to the industry case that we have analyzed in the context of a collaborative research project called MERgE [START_REF]Merge: Multi-concerns interactions system engineering[END_REF]. This case involves the design of an integrated Hall Effect sensor used in automotive systems. This product by Melexis, a market leader in automotive sensors, is called Triaxis® MLX90365 [START_REF] Melexis | MLX90365 Hall Effect Sensor IC. Product Datasheet[END_REF]. A Hall Effect sensor is a transducer that varies its output voltage in response to a magnetic field, allowing sensors to calculate angles in two-or threedimensional spaces. This product is currently integrated in a wide range of automotive applications with varying safety requirements, ranging from windshield wipers, to brake or gas pedals. On average, recent cars may have 10 such sensors, and the MLX90365 Hall Effect sensor is currently being used for around 30 different automotive applications. Economy of scale is realized by mass-producing a one-size-fits-all product and the burden of configuration and integration is placed on the integration engineer or the customer (typically an automobile constructor).

Melexis currently applies a hardware-software codesign [START_REF] Wolf | Hardware/Software Co-Design: Principles and Practice[END_REF] development methodology. Although this is an effective approach to deliver versatile products to the market, this practice suffers from the following shortcomings:

1. Safety is a key concern that affects both the development process and the end product. The main hardware-and software-related design decisions are strongly motivated and affected by safety solutions (e.g. architectural patterns and tactics for safety). In the current practice, safety complicates matters in two ways. Firstly, as safety solutions have a profound impact on the end product, it is hard to reason about them in isolation (for example to validate their soundness) and to explore alternatives. Secondly, safety verification and assessment in practice is cumbersome, repetitive and therefore costly as (i) the notion of safety is strongly based on that of a safety hazard, which is very specific to the automotive application at hand and (ii) the versatile nature of the application defines a large configuration space which must in principle be explored in full (all possible combinations of configuration parameters) to assess the effects of different parameter combinations on safety.

Reusability.

A consequence of the hardware-software co-design approach is that the resulting implementation artifacts are of a platform-specific nature, which makes them hard to reuse across different hardware platforms. However, since Melexis already adopts a hardware-based product-line approach, there is large potential for (i) implementationlevel reuse, (ii) reuse of architectural safety patterns, and (iii) consolidation and reuse of expert knowledge over product variants.

3.

Variability. The focus on designing a highly versatile component is in essence the materialization of variability as a key development concern. The core problem with the current practice is caused by the fact that the complexity associated to variability profoundly affects the end product, and this complexity is addressed very late in the development process (at integration/configuration time). This is complicated further by the observation that three fundamentally different types of variability affect the Hall Effect sensor: (i) variability in the functionality, (ii) variability in the different safety solutions, (iii) variability across the hardware-software boundary. The current state of practice mainly addresses the first type [START_REF] Schulze | Functional safety and variability: Can it be brought together?[END_REF][START_REF] Rosana | Incorporating certification in feature modelling of an unmanned aerial vehicle product line[END_REF]. We face the challenge of handling two additional forms of variability that also are highly interrelated.

In this paper, we report on our detailed analysis of these concerns and the interplay between them in the context of this industry case. In a second step, we propose a tailored approach that combines Software Product Line Engineering (SPLE) with Model-driven Development (MDD) and advanced model-based concern composition techniques for model-based instantiation of safety patterns. Finally, we provide insights about how our proposal can reduce the overall complexity, improve the reusability, and facilitate the safety assessment of the Hall Effect sensor. In comparison to related work [START_REF] Schulze | Functional safety and variability: Can it be brought together?[END_REF][START_REF] Rosana | Incorporating certification in feature modelling of an unmanned aerial vehicle product line[END_REF], these are complementary insights about the impact of safety in a variability-intensive industrial context.

This paper is structured as follows. Section 2 highlights the results of our in-depth concern analysis exercise on the existing product and current development practices. Section 3 distills the overall motivation for investigating and exploring alternative development methods and techniques. Then, Section 4 presents the proposed development approach, and Section 5 provides our insights and arguments why we expect it to be beneficial to Melexis. Section 6 presents related work and Section 7 concludes the paper.

CONCERN ANALYSIS

We have performed a detailed analysis of the different concerns that affect the current design of the MLX90365 Hall Effect Sensor. This was conducted as follows: firstly, we have studied the existing technical specifications and design documents. Secondly, we have conducted a number of ATAM-style [START_REF] Bass | Software Architecture in Practice[END_REF] workshops with Melexis engineers to obtain a precise understanding of the current product and the different concerns playing a role, how they interact and which essential trade-offs have been made between these concerns. In the following sections, we discuss the main results of this activity.

Safety

Given its integration in automotive applications that potentially lead to hazards endangering human life, MLX90365 is a safety-critical building block. The Functional Safety for Road Vehicles standard (ISO 26262 [START_REF]Road vehicles -functional safety (iso 26262[END_REF][START_REF]J2980 -Considerations for ISO 26262 ASIL Hazard Classification[END_REF]) is the applicable safety standard in the Automotive domain, defining a risk classification scheme called the Automotive Safety Integrity Level (ASIL). As with other safety assessment standards (e.g. IEC-61508 [START_REF]) Subcommittee 65A: Industrial-process measurement, control and automation -Systems aspects. Functional safety[END_REF]), the assessment of hazard factors is based on the relative impact of hazardous effects related to a system (Severity), and the relative likelihoods of the hazard manifesting those effects (Exposure and Controllability). ASIL defines five Risk Levels, ranging from ASIL D, the strictest level, to QM (Quality Management), representing applications in which the safety hazards are tolerable and do not need to be governed by ISO 26262. The remaining levels (ASIL C, B and A) represent intermediate degrees of hazard.

In the design of the MLX90365 Hall Effect sensor, the safety concern has had a clear impact on:

1. The development process: ISO 26262 prescribes a number of development-related practices, e.g. imposing clear traceability between requirements and code, imposing documentation quality, but also introducing safety verification and assessment activities (involving safety testing and expert review).

2. The end product: From a software engineering point of view, "architectural concerns with safety are almost identical to those for availability, which is also about recovering from failures. Tactics for safety, then, overlap with those for availability for a large degree." [START_REF] Bass | Software Architecture in Practice[END_REF]. Two examples of architectural safety patterns that have been instantiated in the design of MLX90365 are:

• Watchdog (similar to the heartbeat-tactic [START_REF] Bass | Software Architecture in Practice[END_REF]): a watchdog is a hardware-based countdown timer that continually decreases a variable. If the variable reaches zero, the watchdog resets the system (hard reset). When the software is operating normally, it continually sends out watchdog "ticks", which causes the variable to be reset to its maximum value. As long as the software runs normally, the watchdog will not intervene.

• Fail-safe mode (graceful degradation tactic [START_REF] Bass | Software Architecture in Practice[END_REF]): when unrecoverable errors are detected (e.g. impossible input values), the system will go into fail-safe mode.

Fail-safe mode is reported to the output: the system is reporting the error instead of outputting unreliable measurements, which might cause unpredictable behavior. Debouncing is a tactic commonly used in combination with this pattern: to avoid going into failsafe mode on the basis of outliers and occasional errors and exceptions, a tactic called debouncing is applied, meaning that certain errors are ignored until they occur systematically.

Reuse

The MLX90365 Hall Effect sensor is not a stand-alone product, but is in itself part of a family of related products (cf. [START_REF] Melexis | Triaxis product overview[END_REF]). Being of MLX heritage, some elements of MLX90365 are the result of practical reuse, in terms of design but mostly implementation. Reuse is accomplished at the code level, i.e. code fragment and/or modular functions have been copy-pasted from different code bases. This has been documented in the technical specification: e.g., "It comes directly from 90360 f/w -reuse, coded in C." (annotated in the documentation of a number of supporting functions).

Variability

We have identified three different types of variability that affected the design of the MLX90365 Hall Effect sensor. We adopt the distinction between internal and external variability [START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF]:

Variability due to versatility.

As discussed, the MLX90365 Hall Effect sensor is designed to be highly versatile, i.e. it must serve the purposes for a wide range of different automotive applications. To realize this degree of versatility, a configuration interface is provided in the form of a set of writable EEPROM parameters that have to be set at integration time, either by a Melexis engineer or by the automobile constructor himself. The functionality of the Hall Effect sensor depends highly on these specific parameters. To address this form of external variability, in total 54 EEPROM parameters are provided to the customer. For example 1 , they provide the means to configure:

• The axes according to which the sensor must be calculate angles (either (X, Y ), (X, Z), or (Y, Z)), and the rotation of the coordinate base.

• Different applications require different types of digital transformations being applied to the acquired angles. For example, for a brake pedal, the range between [10 -15] will only apply light braking, while the range between [15 -25] will apply heavy braking, and the range [25 -30] will apply emergency braking.

Realization-driven variability for safety.

Apart from these functionality-related configurations, the EEPROM parameters provide the means to set safetyrelated configuration parameters. Examples include: debouncing parameters, ROM checksums, optionality parameters, sanity intervals, etc.

These variables realize a form of internal variability as they directly influence the safety mechanisms at play and thus indirectly affect the ASIL safety level that can be attained. For example, in automotive applications that are less safety-critical (e.g. windshield wiper), some safety features can be disabled or configured to be very liberal (e.g. setting the debouncing threshold to an unrealistic value) to practically disable them. This is a form of internal variability that relates to how a specific safety level can be realized. There are in practice different strategies to realize compliance to a certain ASIL level (different combinations of safety patterns), and making the appropriate decision is left to the Melexis integration engineer with expert knowledge on the matter.

Variability across HW/SW boundary.

Another form of internal variability is related to the embedded nature of the Hall Effect sensor. As the hardware platform is designed and refined, so too will these decisions 1 These are strongly simplified and abstracted examples. affect the implementation of the software. One example is the inclusion of the necessary hardware components to implement for example a Watchdog in products that require safety levels to which the Watchdog pattern contributes. Another example is related to the necessity of implementing a safety pattern involving continuously testing the RAM, which depends highly on the likelihood of RAM corruptions (bit flips), and is a specific characteristic of the selected hardware.

MOTIVATION

We have identified a number of essential problems with the current state of practice that was characterized in the previous section. These problems are elaborated below.

Safety engineering.

In the current practice, safety assessment and verification (i.e. ASIL) are cumbersome, repetitive and therefore costly development activities. This has a number of causes:

• Safety verification is based heavily on the notion of a safety hazard that in turn depends on the nature of the automotive application for which the Hall Effect sensor is used. For example, a windshield wiper is less safety-critical than a brake pedal because less safety hazards are associated to a faulty windshield wiper. As a consequence, safety assessment and verification has to be re-executed whenever the Hall Effect sensor is used in a different application, and in many cases, this entails repeating earlier efforts.

• In addition, safety verification activities always start from scratch. However, as many products in the same product family share a large number of architectural decisions and design elements, there is large potential for reuse of verification effort. Because the current development methodology does not involve reuse of existing safety solutions (e.g. safety patterns), nor reuse of architectural decisions (architectural knowledge related to when to pick which safety pattern), these activities involve repeating earlier-spent and costly verification efforts.

• The versatile nature of the Hall Effect sensor implies that the entire configuration space (all potential combinations of configuration parameters) has to be explored to attain a certain degree of confidence, even though some solutions will in practice be inactive (e.g. safety mechanisms such as debouncing). Due to the versatile nature of the Hall Effect sensor, the safety solutions provided in the end product must comply for the strictest validation requirements. In addition, safety verification must include showing that there is freedom of interference between the inactive and the active safety mechanisms.

Product-line reuse.

The existing product line setting described in Section 2.2 has a lot of potential for reuse. However, reuse of specific elements of a single product is difficult in the current state of practice:

• Implementation-level reuse is difficult due to the hardware-specific nature of development on the one hand, and due to typical maintainability problems associated to the current state of practice of copypasting code fragments and/or individual functions on the other hand.

• Safety patterns. As mentioned above, the current methods and techniques do not allow reusing architectural patterns related to safety. More so, current safety solutions are not described as separate, reusable patterns, but are implemented directly in the Hall Effect sensor. The safety engineer is responsible for instantiating these patterns correctly, but he is provided limited tool support for the task at hand.

• Consolidation and reuse of expert knowledge. Most of the architectural knowledge about key decisions related to safety and other concerns remains implicit. As a result, the knowledge about (i) when to use which pattern, (ii) the costs associated to specific safety patterns, (iii) the implications of selecting a pattern on ASIL assessment, and (iv) which patterns interaction (either positively or negatively) remains unrecorded. Nonetheless, this is critical information to create and maintain a successful product line-based offering.

Variability management.

In Section 2.3, we introduced three types of variability that affect the design of the Hall Effect sensor.

• Variability due to versatility is currently covered very late in the development process (i.e. at configuration/integration time), at the cost of dragging along features (that are potentially unnecessary for the targeted automotive application and require unnecessary verification and assessment effort) throughout the development life-cycle.

• Realization-driven variability for safety is not supported in current practice. Safety decisions are made early on in the development process and motivated by implicit expert knowledge, while alternative solutions are disregarded.

• Finally, variability across the HW/SW boundary is not supported in current practice. More specifically, the design of the hardware platform is decided in an initial phase of the development process, and thereafter, these hardware decisions serve as fixed technical constraints for the software design activities.

APPROACH

Figure 1 depicts the proposed development approach, which is tailored for the design of the MLX90365 Hall Effect sensor. Our approach is aligned with the generic SPLE method by Pohl et al. [START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF]. The practical realization of this approach is currently ongoing work in the context of the MERgE research project [START_REF]Merge: Multi-concerns interactions system engineering[END_REF].

The Domain Engineering activities (presented at the top of the figure) are:

• Domain Analysis involves studying the requirements for multiple instances of the Hall Effect sensor. Some of the results of this activity have been highlighted in Section 2. This activity leads to the definition of the feature model for external variability, which in our ongoing implementation efforts is created using FAMIL-IAR [START_REF] Mathieu Acher | Familiar: A domain-specific language for large scale management of feature models[END_REF], a domain-specific language for performing feature model elaboration, reasoning, and manipulation (e.g., composition).

• Domain Design concerns defining reusable architectural models that can be composed to generate specific solutions. We create these models using SysML [START_REF]The Object Management Group (OMG. SysML: Systems Modeling Language[END_REF], an OMG standard for systems engineering. In addition, the internal variability model is created which defines the alternative safety solutions and their effect on the ASIL level.

• Domain Realization involves creating implementation artifacts on a per-feature basis.

• Domain Verification involves the creation of reusable tests and ASIL verification inputs on a perfeature basis.

The Application Engineering activities (presented at the bottom of the figure) are:

• Product Configuration involves tailoring the product to the specific requirements of the automotive application (e.g. setting the axes) on the basis of the external feature model. This is supported by FAMIL-IAR [START_REF] Mathieu Acher | Familiar: A domain-specific language for large scale management of feature models[END_REF].

• Solution Generation involves generating alternative solutions that comply to the product configuration by combining the alternatives for realization defined in the internal feature model. These architectural variants are generated by instantiating the safety patterns into the base model. This is done with the Pattern Instantiation tool, which is part of the Thales Melody Advance software [START_REF]Melody advance system modeler: Pattern instantiation tool, soon to be opensourced[END_REF].

• Analysis and Selection involves comparing the different architectural candidates and selecting the most suitable variant.

• Code Generation deals with creating an implementation by composing the feature implementations that correspond to the selected architectural variant.

• Safety Assessment and Verification involves applying the composed tests, and extended test activities, which for example lead to ASIL validation of the entire end product.

To realize the entire approach, we are applying kCVL, an implementation of CVL [START_REF]The Common Variability Language (CVL)[END_REF]. kCVL is able to manage the different artifacts (feature models, SysML models, safety patterns) and supports variant derivation. For more details, please refer to http://barais.github.io/splc2014merge/

DISCUSSION

In this section, we provide insights on how the key principles behind this process are expected to improve the current state-of-practice. Safety is supported explicitly. The internal variability model documents safety solutions and provides explicit support on how to attain specific safety levels. As such the Reuse is accomplished at multiple levels. At the level of architectural models, which describe either the main functionality for angle measurement (the base model ), or specific architectural safety patterns. As part of the Model-Driven nature of the approach, these are then composed using advanced model transformation techniques and composition mechanisms as part of the Solution Generation activity. As corresponding implementation and tests are structured on a per-feature fashion, different variants of the firmware respectively the test suites for that firmware can be generated. As a direct result of this tailored approach, traceability links can easily be maintained and documented.

Variability is managed up front by adopting a top-down SPLE-based approach. External variability is kept apart from internal variability by introducing two distinct variability models. Maintaining this distinction is essential as the former represents configuration options offered to the customer, while the latter represents architectural alternatives in the safety solution space. Unnecessary features (those that are not selected during product configuration) will not be present in the generated firmware and will not be taken into account during safety assessment and verification. In addition, the generated firmware is a priori compliant to the constraints set by the feature models, and so, unrealistic or impossible variants are excluded very early on in the development process. Finally, by having a streamlined approach, the generation of traceability documentation will require less manual effort and thus be easier (a consequence of feature decomposition applied already at the early stages of development and maintained thereafter) and this in turn facilitates ASIL assessment.

RELATED WORK

Safety and SPLE. The issues raised by safety assessment are apparent in many software-intensive systems. In an SPLE context, the process of assessing and checking safety properties has to be applied to each (potential) product. The variability (or versatility) of a product (or the management of related similar products) substantially increases the complexity. In practice, the amount of possible products is exponential to the number of variation points (parameters, features, options, etc).

At the theoretical level, numerous techniques have been developed to efficiently check a SPL [START_REF] Thüm | A classification and survey of analysis strategies for software product lines[END_REF][START_REF] Kishi | Formal verification and software product lines[END_REF]. These techniques are based on testing, type checking, model checking, or theorem proving; they can verify the whole set of product or only a subset, etc. With many sources of variability, our context precludes a full checking of every possible product. Moreover the safety properties are difficult to properly formalize, an assumption of many research works.

From an industrial perspective, few papers report on their experience in managing safety in an SPLE context [START_REF] Schulze | Functional safety and variability: Can it be brought together?[END_REF][START_REF] Rosana | Incorporating certification in feature modelling of an unmanned aerial vehicle product line[END_REF]. Schulze et al. [START_REF] Schulze | Functional safety and variability: Can it be brought together?[END_REF] demonstrated that safety-related artifacts can be treated like other artifacts and presented a comprehensive model-based tool. We are following the same direction by linking feature models with safety modeling artifacts. Yet two additional, technical solutions have to be developed and integrated for (1) applying safety patterns (as part of the derivation process) and (2) managing multiple feature models (see below). As emphasized in the paper, the former activity is central to the success of a product line approach and requires further work (e.g., to compare applications of different safety patterns and then determine the most suitable).

Multi-variability. We observe multiple sources of variability in the industrial context. Pohl et al. proposed to distinguish internal variability from external variability [START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF]. Hubaux et al. reviewed the different concerns addressed in feature modeling [START_REF] Hubaux | Separation of concerns in feature diagram languages: A systematic survey[END_REF]. Two kinds of variability caught our attention: hardware variability and realization-driven variability. Another noticeable observation is that the different sources of variability are intimately related. We are investigating compositional SPL techniques to manage this complexity [START_REF] Hubaux | Separating concerns in feature models: Retrospective and support for multi-views[END_REF][START_REF] Bosch | Toward compositional software product lines[END_REF].

CONCLUSION

This paper has presented an industrial case -the design of a Hall Effect sensor-in which we combine techniques of Software Product Line Engineering (SPLE), Modeldriven Development (MDD) and advanced model composition mechanisms to model and instantiate architectural safety patterns. Specifically, we presented a detailed concern analysis with a focus on safety, reusability and variability. In addition, we presented a tailored development methodology for the Hall Effect sensor, of which we expect that it will simplify the end product, and make safety verification easier and less costly.

One of the main merits of this case is that it is a rather atypical example of an industrial system suited for SPLE, yet that it provides clear indications of the added value of adopting these techniques. In addition, the presented approach is effectively being applied on next-generation products and actively influences the business and product roadmap of Melexis.

Future work will focus on empirically validating the proposed approach, by assessing how this alternative development methodology improves the current practice, in terms of key performance indicators (KPIs) currently employed by Melexis, such as the required developer effort and effective reuse of expert knowledge and solutions over time. In addition, we will investigate broadening the scope from software design to system design (SW/HW), in order to address the most challenging type of variability manifesting itself in this industry case: variability across the hardware/software boundary.

Acknowledgements. The presented research is partially funded by the Research Fund KU Leuven and the Flemish agency for Innovation by Science and Technology (IWT 120085). The research activities were conducted in the context of ITEA2-MERgE (Multi-Concerns Interactions System Engineering, ITEA2 11011), a European collaborative project with a focus on safety and security [5].


Fanny Dufossé

Kamer Kaya

Bora Uçar

Bipartite matching heuristics with quality guarantees on shared memory parallel computers

Keywords: matching, bipartite graphs, graphs, randomized algorithm, approximation algorithm, shared memory

We propose two heuristics for the bipartite matching problem that are amenable to shared-memory parallelization. The first heuristic is very intriguing from parallelization perspective. It has no significant algorithmic synchronization overhead and no conflict resolution is needed across threads. We show that this heuristic has an approximation ratio of around 0.632. The second heuristic is designed to obtain a larger matching by employing the well-known Karp-Sipser heuristic on a judiciously chosen subgraph of the original graph. We show that the Karp-Sipser heuristic always finds a maximum cardinality matching in the chosen subgraph. Although the Karp-Sipser heuristic is hard to parallelize for general graphs, we exploit the structure of the selected subgraphs to propose a specialized implementation which demonstrates a very good scalability. Based on our experiments and theoretical evidence, we conjecture that this second heuristic obtains matchings with cardinality of at least 0.866 of the maximum cardinality. We discuss parallel implementations of the proposed heuristics on shared memory systems. Experimental results, for demonstrating speed-ups and verifying the theoretical results in practice, are provided.

Heuristiques de couplage avec garantie de cardinalité dans des graphes bipartis pour les ordinateurs parallèles à mémoire partagée

Résumé : Cet article étudie le problème de couplage dans des graphes bipartis et propose deux heuristiques adaptées à une parallélisation dans un contexte de mémoire partagée. La première heuristique est particulièrement intéressante du point de vue du parallélisme. Sa parallélisation ne cause aucun surcoût lié à des synchronisations, ni aucun conflit mémoire. Nous montrons que cette heuristique approche le couplage maximal d'un ratio d'environ 0,632. La seconde heuristique utilise l'heuristique de Karp-Sipser sur un sous-graphe judicieusement choisi du graphe original. Nous montrons que l'algorithme de Karp-Sipser obtient toujours le couplage maximal pour le sous-graphe considéré. Cet algorithme n'est que difficilement parallélisable dans le cas général, mais la structure particulière des sous-graphes considérés nous permet de proposer une implémentation adaptée à une exécution parallèle. Nous conjecturons que cette seconde heuristique approche le couplage maximal d'un ratio d'environ 0,866. Nous abordons les possibles implémentations parallèles de ces heuristiques sur un système à mémoire partagée. Des résultats expérimentaux montrent l'accélération du calcul due à l'exécution parallèle et confirment dans la pratique les résultat théoriques.

Mots-clés : couplage, graphes bipartis, graphes, algorithme aléatoire, algorithme d'approximation, mémoire partagée.

Introduction

We consider the maximum cardinality bipartite matching problem. A matching in a graph is a set of edges no two of which share a common vertex. The maximum cardinality matching problem asks for a matching of maximum size. There are a number of polynomial time algorithms to solve this problem exactly. The smallest worst-case time complexity of the known algorithms is O( √ nτ ) for a bipartite graph with n vertices and τ edges-the first of such algorithms is described by Hopcroft and Karp [START_REF] Hopcroft | An n 5/2 algorithm for maximum matchings in bipartite graphs[END_REF]. There is considerable interest in simpler and faster algorithms that have some approximation guarantee. Such cheap algorithms are used as a jump-start routine by the current state of the art matching algorithms [START_REF] Duff | Design, implementation, and analysis of maximum transversal algorithms[END_REF][START_REF] Langguth | Heuristic initialization for bipartite matching problems[END_REF]. Most of these heuristics obtain good results in practice, but their worst-case guarantee is only around 1/2. A well-known heuristic, called Karp-Sipser (KS) heuristic [START_REF] Karp | Maximum matching in sparse random graphs[END_REF], finds maximum cardinality matchings in highly sparse (random) graphs but does not have a constant ratio approximation for denser ones (this algorithm will be reviewed later in Section 2). Algorithms that achieve an approximation ratio of 1 -1/e, where e is the base of the natural logarithm are designed for the online case [START_REF] Karp | An optimal algorithm for on-line bipartite matching[END_REF]. Many of these algorithms are sequential in nature in that a sequence of greedy decisions are made in the light of the previously made decisions.

We propose two matching heuristics (Section 3) for bipartite graphs. Both heuristics construct a subgraph of the input graph by randomly choosing some edges. They then obtain a maximum matching in the selected subgraph and return it as an approximate matching for the input graph. The probability density function for choosing a given edge in both heuristics is obtained with a sparse matrix scaling method. The first heuristic is shown to deliver a constant approximation guarantee of 0.632 of the maximum cardinality matching. The second one builds on top of the first one and improves the approximation ratio. Based on thorough experiments and theoretical evidence, we conjecture that the second heuristic obtains matchings with cardinality of at least 0.866 of the maximum. Both of the heuristics are designed to be amenable to parallelization. The first heuristic does not require a conflict resolution scheme nor it has any synchronization requirements. The second heuristic employs KS to find a matching on the selected subgraph. We show that KS becomes an exact algorithm on those subgraphs. Further analysis of the properties of those subgraphs is carried out to design a specialized implementation of KS for efficient parallelization on shared memory systems. The approximation guarantees of the two proposed heuristics do not deteriorate with the increased degree of parallelization, thanks to their design, which is usually not the case for parallel matching heuristics [START_REF] Azad | Multithreaded algorithms for maximum matching in bipartite graphs[END_REF].

Let G = (V R ∪ V C , E) be a bipartite graph, where V R and V C are two vertex classes and E is the edge set. G can be represented as a sparse matrix A. Each row (column) of A corresponds to a unique vertex in V R (in V C ) so that a ij = 1 if and only if (v i , v j ) ∈ E. We first assume that bipartite graphs have two properties: (i) the same number of vertices in both vertex classes; (ii) each edge appears in a matching that contains all vertices. These bipartite graphs correspond to square, fully indecomposable matrices, or block diagonal matrices with each block being fully indecomposable. These assumptions simplify the theoretical analysis. Later on, we discuss the bipartite graphs without these properties and demonstrate (in Section 4) that the proposed heuristics deliver results that concur with those of the assumed case.

Notation and preliminaries

Using the analogy between a matrix and a bipartite graph, we refer to the vertices in the two classes as row and column vertices. The number of edges incident on a vertex is called its degree. A path in a graph is a sequence of vertices such that each consecutive vertex pair share an edge. A vertex is reachable from another one, if there is a path between them. The connected components of a graph are the equivalence classes of vertices under the "is reachable from" relation. A cycle in a graph is a path whose start and end vertices are the same. A simple cycle is a cycle with no vertex repetitions. A tree is a connected graph with no cycles. A spanning tree of a connected graph G is a tree containing all vertices of G.

Matching

A matching M in a graph G = (V R ∪V C , E) is a subset of edges E where a vertex in V R ∪ V C is in at most one edge in M. Given a matching M, a vertex v is said to be matched by M if v is in an edge of M, otherwise v is called unmatched.
If all the vertices are matched by M, then M is said to be a perfect matching. The cardinality of a matching M, denoted by |M|, is the number of edges in M. The maximum cardinality matching problem asks for a matching of maximum size. There are a number of well-known, exact, and polynomial-time algorithms for this problem. A recent paper [START_REF] Kaya | Push-relabel based algorithms for the maximum transversal problem[END_REF] gives a classification of those algorithms.

Parallel (exact) matching algorithms on modern architectures have been recently investigated. Azad et al. [START_REF] Azad | Multithreaded algorithms for maximum matching in bipartite graphs[END_REF] study the implementations of a set of known bipartite graph matching algorithms on shared memory systems. Deveci et al. [START_REF] Deveci | A push-relabel-based maximum cardinality matching algorithm on GPUs[END_REF][START_REF] Deveci | GPU accelerated maximum cardinality matching algorithms for bipartite graphs[END_REF] investigate the implementation variants of some matching algorithms on GPU. There are quite good speedups reported in these implementations, yet there are non-trivial instances where parallelism does not help in any of them.

Our focus is on matching heuristics that have linear running time complexity and good quality guarantees on the size of the matching. A survey of matching heuristics is given by Kaya et al. [START_REF] Duff | Design, implementation, and analysis of maximum transversal algorithms[END_REF] and Langguth et al. [START_REF] Langguth | Heuristic initialization for bipartite matching problems[END_REF]. Recent studies focusing on approximate matching algorithms on parallel systems include heuristics for graph matching problem [START_REF] Çatalyürek | Multithreaded clustering for multi-level hypergraph partitioning[END_REF][START_REF] Fagginger Auer | A GPU algorithm for greedy graph matching[END_REF][START_REF] Halappanavar | Approximate weighted matching on emerging manycore and multithreaded architectures[END_REF] and also heuristics used for initializing bipartite matching algorithms [START_REF] Azad | Multithreaded algorithms for maximum matching in bipartite graphs[END_REF].

The simplest heuristic is called the cheap matching that has two variants in the literature. The first variant randomly visits the edges and matches the two endpoints of an edge if they are both available. The theoretical performance guarantee of this heuristic is 1/2, i.e., the heuristic delivers matchings of size at least half of the maximum matching cardinality. This is analyzed theoretically [START_REF] Dyer | Randomized greedy matching[END_REF] and shown to obtain results that are near the worst-case on certain classes of graphs. The second variant of the cheap matching heuristic repeatedly selects a random vertex and matches it with a random neighbor. The matched vertices, along with the ones which become isolated, are removed from the graph and the process continues until the whole graph is consumed. This variant also has a 1/2 worst-case approximation guarantee (see for example a proof by Pothen and Fan [START_REF] Pothen | Computing the block triangular form of a sparse matrix[END_REF]), and it is somewhat better (0.5 + for ≥ 0.0000025 [START_REF] Aronson | Randomized greedy matching II[END_REF] which has been recently improved to ≥ 1/256 [START_REF] Poloczek | Randomized greedy algorithms for the maximum matching problem with new analysis[END_REF]).

We make use of a heuristic algorithm, called Karp-Sipser (KS). We summarize it and refer the reader to original paper [START_REF] Karp | Maximum matching in sparse random graphs[END_REF]. The theoretical foundation of the KS heuristic is that if there is a vertex v with exactly one neighbor (v is called RR n°8386 degree-one), then there is a maximum cardinality matching in which v is matched with its neighbor. That is, matching v with its neighbor is an optimal decision. Using this, the KS heuristic runs as follows. Check whether there is a degree-one vertex; if so then match the vertex with its unique neighbor and delete both vertices (and the edges incident on them) from the graph. Continue this way until the graph has no edges (in which case we are done) or all remaining vertices have degree larger than one. In the latter case, pick a random edge, match the two endpoints of this edge, and delete those vertices and the edges incident on them. Then repeat the whole process on the remaining graph. The phase before the first random choice of edges made by the KS algorithm is called Phase 1, and the rest is called Phase 2 (where new degree-one vertices may arise). The running time of this heuristic is linear. This heuristic matches all but Õ(n 1/5 ) vertices of a random undirected graph [START_REF] Aronson | Maximum matchings in sparse random graphs: Karp-Sipser revisited[END_REF]. One disadvantage of KS is that because of the degree dependencies of the vertices to the already matched vertices, an efficient parallelism is hard to achieve (a list of degree-one vertices needs to be maintained). That is probably why some inflicted forms (successful but without any known quality guarantee) of this heuristic were used in recent studies [START_REF] Azad | Multithreaded algorithms for maximum matching in bipartite graphs[END_REF].

Scaling matrices to doubly stochastic form

An n × n matrix A is said to have a support if there is a perfect matching in the associated bipartite graph. An n × n matrix A is said to have total support if all its nonzero entries can be put into a perfect matching. Any nonnegative matrix A with total support can be scaled with two (unique) positive diagonal matrices D R and D C such that D R AD C is doubly stochastic (that is, the sum of entries in any row and in any column of D R AD C is equal to one). If A has a support but not a total support then A can be scaled to a doubly stochastic matrix but not with two positive diagonal matrices (see [START_REF] Sinkhorn | Concerning nonnegative matrices and doubly stochastic matrices[END_REF] or more recent treatments [START_REF] Knight | The Sinkhorn-Knopp algorithm: Convergence and applications[END_REF][START_REF] Knight | A symmetry preserving algorithm for matrix scaling[END_REF][START_REF] Ruiz | A scaling algorithm to equilibrate both row and column norms in matrices[END_REF]).

Here we review two algorithms for doubly-stochastic matrix scaling from the literature. The Sinkhorn-Knopp scaling algorithm [START_REF] Sinkhorn | Concerning nonnegative matrices and doubly stochastic matrices[END_REF] generates a sequence of matrices (whose limit is doubly stochastic) by normalizing the columns and the rows of the sequence of matrices alternately. That is, the initial matrix is normalized such that each column has sum one. Then, the resulting matrix is normalized so that each row has sum one and so on so forth. This algorithm has been recently analyzed where most of the known results are summarized [START_REF] Knight | The Sinkhorn-Knopp algorithm: Convergence and applications[END_REF].

Another scaling algorithm is proposed by Ruiz [START_REF] Ruiz | A scaling algorithm to equilibrate both row and column norms in matrices[END_REF], parallelized for distributed [START_REF] Amestoy | A parallel matrix scaling algorithm[END_REF] and shared memory [START_REF] Çatalyürek | On shared-memory parallelization of a sparse matrix scaling algorithm[END_REF] parallel systems, and its properties are investigated [START_REF] Knight | A symmetry preserving algorithm for matrix scaling[END_REF]. This algorithm also builds a sequence of matrices converging to a double stochastic matrix. Instead of normalizing the rows and columns of the matrices alternately, this algorithm scales the rows and the columns of each matrix in the sequence. It has been shown that [START_REF] Knight | A symmetry preserving algorithm for matrix scaling[END_REF] this algorithm converges slower than the Sinkhorn-Knopp algorithm for unsymmetric matrices. For the symmetric matrices, there is no such a clear cut distinction.

We use a parallel implementation of the Sinkhorn-Knopp scaling method, shown in Algorithm 1, but other doubly stochastic scaling methods can also be used. In Algorithm 1, A i * and A * j are the sets of column and row indices of the nonzeros at the ith row and jth column of A, respectively. Instead of the diagonal scaling matrices D r and D c , we use two arrays d r and d c to store the (diagonal) entries of the scaling matrices. As is seen, the method runs until convergence, where we want to stop when both the row sums and column sums are sufficiently close to one. At each iteration, we first balance the columns and then the rows, at which point the row sums are one (modulo round-off errors), but the column sums are not. The stopping criteria for convergence is therefore to have the maximum difference between the column sums and one as small as possible. At the end, d r [i] × a ij × d c [j] gives the scaled entry. There are techniques to improve the parallel performance of Algorithm 1. For example, in case of skewness in degree distributions, one assign multiple threads to a single row with many nonzeros. However, we do not focus on this issues here.

Input: A: an n × n matrix with total support Output: dr, dc: row/column scaling arrays 1: for i = 1 to n in parallel do 2:

dr[i] ← 1 3: dc[i] ← 1 4: while not converged do 5: for j = 1 to n in parallel do 6: csum ← i∈A * j dr[i] × aij 7: dc[j] ← 1/csum 8: for i = 1 to n in parallel do 9: rsum ← j∈A i * aij × dc[j] 10: dr[i] ← 1/rsum Algorithm 1: ScaleSK: Parallel Sinkhorn-Knopp scaling

Two matching heuristics

We propose two simple matching heuristics for the maximum cardinality bipartite matching problem that are highly parallelizable and have guaranteed approximation ratios. The first heuristic does not require synchronization or conflict resolution. This heuristic and its approximation guarantee of around 0.632 are discussed in the following subsection. The second heuristic is designed to obtain larger matchings compared to those obtained by the first one. This heuristic employs KS on a judiciously chosen subgraph of the input graph. We show that for this subgraph, the KS heuristic is an exact maximum cardinality matching algorithm. Based on our experiments and theoretical evidence, we conjecture that the second heuristic obtains matchings of size around 0.866 of the maximum matching cardinality.

One-sided matching

The first matching heuristic we propose, OneSidedMatch, scales the given adjacency matrix A (each a ij is originally either 0 or 1) and uses the scaled entries to randomly choose a column as a match for each row. The pseudocode of the heuristic is shown in Algorithm 2.

OneSidedMatch first obtains the scaling vectors d r and d c corresponding to a doubly stochastic matrix S (line 1). After initializing the cmatch array, for each row i of A, the heuristic randomly chooses a column j ∈ A i * based on the probabilities computed by using corresponding scaled entries of row i. It then matches i and j. Clearly multiple rows can choose the same column and Input: A: an n × n, (0,1)-matrix with total support Output: cmatch[•]: the rows matched to columns 1: (dr, dc) ← ScaleSK(A) 2: for j = 1 to n in parallel do

3: cmatch[j] ← NIL 4: for i = 1 to n in parallel do 5:
Pick a random column j ∈ Ai * by using the probability density function

pi(k) = s ik Σ ∈A i * s i , for all k ∈ Ai *
where

s ik = dr[i] × dc[k]
is the corresponding entry in the scaled matrix S = DRADC .

6: cmatch[j] ← i
Algorithm 2: OneSidedMatch write to the same entry in cmatch. In a parallel, shared-memory setting, one of the write operation survives, and the cmatch array defines a valid matching, , i.e., {{cmatch[j], j} : cmatch[j] = NIL}. We now analyze its approximation guarantee in terms of the matching cardinality.

Theorem 1. Let A be an n×n, (0,1)-matrix with total support. Then, OneSid-edMatch obtains a matching of size at least n(1 -1/e) ≈ 0.632n.

Proof. To compute the matching cardinality, we will count the columns that are not picked by any row and subtract it from n. Since Σ k∈Ai * s ik = 1 for each row i of S, the probability that a column j is not picked by any of the rows in A * j is equal to i∈A * j (1 -s ij ). By applying the arithmetic-geometric mean inequality, we obtain

d j i∈A * j (1 -s ij ) ≤ d j -i∈A * j s ij d j ,
where

d j = |A * j | is the degree of column vertex j. Therefore, i∈A * j (1 -s ij ) ≤ 1 - i∈A * j s ij d j dj .
Since S is doubly stochastic, we have i∈A * j s ij = 1 and

i∈A * j (1 -s ij ) ≤ 1 - 1 d j dj .
The function on the right hand side above is an increasing one, and has the limit

lim dj →∞ 1 - 1 d j dj = 1 e ,
where e is the base of the natural logarithm. By the linearity of expectation, the expected number of unmatched columns is no larger than n e . Hence, the cardinality of the matching is no smaller than n (1 -1/e).

RR n°8386

In Algorithm 2, we split the rows among the threads with a parallel for construct. For each row i, the corresponding thread chooses a random number r from a uniform distribution with range (0, k∈Ai * s ik ]. Then the smallest column index j for which k∈Ai * s ik ≤ r is found and cmatch[j] is set to i. Since no synchronization or conflict detection is required, the heuristic promises significant speedups.

Two-sided matching

OneSidedMatch's approximation guarantee and suitable structure for parallel architectures make it a good cheap matching heuristic. The natural question that follows is whether a heuristic with a better guarantee while without being too complicated to parallelize exists. We asked: "what happens if we repeat the process for the other (column) side of the bipartite graph"? The question led us to the following algorithm. Let each row select a column, and let each column select a row. Take all these 2n choices to construct a bipartite graph G (a subgraph of the input) with 2n vertices and at most 2n edges (if i chooses j and j chooses i, we have one edge), and seek a maximum cardinality matching in G. Since the number of edges is at most 2n, any exact matching algorithm on this graph would be fast-in particular the worst case running time would be O(n 1.5 ) [START_REF] Hopcroft | An n 5/2 algorithm for maximum matchings in bipartite graphs[END_REF]. Yet, we can do better and obtain a maximum cardinality matching in linear time by running the Karp-Sipser heuristic on G, as we display in Algorithm 3. Pick a random column j ∈ Ai * by using the probability density function

pi(k) = s ik Σ ∈A i * s i , for all k ∈ Ai *
where

s ik = dr[i] × dc[k]
is the corresponding entry in the scaled matrix S = DRADC .

4:

rchoice[i] ← j 5: for j = 1 to n in parallel do

6:

Pick a random row i ∈ A * j by using the probability density function

qj(k) = s kj Σ ∈A * j s j
, for all k ∈ A * j.

7: cchoice[j] ← i 8: Construct a bipartite graph G = (VR ∪ VC , E) where E ={{i, rchoice[i]} : i ∈ {1, . . . , n}}∪ {{cchoice[j]
, j} : j ∈ {1, . . . , n}}.

9: match ←KarpSipser(G)

Algorithm 3: TwoSidedMatch

The most interesting component of TwoSidedMatch is the incorporation of the Karp-Sipser heuristic for two reasons. First, although it is only a heuristic, KS computes a maximum cardinality matching on the bipartite graph G constructed in Algorithm 3. Second, although KS has a sequential nature, we can obtain good speedups with a specialized, parallel implementation. In general, it is hard to parallelize (non-trivial) graph algorithms, and it is even harder when the overall cost is O(n) which is the case for KS on G. We give a series of lemmas below which enables us to use KS as an exact algorithm with a good shared-memory parallel performance.

The first lemma describes the structure of G constructed at line 8 of TwoSid-edMatch.

Lemma 1. Each connected component of G constructed in Algorithm 3 contains at most one simple cycle.

Proof. A connected component M ⊆ G with n vertices can have at most n edges. Let T be a spanning tree of M . Since T contains n -1 edges, the remaining edge in M can create at most one cycle when added to T . Lemma 1 explains why KS is an exact algorithm on G. If a component does not contain a cycle, KS consumes all its vertices in Phase 1. Therefore, all of the matching decisions given by KS are optimal for this component. Assume a component contains a simple cycle. After Phase 1, the component is either consumed, or due to Lemma 1, it is reduced to a simple cycle. In the former case, the matching is a maximum cardinality one. In the latter case, an arbitrary edge of the cycle can be used to match a pair of vertices. This decision necessarily leads to a unique perfect matching in the remaining simple path. These two arguments can be repeated for all the connected components to see that the KS heuristic finds a maximum cardinality matching in G.

Algorithm 4 describes our parallel KS implementation KarpSipserMT. The graph is represented using a single array choice, where choice[u] is the vertex randomly chosen by u ∈ V R ∪ V C . The choice array is a concatenation of the arrays rchoice and cchoice set in TwoSidedMatch. Hence, an explicit graph construction for G (line 8 of Algorithm 3) is not required, and a transformation of the selected edges to a graph storage scheme is avoided. KarpSipserMT uses three atomic operations for synchronization. The first operation _Add(memory, value) atomically adds a value to a memory location. It is used to compute the vertex degrees in the initial graph (line 9). The second operation _CompAndSwap(memory, value, replace) first checks whether the memory location has the value. If so, its content is replaced. The final content is returned. The third operation _AddAndFetch(memory, value) atomically adds a given value to a memory location and the final content is returned. We will describe the use of these two operations later.

KarpSipserMT has two phases which correspond to the two phases of KS. The first phase of KarpSipserMT is similar to that of KS in that optimal matching decisions are made about some degree-one vertices. The second phase of KarpSipserMT handles remaining vertices very efficiently, without bothering with their degrees. The following definitions are used to clarify the difference between an original KS implementation and KarpSipserMT.

RR n°8386

Input:

G = {V, choice[•]: the chosen vertex for each u ∈ V } Output: match[•]: the match array for u ∈ V 1: for all u ∈ V in parallel do 2: mark[u] ← 1 3: deg[u] ← 1 4: match[u] ← NIL 5: for all u ∈ V in parallel do 6: v ← choice[u] 7: mark[v] ← 0 8: if choice[v] = u
match[u] ← v 28: match[v] ← u Algorithm 4: KarpSipserMT RR n°8386
• in-one, if v is matched, and only a single unmatched vertex w with choice[w] = u exists. The first phase of KarpSipserMT (for loop of line 10) does not track and match all degree-one vertices. Instead, only the out-one vertices are taken into account. For each such vertex u that is already out-one before Phase 1, we have mark[u] = 1. KarpSipserMT visits these vertices (lines 10-11). Newly arising out-one vertices are consumed right away without maintaining a list. The second phase of KarpSipserMT (for loop of line 24) is much simpler than that of KS as the degrees of the vertices are not tracked/updated. We now discuss how these simplifications are possible while ensuring a maximum cardinality matching in G.

Observation 1. An out-one or an in-one vertex is a degree-one vertex according to KS. Proof. Let u be an in-one vertex and let v be the unmatched vertex such that choice[v] = u. Let P be the longest vertex sequence w 1 , w 2 , . . . , w k , u such that all w i s are unmatched, choice[w i ] = w i+1 for 1 ≤ i < k, and v = w k . If P has a finite length, then w 1 is an out-one vertex and we are done. On the other hand, if P has an infinite length it must contain a cycle. Furthermore, u must be in this cycle, since each w i 's next vertex, which also needs to be in the cycle, is uniquely defined by choice. But u is an in-one vertex and choice[u] is already matched. Thus P has a finite length, and an out-one vertex (w 1 ) always exists.

According to Observation 1, all the matching decisions given by Karp-SipserMT in Phase 1 are optimal, since an out-one vertex is a degree-one vertex. Observation 2 implies that among all the degree-one vertices, Karp-SipserMT ignores only the in-ones and 2-cliques. According to Lemma 2, an in-one vertex cannot exist without an out-one vertex, therefore they are handled in the same phase. The 2-cliques that survive Phase 1 are handled in KarpSipserMT's Phase 2, since they can be considered as cycles.

To analyze the second phase of KarpSipserMT, we will use the following lemma.

Lemma 3. Let G = (V R ∪ V C , E
) be the graph induced by the remaining vertices after the first phase of KarpSipserMT. Then, the set

{(u, choice[u]) : u ∈ V R , choice[u] ∈ V C } is a maximum cardinality matching in G .
Proof. Apart from 2-cliques, no out-one or in-one (that is no degree-one) vertex remains after Phase 1. A component of G can be a trivial (a singleton vertex), a 2-clique, or a simple cycle, according to Lemma 1. Let P be a non-trivial component. Since the original graph is bipartite, if P is a cycle it has the edges (u, choice[u]) and (choice[v], v) for u ∈ V R ∩ P and v ∈ V C ∩ P . The edge set

{(u, choice[u]) : u ∈ V R ∩ P, choice[u] ∈ V C }
defines a maximum cardinality matching for P . The union of these edge sets matches all the vertices except those in the trivial components, hence it is a maximum matching in G .

In the light of Observations 1 and 2 and Lemmas 1-3, KarpSipserMT is an exact algorithm on the graphs created in Algorithm 3. The worst case (sequential) running time of our implementation of KS is linear.

KarpSipserMT tracks and consumes only the out-one vertices. This brings high flexibility while executing KarpSipserMT in multi-threaded environments. Consider the example in Figure 1. Here, after matching a pair of vertices and removing them from the graph, multiple degree-one vertices can be generated. The standard KS uses a list to store these new degree-one vertices. Such a list is necessary to obtain larger matching, but the associated synchronizations while updating it in parallel will be an obstacle for parallel efficiency. The synchronization can be avoided up to some level if one sacrifices the approximation quality by not making all optimal decisions (as in [START_REF] Azad | Multithreaded algorithms for maximum matching in bipartite graphs[END_REF]). We continue with the following lemma to take advantage of the special structure of the graphs in TwoSidedMatch for parallel efficiency in Phase 1.

Lemma 4. Consuming an out-one vertex creates at most one new out-one vertex.

Proof. Let u be the out-one vertex that is selected by KarpSipserMT and let v be choice[u]. Since u is a degree-one vertex, its removal will only affect v. On the other hand, although a number of in-one vertices may appear, v's removal can only make the vertex w = choice[v] out-one. This happens iff w is still unmatched and there is no other unmatched vertex y such that choice[y] = w. Assuming all the vertices are currently unmatched, matching 15-7 (or 5-13) creates two degree-one vertices. But no out-one vertex arises after matching (15-7) and only one, vertex 6, arises after matching [START_REF] Bader | Graph Partitioning and Graph Clustering -10th DIMACS Implementation Challenge Workshop[END_REF][START_REF] Çatalyürek | Multithreaded clustering for multi-level hypergraph partitioning[END_REF][START_REF] Çatalyürek | On shared-memory parallelization of a sparse matrix scaling algorithm[END_REF][START_REF] Davis | The University of Florida sparse matrix collection[END_REF][START_REF] Deveci | A push-relabel-based maximum cardinality matching algorithm on GPUs[END_REF][START_REF] Deveci | GPU accelerated maximum cardinality matching algorithms for bipartite graphs[END_REF][START_REF] Duff | Design, implementation, and analysis of maximum transversal algorithms[END_REF][START_REF] Dulmage | Coverings of bipartite graphs[END_REF][START_REF] Dyer | Randomized greedy matching[END_REF].

According to Lemma 4, KarpSipserMT does not need a list to store the new out-one vertices, since the process can continue with the new out-one vertex. In a shared-memory setting, there are two concerns for the first phase from the synchronization point of view. First, multiple threads that are consuming different out-one vertices can try to match them with the same unmatched vertex. To handle such cases, KarpSipserMT uses the atomic _CompAndSwap operation (line 15 of Algorithm 4) and ensures that only one of these matchings will be processed. In this case, other threads, whose matching decisions are not performed, continue with the next vertex in the for loop at line 10. The second

RR n°8386
concern is that while consuming out-one vertices, several threads may create the same out-one vertex (and want to continue with it). For example, in Figure 1, when two threads consume the out-one vertices 1 and 2 at the same time, they both will try to continue with vertex 4. To handle such cases, an atomic _AddAndFetch operation (line 20 of Algorithm 4) is used to synchronize the degree reduction operations on the potential out-one vertices. This approach explicitly orders the vertex consumptions and guarantees that only the thread who performs the last consumption before a new out-one vertex u appears continues with u. The other threads who originally want to continue with the same path stop and skip to the next unconsumed out-one vertex in the main for loop. We did not observe such paths to be long enough to hurt the parallel performance.

The second phase of KarpSipserMT is efficiently parallelized by using the idea in Lemma 3. That is, a maximum cardinality matching for the graph remaining after the first phase of KarpSipserMT can be obtained via a simple parallel for construct (see line 24 of Algorithm 4).

Quality of approximation

We do not have a proof on the approximation guarantee of TwoSidedMatch. However, we have the following claim.

Conjecture 1. Let A be an n × n matrix with total support. Then, TwoSid-edMatch obtains, asymptotically always surely, a matching of size 0.866n.

Here is some supporting evidence for the conjecture. Let the initial matrix A be an n × n matrix of 1s; that is a ij = 1 for all 1 ≤ i, j ≤ n. Then, the doubly stochastic matrix S is such that s ij = 1 n for all 1 ≤ i, j ≤ n. In this case, the graph G created by Algorithm 3 is a random 1-out bipartite graph [START_REF] Walkup | Matchings in random regular bipartite digraphs[END_REF]. Referring to a study by Meir and Moon [START_REF] Meir | The expected node-independence number of random trees[END_REF], Karoński and Pittel [START_REF] Karoński | Existence of a perfect matching in a random (1 + e -1 )-out bipartite graph[END_REF] argue that the maximum cardinality of a matching in a random 1-out bipartite graph is 2(1ρ)n ≈ 0.866n where ρ ≈ 0.567 is the unique solution of the equation xe x = 1. We also present some experimental results in the next section to support the claim.

The proof of Conjecture 1 will contribute to the known results about the Karp-Sipser heuristic (recall that it is known to leave out Õ(n 1/5 ) vertices) by showing a constant approximation ratio with some preprocessing. The existence of a total support does not seem to be necessary for the conjecture to hold (see next subsection).

Further discussions

The Sinkhorn-Knopp scaling algorithm converges linearly (when A has total support) where the rate is equivalent to the square of the second largest singular value of the resulting, doubly stochastic matrix [START_REF] Knight | The Sinkhorn-Knopp algorithm: Convergence and applications[END_REF]. Although convergence is not required, we can bound the theoretical running time of OneSidedMatch and TwoSidedMatch as linear (hiding the number of iterations to convergence behind the big-oh notation). If the matrix does not have (total) support, less is known about the Sinkhorn-Knopp scaling algorithm, in which case, we are not able to bound the running time of the scaling step. However, the scaling algorithms should be run only a few iterations (see also below), in which case the practical running time of our heuristics become linear (in edges and vertices).

We have discussed the proposed matching heuristics while assuming that A has total support. This can be relaxed in two ways to render the overall approach practical in any bipartite graph. First, we do not need to run the scaling algorithms until convergence. If i∈A * j s ij ≥ α instead of i∈A * j s ij = 1 for all j ∈ {1, . . . , n} then, lim d→∞ 1 -

α d d = 1 e α .
In other words, if we apply the scaling algorithms a few iterations, or until some relatively large error tolerance, we can still derive similar results. For example, if α = 0.92, we will have a matching of size n 1 -1 e α ≈ 0.6015n (column sums that are larger than one give improved ratios; but there are columns whose sum is less than one, when the convergence is not achieved) for Algorithm 2. In our experiments, the number of iterations were always a few, where OneSidedMatch's proven approximation guarantee and TwoSidedMatch's conjectured guarantee were always observed. The second relaxation is that we do not need total support; we do not even need support nor equal number of vertices in the two vertex classes. We note that most theoretical studies on randomized matching heuristics concentrates on graphs with perfect matching, as this is enough to present approximation guarantees [START_REF] Poloczek | Randomized greedy algorithms for the maximum matching problem with new analysis[END_REF]Section 2]. Since little is known about the scaling methods on such matrices, we do not dwell into the subject (scaling algorithms are not our focus), but we mention some facts and observations, and later on, present some experiments to demonstrate the practicality of the proposed OneSidedMatch and TwoSidedMatch heuristics.

A sparse matrix (not necessarily square) can be permuted into a block upper triangular form using the canonical Dulmage-Mendelsohn (DM) decomposition [START_REF] Dulmage | Coverings of bipartite graphs[END_REF]

A =   H * * O S * O O V   , S = S 1 * O S 2
where, H (horizontal) has more columns than rows and has a matching covering all rows; S is square and has a perfect matching; and V (vertical) has more rows than columns and a matching covering all columns. The following facts about the DM decomposition are well known [START_REF] Pothen | Sparse null bases and marriage theorems[END_REF][START_REF] Pothen | Computing the block triangular form of a sparse matrix[END_REF]. Any of these three blocks can be void. If H is not connected, then it is block diagonal with horizontal blocks. If V is not connected, then it is block diagonal with vertical blocks. If S does not have total support, then it is in block upper triangular form, shown on the right, where S 1 and S 2 have the same structure recursively, until each block S i is has total support. The entries in the blocks shown by "*" cannot be put into a maximum cardinality matching. When the presented scaling methods are applied to a matrix, the entries in "*" blocks will tend to zero (the case of S is well documented [START_REF] Sinkhorn | Concerning nonnegative matrices and doubly stochastic matrices[END_REF]). Furthermore, the row sums of the blocks of H will be a multiple of the column sums in the same block; a similar statement holds for V ; finally S will be doubly stochastic. That is, the scaling algorithms applied to bipartite graphs without perfect matchings will zero out the entries in the irrelevant parts and identify the entries that can be put into a maximum cardinality matching.

Figure 2 -A generic full-sprank matrix structure that is bad for KS.

Experiments

The experiments were carried out on a machine equipped with two Intel Sandybridge-EP CPUs clocked at 2.00Ghz and 256GB of memory split across the two NUMA domains. Each CPU has eight-cores (16 cores in total) and HyperThreading is enabled. Each core has its own 32kB L1 cache and 256kB L2 cache. The 8 cores on a CPU share a 20MB L3 cache. The machine runs 64-bit Debian with Linux 2.6.39-bpo.2-amd64. All the codes are compiled with gcc 4.4.5 with the -O2 optimization flag. All algorithms are implemented using C and OpenMP parallelism. The (dynamic,512) OpenMP scheduling policy is employed while running all the algorithms except KarpSipserMT for which we used (guided). Parallel runs are performed with 2, 4, 8, 16 threads. For atomic operations, gcc's built-in functions are used.

Experimental verification of theoretical results

Matching quality

We investigate the matching quality of the proposed heuristics on all square, fully indecomposable matrices from the UFL Sparse Matrix Collection [START_REF] Davis | The University of Florida sparse matrix collection[END_REF] having at least 1000 non-empty rows/columns and at most 20000000 nonzeros (some of the matrices are also in [START_REF] Bader | Graph Partitioning and Graph Clustering -10th DIMACS Implementation Challenge Workshop[END_REF]). For all but 37 of these matrices (there were 743 of them), the quality guarantees 0.632 and 0.866 were surpassed with 10 iterations of the scaling method. Making 10 more scaling iterations smoothed out those 37 problematic instances.

Comparisons with KarpSipser

Next, we analyze the performance of the proposed heuristics with respect to KS on a matrix class which we designed as a bad case for KS. Let A be an n × n matrix, R 1 (C 1 ) be the set of A's first n/2 rows (columns), and R 2 (C 2 ) be the set of A's last n/2 rows (columns). As Figure 2 shows, A has a full R 1 × C 1 block and an empty R 2 × C 2 block. The last k n rows and columns of R 1 and C 1 , respectively, are full. Each of the blocks R 1 × C 2 and R 2 × C 1 has a nonzero diagonal. Those diagonals form a perfect matching when combined. In the sequel, a matrix whose corresponding bipartite graph has a perfect matching will be called full-sprank, and sprank-deficient otherwise. When k ≤ 1, the KS heuristic consumes the whole graph during Phase 1 and finds a maximum cardinality matching. When k > 1, Phase 1 immediately ends, since there is no degree-one vertex. In Phase 2, the first edge (nonzero) consumed by KS is selected from a uniform distribution over the nonzeros whose corresponding rows and columns are still unmatched. Since the block R 1 × C 1 is full, it is more likely that the nonzero will be chosen from this block. Thus, a row in R 1 will be matched with a column in C 1 , which is a bad decision since the block R 2 × C 2 is completely empty. Hence, we expect a decrease on the performance of KS as k increases. On the other hand the probability that TwoSidedMatch chooses an edge from that block goes to zero, as those entries cannot be in a perfect matching.

The results of the experiments are in Table 1. The first column shows the k value. Then the matching quality obtained by KS, and by TwoSidedMatch with different number of scaling iterations (0, 1, 5, 10), as well as the scaling error are given. The scaling error is the maximum difference between 1 and each row/column sum of the scaled matrix (for 0 iterations it is equal to n -1 for all cases). The quality of a matching is computed by dividing its cardinality to the maximum one, which is n = 3200 for these experiments. To obtain the values in each cell of the table, we run the programs 10 times and give the minimum quality (as we are investigating the worst-case behavior). The highest variance for KS and TwoSidedMatch were (up to four significant digits) 0.0041 and 0.0001, respectively. As expected, when k increases, the KS heuristic performs worse, and the matching quality drops to 0.67 for k = 32. TwoSidedMatch's performance increases with the number of scaling iterations. As the experiment shows, only 5 scaling iterations are sufficient to make the proposed two-sided matching heuristic significantly better than KS. However, this number is not enough to reach 0.866 for the matrix with k = 32. On this matrix, with 10 iterations, only 2% of the rows/columns remain unmatched.

Matching quality on bipartite graphs without perfect matchings

We analyze the proposed heuristics on a class of random sprank-deficient square (n = 100000) and rectangular (m = 100000 and n = 120000) matrices with a uniform nonzero distribution (two more sprank-deficient matrices are used in the scalability tests as well). These matrices are generated by Matlab's sprand command (generating Erdös-Rényi random matrices [START_REF] Erdös | On random matrices[END_REF]). The total nonzeros is set to be around d × n for d ∈ {2, 3, 4, 5}. the previous experiments, the matching qualities in the table is the minimum of 10 executions for the corresponding instances. As Table 2 shows, when the deficiency is high (correlated with small d), it is easier for our algorithms to approximate the maximum cardinality. However, when d gets larger, the algorithms require more scaling iterations. Even in this case, 5 iterations are sufficient to achieve the guaranteed qualities. In the rectangular case, the minimum quality achieved by OneSidedMatch and TwoSidedMatch were 0.753 and 0.930, respectively, with 5 scaling iterations.

OneSidedMatch and TwoSidedMatch in parallel

To analyze the scalability of the proposed heuristics in practice, we used 12 large bipartite graphs corresponding to real-life matrices from UFL collection arising in different application domains. The names hugebubbles and channel refer to the matrices hugebubbles-00020 and channel-500x100x100-b050, respectively. The properties of the bipartite graphs are given in Table 3 along with the sequential running times (the running time of OneSidedMatch includes that of ScaleSK, and TwoSidedMatch includes those of ScaleSK and Karp-SipserMT). All the executions in this experiment are repeated 20 times and the first five are ignored. The times are computed by using the geometric mean of the remaining 15 executions for each instance. No significant variances were observed among the remaining individual running times. The speedup values are computed with respect to the execution with a single-thread. Figures 3a and3b show the individual speedup values for ScaleSK and the proposed matching heuristic OneSidedMatch, respectively. When executed with 16 threads, ScaleSK obtains a speedup value around 8 or more for all matrices. The maximum speedup of 10.6 is obtained for hugebubbles. The scalability of OneSidedMatch is better. For 10 matrices, a speedup value around 10 or more is obtained. The maximum speedup of 11.4 is obtained for the matrix europe_osm with 16 threads.

The structure of a matrix can affect the scalability. Both for ScaleSK and OneSidedMatch, the minimum speedups (7.7 and 8.4, respectively) are obtained on torso1. As Table 3 shows, torso1 and audikw_1 are the two smallest matrices with less than 10 6 rows and columns. As Figure 3b shows, OneSided-Match obtains its worst speedups on these matrices. This is not a coincidence. When the variance of the number of nonzeros per row is high, the effects of load imbalance can be significant. For torso1 and audikw_1, the variances (computed in Matlab) are 176056 and 1802, respectively. Among the 12 matrices, the next largest variance is 42 (kkt_power). Although we conducted a set of preliminary experiments on OpenMP scheduling policies, we did not fine tune it to have the best one. A different policy may work better especially for these matrices with a high variance on the number of nonzeros per row. We repeated the scalability experiment for KarpSipserMT and TwoSid-edMatch on the same matrix set. The results can be seen in Figures 4a and4b, respectively. On average (geometric mean), KarpSipserMT obtains a speedup of 11.1 with 16 threads. The maximum speedup of 12.6 is obtained on the matrix channel. These results show that the proposed KarpSipserMT is highly scalable on the graphs generated in TwoSidedMatch without any quality loss with the increasing thread counts (see [START_REF] Azad | Multithreaded algorithms for maximum matching in bipartite graphs[END_REF] for an efficient but inexact parallel KS implementation). With 16 threads, TwoSidedMatch obtains a speedup value of 10.6 on the average. Compared to the average of OneSidedMatch (10.1), it is slightly better. However, in a sequential setting, TwoSidedMatch is 2.6 times slower. To further compare these two heuristics, we present Figures 5a and5b that show the qualities on our test matrices. In the figures, the first columns represent the case that the neighbors are picked from a uniform distribution over the adjacency lists, i.e., the case with no scaling, hence no guarantee. The quality guarantees are achieved with only 5 iterations for almost all the cases except TwoSidedMatch on nlpkkt240 which required 15 scaling iterations. Even with a single iteration, the quality of TwoSidedMatch is more than 0.86 for all matrices. Only for two among them, the quality is between 0.863 and 0.866. The results are similar for OneSidedMatch. However, even with 10 scaling iterations, OneSidedMatch cannot achieve a quality of 0.80 on any of the matrices. We conclude that OneSidedMatch is faster, TwoSidedMatch has a better quality guarantee, and both demonstrate good speedups.

Conclusion

We proposed two heuristics for the bipartite maximum cardinality matching problem. The first one, OneSidedMatch, is shown to have an approximation guarantee no smaller than 1 -1/e ≈ 0.632. The second heuristic, TwoSid-edMatch, is conjectured to have an approximation guarantee no smaller than 0.866. Both algorithms use well-known methods to scale the sparse matrix associated with the given bipartite graph to a doubly stochastic form whose entries are used as the probability density functions to randomly select a subset of the edges of the input graph. OneSidedMatch selects exactly n edges to construct a subgraph in which a matching of the guaranteed cardinality is identified with virtually no overhead, both in sequential and parallel execution. TwoSided-Match selects around 2n edges and then runs the Karp-Sipser (KS) heuristic as an exact algorithm on the selected subgraph to obtain a matching of conjectured cardinality. The subgraphs are analyzed to develop a specialized KS algorithm for efficient parallelization. All theoretical investigations are first performed assuming bipartite graphs with perfect matchings. Then, theoretical arguments and experimental evidence are provided to extend the results to cover other cases and validate the applicability and practicality of the proposed heuristics in general settings. Parallel performance is analyzed on a shared memory parallel computer with up to 16 threads and speedups beyond 10 fold are demonstrated.

We are investigating variants of the proposed heuristics for finding approximate matchings in undirected graphs. The algorithms and results extend naturally, but more work need to be done for theoretical explanations.

  Input: A: an n × n, (0,1)-matrix with total support Output: match[•]: the mate of each vertex or NIL 1: (dr, dc) ← ScaleSK(A) 2: for i = 1 to n in parallel do 3:

Definition 1 .

 1 Given a matching and the array choice, let u be an unmatched vertex and v = choice[u]. Then u is called: • out-one, if v is unmatched, and no unmatched vertex w with choice[w] = u exists.

  then

9 : 12 :← u 13 : 24 :

 9121324 _Add(deg[v], 1) 10: for each vertex u in parallel do Phase 1: out-one vertices. 11: if mark[u] = 1 then curr while curr = NIL do 14: nbr ← choice[curr] 15: if _CompAndSwap(match[nbr], NIL, curr) = curr then 16: match[curr] ← nbr 17: curr ← NIL 18: next ← choice[nbr] 19: if match[next] = NIL then 20: if _AddAndFetch(deg[next], -1) = 1 then 21: for each column vertex u in parallel do Phase 2: the rest 25: v ← choice[u] 26: if match[u] = NIL and match[v] = NIL then 27:

Observation 2 .Lemma 2 .

 22 A degree-one vertex (of KS) is either an out-one or an inone vertex, or it is one of the two vertices u and v in a 2-clique such that v = choice[u] and u = choice[v]. If there exists an in-one vertex in G at any time during the execution of KarpSipserMT, an out-one vertex also exists.

Figure 1 -

 1 Figure 1 -A toy bipartite graph with 9 row (circles) and 9 column (squares) vertices. The edges are oriented from a vertex u to the vertex choice[u].Assuming all the vertices are currently unmatched, matching 15-7 (or 5-13) creates two degree-one vertices. But no out-one vertex arises after matching (15-7) and only one, vertex 6, arises after matching[START_REF] Bader | Graph Partitioning and Graph Clustering -10th DIMACS Implementation Challenge Workshop[END_REF][START_REF] Çatalyürek | Multithreaded clustering for multi-level hypergraph partitioning[END_REF][START_REF] Çatalyürek | On shared-memory parallelization of a sparse matrix scaling algorithm[END_REF][START_REF] Davis | The University of Florida sparse matrix collection[END_REF][START_REF] Deveci | A push-relabel-based maximum cardinality matching algorithm on GPUs[END_REF][START_REF] Deveci | GPU accelerated maximum cardinality matching algorithms for bipartite graphs[END_REF][START_REF] Duff | Design, implementation, and analysis of maximum transversal algorithms[END_REF][START_REF] Dulmage | Coverings of bipartite graphs[END_REF][START_REF] Dyer | Randomized greedy matching[END_REF].

Figure 3 -

 3 Figure 3 -Speedups for ScaleSK (left) and OneSidedMatch (right) with a single scaling iteration.

Figure 4 -

 4 Figure 4 -Speedups for KarpSipserMT (left) and TwoSidedMatch (right) with a single scaling iteration.

  n n e l $ e u r o p e _ o s m $ H a m r l e 3 $ h g b u b b l e s $ k k t _ p o w e r $ n l p k k t 2 4 0 $ r o a d _ u s a $ t o r s o 1 $ v e n t u r i L e v e l 3 $

Figure 5 -

 5 Figure 5 -Matching qualities of OneSidedMatch (left) and TwoSided-Match (right). The horizontal lines are at 0.866 and 0.632, respectively, which are the approximation guarantees for the heuristics (conjectured for TwoSid-edMatch). Legend contains iteration numbers.

Table 1 -

 1 Quality comparison (minimum of 10 executions for each instance) of the KS heuristic and TwoSidedMatch on matrices described in Fig.2with n = 3, 200 and k ∈ {2, 4, 8, 16, 32}.

			number of iterations
		Karp	0	1	5	10
	k	Sipser Qual. Err.	Qual. Err.	Qual. Err.	Qual.
	2	0.782 0.522 13.853 0.557 3.463 0.989 0.578 0.999
	4	0.704 0.489 11.257 0.516 3.856 0.980 0.604 0.997
	8	0.707 0.466	8.653 0.487 4.345 0.946 0.648 0.996
	16	0.685 0.448	6.373 0.458 4.683 0.885 0.725 0.990
	32	0.670 0.447	4.555 0.453 4.428 0.748 0.867 0.980

Table 2 -

 2 Table 2 presents the results of this experiment with square matrices (rectangular case is not shown). As in Matching qualities of the proposed heuristics on random matrices with n = 100, 000 and uniform nonzero distribution. d: average number of nonzeros per row/column.

			One	Two		One	Two
			Sided	Sided		Sided	Sided
	d iter sprank Match Match d iter sprank Match Match
	2	0 78,225	0.770	0.912 4	0 97,787	0.644	0.838
	2	1 78,225	0.797	0.917 4	1 97,787	0.673	0.848
	2	5 78,225	0.850	0.939 4	5 97,787	0.719	0.873
	2	10 782,25	0.879	0.954 4	10 97,787	0.740	0.886
	3	0 92,786	0.673	0.851 5	0 99,223	0.635	0.840
	3	1 92,786	0.703	0.857 5	1 99,223	0.662	0.851
	3	5 92,786	0.756	0.884 5	5 99,223	0.701	0.873
	3	10 92,786	0.784	0.902 5	10 99,223	0.716	0.882

Table 3 -

 3 sprank: the maximum cardinality of a matching; Scaling error: the maximum difference between one and column sums; Sequential execution times of ScaleSK(one iteration), OneSidedMatch, KarpSipserMT, and TwoSidedMatch.

	Execution times with single thread (secs)	Scaling error One Karp Two	Avg. (number of iterations) Scale Sided Sipser Sided	n # of edges deg. sprank/n 1 5 10 SK Match MT Match	1,489,752 10,319,760 6.9 1.00 0.06 0.01 0.00 0.037 0.095 0.236 0.273	943,695 77,651,847 82.2 1.00 0.17 0.02 0.01 0.188 0.364 0.452 0.640	5,154,859 99,199,551 19.2 1.00 0.18 0.03 0.02 0.306 0.627 1.373 1.679	4,802,000 85,362,744 17.8 1.00 0.10 0.01 0.00 0.274 0.537 0.937 1.211	50,912,018 108,109,320 2.1 0.99 8.43 8.00 8.00 1.625 3.599 9.643 11.270	1,447,360 5,514,242 3.8 1.00 0.99 0.37 0.15 0.028 0.067 0.196 0.223	21,198,119 63,580,358 3.0 1.00 0.33 0.17 0.11 1.303 2.840 7.942 9.251	2,063,494 12,771,361 6.2 1.00 13.83 1.27 1.00 0.063 0.132 0.339 0.401	27,993,600 760,648,352 26.7 1.00 2.23 0.99 0.71 1.864 3.704 6.642 8.481	23,947,347 57,708,624 2.4 0.95 6.08 6.00 6.00 0.712 1.581 4.237 4.949	116,158 8,516,500 73.3 1.00 0.13 0.02 0.01 0.021 0.040 0.045 0.066	4,026,819 16,108,474 4.0 1.00 0.23 0.05 0.03 0.094 0.239 0.672 0.766
				Name	atmosmodl	audikw_1	cage15	channel	europe_osm	Hamrle3	hugebubbles	kkt_power	nlpkkt240	road_usa	torso1	venturiLevel3

RR n°8386

Acknowledgements

Fanny Dufossé is supported by the foundation STAE, Toulouse, France.

RR n°8386