Fabien Gandon
email: fabien.gandon@inria.fr

Michel Buffa

Elena Cabrio

Olivier Corby

Catherine Faron Zucker

Alain Giboin

Nhan Le Thanh

Isabelle Mirbel

Peter Sander

Andrea G B Tettamanzi

Catherine Faron-Zucker

Serena Villata

Challenges in Bridging Social Semantics and Formal Semantics on the Web

Keywords: semantic web, social web, knowledge representation, ontologies, typed graphs

établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

As the Web becomes a ubiquitous infrastructure bathing all the objects of our world, this is just one example of the many frictions it will create between formal semantics and social semantics. This trend is also amplified by the growing number of datasets published and interlinked online by initiatives like Linking Open Data. This expanding web of data together with the schemas, ontologies and vocabularies used to structure and link it form a formal semantic web with which we have to design new interaction means to support the next generation of web applications. This is why the Wimmics1 research laboratory proposes to study methods, models and algorithms to bridge formal semantics and social semantics on the Web. This article provides a survey of the current research topics of the laboratory.

Challenges in bridging formal semantics and social semantics

From a formal modeling point of view one of the consequences of the evolutions of the Web is that the initial graph of linked pages has been joined by a growing number of other graphs. This initial graph is now mixed with sociograms capturing the social networks structure, workflows specifying the decision paths to be followed, browsing logs capturing the trails of our navigation, automatas of service compositions specifying distributed processing, linked open data from distant datasets, etc. Moreover, these graphs are not available in a single central repository but distributed over many different sources with very different characteristics. Some subgraphs are public (e.g. dbpedia) while others are private (e.g. corporate data). Some sub-graphs are small and local (e.g. a users' profile on a device), some are huge and hosted on clusters (e.g. Wikipedia).Some are largely stable (e.g. thesaurus of Latin), some change several times per second (e.g. sensor data), etc.

And each type of network of the Web is not an isolated island. Networks interact with each other: the networks of communities influence the message flows, their subjects and types, the semantic links between terms interact with the links between sites and vice-versa, the small changing graphs of sensors are joint to the large stable geographical graphs that position them, etc.

Not only do we need means to represent and analyze each kind of graphs, we also need the means to combine them and to perform multi-criteria analysis on their combination.

Wimmics proposes to address this problem focusing on the characterization of (a) typed graphs formalisms to model and capture these different pieces of knowledge and (b) hybrid operators to process them jointly. Our team especially considers the problems that occur in such structures when we blend formal stable semantic models and socially emergent and evolving semantics.

The two next sections detail this research program according to two main research directions combining two complementary types of contributions we target:

1. First research direction: to propose multidisciplinary approach to analyze and model the many aspects of these intertwined information systems, their communities of users and their interactions; 2. Second research direction: to propose formalizations of the previous models and reasoning algorithms on these models providing new analysis tools and indicators, and supporting new functionalities and better management.

In a nutshell, the first research direction looks at models of systems, users, communities and interactions while the second research direction considers formalisms and algorithms to represent them and reason on their representations.

In the short term we intend to survey, extend, formalize and provide reasoning means over models representing systems, resources, users and social links in the context of social semantic web applications.

In the longer term we intend to extend these models (e.g. dynamic aspects), unify their formalisms (dynamic typed graphs) and propose mixed operations (e.g. metrical and logical reasoning) and algorithms to scale them (e.g. random walks) to support the analysis of epistemic communities' structures, resources and dynamics.

Ultimately our goal is to provide better collective applications on the web of data and the semantic web addressing jointly two sides to the problem: (1) improve access and use of the linked data for epistemic communities and at the same time (2) use typed graph formalisms to represent the web resources, users and communities and reason on them to support their management.

Analyzing and modeling users, communities and their interactions in a Social Semantic Web context

The first challenge we identified in the introduction was to propose multidisciplinary approach to analyze and model intertwined information systems, communities of users and their interactions. Examples of research questions here include:

─ How do we improve our interactions with an information system that keeps getting more and more complex? ─ How do we reconcile and integrate the formalized stable semantics of computer science and the negotiable social interactions? ─ How do we facilitate communication between systems and system developers using formal representations and between users and usage analysts using corresponding less formal or non-formal representations? ─ How do we reconcile local contexts of users and global characteristics of the world-wide system?

The main goal of this first research direction is to improve the understanding the systems have of the communities of their users. To provide better collective applica-tions on the web of data and the semantic web we need to adapt classical models to the specificities and variety of web systems (requirements, functionalities, specifications), users (profiles and context: location, devices, activities, etc.), and groups (communities and networks of interest, communities and networks of practice, social constructs, etc.). In Wimmics, these models are designed, integrated, and published according to web standards to support functionalities of web applications providing access and use of the linked data to epistemic communities.

We defend that such models necessarily call for multidisciplinary approaches to analyze and model the many aspects of the information systems.Our proposal relies:

─ on extending requirement modeling to build models of the systems; ─ on cognitive studies and user modeling results to build models of the users; ─ on ergonomic studies and interaction design methods to model the interactions between users through the system and with the system, in order to support and improve these interactions.

We had several experiences in past projects with a user modeling technique known as Personas [START_REF] Cooper | About Face 2.0: The Essentials of Interaction Design[END_REF]. We are interested in these user models that are represented as specific, individual humans and we apply them to capture models of the members of webbased communities. Personas are derived from significant behavior patterns (i.e., sets of behavioral variables) elicited from interviews with and observations of users (and sometimes customers) of the future product. The main merit of the Personas method is to engage design team members more effectively in not only taking users into account but also having constantly in mind that they are designing for people. This effectiveness comes from several aspects, in particular:

1. by integrating concrete elements in the description of a user-type (name, photo, etc.)., it prevents that the user remains an abstraction for the designer (this abstraction leading the designer to lose sight of the user); 2. by connecting more strongly scenarios to the actors of these scenarios (i.e., the users), the Personas method avoids the problem often encountered in conventional methods of scenario-based design, namely to ignore users in the development of scenarios and thus "dehumanizing" these scenarios.

In the Personas method, the link between scenarios and users is established with the most important characteristic of personas: their goals.These goals form the basis for scenario development. Our user models specialize "Personas" approaches to include aspects appropriate to Web applications. The formalization of these models will rely on ontology-based modeling of users and communities starting with generalist schemas (e.g. FOAF).

Beyond the individual user models we propose to rely on social studies to build models of the communities, their vocabularies, activities and protocols in order to identify where and when formal semantics is useful. We already proposed an extension of the Persona approach to Collective Personas [START_REF] Giboin | From Individual to Collective Persona: Modeling Realistic Groups and Communities of Users (and not Only Realistic Individual Users)[END_REF] and wenow develop our method to encompass web-based communities. We compare this approach to the related "collaboration personas" method [3][4] and to the group modeling methods [START_REF]User Modeling to Support Groups, Communities and Collaboration[END_REF] which are extensions to groups of the classical user modeling techniques dedicated to individuals. Both methods having been developed independently from one another, they differ along several dimensions, for example: whereas the Collaboration Personas method (CnP) focuses on forms of collaboration within a group, the Collective Personas method (CeP) focuses on the nature of the collective; whereas CeP refers to models or theories of collectives to define types of collectives, CnP uses pragmatic classifications; whereas CnP describes scenarios as stories, CeP describes them in a more structured way. We also propose to rely on and adapt participatory sketching and prototyping to support the design of interfaces for visualizing and manipulating representations of collectives.

Wimmics also has a background in requirement models and, in the short term, we want to consider their extension and specialization to web applications (in particular semantic web and linked data applications) and their representation in web-based formalisms in order to support mutual understanding and interoperability between requirements, resources and specifications of interconnected web applications and web datasets. (e.g. [START_REF] Neveu | Using Ontologies of Software: Example of R Functions Management[END_REF])

For all the models we identify we rely on and evaluate knowledge representation methodologies and theories, in particular ontology-based modeling.

In addition to the persona models identified previously, in a longer term we will consider a number of additional features to be captured in the user models.

We already added contexts, devices, processes and media descriptions that are formalized and used to support adaptation, proof and explanation and foster acceptation and trust from the users [START_REF] Hasan | Generating and Summarizing Explanations for Linked Data[END_REF] [START_REF] Hasan | Predicting SPARQL Query Performance and Explaining Linked Data[END_REF]. We specifically target a unified formalization of these contextual aspects to be able to integrate them at any stage of the processing. This unified formalization already allows us to use the same model and data for very different functionalities such as access control [START_REF] Costabello | Context-Aware Access Control for RDF Graph Stores[END_REF] or presentation customization [START_REF] Costabello | Error-Tolerant RDF Subgraph Matching for Adaptive Presentation of Linked Data on Mobile[END_REF].

We extended current descriptions of relational and emotional aspectsin existing variants of the personas technique. In particular we intendto exploit Olsen's characterization of a user's relationship to a product [START_REF] Olsen | Persona Creation and Usage Toolkit, Information Architecture (IA) Summit[END_REF] since this characterization was made by analogy to human relationships. The elaboration of the characteristics to be included in a "relational-user" model will rely on work dealing with "relational agency" ("as a capacity to recognize others as resources, to elicit their interpretations and to negotiate aligned actions" [START_REF] Edwards | Relational Agency in Professional Practice: a CHAT analysis[END_REF]), and on "relational agents" (as "computational artifacts designed to build long-term social-emotional relationships with users" [11]). The elaboration of relational characteristics will be informed by empirical studies of relationship characterization, and of personality definition by users on the Web. These directions are a natural extension of our work on the use of affective ontologies in semantic web applications [START_REF] Giboin | Motivating the Use of Affective Ontologies in Semantic Web Applications Which Mediate Interactions Between Members of Organizations or Communities[END_REF] and algebraic modeling of emotional states [START_REF] Imentayari | Towards an algebraic modeling of emotional states[END_REF]. We also proposed algorithm to detect and classify the emotional states [START_REF] Berthelon | Regression algorithm for emotion detection[END_REF][15] that can then be represented and exchanged together with their ontologies on the Web. Indeed, for each of these extensions we systematically consider additional extensions of the corresponding schemas to capture additional aspects and publish them as public ontologies on the semantic web.

Concerning the social dimension we now focus on studying and modeling mixed representations containing social semantic representations (e.g. folksonomies) and formal semantic representations (e.g. ontologies) and propose operations that allow us to couple them and exchange knowledge between them [START_REF] Limpens | NiceTag Ontology: tags as named graphs[END_REF]. The very long term objective is to obtain a uniformed and integrated representation of social aspects (e.g., groups, networks, communities), social objects (web resources e.g. pictures, posts), social informal semantics (e.g. tags, folksonomies) and social formal semantics (e.g. ontologies, schemas).

In addition, to take into account social dynamics, we believe that argumentation theory can provide models (e.g. [START_REF] Minh | On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games[END_REF]) that must be adapted to open web constraints. Argumentation theory can be combined to requirement engineering to improve participant awareness and support decision-making (e.g. [START_REF] Mirbel | Enhancing Goal-based Requirements Consistency: an Argumentation-based Approach[END_REF]). On the methodological side, we propose to adapt to the design of such systems the incremental formalization approach originally introduced by the CSCW and HCI communities [START_REF] Blythe | Incremental Formalization of Document Annotations through Ontology-based Paraphrasing[END_REF] [START_REF] Shipman | Supporting Knowledge-Base Evolution with Incremental Formalization[END_REF]. In incremental formalization users first express information informally and then the system helps them formalize it. The goal of such an approach is to get users to interact at least partially with formal representations, to make them contribute to a formalization closer to their needs [START_REF] Giboin | Interagir avec des représentations formelles[END_REF].

Argumentation theory can also be combined with semantic web models and social web approaches to provide explicit formal representation of some social dynamics (e.g. opinions, agreements, debates, disagreements) more and more useful to understand the state and status of a resource and, for instance, decide on whether to trust it or not.

This kind of understanding and models allow scaling-up some very timeconsuming tasks on the social web (e.g. managingand moderating Wikipedia) in particular when they are combined with natural language processing (NLP) to tackle the textual nature of these interactions as in [START_REF] Cabrio | A Natural Language Account for Argumentation Schemes[END_REF][23] [START_REF] Cabrio | Argumentation-based Inconsistencies Detection for Question-Answering over DBpedia[END_REF][25] [START_REF] Cabrio | A Support Framework for Argumentative Discussions Management in the Web, Best Paper of the Extended Semantic Web Conference[END_REF].In addition NLP approaches can also improve the design of interaction with the collections of models and data that are growing on the Web. For instance NLP allows us to support natural language querying of semantic web triple stores [START_REF] Cabrio | Querying Multilingual DBpedia with QAKiS[END_REF] [START_REF] Cojan | Filling the Gaps Among DBpedia Multilingual Chapters for Question Answering[END_REF].

And the linguistic knowledge useful for such processing can in turn be the subject of knowledge representation and data exchanged on the Web [START_REF] Maximelefrançois | Application of the unit graphs framework to lexicographic definitions in the RELIEF project[END_REF] [START_REF] Maximelefrançois | Reasoning with dependency structures and lexicographic definitions[END_REF].

Finally, on a very long term a much needed evolution of all our models is the temporal and dynamic dimension. We now plan to study and survey initiatives and contributions on dynamic graph representation and analysis and merge them with typed graph models of the Web of data to natively and uniformly support the time dimension in our representations.

Formalizing and reasoning on heterogeneous semantic graphs

The second challenge identified in the introduction is to propose formalizations of the previous models and reasoning algorithms on these models providing new analysis tools and indicators, and supporting new functionalities and better management.Examples of research questions include for instance:

─ What kind of formalism is the best suited for the models of the previous section? ─ How do we analyze graphs of different types and their interactions?

─ How do we support different graph life-cycles, calculations and characteristics in a coherent and understandable way?

In this second research direction members of Wimmicsfocus on formalizing as typed graphs the models identified in the previoussection in order for software to exploit them in their processing. The challenge is two-sided: ─ To propose models and formalisms to capture and merge representations of both kinds of semantics (e.g. formal ontologies and social folksonomies). The important point is to allow us to capture those structures precisely and flexibly and yet create as many links as possible between these different objects. ─ To propose algorithms (in particular graph-based reasoning) and approaches (e.g. human-computing methods) to process these mixed representations. In particular we are interested in allowing cross-enrichment between them and in exploiting the life cycle and specificities of each one to foster the life-cycles of the others.

While some of these problems are known, for instance in the field of knowledge representation and acquisition (e.g. disambiguation, fuzzy representations, and argumentation theory), the Web reopens them with exacerbated difficulties of scale, speed, heterogeneity, and an open-world assumption by default.

Many approaches emphasize the logical aspect of the problem especially because logics are close to computer languages. We defend that the graph nature of linked data on the Web and the large variety of types of links that compose them call for typed graphs models. We believe the relational dimension is of paramount importance in these representations and we propose to consider all these representations as fragments of a typed graph formalism directly built above the semantic Web formalisms. Our choice of a graph based programming approach for the semantic and social web and of a focus on one graph based formalism is also an efficient way to support interoperability, genericity, uniformity and reuse.

We targeted an abstract graph model close to the GRIWES model [START_REF] Baget | Griwes: Generic Model and Preliminary Specifications for a Graph-Based Knowledge Representation Toolkit[END_REF] and we evaluate it in merging social graphs (e.g. sociograms, folksonomies) and semantic Web graphs (e.g. RDF, schemas, linked data) in a unified typed graph formalism. This work on abstracting the knowledge representation models follows our experience with conceptual graphs and semantic networks approaches.

An example of such abstract structure is theERGraph [START_REF] Baget | Griwes: Generic Model and Preliminary Specifications for a Graph-Based Knowledge Representation Toolkit[END_REF] defined relatively to a set of labels L as a 4-tuple G=(E G , R G , n G ,l G ) where:

─ E G and R G are two disjoint finite sets respectively, of nodes called entities and of hyperarcs called relations.

─ n G : R G  E G

* associates to each relation a finite tuple of entities called the arguments of the relation.

─ l G : E G  R G  Lis a labelling function of entities and relations.

This type of oriented labelled multi-graph structure is at the core of most of our formalizations. New knowledge structures are regularly identified (e.g. folksonomies, named graphs) and old ones re-launched (e.g. thesauri and SKOS). This kind of ab-stract construct can be used and reused across graph representations such as RDF, Topic Maps, Social Networks, Knowledge Graphs, etc.

There exists now an extensive body of work in Graph-based Knowledge Representation [START_REF] Michel Chein | Graph-based Knowledge Representation: Computational Foundations of Conceptual Graphs (Advanced Information and Knowledge Processing[END_REF] that we align with the ones needed for semantic web data structures (e.g. [START_REF] Baget | Griwes: Generic Model and Preliminary Specifications for a Graph-Based Knowledge Representation Toolkit[END_REF][33] [START_REF] Gandon | Graphes RDF et leur Manipulation pour la Gestion de Connaissances, Habilitation à Diriger les Recherches[END_REF]) and in the short term we intend to continue specifying the required characteristics of such a language and systematically evaluate their effectiveness in implementing these abstract graph models in real applications [START_REF] Corby | The KGRAM Abstract Machine for Knowledge Graph Querying[END_REF] [START_REF] Faron-Zucker | Implementation of SPARQL Query Language based on Graph Homomorphism[END_REF].

Likewise we extend our abstract graph machine not only to cover as many features as possible of new languages like SPARQL 1.1, RDF 1.1 and RIF, but also to extend them with experimental features (e.g. semantic distances) and a challenge is to integrate other operators with classical graph manipulation in particular: approximation, clustering, analysis operations, spreading algorithm, temporal reasoning and extend them to work on typed graphs. For instance,we considered the near linear time algorithm to detect community structures in large scale network RAK/LP [START_REF] Raghavan | Near Linear Time Algorithm to Detect Community Structures in Large Scale Network[END_REF] based on label propagation and changed the propagation algorithm to take semantics into account the algorithmSemTagP [START_REF] Erétéo | SemTagP: Semantic Community Detection in Folksonomies[END_REF].

Currently, graph operators (joint, homomorphism, propagation, distances, etc.) allow us to perform a broad range of queries and reasoning operations. An example of abstract graph operation is an ERMapping [START_REF] Baget | Griwes: Generic Model and Preliminary Specifications for a Graph-Based Knowledge Representation Toolkit[END_REF]: Let G and H be two ERGraphs, an ERMapping <x> from H to G for a binary relation X over LL is a partial function M from E H to E G such that:

─ e M -1 (E G ), (l G (M(e)), l H (e)) X ─ r'R H' r R G such that card(n H' (r'))= card(n G (r)) ─  1icard(n G (r)), M(n H' i (r'))= n G i (r) ─ r'R H' rM(r') such that (l G (r), l H (r'))Xwhere H' is the sub-ERGraph of H in- duced by M -1 (E G ).
This mapping operator can then be used and reused for many operations (searching, deriving, grouping, etc.) and across many graph formalisms compatible with the ERGraph structure. In particular when X is a preorder over L, it captures a hierarchy such as the taxonomical skeleton of an ontology, a thesaurus, a partonomy, etc.

