Riichiro Mizoguchi

Yusuke Hayashi

Jacqueline Bourdeau

Inside Theory-Aware and Standards-Compliant Authoring System

, Bourdeau and Mizoguchi foresaw a framework for ontology-based intelligent systems. Although it took longer years than their expectation, the ontology they have been developing is now released for evaluation with the help of the second author. Ontology building is a labor-intensive process and it is rarely perfect. Our enterprise is not an exception. The current ontology is still very preliminary because it has been completely reconstructed from the existing one with a few new ideas. So, we hope the readers be generous when they read the ontology. The ontology presented here is not a light-weight ontology but a heavyweight ontology. It is built based on philosophical consideration of all the concepts necessary for understanding learning, instruction and instructional design. Although it is full of axioms, the Hozo GUI which is based on a frame structure makes it easier to read it. However, the readers are expected to have basic knowledge of ontology and preferably be aware of the theory of role and of the Hozo way of role representation. Papers [6][7] would be helpful to grasp what we are doing with this ontology. The prototype system named SMARTIES is a totally ontology-aware system which fully utilizes the merits of ontology computationally as well as conceptually. It is so preliminary that it cannot be open to public, though you can get a rough idea of what it is from the papers.

Introduction

Nowadays standard technologies play an important role in the development and delivery of learning contents. Standard technologies provide stakeholders with great benefits; there is however a lack of pedagogical justification of standard-compliant contents. This project focuses on educational theories as a kind of pedagogical knowledge and aims at building an information system that helps users to utilize them for instructional and learning design (Here, the term "instruction" does not have a narrow definition such as lecture but has a broad definition to include anything that fosters or suggest learning in a learning environment). This project takes an ontological engineering approach to grasp fundamental concepts of learning and instruction in order to enable information systems to be aware of the theories on the basis of such concepts.

This article introduces a comprehensive ontology which covers different theories and paradigms about instructional and learning design 1 . Note that this ontology is still a tentative result of our project. We have plans in the future to continue to make further refinement on it and we welcome your contribution to the refinement. In addition, at the current moment, this ontology focuses only on the abstract design of learning contents and has not been yet related to domain knowledge or learning objects to concretize the abstract design. This is one of the future plans of this project.

Scope: Objectives and non-Objectives

This project's objectives include:

• To find an engineering approximation that allows building of an engineering infrastructure that enables instructional designers and educational practitioners to apply knowledge derived from educational theories, and

• To establish a method for building theory-aware systems for education. This project's objectives do not include:

• To insist on the scientific validity of the proposed framework for organizing educational theories, • To reconstruct existing educational theories on such a basis, nor • To create new theories 1.2 Expected outcomes a) Providing a sharable model of instructional design knowledge Instructional design knowledge includes theoretical knowledge such as instructional and learning theories as well as empirical one such as heuristics and best practices. The ontology introduced in this document includes about 100 pieces of "WAYknowledge" based on some theories. b) Increasing theory-awareness in authoring tools Based on the ontology, an authoring tool can become aware of instructional knowledge and help authors. This project has developed "SMARTIES": a prototype system of a theory-aware authoring tool based on the ontology. This prototype system provides support functions for making learning/instructional scenarios based on this ontology.

To put it more completely, this system provides a modeling environment and guidelines for making theory-compliant learning/instructional scenarios. This system has the flexibility of ontologies. The upper level concepts are built-in but the lower level concepts can be imported from the ontology built in Hozo2 [START_REF] Kozaki | Hozo: An Environment for Building/Using Ontologies Based on a Fundamental Consideration of "Role" and "Relationship[END_REF]. c) Linking standard-technologies to instructional design knowledge Instructional design knowledge is expected to enhance the educational justification of standard-compliant contents. The prototype system supports authors in building standard-compliant scenarios with theoretical justification because it can export a theory-based instructional/learning scenario model into IMS LD level A format [START_REF]IMS Learning Design. Version 1.0 Final Specification[END_REF].

Current state and Future plans a) Updating this ontology

The current version of this ontology is the version 1.0. Comments received and discussion done on this workshop will be reflected in the modification as much as we can. In addition, we want to continue the discussion about ontologies of instructional design on our website.

b) Expansion of this ontology

We are planning to include concepts related to instructional design theories/processes and CSCL. In addition, we currently plan to put this ontology to the core of our infrastructure for instructional design knowledge sharing. This means that the ontology enables us to utilize theories for contents design through the top-down approach as well as to build new theories and to share best practices through the bottom-up approach. We believe such an infrastructure will harmonize theory and practice of instructional and learning design. c) Link with learning objects and learning object metadata

In order to implement such abstract design as our scenarios, it is necessary to link it to learning objects. We have defined attributes of learning and instruction in the proposed ontology. To consider the relation between these attributes and learning object metadata (e.g. IEEE LOM [START_REF]The Learning Object Metadata standard[END_REF])is one of the future directions of this study.

Building a comprehensive ontology for educational theories

The objective of this study is building a comprehensive ontology which covers different theories and paradigms. In this section we briefly discuss the problems and our approach for building such an ontology.

Basic consideration

In building such a comprehensive ontology, there is one big problem. It is considered that, in the first place, each paradigm or theory has its own definition of "Learning" and hence we cannot organize variety of theories on a common basis. However, for example, Reigeluth [START_REF] Reigeluth | Instructional-design theories and models: An overview of their current status[END_REF][18] and Ertmer [START_REF] Ertmer | Behaviorism, cognitivism, constructivism: Comparing critical features from an instructional design perspective[END_REF] give some observations about commonality and difference among paradigms and theories. We can summarize these statements as follows; Every theory has some sort of common basis for explaining learning and instruction, and while the assumed mechanism of developing knowledge is different for each paradigm, the idea of states in the learning process is common. In a similar line of the thought, this study sets up a working hypothesis that there must be an engineering approximation of the states where we can conceptualize "Learning" in terms of state change of learners [START_REF] Mizoguchi | Using Ontological Engineering to Overcome AI-ED Problems[END_REF].

Note that the purpose of this study is not to expose a scientifically valid basis for organizing theories nor to reconstruct them on this basis, but rather to find an engineering approximation that allows building of an engineering infrastructure that enables practitioners to utilize instructional and learning theories. This paper thus proposes a foundation from the view point of ontological engineering based on the results of previous research in this respect [START_REF] Bourdeau | Collaborative Ontological Engineering of Instructional Design Knowledge for an ITS[END_REF][14] [START_REF] Psyche | Making Learning Design Standards Work with an Ontology of Educational Theories[END_REF].

Conceptualization of the interaction between learning and instruction

We have defined a concept that we named I_L event as shown in Figure 1. An I_L event is a concept to link instructional events to learning events. In this study a learning event is composed of state-change and learning action. Learning actions cause the change of learner's state. On the other hand, an instructional event is composed of an instructional action which affects learning events. The key points of our conceptualization include to emphasize the relations among these three and to model a contribution of instructional action on the change of learner's state.

Instructional theory

I_L event

Advance the development / Develop / Developed

Instructional event

Learning event

State-change (Terminal state)

Instructional action

Learning theory

Learning action

Influence

Cause

Figure 1 An I_L event

Conceptualization of the abstract structure of instructional/learning scenario

In our modeling framework, a scenario can be modeled as a hierarchical structure of I_L events for achieving a certain change of a learner state. We call it an "I_L event decomposition tree". The basic idea of an I_L event decomposition tree is to relate a macro-I_L event to the lower (micro) ones that collectively achieve the upper (macro) I_L event as a way of achievement of the change of a learner state (referred to just as "WAY" hereafter). Figure 2 illustrates an example of an I_L event decomposition. This shows that there are two WAYs to achieve the macro-I_L event, which is to introduce a content for making a learner recognize it. WAY1 is based on Gagne and Briggs's theory [START_REF] Gagne | Principles of Instructional Design[END_REF]. This firstly presents what to learn and then gives guidelines. The other is based on Collins' [START_REF] Collins | Cognitive apprenticeship: Teaching the crafts of reading, writing and mathematics[END_REF]. This gives only demonstrations and no explanations. In this case the macro-I_L event is not decomposed but concretized. These ways can be thought to have the same goal but achieve it by different strategies. Such relation between WAYs is described by OR relation like between WAY1 and WAY2. In the proposed modeling framework, a scenario is described as a sequence of the leaves in the tree structure and the tree-structure model layered multiply with WAYs accounts for the design intention.

Conceptualization of strategies suggested by instructional/learning theories

Theories prescribe strategies for planning the instructional and learning process according to supposed situations. In our modeling framework, a learning and instructional strategy is modeled as a WAY in view of generality which can be adapted to the specialized concrete application situations. Such a generic WAY is named "WAY-knowledge". Currently, we have organized about 100 pieces of "WAY-knowledge" based on some theories: Gagne's nine events of instruction [START_REF] Gagne | Principles of Instructional Design[END_REF], Dick and Carey's ID theory [START_REF] Dick | The systematic design of instruction[END_REF], Merrill's Component display theory [START_REF] Merrill | Component display theory[END_REF], Keller's ARCS model [START_REF] Keller | An application of the ARCS model of motivational design[END_REF], Collins's cognitive apprenticeship [START_REF] Collins | Cognitive apprenticeship: Teaching the crafts of reading, writing and mathematics[END_REF], and Jonassen's Design of constructivist learning environments [START_REF] Jonassen | Designing constructivist learning environment[END_REF]. These are defined as relational concepts (see 3.4).

Organizing "WAY-knowledge" is expected to contribute to the clarification of the conceptual structure of each theory and to theory-eclectic design guidelines for the

Learning object characteristics

-Language -Language level -Representation mode -Japanese, English, French -child, adult -text, graphics, image, video, simulation, game modeling learning and instructional processes. Through this process, we have tried to classify the properties of the theories. Table 1 shows the current classification of the properties. These properties are common to learning/instructional scenarios and models, the pieces of "WAY-knowledge" and concepts of theories in the OMNIBUS ontology. One of the contributions of this is to enable authoring tools to understand the relation between theories and a scenario and to explain it to the authors. Using these properties, such an authoring tool can suggest theories that have the same properties as a scenario to the authors, or can provide the accordance of properties between a scenario and a theory as the justification of a scenario for the authors. We have implemented authoring supports of this kind. This is discussed in 4.4.

Concepts defined in the ontology

Among various types of concepts defined in the ontology, we are here concerned only with the main concepts related to the instructional/learning scenario models introduced above. This section describes what are defined in this ontology and how to read it using Hozo ontology editor.

The basic principle of conceptualization in the Hozo ontology editor

Although the ontology is presented in two versions -Hozo and OWL -, we recommend to read the Hozo version, since it represents the full semantics of the ontology. However, you need to know the basics of the Hozo way of representation.

The Hozo ontology editor handles the following two concepts separately:

• Wholeness concept: A concept of a thing considered as a whole (e.g. bike), which is composed of multiple concepts (e.g. wheel, handle, etc.), each of which makes up a part of the whole, • Relational concept: Conceptualized relationship between multiple (usually two) concepts. This distinction is done based on the following consideration [START_REF] Kozaki | Hozo: An Environment for Building/Using Ontologies Based on a Fundamental Consideration of "Role" and "Relationship[END_REF]. For example, let us consider a "brothers" and a "brotherhood". Assume that there are two brothers, Bob and Tom. "The Smith brothers" could be a conceptualization as a whole, which is a pair of two persons. On the other hand, "brotherhood between Bob and Tom" is conceptualized as a relation. On the basis of the observations that most of the things are composed of parts and that those parts are connected by a specific relation to form the whole, wholeness concept and relational concept are distinguished in Hozo ontology editor. In this example, the "brothers" can be considered as a wholeness concept and the "brotherhood" as a relational concept. Theoretically, every thing that is a composite of parts can be conceptualized in both perspectives as a wholeness concept and a relational concept.

In the ontology, two types of relations are defined: pure relation such as "same as" and "before-after", and "WAY-knowledge" (strategy) such as "Educational strategy". While the former is used as constraints on the wholeness concepts(normal classes), the latter is not used that purpose but used for representing "WAY-knowledge". Details are explained in relational concept.

Ontological approach to the systematization of educational theories

Fundamental viewpoint

The relation among theories behind instructional design is considered as a nested structure as shown in Figure 3. The bottom of the structure is the "learning world". Learning theories explain processes and events in the world. The "Instructional world" is on top of the learning world. The instructional process influences or facilitates the learning process. Instructional theories prescribe the effective instructional process for the learning process with the desired outcome. The instructional process happens in parallel with the learning process. Moreover, the "Instructional design world" is on top of the instructional world. Instructional design process is the design process of the instructional process. An instructional design theory prescribes the rational process for designing the instructional process. One of the major differences among the three kinds of processes is that while the lower two are real world processes, the other is a planning or design process of real world processes/events. However, thinking along the nested structure, we see an essential characteristic that all the processes rely on the learning process which can be modeled as a state-change in a learner. Therefore, based on our working hypothesis stated in 2.1, we built this ontology with the state-change in a learner as the foundation of the conceptual system.

Upper level structure

The upper level structure of this ontology is shown in Figure 4. Roughly speaking, the OMNIBUS ontology is mainly composed of concepts related to the "Common", "Cognition", "Learning", "Instructional" and "Instructional design /Instructional system design (ID-ISD)" worlds, and "Event". We would like to emphasize that our policy of conceptual distinction between "Event" and the other process-related concepts is based on context-dependence. Concepts related to each world are defined as those necessary to represent processes in the respective worlds with minimal context-dependence. On the other hand, "Event" and its subclasses are defined as those for representing (1) events with maximal contextdependence on education referring to those defined in other worlds and (2) relations between them. We discuss the distinction and the context-dependence of them in a bit more detail in 3.3.3. This paper discusses OMNIBUS ontology with a focus only on the learning and instructional worlds and the relations between them. In the following sections, we mainly explain "State" and "Action" that are defined in the common world and that are shared among the learning and instructional worlds in order to describe learning and instructional process, "Educational event" as a contextualized description of process, and "WAY" as the relational concept.

Main wholeness concepts

This sub-section introduces the main wholeness concepts in this ontology.

State

As discussed in 2.1, states in the learning process are the most important factor for building the comprehensive ontology. Each description of educational theories uses its own terminology. Hence each theory has different concepts of states from the other theories at a glance. However, Reigeluth points out that many theories are described in different terminology although some of them describe or prescribe the same method for the same situation (states as the precondition and the outcome) [START_REF]Instructional-design theories and models A new paradigm of instructional theory[END_REF].

In accordance with our working hypothesis stated in 2.1, we have collected such states from several theories and categorized them under an is-a hierarchy from the view point of the conceptual meaning (Figure 5). States in the OMNIBUS ontology are mainly classified into the following two types of classes.

• Internal state: This is a state about the inside of agents. This includes "Cognitive process state", "Attitudinal state", "Progression state", "Developmental state". • External state: This is a state locating between internal state and situation and is an aspect of the agent's engagement/participation in an action. In this ontology, these states are common to any theory and learning is described by changes of learner state. Therefore the difference between theories is described as the difference of states used or not used in the theories, process of changes of the state supported in the theory, and the relation between changes of states and learning actions.