Our implementations [START_REF] Corby | The KGRAM Abstract Machine for Knowledge Graph Querying[END_REF] and their applications (e.g.ISICIL [START_REF] Buffa | Folksonomies and Social Network Analysis in a social Semantic Web[END_REF], DATALIFT [START_REF] Scharffe | Enabling linked data publication with the Datalift platform[END_REF], DiscoveryHub [START_REF] Marie | Discovery Hub: on-thefly linked data exploratory search[END_REF]) show that type-based inference algorithms (e.g. conceptual graph projection, inference rules) and type-parameterized operators (e.g. parameterized betweeness centrality) provide declarative formalisms to flexibly define operations to monitor, filter, query, mine, validate, protect, etc. these imbricated graph structures taking into account constraints spanning several types of network at once.

In the longer term we intend to build on our experience with such formalisms to identify, propose and characterize fragments of typed graph formalisms best suited for each type of model identified before. We will restrain ourselves to specify the required characteristics of a limited number of formalisms (ideally one) and systematically evaluate their effectiveness in implementing these abstract graph models in real applications.

The mixed representations identified in the previous sectionreally call for hybrid reasoning methods merging semantic Web inferences, social graph analysis and content mining in cross-dimensional indicators and operators. The key problem is to have integrated operators on these formalisms, able to perform at the same time exact reasoning and more approximate one to combine all aspects of the problem. For instance a centrality [START_REF] Freeman | Centrality in social networks: Conceptual Clarification[END_REF] can be computed on a social network taking into account only some relation types [START_REF] Erétéo | Analysis of a Real Online Social Network using Semantic Web Frameworks[END_REF] or some topics of interest using an extension of regular expressions to graph paths [START_REF] Olivier | Graphs & Semantics[END_REF]. This same centrality can also be computed by using a complete walk algorithm or approximated by using random walks but in both cases the ability to consider and reason on types of links and nodes will be a core problem. Another example is combining folksonomies and ontologies in the same application and using a combination of automated processing (e.g. a range of semantic similarities and inference rules) and human-based computing (e.g. analyzing the behaviors of users carrying out a search) to structure and maintain a thesaurus of tags and keywords used in a community [START_REF] Limpens | Helping Online Communities to Semantically Enrich Folksonomies[END_REF].