In the following, we explain the definition of actions and discuss the relation between changes of states and learning actions.

Action

Actions are defined in common with learning and instruction (Figure 6). All actions are decomposed into some subactions and the decomposition can be repeated almost endlessly. However, in most cases, the decomposition should be stopped at a certain granularity level under which There are two kinds of actions: one which has a unique decomposition into subactions like "walk" and the other which has multiple ways of decomposition according to the context/goal under which actions are being performed like "teach". The former case is a normal case so that subactions are defined using (part-of) slots. The latter case needs special care to grasp its rich meaning properly, that is, to uncover its deep implications underlying the ways of performing the sequence of subactions. This is why we don't use part-of slots but instead introduce "WAY-knowledge" (way of decomposition) together with "Event" for the latter kind of actions. Needless to say, the distinction between these two kinds of actions is relative. Furthermore, we introduce the idea of "Event" to capture the latter kind of actions. By event, we mean a large chunk of actions full of contextual stuff such as "learning event" and "instructional event". "Event"s refer to "Action"s at particular situations which require particular actions to achieve their goals.

Primitive action

This action changes the "Communicative state" of the doer or of the object. In this ontology, actions of this type cannot be decomposed into some sub actions. That is to say, they are primitive actions.

Physical state action

This action also changes Communicative state of the doer or the target object. In contrast to primitive actions, this action can be decomposed into some sub actions to achieve the state change intended in the action. However, the decomposition is not defined in the definition of the action. It is defined as a "WAY" that will be explained in the later section: WAY: prescriptive model derived from strategies defined in theories. d) Example1: Inform (Figure 7) This class defines the action "Inform" as the state change of the recipient of the "Inform" action, which is an Agent, to the state of "Informed" which is a subclass of communicative state. a) Example2: Remind (Figure 8)

This class defines "Remind" as the state change of recipient of the action to the state of "Led", which is a sub-class of communicative state, to "Recall" action. Note that it is out of the scope whether the action led is actually done or not. This definition intends to describe the intention of the doer of the action. The action of "Recall" is defined as a sub-class of the "Cognitive action" which is explained below.

Cognitive (state) action

This action changes the internal state of the doer or the object. This action can be also decomposed into some sub actions to achieve the state change intended in the action. a) Example 1: Recall (Figure 9) This defines that the action of "Recall" changes the state of doer of the action to the state of "Have recalled", which is a sub-class of the internal state. This is illustrated below.

Educational event

"Educational event" is the concept for representing (1) events of learning and instruction, and (2) relations between them. Its is-a hierarchy is shown in Figure 10. "Learning event" and "Instructional event" are the concepts for representing events of learning and instruction. "I_L event" is a concept for relating "instructional event" to "learning event".

In this ontology, the instructional and learning process is defined as a process with a goal related to the situation. A process can have different meanings in different contexts, which are composed of goal, situation, etc. For example, informing a topic has an intention to afford better understanding of a learner in a context but has an intention to just call a learner's attention in another context. Based on such considerations, this ontology focuses on describing the instructional and learning process with the context clearly. The concept to describe such a process is "Event". Basically, "Event" is defined as composition of "process" and the contextual information of it such as "participant", "time", and "location". In "Educational Event", "process" is specified by "Action". You may wonder why we define "Action" and "Event" separately. The definition of "Action" also has "participant" as explained in the previous section and "time" and "location" will be fixed when an instance of "Action" is made. But what we can say here is that our policy of conceptual distinction between "Action" and "Event" in this ontology is context-dependence as mentioned in 3.2.2, especially the relation to the goal of "Action": "Event" is defined to be dependent on a context. On the other hand, "Action" is defined independently of the context, and just defined as the change of states with no relation to any intention.

Learning event

A "learning event" is composed of an agent as a learner, a learning action, its objects, effects and conditions of learning, and spatial/temporal attributes. The relation among them is suggested by learning theories.

Effect of learning

By "Effect of learning", we mean that a learning theory can tell us what effect is expected after this learning action. This meaning is described by the "Action result" relation among "Learning action", "Learning effect" and "Learning theory" slots as shown in Figure 11.

Preparing learning condition

By "Preparing learning condition", we mean that when learning conditions are satisfied, the learning theory assures that the learning action should be successful. This meaning is described by the "Guarantee" relation among "Learning action", "Learning condition" and "Learning theory" slots as shown in Figure 12.

Instructional event

An "Instructional event" is composed of an agent as an instructor, an instructional action, its objects and spatial/temporal attributes. The definition of this event itself is defined independently of the definition of "Learning event"; therefore an "instructional event" does not include how the instruction affects learning. The effect of instruction on learning is described within "I_L event" as presented below.

I_L event

An "I_L event" defines the relation between a "Learning event" and an "Instructional event". That is to say, an "I_L event" describes how an "Instructional event" contributes to a "Learning event". This relation is defined from two points of view. The first is the contribution of "Instructional event"s to the change of a learner's state. The other is the preparation for the following "Learning event".

Example 1: Preparing learning condition and Remind event

Figure 13 shows the definition of "Preparing learning condition", which is a sub-class of "I_L event", and Figure 14 shows "Remind event", which is a subclass of "Preparing learning condition". "Preparing learning condition" is composed of one "I event" slot and two "L event" slots (one is constrained by "Effect of learning" and the other is constrained by "Preparing learning condition"). This defines the following two kinds of relation between learning and instruction:

1. An "instructional action" influences a "learning action" that causes an expected "learning effect" (Of course, this never means that the learner always does the intended learning action and changes to the intended state). This is defined as the "influence" relation between the "instructional action" slot in the "I event" slot and the "learning action" slot in the "L event" slot constrained by "Effect of learning" ("Learning event"). 2. "learning action" is a preparation of the other "learning action". That is, "learning effect" satisfies the condition of the other learning action ("learning condition"). This is defined as the relation between the "learning action" slot in the "L event" slot constrained by "Effect of learning" slot and the "L event" slot constrained by "Preparing learning condition". These are defined as three slots (one "I event" and two "L event") and by the relation between them ("Influence" and "Prepare-cond").

In "Remind event", these are defined more concretely as shown in Figure 14: 1. A "Remind" action of an "instructor" influences a "Recall" action of a "learner", which causes a change of learner state to the "Have recalled" state. This relation is defined as the "Influence" relation. (In the Figure 14, the "Influence" relation in the "Remind" event appears just in order to make the explanation easy to understand. It is not necessary to define this link in the "Remind event". "Remind event" is a sub-class of "Preparing learning condition" so that the "Influence" relation is inherited.) You may think that the "learning effect" slot of "L event" slot and the "terminal state" slot of "doer" slot in "learning action" are redundant descriptions. However the "learning effect" slot of the "L event" slot describes only a notable state in this event picked from states defined in the learning action. 2. The "Have recalled" state as the "effect of the learning" is a preparation of the other future learning action of the learner. That is, the effect satisfies the condition of a future learning action. This relation is defined as the "Prepare-cond" relation and "same as" relation.

Relational concepts

In this ontology, we define the following two types of relational concepts in HOZO:

• Pure relational concepts: This is a concept to define a relation among slots in a wholeness concept. In this ontology, relational concepts other than sub-classes of "WAY" are pure relational concepts. • "WAY" and "WAY-knowledge": "WAY" is a special relational concept to describe a way of achievement of the state change in a learner. This type of relation is not used for defining the relation among slots in a wholeness concept. "WAY-knowledge" is a specified concept of "WAY" based on theories as of now. In the future, we are planning to extend this definition not only to theory but also to empirical knowledge. In OWL, both of them are defined as a sub-class of "RelationalConcept", which is a sub-class of owl:Thing. Note that they are not defined as sub-classes of owl:Property.