Our final goal is to have both an abstract language dissociated from the concrete languages and an extensible abstract machine to process them. In particular this allows us to define parameterizable graph operators for instance to revisit classical structural metrics and adapt their definition to go beyond the pure structural calculation and take into account the types in the graphs. In the longer term, we intend to perform search (e.g. homomorphism) and logical derivation (e.g. homomorphism and merge) but also approximation (e.g. distances), clustering (e.g. propagation), analysis (e.g. centrality), etc. jointly on the same graphs. We target the design of an abstract graph machine [START_REF] Corby | The KGRAM Abstract Machine for Knowledge Graph Querying[END_REF] generalizing operations needed by and sometime shared across different languages (e.g. SPARQL, RIF, POWDER, RDF/S and OWL inferences) and operations. In addition we also believe it is interesting to study alternatives to OWL stack and the associated DL-reasoning. For instance a rule-based semantic web with an alternative stack (RDF/S + SPARQL + Rules) provides certain advantages: rules are often more natural for humans, they support event-based programming and web service integration, they are usable both for domain independent and domain dependent inferences, etc.

To adapt to web growth and dynamics, we also plan to evaluate other approaches (e.g. Random walk on graphs approaches) that do not naturally use labels but could be indirectly parameterized (e.g. making a correspondence between probabilistic distributions and the types of links) and to consider temporal reasoning approaches to include temporal context and change patterns to identify trends, mine temporal propagation to build oriented networks, track behavioral patterns to qualify actors and communities (e.g. detect a dying community) extending models from [START_REF] Angeletou | Modelling and analysis of user behaviour in online communities[END_REF] for instance.

We believe that moving to graph languages with open-world logics, temporal aspects, distributed and loosely coupled algorithms and model-driven programming relying on higher abstractions (e.g. formal ontologies) provides an adequate theoretical and operational framework to allow not only the specification and operationalization of the models and algorithms,but also the opening of these black boxes to be able to explain, document, prove and trace query performances and results for the users, as in [START_REF] Hasan | Generating and Summarizing Explanations for Linked Data[END_REF] and [START_REF] Hasan | Predicting SPARQL Query Performance and Explaining Linked Data[END_REF].

As a last example, the same graph-based formalisms we propose to use in representing our models can be used to declaratively capture the landscape of the data distribution and the workflows of our operations [START_REF] Lo | Semantic web services in corporate memories[END_REF], interpret them and execute them. This is the approach we would like to explore to support different operations on heterogeneous and distributed data (e.g. summarizing the content of distributed triple stores [START_REF] Basse | Frequent Graph Pattern to Advertise the Content of RDF Triple Stores on the Web[END_REF]) and automated explanation, trace and documentation of the processes.

Conclusion

Wimmics provides models and algorithms to bridge formal semantics and social semantics by formalizing and reasoning on heterogeneous semantic graphs. The models we design include: users, their profiles, their requirements, their activities and their contexts; social links, social structures, social exchanges and processes; conceptual models including ontologies, thesauri, and folksonomies. Whenever possible these models are formalized and published according to standardized web formalisms and may motivate research and suggestions on extending these standards. The schemas and datasets produced are published as linked data following the web architecture principles.