Pure relational concept

In this ontology, some pure relational concepts are defined. For example, "less-than", "same as", "Influence", "prepare-cond", etc. Please see in detail in the Hozo or OWL-compliant ontology editor. These pure relational concepts are used in order to define the relation among slots of a wholeness concept as shown below.

WAY: prescriptive model derived from strategies defined in theories

As mentioned above, "WAY" is a relation between an "upper (macro) I_L event" and one or several "lower (micro) I_L event"s that achieve the upper one. That is to say, a "WAY" is a description of an educational strategy. Theories prescribe strategies for planning the instructional and learning process according to supposed situations. In our modeling framework, a learning and instructional strategy is modeled as a "WAY" in view of generality which can be adapted to the specialized concrete application situations. Such a generic "WAY" is named "WAY-knowledge". Figure 15 illustrates examples of the description of "WAY-knowledge" named "Presentation" WAY. This is based on a part of Gagne and Briggs's nine events of instruction. The key of this strategy is to tell directly to a learner the content and way of learning. This "WAYknowledge" describes this learning and instructional process as the sequence of two "micro I_L event". One is to inform the content of learning as a learning item in order to let a learner recognize it and the other is to inform guidelines for learning to the learner in order to let a learner recognize the guidelines. These processes are described by "Guiding event", which is a subclass of "I_L event". "Guiding event" focuses on the continuous interaction between an instructor and a learner. In this "I_L event", the interaction is taking place from the start to the end. On the other hand, there are the other types of "I_L event", for example, "Enhancing". This focuses on a non-continuous interaction. In this type of "I_L event", basically the interaction between an instructor and a learner is taking place only once at the beginning. Then the learner does by him/herself.

A theory-aware and standards-compliant authoring system: SMARTIES

This section discusses the application of the ontology of learning and instruction and the framework of function decomposition tree.

Existing authoring environments for learning support systems aim at combining authoring tools and knowledge representation [START_REF] Murray | Authoring Tools for Advanced Technology Learning Environments: Toward Cost-Effective Adaptive, Interactive and Intelligent Educational Software[END_REF]. Most of the systems have functionalities to support instructional and learning design based on some sort of fixed theories (or empirical knowledge). Of course, such systems provide designers with guidelines and improve the consistency of design on this basis. However, all of knowledge from the theories in many of the theory-based systems is built in the procedures. It is the developer, not the system, who knows the theory. It causes concealment of the relation between the system's functionalities and the theories they are based on.

Our study aims to build a theory-aware design support system that understands theories. Such a system has the capability of explaining which theory underlies any suggestion the system makes to authors, as opposed to a system in which the theories are implemented as built-in procedures. The following sub-sections present our idea of a design support system called "SMARTIES: SMART Instructional Engineering System", which we have been developing.

An overview of a theory-aware design support system

Figure 16 shows a block diagram of SMARTIES, which has been under development in this study. The scope of support is limited to the design phase of ID process, rather than the analysis and development phases.

SMARTIES helps two types of users; one is scenario authors, which includes instructional designers, educational practitioners and occasionally learners. The other is knowledge author, which mainly includes researchers and theorists.

A scenario author makes a particular instructional and learning process model using the authoring interface. The model manager manages a model that scenario authors made. In addition, the model manager provides the author with guidelines for making a model. Based on the ontology, basic guidelines for modeling instructional and learning process are supplied; concepts and a vocabulary representing them, and the basic structure of concepts. In addition, based on "WAY-knowledge", instructional and learning strategies from theories are supplied. Finally a scenario is generated as the leaves of an instructional and learning process model. The model can also be finally exported according to IMS LD specification [START_REF]IMS Learning Design. Version 1.0 Final Specification[END_REF].

A knowledge author describes instructional and learning strategies as "WAYknowledge" with an understanding of theories and put them to the Way-knowledge base. The Way-knowledge manager manages Way-knowledge base and provides knowledge authors with the ontology as basic guidelines as well as the model manager. Describing "WAY-knowledge" makes it possible for scenario authors to retrieve strategies for intertheory cooperation and apply multiple theories to a particular instructional and learning process model. decomposition in an I_L event decomposition tree can be converted to two activitystructures for learner and instructor in an IMS LD description as shown in Figure 18.

In IMS LD, only top and leaf activities have the description of the objective while the others do not have. Therefore only a part of the design intention can be converted to the IMS LD description although it keeps sharability and executability of learning/instructional scenarios. On the other hand, an I_L event decomposition tree keeps the whole design intention together with theoretical justification of it. For these reasons, IMS LD and our modeling approach are complementary to each other.

Scenario explanation support

One of the characteristics of theory-aware systems is the ability to interpret learning/instructional scenarios in terms of theories. An I_L event as a descriptive concept and "WAY-knowledge" as a prescriptive concept enable information systems to explain theories and scenarios described as an I_L event decomposition tree and to give suggestions for scenario design/improvement.

A classification of explanation types and cases

In this study, we have classified explanation of a scenario into two types. Table 2 summarizes the classification. Each type covers some cases of explanation about interpretations of learning/instructional processes or problems in achievement of the goals. These types of explanation are based on the properties of theories discussed in 2.4. I_L event decomposition tree, "WAY-knowledge" and the definition of theories in the OMNIBUS ontology are characterized by the properties. Such scenario explanation can be done by comparison between their properties.

Interpretative explanations report interpretation result of a scenario based on the ontology and "WAY-knowledge". Scenario comprehension uses the scenario model and the descriptive concepts in the ontology. Even if an author does not use any pieces of "WAY-knowledge" for scenario authoring, this interpretation can be done. Theory exposition uses only "WAY-knowledge". This just tells what each theory proposes independently of a particular scenario. A theoretical justification of scenarios is a combination of them. This explains both interpretation of a particular scenario and its

Insufficiency of supplementary goals

It seems learners can achieve the goal but not so effective. If some supplementary goals are added, it will be better.

Excess of goals

It seems that it is difficult for learners to achieve the goal because there are too much unnecessary goals in the scenario.

Disproportion in process

The scenario doesn't have proper proportion of process. E.g. lack of motivating, too much assessment, etc.

Inconsistency of principle

The principle of learning and instruction isn't stable. A scenario needs some extent of sustainment of principle. E.g. too many suggestions in inquiry learning.

Suggestive explanation

Unsustained state

A state doesn't sustain until when it is required. E.g. an event reminds a learner of prerequisite knowledge but another event that needs it is far ahead.

justification based on pieces of "WAY-knowledge". These kinds of explanations are expected to be useful for authors to review their own scenario or to know the deign intention of those made by others. Suggestive explanations generate suggestions for improvement of scenarios. This is used when scenario authors did not use applicable "WAY-knowledge" suggested by SMARTIES but decomposed the tree using their own way knowledge in terms of the system vocabulary. In such a case, scenarios would lack theoretical validity but the system can infer the authors' intention to some extent. This type of explanation is based on the interpretation of a scenario and includes improvement suggestions of a scenario. Cases that suggestive explanations cover are listed in Table 2. Note that it is intended not to force authors to follow but to recommend alternative ways or different viewpoints. These explanations are expected to be useful to check the validity of authors own scenarios.

Generation mechanism of scenario explanation