The algorithms we study include: typed graphs indexing, reasoning and searching; hybrid processing merging logical inferences, rules and metrical inferences; approximation and propagation algorithms; distributed and scalable alternatives to classical reasoning. These algorithms are implemented and distributed as part ofgeneric open source software.

Wimmicshasindeed the culture of producing prototypes of applications and extensions of existing applications relying on web languages as demonstrators and proofs of concept. At the core of many of our prototypes is the abstract graph library we develop, maintain and publish as open-source software. This platform called Corese/KGRAM [START_REF] Corby | The KGRAM Abstract Machine for Knowledge Graph Querying[END_REF] currently implements W3C standards (in particular RDF/S 1.1 and SPARQL 1.1) and is both a research result and a library on top of which we test new ideas and algorithms. Currently this platform is extensively used in several applications such as: Isicil, Neurolog,DiscoveryHub, etc.

Finally we continuously participate to the extension, specifications, implementation, tests, deployment and teaching of W3C Web standards and our research results support, use and influence the evolution of these standards.

Wimmics is a joint research laboratory between Inria Sophia Antipolis -Méditerranée and I3S (CNRS and Université Nice Sophia Antipolis).http://wimmics.inria.fr


Maxime Pelcat
email: mpelcat@insa-rennes.frweb

Karol Desnos
email: kdesnos@insa-rennes.frweb

Julien Heulot
email: jheulot@insa-rennes.frweb

Clément Guy
email: cguy@insa-rennes.frweb

Jean-Franc ¸ois Nezan
email: jnezan@insa-rennes.frweb

Slaheddine Aridhi
email: saridhi@ti.com

PREESM: A DATAFLOW-BASED RAPID PROTOTYPING FRAMEWORK FOR SIMPLIFYING MULTICORE DSP PROGRAMMING

The high performance Digital Signal Processors (DSPs) currently manufactured by Texas Instruments are heterogeneous multiprocessor architectures. Programming these architectures is a complex task often reserved to specialized engineers because the bottlenecks of both the algorithm and the architecture need to be deeply understood in order to obtain a fairly parallel execution.

The PREESM framework objective is to simplify the programming of multicore DSP systems by building on dataflow programming methods. The current functionalities of this scalable framework cover memory and time analysis, as well as automatic deadlock-free code generation. Several tutorials are provided with the tool for fast initiation of C programmers to multicore DSP programming. This paper demonstrates PREESM capabilities by comparing simulation and execution performances on a stereo matching algorithm prototyped on the TMS320C6678 8-core DSP device.

INTRODUCTION

The currently available high performance signal processing systems manufactured by Texas Instruments, including the Keystone I [START_REF]Texas Instruments: Multicore Fixed and Floating-Point Digital Signal Processor -SPRS691E[END_REF] and Keystone II [START_REF]Texas Instruments: Multicore DSP+ARM Key-Stone II System-on-Chip (SoC) -SPRS866E[END_REF] architectures, as well as the TDA2x with Embedded Vision Engine (EVE) [START_REF]Texas Instruments: Empowering automotive vision with TIs Vision AccelerationPac -SPRY251[END_REF], are heterogeneous multiprocessor architectures. These architectures currently embed up to 12 heterogeneous cores and this number is likely to increase in the next generations in order to cope with the ever more complex applications.

In this context, training engineers to program DSP architectures is a challenging task because the impact of application and architecture bottlenecks on system performance is high and difficult to predict. The main challenges to overcome when designing a multicore signal processing system are:

• to exploit enough algorithm parallelism (task, data and pipeline parallelisms) to minimize latency in general, • to choose the right core for each application subtask, • to provide data where and when needed so as to avoid stalling cores and underusing the hardware, hence maximizing the usage efficiency.

PREESM is an Eclipse-based framework that provides dataflow-based methods to study a multicore DSP system.

The framework is open-source and provided with extensive tutorials for easy initiation of C/C++ programmers to multicore DSP programming. PREESM provides a system designer with high level rapid prototyping information on algorithm parallelism and latency, as well as on system memory requirements. Moreover, a code generation is provided to transform the dataflow representation into a compilable code. Parallel processes called actors are manually implemented by the system designer in the language supported by the architecture compiler (e.g. C or C++ code for the Texas Instruments TMS320C6678 DSP) with the restriction that no memory should be shared between actors. The executable resulting from compiling together the generated and the manual code constitutes a multicore system prototype that is guaranteed deadlock-free and can be retargeted to a different number of cores within a few minutes.

Dataflow Models of Computation (MoC) are a promising solution to the limitation of imperative languages (C, C++...) to represent application parallelism. The Parameterized and Interfaced Synchronous Dataflow (PiSDF) [START_REF] Desnos | Pimm: Parameterized and interfaced dataflow meta-model for MPSoCs runtime reconfiguration[END_REF] MoC tested within the PREESM framework Version 2 divides an application into actors. These actors communicate through data First In, First Out data queues (FIFOs) and their data production and consumption rates on these FIFOs can be modified by parameters.

The paper is organized as follows: after a presentation of related works in Section 2, an overview of the PREESM framework is given in Section 3. A focus is put on the algorithm and architecture models in Section 4 and the most important rapid prototyping tasks are explained in 5. Experimental results of the PREESM rapid prototyping process are discussed in Section 6. The chosen use case is a stereo matching algorithm running on an 8-core TMS320C6678 DSP.

RELATED WORKS

OpenMP [START_REF] Chapman | Using OpenMP: portable shared memory parallel programming[END_REF] is becoming the defacto standard for multiprocessor programming. Most C-based toolchains, including the Texas Instruments toolchain for multi-C66x core DSPs, support OpenMP. OpenMP is a set of pragmas for parallelizing loops or sections of an imperative (e.g. C) code. Current OpenMP implementations are oriented towards the dynamic creation of tasks by a runtime support based on pragma information. In this context, no rapid prototyping is available to check the system conformance to performance constraints.

The creation of the PREESM rapid prototyping framework has been inspired by the Algorithm-Architecture Matching methodology (AAM, also sometimes called AAA) [START_REF] Grandpierre | From algorithm and architecture specifications to automatic generation of distributed real-time executives: a seamless flow of graphs transformations[END_REF]. AAM consists in simultaneously searching the best software and hardware configurations for respecting the system constraints. The SynDEx tool [START_REF] Grandpierre | Optimized rapid prototyping for real-time embedded heterogeneous multiprocessors[END_REF] is also based on the AAM methodology but it differs from PREESM on several ways: SynDEx is not open source, has a unique dataflow Model of Computation that does not support schedulability analysis and the function of code generation is possible but not provided with the tool. Schedulability analysis is an important feature of PREESM because it ensures deadlock freeness in the generated code.

The Open RVC-CAL Compiler (Orcc) [START_REF] Wipliez | Compilation infrastructure for dataflow programs[END_REF] is an opensource tool that generates different types of hardware and software code from a unique dataflow-based language named RVC-CAL. The recent TURNUS tool [START_REF] Brunei | TURNUS: a design exploration framework for dataflow system design[END_REF] is an exploration tool that complements the Orcc compiler by offering RVC-CAL design space exploration. An important difference between Orcc, TURNUS and PREESM is the MoC of the algorithm description. While PREESM uses the decidable [START_REF] Bhattacharyya | Optimization of signal processing software for control system implementation[END_REF] PiSDF MoC, the MoC implemented in RVC-CAL is not decidable and thus, in the general case, no guarantee can be given in Orcc and TURNUS on the deadlock-freeness and memory boundedness of the generated code.

SDF3 [START_REF] Stuijk | SDF 3 : SDF For Free[END_REF] is an open-source dataflow analysis tool that supports the Synchronous Dataflow (SDF), Cyclo-Static Dataflow (CSDF) and Scenario-Aware Dataflow (SADF) MoC. SDF3 is oriented towards model analysis and simulation while PREESM aims at both simulating the system and generating an executable prototype.

The features that differentiate PREESM from the related works and similar tools are:

• the tool is open source and accessible online [START_REF]PREESM framework[END_REF];

• the algorithm description is based on a single well-known and predictable model of computation; • the scheduling is totally automatic;

• the functional code for heterogeneous multi-core embedded systems is generated automatically; • rapid prototyping metrics are generated to help the system designer to take decisions; • the PiSDF algorithm model provides a helpful hierarchical encapsulation and parameterization, thus simplifying the scheduling; • the System-Level Architecture Model (S-LAM) architecture model provides a high-level architecture description to study system bottlenecks. Next Sections cover these features through a presentation of the rapid prototyping tool chain of PREESM.

RAPID PROTOTYPING OVERVIEW

Figure 1 shows a PREESM typical rapid prototyping process described in the PREESM tool by a graphical workflow. A PREESM workflow is a graph connecting rapid prototyping tasks such as scheduling and simulation. Each task is implemented in a different Eclipse plug-in, providing a high scalability to the tool. Workflow support is a feature that makes PREESM scalable and adaptable to designer's needs. A developer tutorial [START_REF]PREESM tutorials[END_REF] provides all necessary information to create new workflow tasks and adapt PREESM to a designer's needs (e.g. for exporting a graph in a custom syntax or for experimenting new scheduling methods).

An algorithm graph description (in PiSDF), an architecture graph description (in S-LAM), and a scenario are retrieved from XML files (left hand side of Figure 1). Graphic editors are provided within PREESM for all the rapid prototyping inputs. These editors ease manipulation and edition of algorithms and architectures and thus the exploration of the design space.

A scenario is a database providing all information to link PiSDF Algo.

S-LAM

Archi. Algorithm and architecture models undergo several transformations (including a graph flattening, equivalent to loop unwinding in a compilation process) to expose parallelism to the scheduling process. They are then passed to a static scheduling and a memory optimization tasks. The static scheduling transformation generates a periodic multicore schedule that will be repeated indefinitely to process the input data stream. At the end of each iteration of the periodic multicore schedule, the FIFO queues are back in their initial state, ensuring deadlock freeness. The memory optimization task computes a memory exclusion graph in order to authorize memory reuse between FIFOs in the intermediate representation used for code generation.

Scenario

Finally, the simulation and the code generation tasks provide respectively metrics for system design and a prototype for testing the multicore execution of the system. Next Section presents in more details the algorithm and architecture models used in PREESM.

RAPID PROTOTYPING INPUT MODELS

The Parameterized and Interfaced Synchronous Dataflow (PiSDF) Model of Computation