In order to generate scenario explanation we made message templates whose vocabulary comes from the ontology and whose structure is partly based on an I_L event decomposition tree. Comparing scenario models with the ontology and pieces of "WAYknowledge" enables a theory-aware system to make interpretation and to generate explanation messages. Figure 19 illustrates an example of explanation generation. Figure 19 (d) shows an example of explanation message about Insufficiency of necessary goals of Suggestive explanation. This message is generated from the message template (Figure 19 (a)). Italic words in the template are specified by the scenario model (Figure 19 (b)) and a definition of a piece of "WAY-knowledge" (Figure 19 (c)) in the ontology. This message template is composed of two parts, which are a scenario interpretation part and a theoretical justification part. The former is related to a scenario model and the latter related to "WAYknowledge". Each part has some blank entries to be filled and each blank is related to a It is likely that the goal of the whole scenario, which is Understand level, will not succeed because the intermediate goal, whish is Prepared, is supposed not to be achieved. Gagne's nine events of instruction proposes to make the learner be in the state Motivated in order to achieve to be Prepared.

It is likely that the goal of the whole scenario, which is Understand level, will not succeed because the intermediate goal, whish is Prepared, is supposed not to be achieved. Gagne's nine events of instruction proposes to make the learner be in the state Motivated in order to achieve to be Prepared. It is likely that the goal of the whole scenario, which is <The goal of the whole scenario>, will not succeed because the intermediate goal, whish is <The goal not to be achieved>, is supposed not to be achieved. <Theory> proposes to make the learner be in the state <The insufficient goal intended to be achieved> in order to achieve to be <The goal not to be achieved>.

Scenario interpretation part Theoretical justification part

Figure 19 A generation mechanism of scenario explanation required model structure or pieces of "WAY-knowledge". This relationship enables a theory-aware system to generate specific messages using templates according to a scenario. When a system generates a message, firstly, a system compares descriptions of learner's state-changes in a scenario model with ones of "macro I_L event" in pieces of "WAYknowledge". If a state-change is the same in both but "micro I_L events" are different, the system checks the difference and generates explanation messages to notify the estimated problems. Note that this comparison cannot work if a user describes statechanges by his/her own words instead of the system vocabulary because this function is based on the concepts defined in the ontology.

The first half of the message explains the current state of the scenario model. In this case, it points out that it seems learners cannot achieve the entire goal of the scenario because one of the sub-goals is unlikely to be achieved. The blank entries in the template are filled using the scenario model (Figure 19 (b)). In this case the necessary information is <The goal of the whole scenario> and <The goal not to be achieved>. These goals are detected from the model, and words representing the goal are put into the template.

The last half explains the reason of the problem and an improvement suggestion based on a theory. The template is embodied as a message using the definition of a piece of "WAY-knowledge" (Figure 19 (c)). In this case, this message is based on Gagne and Briggs's theory. The insufficient goal in the scenario, which is "Motivated", is identified with the piece of "WAY-knowledge" and fills the blank of the template.

We are currently developing the explanation function in our prototype. Figure 17 (F) is an example of generated explanation messages.

Figure 2

 2 Figure 2 An example of an I_L event decomposition by WAYs

Figure 3 A

 3 Figure 3 A nested structure of learning, instruction and instructional design

Figure 4

 4 Figure 4The upper level structure of OMNIBUS ontology

Figure 5 Figure 6

 56 Figure 5 Is-a hierarchy of "State"

Figure 9 7 Figure 8

 978 Figure 9 Definition of "Recall" in Hozo Figure 7 Definition of "Inform" in Hozo Figure 8 Definition of "Remind" in Hozo

Figure 11 Figure 10 Figure 12

 111012 Figure 11 Definition of "Effect of learning" in Hozo

Figure 14 Figure 13

 1413 Figure 14 Definition of "Remind event"in Hozo

Figure 15

 15 Figure 15 Definition of "Presentation" WAY-knowledge (a portion)

Figure 16

 16 Figure[START_REF] Psyche | Making Learning Design Standards Work with an Ontology of Educational Theories[END_REF] Block diagram of the design support system: SMARTIES (This diagram focuses only on support for abstract design of learning contents and does not show domain knowledge and learning objects to realize the abstract design.)

  (b) A scenario model (c) A definition of a piece of Way-knowledge (d) Explanation message generated from the template. (Italic words are derived from the model and the Way-knowledge) n=1), 1.. (n?1) Relation: p/i (participate-in), p/o (part-of) Slot (a) A message template

Table 1 .

 1 A classification of the properties (not exhaustive)

	Categories	Properties	values
	Learner	-Age (type)	-child, adult
	characteristics	-Language	-Japanese, English, French
		-Prior knowledge:	-learned, not learned
		fact, concept, rule
	Domain/topic	-Concreteness	-concrete, abstract
	characteristics	-Complexity	-simple, complex
	(what to learn,	-Causality	-causal, not causal
	content)	-Prerequisiteness	-prerequisite, not prerequisite
	Context	-Context of learning	-School, workplace, university
	characteristics	-Testing	-summative, formative, Assessment, certification
		-Instruction mode	-individual, group, community
		-Delivery mode	-classroom, distance, distributed
	I_L event	-Event kind	-I_L, assessment
	characteristics	-Authenticity	-authentic, artificial, virtual-
	(scenario)	-Interaction kind	-action, interaction, social interaction

Table 2 . A classification of explanation types and cases (not exhaustive) Type Case Notes

 2

		Scenario	Explaining just interpretation of relation among events in a scenario without
		comprehension	theoretical justification. E.g. An event is preparation of another event.
	Interpretative	Theory exposition	Explaining theory itself independently of a specific situation.
	explanation	Theoretical	Explaining interpretation of relation among events in a scenario with
		justification	theoretical justification. E.g. An event is preparation of another event and the
			necessity is guaranteed by a theory.
		Insufficiency of	It seems learners can't achieve the goal because necessary (sub) goal is
		necessary goals	insufficient in the scenario.

This ontology is open to the public on our web site: http://edont.qee.jp/omnibus/.

Hozo ontology editor can be downloaded from http://www.hozo.jp

Concluding remarks

We have discussed the OMNIBUS ontology together with its application to building a theory-aware authoring tool, SMARTIES. Especially, the stress has been put on the details of design rationale and how the ontology is used at the computational level. We are just in the middle point of our long-term project. Because we already summarized what are left undone in 1.3, we only confirm here that there remain a number of problems to solve. The authors would like to kindly ask your warm help and feedback.

Ontology engineering is the key technology whose roles should be apparent. While the problem attacked in OMNIBUS project looks very AI-oriented, it is essentially different from the traditional AI in which people try to build problem solvers for humans. In other words, people try to make performance systems such as ITSs intelligent. Ontological engineering is different. It helps people solve problems by providing useful, long-lasting and reusable fundamental concepts and knowledge. It tries to make authoring tools (meta systems) intelligent rather than performance systems (ITSs). Hidden goals of OMNIBUS project include showing this new direction of AI technology application in AIED community.

The list of applicable WAY-knowledge

The list of applicable WAY-knowledge

Scenario description support

Figure 17 shows a screen shot of SMARTIES. This scene shows how a scenario author makes an instructional and learning scenario using "WAY-knowledge".

The scenario editor provides a scenario author with an environment to describe an I_L event decomposition tree as an instructional and learning process model. I_L events are represented as nodes and the decomposition of them is represented from top to bottom. In this window, an author decomposes the learning goals of the scenario step-by-step by choosing applicable "WAY-knowledge".

The Way-knowledge window provides an author with applicable "WAY-knowledge" candidates in order to help him/her decompose each I_L event. It displays applicable pieces of "WAY-knowledge" appropriate to the selected I_L event that he/she wants to decompose. When the author chooses one of them, a proposed decomposition is displayed on the window. If the author decides to adopt the selected Way, the proposal is applied to the main window. By repetition of the process mentioned above, a scenario author makes instructional and learning process model, moving from abstract levels to concrete ones.

IMS LD export

In order to enhance sharability and reusability of the scenario descriptions, we have mapped I_L event decomposition tree onto IMS LD specifications. Briefly speaking, each unit of <imsld:activities> (Snip)... <imsld:activity-structure Identifier="LAS-Advance the development836231168" structure-type="sequence"> <imsld:title>LAS-Advance the development</imsld:title> <imsld:activity-structure-ref ref="LAS-Present content857059328"/> <imsld:activity-structure-ref ref="LAS-Guide practice858066944"/> </imsld:activity-structure> <imsld:activity-structure identifier="IAS-Develop836231168" structure-type="sequence"> <imsld:title>IAS-Develop</imsld:title> <imsld:activity-structure-ref ref="IAS-Recognize857059328"/> <imsld:activity-structure-ref ref="IAS-Develop858066944"/> </imsld:activity-structure> (Snip)... <imsld:environments> (Snip)... <imsld:activities> (Snip)... <imsld:activity-structure Identifier="LAS-Advance the development836231168" structure-type="sequence"> <imsld:title>LAS-Advance the development</imsld:title> <imsld:activity-structure-ref ref="LAS-Present content857059328"/> <imsld:activity-structure-ref ref="LAS-Guide practice858066944"/> </imsld:activity-structure> <imsld:activity-structure identifier="IAS-Develop836231168" structure-type="sequence"> <imsld:title>IAS-Develop</imsld:title> <imsld:activity-structure-ref ref="IAS-Recognize857059328"/> <imsld:activity-structure-ref ref="IAS-Develop858066944"/> </imsld:activity-structure> (Snip)... <imsld:environments> (Snip)...

(a) XML description of IMS LD


Sourbier Nicolas
email: nicolas.sourbier@insa-rennes.fr

Nezan Jean-Franc

Tasse Cyril
email: cyril.tasse@obspm.fr

Hascoet Julien
email: jhascoet@kalray.eu

Optimization of Calibration Algorithms on a Manycore Embedded Platform

Keywords: Signal Processing, Astronomy, Calibration, SKA project, Many-core Embedded Systems, Optimizations

This paper presents the porting and the optimization of full polarization, direction independent calibration algorithm for radio-interferometry, on an embedded many-core platform. In astronomy, calibration algorithms consist of solving for the unknown complex antenna gains using a known model of the sky. Calibration is a key computation to provide images of the sky at good quality and high resolutions. In the context of the Square Kilometer Array (SKA) project, real-time and low power execution of the calibration is challenging. In this paper, we show that the CohJohnes algorithm provides good properties for being executed efficiently on the new generation of many-core embedded platforms. Experimental results are provided using the Kalray MPPA Bostan platform running 288 64-bit VLIW cores and delivering up to 845 GFLOPS at 12W.

I. INTRODUCTION

Calibration is a key computation to go from the radio interferometer measurement to the evaluation of the signal produced by a source in the universe. The gain calibration aims to converge theoretical gains toward the unknown complex antenna gains using a sky model. In the context of the Square Kilometer Array (SKA) project, the calibration algorithm will have to compute the data from a huge number of antenna. For instance, the SKA1 Low subproject will deliver 157 terabytes per second, enough to fill up 35000 DVD every second. Furthermore the computations must be done on site, as close as possible to the antenna to decrease the cost of the data transfers. As a result, the calibration algorithm must provide the best trade-off in terms of the resulting image quality, computation time and energy consumption.

After decades of exponential growth, the processing capability of individual Processing Elements (PEs) have leveled-off, due to complexity and power consumption considerations. In order to cope with the rising complexity of modern embedded applications, Multiprocessor Systems-on-Chips (MPSoCs) have now increased their processing capabilities by integrating more and more PEs, a wide variety of memory architectures, and complex on-chip interconnects. The MPPA processor from Kalray consists of a set of 16 clusters communicating through a Network-on-Chip (NoC), where a cluster designates a set of 16 PEs sharing a local memory of 2 MBytes. Programming MPSoCs with hundreds of heterogeneous PEs, complex mem-ory architectures, and NoCs remains a challenge for embedded system designers but at the same time it delivers high energy efficiency compared to conventional solutions.

Gain calibration is a complex non-linear least square problem and is solved here by the approach of Levenberg-Maquardt (LM) based on the Radio-Interferometric Measurement Equation (RIME [1]) to compute direction independent (DI) gain calibration. Furthermore, this study will rely on the Wirtinger optimization presented in [START_REF] Tasse | Applying wirtinger derivatives to the radio interferometry calibration problem[END_REF] that allows faster computations due to matrix simplifications. The sparse properties of matrices allows to drastically reduce the algorithmic complexity of some computations such as inversions or matrix products.We show here how the properties of the CohJohnes algorithm can be exploited to efficiently execute the calibration on modern MPSoCs. Results are obtained on an Bostan MPPA platform in term of speed and energy consumption.

In section II we present the MPPA platform and its architecture. You will find there more details about the data communication on the chip, the clustered architecture and the organization of the shared memory. Section III is about the Antenna calibration algorithms, related works and optimizations used to solve the calibration problem. The RIME equation are first reminded. The scalar polarization calibration is then briefly explained followed by the fully polarized case. Section IV shows how we adapt the calibration algorithms to the MPPA platform, present the structure of the program and the results in terms of speed and energy consumption.

Notations and frequently used symbols Symbol Description g i Gain vector at the iteration i The Kalray MPPA (Multi-Purpose Processing Array) manycore architecture is the state-of-the-art in terms of many-core embedded architecture. It is a great opportunity to execute calibration algorithms in SKA in real-time and at low power. The MPPA2-256 many-core processor integrates 256 VLIW application cores and 32 VLIW management cores operating at 400MHz on a single chip and delivers more than 80 GOPS/W.

The 256 VLIW application cores are grouped in 16 compute clusters connected with each other by a dual Network-On-Chip (NoC). Each cluster has 2 MB of locally shared memory called SMEM and available for application code and data. In addition to the 16 compute clusters, the MPPA includes 2 Input/Output clusters that communicate with the external world through high-speed interfaces such as the PCIe Gen3 and Ethernet 10 Gbits/s. Those I/O clusters also integrate quad-cores with the same VLIW architecture and are connected to up to 4GB of external DDR3 memory. Each MPPA core implements a 32-bit VLIW architecture which issues up to 5 instructions per cycle, corresponding to the following execution units: branch & control unit (BCU), ALU0, ALU1, load-store unit (LSU), multiply-accumulate unit (MAU) combined with a floating-point unit (FPU). We use the MPPA POSIX-Level programming model [START_REF] Dinechin | A Distributed Run-Time Environment for the Kalray MPPA-256 Integrated Manycore Processor[END_REF] in which the distribution of code and data across the compute clusters are explicitly managed. With this model, each compute cluster can execute an independent process started from its own binary executable. Inside each compute cluster, up to 15 additional POSIX threads can be created as a first thread already runs the main program. This programming model offers control over the memory footprint and supports thread-level parallel execution within each cluster with one thread per core. The POSIX-Level programming model also manages data transfers by using the POSIX synchronous and asynchronous file operations. These operations activate the dual NoC for internal communications and the high speed interfaces (Ethernet, PCIe Gen3, NoCX) for communications with the external world.

The programming of such an architecture is challenging due to the memory architecture (shared memory inside clusters and distributed memory between clusters) and the small size of the SMEMs compared to the large data to compute. The 80 GOPS/W are reached if the algorithm can be mapped and scheduled on the 256 cores without waiting times due to data transfers. A great care on the algorithm selection and implementation strategies are required.