The PiSDF dataflow model [START_REF] Desnos | Pimm: Parameterized and interfaced dataflow meta-model for MPSoCs runtime reconfiguration[END_REF] used to describe algorithms aims at providing coarse grain parallel descriptions of algorithms specifying precisely the data flowing between actors and offering a tradeoff between dynamic behavior and predictability.

An example of a PiSDF model is shown in Figure 2. This example corresponds to a filter that takes a fixed size number of data tokens (indivisible unit of data) as inputs and internally distributes these tokens to N kernels that effectively execute the filtering. This example can for instance be used to execute the filtering of an image by slice (without overlapping between slices) so as to provide data parallelism.

The internal behavior of actors is programmed in plain C code. Actors are authorized to access their input and output data tokens in any order. This construction automates the computation of the number of executions (or firings) of the actors per invocation of the graph. This computation is based on the production and consumption of data and can ensure deadlock-freeness at compile-time. Actors are stateless and the only possibility for an actor to keep a state information between two executions is to send information to its future iterations. The feedback loop of the actor Filter with a delay of size tokens provides the Kernel actor with the corresponding slice of the preceding processed image.

Production and consumption rates of PiSDF actors, as delays of FIFOs between actors, can be parameterized depending on the need of the application. In our example, size and N are two parameters enabling to vary the number of tokens filtered and the number of kernels executing the filtering. The value of these parameters can be modified at runtime, in which case we talk about dynamic parameters.

The System-Level Architecture Model (S-LAM)

With the convergence of hardware and software languages, the reconfigurable architectures and the High-Level Synthesis (HLS), the distinction between hardware and software is becoming unclear. S-LAM describes architectures in a graph as a set of cooperative processing elements offering processing capabilities to dataflow actors and a set of communication features offering communication services to dataflow FIFOs [START_REF] Pelcat | Physical Layer Multi-Core Prototyping: A Dataflow-Based Approach for LTE eNodeB[END_REF]. This definition authorizes the use of S-LAM for describing parallel architectures at different levels of granularity: a set of PCs communicating through ethernet, a set of cores communicating through shared memory, etc.

An example of an S-LAM model is shown in Figure 3. It describes a TMS320C6678 architecture by describing the 8 C66x cores and the capacity of each core to communicate with any other core through two parallel communication nodes: an internal shared memory (Multicore Shared Memory Controller (MSMC)) and an external shared memory ( Double Data Rate SDRAM (DDR3)). The graph does not represent the architecture itself but the services it provides to the dataflow algorithm. The same hardware architecture can thus be represented in several ways depending on the modeled communication capacities.

The black dots represent Time Division Multiple Access (TDMA) for the data transfers on the communication nodes and for the actor executions on the processing elements. The absence of a black dot on the MSMC node means that simulation will consider it as capable of managing any number of communication simultaneously. The motivation for this representation is that MSMC controller has an independent link for each core at 16 GB/s while the external DDR3 has a unique link to the processor at 10.6 GB/s. More advanced features are representable in S-LAM such as the delegation of communications to a Direct Memory Access (DMA). Next section describes the main PREESM workflow tasks which process PiSDF algorithm models and S-LAM architecture models.

RAPID PROTOTYPING TASKS

Rapid prototyping consists in exploring the design space of a target system in order to minimize its cost and guarantee the respect of different constraints, the most common ones being: latency, throughput, memory, and energy consumption. Other constraints may exist, such as jitter or signal simultaneity. The diversity of constraints invalidates a unique approach targeting all types of signal processing systems. However, it fosters frameworks such as PREESM with plugged-in functionalities that adapt to different targets.

The PREESM multicore scheduler implements the List and Fast scheduling methods described by Kwok [START_REF] Kwok | High-performance algorithms for compile-time scheduling of parallel processors[END_REF]. The current PREESM plug-ins are focusing on latency dominated systems. A latency dominated system is a system where the respect of the latency constraints of the processing assures the respect of its throughput constraints [START_REF] Ghamarian | Throughput analysis of synchronous data flow graphs[END_REF]. In this case, the main processing iteration does not need to be pipelined (i.e. only one iteration of the processing is alive at any moment) but it may need to be parallelized if the work to execute is longer in time than the latency constraint. In the current PREESM code generation, all cores are synchronized with a barrier between two application iterations. It is important to note that while inter-iteration pipelining is not supported, intra-iteration pipelining of actors is already available. This constraint may be relaxed in the future, at the cost of a more complex memory and time analysis.

Bounded memory execution is an important property of decidable MoC [START_REF] Bhattacharyya | Optimization of signal processing software for control system implementation[END_REF]. Without this property, unexpected deadlocks can appear when a FIFO becomes out of memory. PREESM currently generates guaranteed deadlock-free code for PiSDF algorithms with purely static parameters. An extension to more dynamic parameters is foreseen in the short term. An advanced memory optimization mechanism based on a memory exclusion graph [START_REF] Desnos | Pre-and post-scheduling memory allocation strategies on MP-SoCs[END_REF] is available in PREESM to avoid preserving fifo memory spaces that are useless for the correct system execution.

The PREESM simulation offers to the system designer a simulated Gantt chart of the code execution on the parallel architecture, a speedup assessment chart that draws the expected algorithm execution speedup depending on the number of cores, and an evaluation of the memory necessary for the execution. The code generation produces a self-timed code [START_REF] Sriram | Embedded multiprocessors: Scheduling and synchronization[END_REF], i.e. a static code for each core with automatic inter-core communication, cache management and synchronization. This code necessitates communication libraries, which are provided for the TMS320C6678 processor.

A more complete description of PREESM rapid prototyping tasks can be found in [START_REF] Pelcat | Physical Layer Multi-Core Prototyping: A Dataflow-Based Approach for LTE eNodeB[END_REF]. Next Section will provide some experimental results using the tasks described above.

EXPERIMENTAL RESULTS