III. ANTENNA CALIBRATION BACKGROUND

A. RIME formalism and Calibration Algorithm

The RIME equation is obtained by correlating data coming from two radio-telescopes. The RIME is presented in [START_REF] Smirnov | Revisiting the radio interferometer measurement equation[END_REF] and details about Antenna calibration can be found in [START_REF] Smirnov | Radio interferometric gain calibration as a complex optimization problem[END_REF]. Each antenna A i delivers complex voltages V from an electromagnetic field E. G are the complex gains we want to compute in the calibration process, B represents the Bias effects and k is the complex exponential term.

V i = E Ai = exp (2jπ(Ωt + kx i )) = G i B i * k i E (1)
The calibration is computed using the visibilities which are correlation between two antenna (A p and A q ) :

V ApAq = < V p * V H q > (2) = G Ap B Ap k Ap E E H * k * Aq * B H Aq G H Aq ( 3
)
Traditional non-linear least squares problem are solved using iterative algorithms like Gauss-Newton (GN) or Levenberg-Marquardt (LM) algorithms. Those algorithms have been extended to complex functions using a formalism called the Wirtinger derivative in which the conventional real Jacobian becomes a complex.

We implement here the CohJones algorithm described in [START_REF] Tasse | Applying wirtinger derivatives to the radio interferometry calibration problem[END_REF] and based on the LM algorithm using the Jacobian matrix in the Wirtinger framework. More details are available in [START_REF] Hunger | An introduction to complex differentials and complex differentiability[END_REF]. In this approach, visibilities are written v pq or v m for a baseline pq, at time t and frequency ν such as :

v pq = v m = V ec(V (pq)tν ) (4) = d (J d qtν ⊗ J d ptν )V ec(S d )k d (pq)tν (5)
Where d represents the directions, J the Jacobian matrix, S d is the four-polarization sky matrix and k = exp(-2iπ(ul

+ vm + w(n -1))) with n = √ 1 -l 2 -m 2 .
Results presented here focus on a single direction (d = 1) and are time frequency independent. Furthermore, we consider only one source in the center of the observation field (l = m = 0) so the complex exponential k = 1. This simplification avoids the calculation of the exponential but does not interfere with the Levenberg-Maquardt algorithm. Eq.5 becomes :

v pq = (J qt ⊗ J pt )V ec(S) (6)
where J p is the 2 X 2 Jones matrix of the antenna p. The CohJones algorithm being iterative, a distinction is made between the measured visibilities v m obtained with eq.4 and the estimated visibilities v i at an iteration i. The calibration gain vector g i at iteration i is computed using Eq.7 and converge toward the G i gains of eq.1.

g i+1 = g i + (H | gi +λ • diag(H | gi )) -1 J | H gi (v m -v i ) (7) with H | gi = J | H gi J | gi (8)

B. Considering a scalar polarization

We can then rewrite eq.5 for a scalar polarization :

v pq = J q × J p (9)
where J p is a scalar term.

1) The Jacobian matrix: The Wirtinger Jacobian matrix J vpq,gw is onerous to compute due to its dimensions. In the DI problem, its size is : N p N bl n t x 2N a N p . and is, for a given baseline:

J vpq,gw = [J vpq,g J vpq,g ] (10)
Hopefully the Wirtinger optimization allows to compute and use only half of that matrix. The matrix below details the structure of the Jacobian (in the case of a three antenna calibration) that we will be dealing with.

J v,gw =         a 0 0 b 0 0 0 c 0 0 d 0 0 0 e 0 0 f         (11)
Where the a to f components are complexes. In fact, for a scalar polarization, one line of the Jacobian for the antenna a can be written as:

[J vpq,g ] = g q f or a = p 0 otherwise (12)
2) Inverting the Hessian Matrix: As the Hessian H = J H J is a diagonal matrix. The diagonal coefficients are no longer complex but real values. This matrix will be easily inverted with an algorithmic computation of O(N a). Furthermore we have that equation from [START_REF] Tasse | Applying wirtinger derivatives to the radio interferometry calibration problem[END_REF] :

v = (J vg | g )g (13)
Injecting equation 13 in equation 7, and having H = diag(H) we obtain the hereafter algorithm:

g i+1 = λ(λ + 1) -1 g i + (λ + 1) -1 H | -1 gi J v,g | H gi v m (14)

C. Considering the fully polarized case

In the fully polarized case, eq.6 cannot be simplified as eq.9 and J p is the 2X2 Jones matrix of the antenna p.

1) The Jacobian matrix: the a to f components described in equation 11 are now 4 x 4 blocks. The shape of one block is described in the hereafter matrix 15. More details about the Jacobian can be found in [START_REF] Smirnov | Revisiting the radio interferometer measurement equation[END_REF].

J vpq,gw =     a 0 b 0 0 a 0 b c 0 d 0 0 c 0 d     (15)
2) Inverting the Hessian Matrix: In the fully polarized case, this matrix is block diagonal with hermitian blocks that present the same structure as the matrix 15 with c = b and each block corresponds to a specific antenna. In practice, the coefficients b and c have a smaller amplitude than a and d. It is then possible to make the approximation H ≈ diag(H) allowing to calibrate data using the algorithm described in equation 14.

Due to floating points approximations, we chose not to approximate the calculation of H -1 . As the inversion of a 4 x 4 matrix is a bit onerous, we rely on its shape and properties to show that as long as H is invertible each block of H -1 can be written as:

α     d 0 -b 0 0 d 0 -b -c 0 a 0 0 -c 0 a     (16) with α = 1 da-|b| 2 .

IV. MPPA IMPLEMENTATION AND RESULTS

A. Mapping the calibration on the MPPA cores

Using the property that it is possible to separate data over antenna, we built a two level master-slave software. The I/Os processor enslaves the clusters, then the main core of a cluster enslaves the other cores of its cluster. The three following graphs display the structure of the program and the parallelism. Considering a scalar polarization and for one In a fully polarized case, the computation is more complex and the number of data is increased so that the 2Mb limit in a cluster do not allow to compute the data of one antenna on each core of a cluster. The matrix operations on the data of one antenna are executed in parallel over the 16 cores of the cluster.

B. Optimizations

As seen before, the calibration involves onerous matrix computation and the MPPA architecture comes with consequent memory constraints. We present here various optimizations to reduce both the complexity and the computation time but also to ensure the portability of the algorithms on the MPPA. We present here the optimizations on the scalar polarization problem but the same have been used for the full-polarization.

1) Optimizations based on the Jacobian shape: Relying on the idea that the Jacobian had the structure presented in eq.11, only the non null components in a vector are stored. As the native Jacobian had to store N a(N a -1) * N a complex floats, we save N a * 64bits. Furthermore, considering the Jacobian as a vector makes the complexity of J v,g | H gi v m product going from O(N a 3 ) to O(N a 2 ).

2) Optimizations around the Hessian: The Hessian H is obtained by the calculation H | gi = J | H gi J | gi . Knowing the diagonal structure of the Hessian, we consider it as a vector of N a components instead of a N a * N a matrix. As we consider the Jacobian as a vector, the computation of the Hessian has no longer a complexity in O(N a 4 ) but in O(N a 2 ). Moreover, considering the Hessian as a 1-D vector saves some memory in a cluster. As long as all the components of H are non-null, this matrix is trivially invertible. Another matrix product is required in this algorithm (the one between H -1 -that should be N a * N a elements-and J v,g | H gi v m -that is a N a elements vector). The complexity of this product is reduced to O(N a) by the previous optimization.