Through the example of a state-of-the-art computer vision application, this Section presents how PREESM can be used to develop an application and automatically deploy a prototype implementation on a multicore Keystone architecture.

Use Case: Stereo Matching Algorithm

The application studied is a stereo matching algorithm. The purpose of stereo matching algorithm is to process a pair of images taken by two cameras in order to produce a disparity map that corresponds to the 3 rd dimension (the depth) of the captured scene. The large computation and memory requirements of stereo matching algorithms, as well as their promising use in Advanced Driver Assistance Systems (ADAS) [START_REF]Texas Instruments: Empowering automotive vision with TIs Vision AccelerationPac -SPRY251[END_REF], make them interesting case studies to illustrate the efficiency of the PREESM rapid prototyping framework.

Figure 4 presents the top-level PiSDF graph of a stereomatching algorithm. Two parameters are used to configure this PiSDF graph: size, which corresponds to the number of pixels of each image of the input stereo pair processed by the algorithm; and nbDisparity, which represents the number of distinct values that can be found in the output disparity map.

The stereo matching PiSDF graph presented in Figure 4 contains 7 actors:

• Read produces the 2 input frames by reading a stream or a file. • PreProcess converts an RGB image into its grayscale equivalent. This actor also produces an 8-bit signature, called census, for each pixel of an input image. This signature results from the comparison of each pixel with its 8 neighbors. • Duplicate produces a configurable number of copies of the data received on its input ports. • CostComputation computes the matching cost of each pixel for a given disparity. This actor is called as many times as the number of tested disparities. • DisparitySelect produces a disparity map by selecting the disparity of the input cost map with the lowest matching cost for each pixel. • MedianFilter applies a 3x3 pixels median filter to the input disparity map to smooth the results. • Display displays the result of the algorithm or writes it in a file. Below each actor is a repetition factor which indicates the number of executions of this actor for each iteration of the graph. This number of executions is computed from the data production and consumption rates of actors. The PiSDF description of the algorithm provides a high degree of data and task parallelism since it is possible to execute in parallel the repetitions of the most computationally intensive actors, namely PreProcess and CostComputation. In addition to the parallelism expressed in this top-level graphs, several actors can be refined with hierarchical subgraphs also containing parallelism. For example, the PreProcess and Median actors can both be implemented in such a way that several parts of their input images are processed simultaneously in parallel.

Nb of cores

PREESM results

The results presented in this section are obtained by applying the PiSDF graph of Figure 4 to stereo pairs of size = 450 * 375 pixels, with nbDisparity = 60. In this configuration, 300 actor firings must be scheduled for each iteration of the complete PiSDF graph, and 987 FIFOs must be allocated in shared memory.

The time taken by the PREESM framework to automatically deploy the stereo matching application on the eight cores of a TMS320C6678 chip is 45 seconds. The scheduling process is responsible for 53% of this time, memory optimization for 36%, graph transformations for 9%, and code generation for 2%. The execution time of the rapid prototyping process remains relatively low compared to the 140 seconds needed to compile the application for the multicore DSP. The fast execution of the PREESM framework is a key feature to accelerate the testing of different deployment scenarios and ease the design space exploration on different multicore architectures.

Figure 5 shows the performance obtained by deploying the stereo matching algorithm on a variable number of cores of the TMS320C6678 multicore DSP chip. On eight cores, a throughput of 0.33 frames per second (fps) is reached. This throughput corresponds to a speed-up by a factor 3.3 compared to the execution of the application on one DSP core.

Figure 5 also plots the theoretical greedy scheduling throughputs [START_REF] Pelcat | Physical Layer Multi-Core Prototyping: A Dataflow-Based Approach for LTE eNodeB[END_REF] computed by PREESM for the stereo matching application. The computation of this theoretical throughput does not take into account communication costs. It could be considered as an upper bound for the achievable throughput. Consequently, the actual throughput of the stereo matching algorithm appears to be inferior to the theoretical throughput.

Figure 6 shows the data memory footprint allocated for the execution of the stereo matching algorithm on a variable number of cores of the TMS320C6678 multicore DSP chip. The smallest memory footprint of 68.4 MBytes is obtained when the application is executed on a single core of the architecture. When the number of cores executing the application is increased, more parallelism of the application is preserved, and the allocated memory footprint is increased. As illustrated in Figure 6, the memory optimization techniques used in PREESM [START_REF] Desnos | Pre-and post-scheduling memory allocation strategies on MP-SoCs[END_REF] limit this increase of the memory footprint allocated for the application, and only 79.7 MBytes of memory are needed to execute the application on 3 to 8 cores. Without the memory optimization techniques of PREESM, more than 1.4 GBytes would be needed to store the application FIFOs, which is far more than the 512 MBytes available on the EVMC6678. These experimental results show that the PREESM framework can be used to deploy and optimize real applications on multicore architectures within minutes. Several tutorials [START_REF]PREESM tutorials[END_REF] are available online to demonstrate the framework functionalities.

CONCLUSION AND FUTURE WORK

PREESM provides a complete rapid prototyping framework for multicore DSP system design. As a C-based open-source framework distributed with complete tutorials, it aims at initiating C programmers and system designers to dataflow methods. Furthermore, the PREESM framework has demonstrated capabilities for developing an optimized real world application (e.g. the stereo matching algorithm) for multicore DSP architectures.

In the future, we plan to improve the framework to provide support for dynamic parameters from modeling to code generation. We will also improve the scheduler so as to take into account memory optimizations in scheduling decisions.

Figure 1 :

 1 Figure 1: PREESM Rapid Prototyping Process: An Example of a Workflow

Figure 2 :Figure 3 :

 23 Figure 2: An Example of a PiSDF Model

Figure 5 :

 5 Figure 5: Throughput of the stereo matching application depending on the number of targeted C6x cores.

Figure 4 :Figure 6 :

 46 Figure 4: PiSDF graph of the stereo matching application