C. Performances

This part presents, compares and comments MPPA and x86 (intel Core i5-3570 CPU -3.40GHz x 4 ) implementations in terms of quality, computation time and energy consumption (estimating the power consumption of an x86 architecture at 50 W). The following 1) Scalar polarization: The figure 5 displays the results in terms of speed and of energy consumption of the calibration of N a antenna while considering a scalar polarization on different platforms and with optimized/unoptimized implementations. The "unable to run" value refers in fact to a saturated memory (RAM for the x86 architecture and Cluster memory for the MPPA). Data separation and reshaping matrices allow us to calibrate up to 6000 antenna on the MPPA. In the unoptimized case, we can estimate the amount of data in one cluster using the formula memory used = N a 3 + 2N a 2 + N a. Without taking into account local variables, code, etc... Using 8 Bytes variables leads to fill the memory of a cluster if we try to calibrate 62 antenna or more (52 in practice).

The calibration time and the energy consumption of a calibration is not linearly scaled up with the number of antenna. This is due to the size of the matrices that we have to compute with. Indeed, if we take the Jacobian's case, dealing with 6 antenna will lead to a matrix with 18 elements (6 with our optimization) and calibrating 4 antenna will lead to a Jacobian of 48 elements (12 with optimizations). Obviously, bigger matrices lead to bigger computation and requires more resources. This justifies all the computational shortcuts and the reshaping of the matrices. The optimized code on the MPPA applies a separation over the antenna. It leads to have in each cluster and for each antenna, matrix sizes that vary linearly with N a. However, using this software architecture don't lead to a linear energy consumption or runtime. As each cluster is designed to calibrate 16 antenna (one antenna per PE) at its maximum, only two clusters are required to calibrate 32 antenna but the 16 clusters start and fetch data 4 time to calibrate 1024 antenna over one iteration. Moreover, updating the Jacobian matrix in the IO is an heavy computation that also increase the energy consumption and calibration time independently of the clusters. With the parameter N a fixed to 256, the measured speed-up between 1 core on 1 cluster and the 256 cores over one iteration of the MPPA is 33. This low value is due to the fact that starting one PE on one cluster will grant him direct access to the DDR as the NoC will not be used by any other cluster. The here after figure 6 Although we know the link between energy consumption and computation time, this table is a good indicator to find out an optimal configuration to run our program. We can easily extract from this table a linear coefficient between the iteration time and the number of started clusters. By choosing the number of started clusters and PE, we are able to regulate the energy consumption to get closer to the real-time constraint. We can use this plot to deduce a better design of our system. As the SKA project requires a specific precision (around 10 -7 ), we can then choose the optimal number of iterations to reduce both computation time and energy consumption.

2) Full polarization: The figure 9 displays the results in terms of speed and energy consumption of the calibration of N a antenna while considering a fully polarized problem using the MPPA and a x86 architecture. The comparison with an unoptimized program on the MPPA is not relevant as without optimization, the memory of a cluster would be filled with 20 antenna. The figure 11 displays the accuracy of the computing on a 10 antenna calibration for the real and imaginary part of each antenna at each polarization. We can see on these plot that the algorithm takes more time to converge. This is partly due to a mathematical shortcut that we use to perform singular value decomposition to take the first antenna as a reference. The time spent for an iteration (the parallelized step) take a negligible amount of time in comparison with the whole program. This is mainly due to the computation of the Jacobian that requires the whole Gain vector to be computed. As this gain vector is wide (N p * N a elements of 8 bytes and the optimized Jacobian has also N a * (N a -1) * N p elements), migrating the computation of this matrix on the clusters is difficult and don't really improve the performances as the NoC is overloaded all the time.

N a

V. CONCLUSION

This paper shows that calibration algorithms are efficiently executed on a MPPA many-core platform in terms of computing time and energy consumption. By studying the various equations, the shapes of the matrix and their properties, we have been able to significantly reduce the time of computation and thus to increase our performances. Numerous efforts have been made to reduce the size of the data, to ensure the computation on the 16 clusters of the chip. Hopefully properties of data separation and the computation on matrices lead to an obvious parallelism that is suitable for the MPPA.

This study was a first approach to the calibration problem and the final algorithms will take several time-frequency blocks and calibration's direction. The architecture of the MPPA is adapted for the computation of integers and the next generation of MPPA will improve the floating point performances. Future research will evaluate and compare fixed point and floating point implementations.

Even if there is still a lot to be done on these algorithms, we show here that the optimizations and the properties of the MPPA platform are relevant solutions for the SKA project on the calibration algorithms.

Fig. 1 .

 1 Fig. 1. MPPA-256 Bostan processor architecture.

Fig. 2 .Fig. 3 .Fig. 4 .

 234 Fig. 2. Program execution on the IO/s

Fig. 5 .

 5 Fig. 5. Program performance in a scalar polarization case

Fig. 8 .

 8 Fig. 8. Amplitude and phase of the difference between the estimated gains at iteration x and the true gain vector in a 40 antenna scalar calibration case

Fig. 11 .

 11 Fig. 11. Amplitude and phase of the difference between the estimated gains at iteration x and the true gain vector in a 10 polarized antenna case

  table is obtained after 60 iterations.

				)
	32	0.279	1.039	51.95
	64	2.163	4.587	229.35
	256	1357	174.364	8718.2
	1024 >8600	unable to run	x
		non-optimized code on the MPPA (single core)
	32	0.279	927.651	435.6
	>62 >1.97	unable to run	x
		optimized code for MPPA (256 cores)
	32	0.008	0.063	0.51
	64	0.017	0.197	0.87
	256	0.066	2.736	8.35
	1024 0.262	43.562	140.15

N a memory (Mo) computing time (s) Energy (J) non-optimized code on a x86 platform (single core

  displays a comparison of the number of operations per Joules between a x86 architecture and the MPPA.

		N a	architecture	op/J
		32	x86	37
			MPPA	2341
		64	x86	16
			MPPA	2526
		256	x86	2
			MPPA	1233
	Fig. 6. Number of operations per Joules on different platforms
	The following table 7 sums up the cost of 1 iteration in terms
	of time and energy consumption with several different started
	cluster/PE configurations (sorted by energy consumption) for
	a fixed number of antenna.
	PE clusters iteration time (ms) Energy (J)
	16 1	35.83	0.097
	16 4	8.99	0.107
	8	8	4.82	0.127
	1	1	76.39	0.132
	1	16	5.80	0.155
	4	16	3.00	0.167
	16 16	2.45	0.207
	Fig. 7. Energy consumption and calibration time depending on the number
	of cluster and PE started

  to start only 64 cores of the MPPA (16 clusters of 4 PE) to reduce the size of the data transfers and focus more on the computation. One antenna is computed at a time on one cluster and we use data parallelism to compute the four different polarizations on four PEs. The speedup on the iterative part of a 256 antenna calibration is 147.

	N a	architecture	op/J
	32	x86	5.47
		MPPA	3979
	64	x86	2.46
		MPPA	2457
	128	x86	0.93
		MPPA	1268
	Fig. 10. Number of operations per Joules
				memory (Mo) computing time (s) Energy (J)
			non-optimized code on a x86 platform (single core)
			32	4.36	28.08	1404
			64	34.2	124.66	6233
			128	271	659.109	32955
				optimized code for MPPA (64 cores)
			32	0.002	0.53	1.93
			64	0.004	2.09	6.25
			128	0.008	8.34	24.23
			512	0.033	133.3	410.85
			1024 0.066	533.2	795.58

Fig. 9. Program performance in a fully polarized case Here, we chose