Anna Bánáti
email: banati.anna@nik.uni-obuda.hu

Eszter Kail

Péter Kacsuk
email: kacsuk@sztaki.mta.hu

Miklos Kozlovszky
email: kozlovszky.miklos@nik.uni-obuda.hu

Miklós Kozlovszky

Usability of Scientific Workflow in Dynamically Changing Environment

Keywords: scientific workflow, dynamic workflow management system, distributed computing, cloud failures, fault tolerance

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

Introduction

Over the last years the e-Science is gaining more and more ground. Existing e-Science experiments being (also called in silico experiments) really data and process intensive, it is inevitable to be executed in High Performance Computing (HPC) environments, such as clusters, grids and more recently clouds. Thanks to the virtualized environments, one of the main advantages of the clouds is the elasticity and the availability of resources. [START_REF] Da Cruz | Capturing distributed provenance metadata from cloud-based scientific workflows[END_REF] The enormous number of nodes, the complexity of the infrastructure and the high end computing resources needed to support scientific applications executed in the cloud, bring increased potential for failures and performance problems. On one hand due to the virtualization the resource management appears simpler from the applications' point of view and many of the system level failures are hidden from the users. However, on the other hand these failures could have significant impact on the execution of scientific workflows and because of their invisibility workflow monitoring, analyzing or reproducibility is even more difficult, than in the case of other distributed systems [START_REF] Samak | Failure analysis of distributed scientific workflows executing in the cloud[END_REF]. Therefore it is even more crucial for the scientists to capture more and more parameters and data about the execution (provenance data) and about the environmental conditions since reproducibility and knowledge sharing in the scientists' community is one of the main challenges that scientific workflow management systems have to face with.

In our PhD research work we investigate provenance data analyses supporting dynamic executions of workflows and fault tolerance techniques. In this work we have summarized and classified the potential failures that may arise during the execution of scientific workflows in the cloud.

The contributions of this paper are:

1. Summarize and classify the emerging failures in the cloud during scientific workflow execution.

2. Examine the possibility of prediction and avoidance of failures with dynamic support.

3. Examine the possibility of prediction and avoidance of failures with provenance support.

The rest of the paper is organized as follows. The next section presents the contribution of our work to cloud based solutions, than we provide a short background and overview about works related to our research. Section 4 presents the dynamic requirements of scientific workflow management systems at different levels and in different phases of the workflow lifecycle. In section 5 we analyze the failures and give a solution to handle or avoid them. Finally we summarize our conclusions and reveal the potential future research directions.

Relationship to Cloud-based Solutions

One of the main challenges in cloud systems is to ensure the reliability of job execution in the presence of failures. Cloud applications may span thousands of nodes and run for a long time before being aborted, which leads to the wastage of energy and other resources. [START_REF] Liang | BlueGene/L failure analysis and prediction models[END_REF][START_REF] Pham | Toward a high availability cloud: Techniques and challenges[END_REF][START_REF] Chen | Failure Analysis of Jobs in Compute Clouds: A Google Cluster Case Study[END_REF] In order to minimize failed execution and thus the multiple re-executions of the same workflow fault tolerance techniques must be investigated and supported. Since the numbers of failures are high and the types of them vary, general methods can hardly exist. In this work we have summarized and classified the most frequent failures that can arise during execution time on parallel and distributed environment focusing on cloud environment solely. We classified the potential failures into four different levels: cloud, workflow, task and user level. After categorizing the potential failures, we show how dynamic behavior and provenance support can give solutions for avoiding and preventing them or to recover from situations caused by failures and problems that cannot be foreseen or predicted.

Related Works

The analyses and recovery or avoidance strategies of failures arising during scientific workflow execution is a widely dealt research area. Many research works focus on different fault tolerance techniques and fault tolerance analyses of workflow management systems. However most of these works deal only with different hardware failures, but higher level failures are not mentioned or specified, in general only the states of jobs are differentiated (finished, failed, and killed). The cause of the failures is usually not investigated.

Vishwanath and Nagappan in their work [START_REF] Vishwanath | Characterizing cloud computing hardware reliability[END_REF] investigate the number and the cause of possible hardware failures in modern day data centers, which consist of thousands of network components, such as servers, routers and switches. These components have to communicate with each other to manage tasks in order to provide highly available cloud computing services. Consequently the number of hardware failures can be surprisingly high. Researchers in this work set up a hierarchical reliability model which helps analyzing the impact of server -, networking equipment and individual component failures in order to decrease hardware costs and to design a more fault tolerant system.

Bala and Chane in their work [START_REF] Bala | Fault tolerance-challenges, techniques and implementation in cloud computing[END_REF] present the existing proactive and reactive fault tolerant techniques that are used in the various cloud systems. They differentiate the reactive techniques into seven categories (Checkpointing/Restart, Replication, Job migration, SGuard, Retry, Task resubmission, user defined exception handling), while proactive techniques in three categories (Software rejuvenation, Proactive Fault Tolerance using Self-Healing and Proactive Fault Tolerance using Preemptive Migration).

Plankensteiner et al. [START_REF] Plankensteiner | Fault-tolerant behavior in state-of-the-art grid workflow management systems[END_REF] investigated the fault tolerance of Grid workflow management systems. They also give an overview of the existing fault tolerant techniques in different grid systems. The detection and avoidance of failures as well as recovery methods are also discussed in the paper. They give a deep and detailed taxonomy about the failures arising during enactment. This taxonomy grounds for our research work as well. To improve fault tolerance they suggest the use of light-weight and heavy-weight checkpoints, the storing of multiple instances of data and tasks and the use of alternate tasks.

Dynamic Scientific Workflow

The Lifecycle of scientific workflows can be partitioned into disjunctive phases (hypothesis generation, design, instantiation, execution, result analyses) [9 10, 11, 12] with the help of which the development, handling and enactment steps and requirements can be clearly defined and understood.

In one of our earlier work [START_REF] Kail | Dynamic workflow support in gUSE[END_REF] we have summarized the requirements of a dynamic workflow management system regarding three phases (design, instantiation, execution) of the workflow lifecycle. In each phase (which can be interpreted as different abstract level as well) we have differentiated additional levels in order to have a deeper insight about this topic. [table 1.] Table 1. The different levels of dynamism and the various solutions and methods that can be used according to the levels

Classifying Arising Failures in the Cloud and Analyzing Dynamic Solutions

As we mentioned earlier, during the different phases of the workflow lifecycle we have to face many types of failures, which lead unfinished task or workflow execution. In these cases the users, instead of getting the appropriate results of their experiment, the workflow process aborts and in general the scientist does not have knowledge about the cause of the failure. The arising failures are examined at four abstract levels, namely the cloud level, task level, workflow level and user level. [Table 2.], [START_REF] Plankensteiner | Fault-tolerant behavior in state-of-the-art grid workflow management systems[END_REF][START_REF] Das | On Fault Tolerance of Resources in Computational Grids[END_REF][START_REF] Mouallem | A fault tolerance framework for kepler-based distributed scientific workflows[END_REF][START_REF] Alsoghayer | Risk assessment models for resource failure in grid computing[END_REF] The cloud level deals on the one hand with errors and problems related to the infrastructure (hardware or network failures), on the other hand with problems related to configuration parameters, which manage the execution.

In the table after the possible failures there is a " " sign inserted and then the potential solutions that can be carried out by a dynamic system are presented.

Cloud Level

Virtualized resource management or "cloud" technologies can simplify the scientific application's view of the resources, but do not remove the inherent complexity of large-scale applications. Thanks to the virtualized environments many levels of failures are hidden from the scientific application, and thus hard to monitor and analyze. [START_REF] Vishwanath | Characterizing cloud computing hardware reliability[END_REF] There are several issues related to computing, memory or storage resources, which are usual in grid, cluster or HPC systems, but thanks to the virtualization in cloud environment they become irrelevant. For example disk quota exceeded, out of memory, out of disk space and CPU time limit exceeded. Cloud level is divided into two sublevels, namely the hardware level and the configuration level.

Hardware level

The infrastructure is constructed from thousands of servers, routers and switches connected to each other. They communicate with each other to process the jobs. The servers consist of multiple hardware elements for example hard disks, memory modules, network cards, and processors etc., which are capable of failing. While the probability of seeing any such failure in the lifetime (typically 3-5 years in industry) of a server can be very small, the probability to meet failures in the datacenter, the number of components that could fail at any given instant is can be very high. At such a large scale, hardware component failure is rather normal than an exception. [START_REF] Vishwanath | Characterizing cloud computing hardware reliability[END_REF] Cloud providers apply hardware redundancy and fault tolerance techniques to handle them transparently. The most popular fault tolerance technique is checkpointing and job migration or replication in order to prevent or to recover from failures. Some systems provide automatic and periodic checkpointing but a dynamic system should give the possibility of dynamic and user defined checkpointing techniques as well.

Configuration level

At cloud level we have to face with not only hardware failures, but also task submission -, authentication -, service unreachable and file staging failures. At configuration level it is also true, that the checkponting technique can decrease the waste derived from any failures. In addition, the execution of a task can be failed, if some configuration policy is not suitable. For example the system should periodically check the queues and guarantee, that all the jobs in the queues will be processed in a limited time. Another example can be the number of job resubmissions, which can influence the success of job executions, when it is a constant value. In order to be able to prevent these types of failures we can adjust the configuration parameters based on provenance information, and we can dynamically change the settings during workflow execution. [START_REF] Bánáti | Towards Flexible Provenance and Workflow Manipulation in Scientific Workflows[END_REF]

Workflow Level

At workflow level we mention those failures, that have impact on the whole workflow and can corrupt the whole execution of the workflow. Independently from the type of failures, the scientists can reduce the severity of waste, if they can or they have the possibility to build the abstract workflow model from smaller modules or subworkflows. In this way the effect of failures is isolated to a small piece of workflow.

At this level, unavailable input data, invalid input data and failed data transfer can lead to errors. To handle these faults, the common fault tolerance techniques, namely data and file replication is one of the best solutions.

Task Level

The task level failures can influence the execution of only one task, and the impact of any failures does not cover the whole workflow. In generally it is true at this level (and at workflow level, too), that in the bulk of the cases the possibility of user intervention is the most helpful and efficient tools to handle the arising failures. On the one hand the user intervention can occur on the fly during execution, if it concerns to only one or a few threads of the whole workflow. On the other hand when a problem affects the entire execution than it has to be suspended and a checkpoint has to be inserted. If user intervention is supported, at these points [START_REF] Kail | A Novel Approach to User-steering in Scientific Workflow[END_REF] the user has the possibility to solve certain failures. In addition the scientist can make some changes, for example modify filtering criteria, change parameters or input data, restart a given task or a whole workflow or even do some time management actions.

In the instantiation phase incorrect output data or missing shared libraries can abort the execution.

Conclusion and Future Work

In order to minimize the effects of failures on the execution of scientific workflows, the failures should be discovered, handled or even predicted. In our work we have investigated the arising failures of scientific workflow execution in cloud environment at the different operation levels. We analyzed the possible solutions to prevent or to handle these failures transparently from the user. We have showed the methods and tools with which most of the problems can be solved. We have also highlighted that with provenance support the problems can be even more effectively handled or prevented. In our future work we would like to prove the effectiveness of the dynamic system and the provenance support with a mathematical model. and based on this model we would like to develop new proactive fault tolerance techniques.

Table 2 :

 2 The failures at the different levels and their possible solution or optimization

		cloud level failures		task level failures	user level
	design phase				-infinite loop
	(abstract wf				advanced language and
	level)				modeling support
		cloud level failures		task level failures	workflow level failures
		-HW failures	-Incorrect output data	-Input data not available
		-network failures	-Missing shared	data and file replication
		-file not found		libraries	-Input error
		-Network congestion			data and file replication
	instantiation	-task submission failure			-Data movement failed
	level	checkpoint			checkpoint
		-authentication failed
		user
		intervention
		-file staging
		-Service not reachable
		cloud level failures		task level failures	workflow level failures	user level failures
		-HW failures	-job crashed	-Data	-User-
		-network failures.		user	movement	definabl
		-file not found		intervention,	failed	e
	level Execution	manager dynamic resource -Job hanging in the queue of the local	dynamic -deadlock/livelock alternate task, checkpoint	checkpoint	exceptio n
		resource brokering		resource allocations,
		-Job lost before reaching	checkpoint
		the local resource	-uncaught exception
		manager dynamic		(numerical)
		resource brokering +		exeption
		user intervention		handling + user
				intervention


Larbi Abdenebaoui

Hans-Jörg Kreowski

Sabine Kuske

Graph-Transformational Swarms with Stationary Members

Keywords: swarm computation, graph transformation, stationary members, cloud computing

The concept of graph-transformational swarms is a novel approach that offers a rule-based framework to model discrete swarm methods. This paper continues the research on graph-transformational swarms by focusing on a special type of members called stationary members. The stationary members are assigned to particular subgraphs of the considered environment graphs. Every stationary member is responsible for calculations and transformations at the assigned area, and the applicability of the member's rules depends only on this area and not on the whole environment. A further advantage of stationary members is that it is easier to guarantee that they can act in parallel than for moving members. Cloud computing is an engineering topic where swarms with stationary members can be applied in an adequate way, namely, by modeling the nodes of the server network that forms the cloud as stationary members. We illustrate the proposed concept by means of a case study.

Introduction

Swarms in the nature are fascinating phenomena that have inspired various concepts and algorithms in computer science (see, e.g., [START_REF] Engelbrecht | Fundamentals of Computational Swarm Intelligence[END_REF][START_REF] Kennedy | Swarm Intelligence[END_REF]). However, there seems to be no framework unifying those concepts. Graph-transformational swarms have been proposed in [START_REF] Abdenebaoui | Graph-transformational swarms[END_REF] to partly fill this gap by providing a framework to model a variety of discrete swarm methods.

A graph-transformational swarm consists of members that act and interact simultaneously in an environment, which is represented by a graph. The members are all of the same kind or of different kinds. Kinds and members are modeled as graph transformation units [START_REF] Kreowski | Graph transformation units -an overview[END_REF] each consisting of a set of graph transformation rules specifying the capability of members and a control condition which regulates the application of rules. The basic framework is introduced in [START_REF] Abdenebaoui | Graph-transformational swarms[END_REF], where a simple ant colony, cellular automata and discrete particle systems are modeled to demonstrate the usefulness and flexibility of the approach.

This paper continues the research on graph-transformational swarms by focusing on a special type of members called stationary members. The stationary members are assigned to particular subgraphs of the considered environment graphs and stay there. They are responsible for calculations and transformations at the assigned areas. The number of such members is proportional to the size of the underlying graph if parts of the members' subgraphs are exclusively assigned. The advantage of stationary members is that it is easier to establish the applicability of rules and to guarantee that the members can act in parallel than for moving members.

Graph-transformational swarms are related to other graph transformation approaches to parallelism and distribution as they are surveyed in [START_REF]Handbook of Graph Grammars and Computing by Graph Transformation[END_REF] (see, particularly the contributions by Litovsky, Métivier and Sopena, by Janssens and by Taentzer et al.). These related approaches consider parallel and distributed computing on the level of rule application rather than on the level of units as in the case of swarms. One of the closest approaches seems to be the graph relabeling systems (see, e.g., [START_REF] Métivier | Graph Relabelling Systems: A General Overview[END_REF][START_REF] Bauderon | Graph Relabelling Systems: A Tool for Encoding, Proving, Studying and Visualizing Distributed Algorithms[END_REF]) where all node labels are changed simultaneously in every step implying massive parallelism and stationarity with respect to nodes.

The paper is organized as follows. Section 2 sketches how cloud-based systems can benefit from the concept of stationary members. In Section 3 we define the new notion of stationary members recalling for this purposes both the basic concepts of the underlying graph transformation approach and the notion of graph-transformational swarms. Section 4 demonstrates the notion of stationary members by means of a case study. The paper ends with the conclusion.

Contribution to Cloud-based Engineering Systems

Cloud computing is an emerging technology with high promises, but also with various technical challenges. A cloud consists of a network of computer systems that have different tasks providing resources as services. Such a network can be modeled in a natural way as a graph. Every computer system in the cloud can be represented by a node and the connections between them via labeled edges. The labels can encode various technical information. Given such a graph, the graph-transformational swarms with stationary members can be applied to solve problems and to analyze the behavior of the cloud. The key connection of this paper to cloud systems is the assignment of the stationary members to the nodes of the cloud network so that the members can execute calculations locally and parallel to each other. Depending on the problem and the architecture of the chosen network, it is possible to define different kinds of stationary members that have different roles. The technical details about how this can be achieved follow in Sections 3 and 4.

Graph-transformational swarms with stationary members can contribute to cloudbased engineering systems at least by (1) offering a visual and mathematical basis for the analysis of cloud behavior, and (2) providing a framework to design distributed algorithms based on parallel rule applications able to be used directly in a cloud. The first claim is directly inherited from the advantages using graph transformation as basic method in the proposed framework. The second claim is illustrated by the example introduced in Section 4: a cycle freeness test. The proposed solution can be directly applied to a cloud system for detecting deadlocks.

Graph-Transformational Swarms and Stationary Members

In this section, we define the new notion of stationary members. To achieve this, we recall the concept of graph-transformational swarms starting with the basic components of the chosen graph transformation approach as far as needed in this paper (for more details, see, e.g. [START_REF] Ehrig | Fundamentals of Algebraic Graph Transformation[END_REF][START_REF] Kreowski | Some essentials of graph transformation[END_REF][START_REF] Kreowski | Graph transformation units -an overview[END_REF][START_REF] Rozenberg | Handbook of Graph Grammars and Computing by Graph Transformation[END_REF]).

Basic Concepts of Graph Transformation

A (directed edge-labeled) graph consists of a set of unlabeled nodes and a set of labeled or unlabeled edges such that every edge is directed. If the target is equal to the source, then the edge is called a loop.

A match of a graph G in a graph H is an image of G in H under a graph morphism. If G is a subgraph of H, we use the notation G H ⊆ .
A rule ( , , , ) r N L K R = consists of four graphs: the negative context N, the lefthand side L, the gluing graph K, and the right-hand side R such that

. N L K R ⊇ ⊇ ⊆
We depict a rule as N R → dashing the elements in N that do not belong to L and using different shapes for nodes so that K can be identified as the identical parts of L and R. Given the rules ( , , , )

i i i i i r N L K R = for 1, , i n = … , the parallel rule 1 n i i p r = =
∑ is given by the disjoint unions of the respective components of each i r .

The application of a rule ( , , , ) r N L K R = to a graph G replaces a match of L in G by R such that the match of K is kept. If L is a proper subset of N the match of L must not be extendable to a match of N. A rule application is denoted by r G H ⇒ where H is the resulting graph and called a direct derivation from G to H. A sequence

1 2 0 1 n r n r r G G G G H ⇒ ⇒ ⇒ = = L is called a derivation from G to H. Such a derivation can also be denoted by G H * ⇒ . Two direct derivations 1 r G H ⇒ and ' 2 r G H ⇒ of two
rules r and ' r are (parallel) independent if the corresponding matches intersect only in gluing items.

The following considerations are based on a parallelization theorem in [START_REF] Kreowski | Manipulationen von Graphmanipulationen[END_REF]:

A parallel rule 1 n i i p r = = ∑
can be applied to G if and only if the rules i r for 1, , i n = … can be applied to G and the matches are pairwise independent. Moreover the i r can be applied one after the other in arbitrary order deriving in each case the same graph as the application of p to G.

This allows the use of massive parallelism in the context of graph transformation based on local matches of component rules which are much easier to find than matches of parallel rules.

A control condition C is defined over a finite set P of rules and specifies a set SEM(C) of derivations. Typical control conditions are priorities and regular expressions over P. Other control conditions are the expressions ||r|| and [r]. The first expression requires that a maximum number of the rule r be applied in parallel and the second one requires that the rule r may be applied or not.

A graph class expression X specifies a set of graphs denoted by SEM(X). We use the graph class expression id-looped(G) which adds to each node of the graph G a loop labeled with the name of the node. Another graph class expression is forbidden(H) for a graph H. SEM(forbidden(H)) contains all graphs without a subgraph isomorphic to H.

A graph transformation unit is a pair gtu= (P,C) where P is a set of rules, and C is a control condition over P. The semantics of gtu consists of all derivations of the rules in P allowed by C. A unit gtu is related to a unit gtu0 if gtu is obtained from gtu0 by relabeling. The set of units related to gtu0 is denoted by RU(gtu0).

Graph-Transformational Swarms

A graph-transformational swarm consists of members of the same kind or of different kinds to distinguish between different roles members can play. All members act simultaneously in a common environment represented by a graph. The number of members of each kind is given by the size of the kind. While a kind is a graph transformation unit, the members of this kind are modeled as units related to the kind so that all members of some kind are alike.

A swarm computation starts with an initial environment and consists of iterated rule applications requiring massive parallelism meaning that each member of the swarm applies one of its rules in every step. The choice of rules depends on their applicability and the control conditions of the members. We allow to provide a swarm with a cooperation condition. Moreover, a swarm may have a goal given by a graph class expression. A computation is considered to be successful if an environment is reached that meets the goal.

Definition 1 (Swarm).

A swarm is a system S=(in,K,size,M,coop,goal) where in is a graph class expression specifying the set of initial environments, K is a finite set of graph transformation units, called kinds, size associates a size ( ( ) )

i i size k M k ∈ with each kind k K ∈ with ( ) ( ) i M k RU k ∈ for all [ ( )] i size k ∈
, coop is a control condition called cooperation condition, and goal is a graph class expression specifying the goal 1 .

A swarm may be represented schematically depicting the components initial, kinds, size, members, cooperation and goal followed by their respective values.

Definition 2 (Swarm Computation).

A swarm computation is a derivation

1 2 0 1 q p q p p G G G ⇒ ⇒ ⇒ L such that G0∈ SEM(in), [ ( )] j k K i size k ki j p r ∈ ∈ = ∑ ∑ with a rule ki j r of 1 0 {0} > = -   and [ ] {1, , } n n = … . ( ) i M k for each [ ] j q ∈ , k K ∈ and [ ( )] i size k ∈
, and coop and the control conditions of all members are satisfied.

That all members must provide a rule to a computational step is a strong requirement because graph transformation rules may not be applicable. In particular, if no rule of a swarm member is applicable to some environment, no further computational step would be possible and the inability of a single member stops the whole swarm. To avoid this global effect of a local situation, we assume that each member has the empty rule ( , , , )

∅ ∅ ∅ ∅ in addition to its other rules. The empty rule gets the lowest priority. In this way, each member can always act and is no longer able to terminate the computation of the swarm. In this context, the empty rule is called sleeping rule. It can always be applied, is always parallel independent with each other rule application, but does not produce any effect. Hence, there is no difference between the application of the empty rule and no application within a parallel step.

Stationary Members

The basic idea of swarm computation is that the members of a swarm can solve problems by team work and massive parallelism better or faster than a single processing unit. In the general setting, there may be two obstacles to meet these advantages. (1) To compute which member can perform which action may take time proportional to k n where n is the size of the environment and k is the size of the lefthand side of the rule to be applied. The latter one can often be chosen small enough, but the former can get very large. [START_REF] Ehrig | Fundamentals of Algebraic Graph Transformation[END_REF] To make sure that members can act in parallel, one must check independence for each pair of matches of rules to be applied which is quadratic in the number of members in general. Both obstacles can be avoided by stationary members. Their matches can be found locally in a small area rather than in the whole environment and independence of most pairs of matches is automatically guaranteed because they are always far away from each other.

Although the environment is changed in a swarm computation, there may be an invariant part. A member of a swarm may be considered as stationary if all left-hand sides of its rules can only match in the vicinity of a fixed subarea of the permanent part of the environment. Then the matches of the rules depend only on the size of this subarea and its vicinity and no longer on the size of the whole environment. Moreover, the independence of such a match from other matches must only be checked if the subareas and vicinities overlap which is never the case if the involved subareas are far enough away from each other. More formally, we get the following definition.

Definition 3 (Stationary Members) .

Let S=(in,K,size,M,coop,goal) be a swarm. Then its members are called stationary if the following holds:

(1) Each initial environment graph ( ) G SEM in ∈ is associated with a set SUB of subgraphs which is kept invariant by swarm computations, i.e., SUB is a set of subgraphs of ' G for each swarm computation ' G G * ⇒ .

(

) Each member ( ) m M k ∈ for each k K ∈ is associated with a subgraph ( ) G m SUB ∈ . ( 2
) Each left-hand side of each rule of each member m contains a subgraph that matches only in ( ) G m and the rest of the match can be found in the neighborhood of ( ) G m .

Here neighborhood is a generic notion and may consist of all nodes adjacent to ( ) G m and the edges connecting them to G(m) or all nodes reachable by paths from ( ) G m of a bounded length.

A Case Study: Cycle Freeness Test

In this section, we illustrate the notion of stationary members by means of a simple and well-known decision problem. We provide a swarm with stationary members that tests an input graph for cycle freeness. Due to the massive parallelism of the swarm members' teamwork, the number of computational steps is linearly bounded. We have chosen this simple example because more sophisticated examples would need too much space. But to illustrate all the features of swarms, we solve the cycle freeness problem in a dynamic setting meaning that new edges can be added to the underlying graph from time to time so that after enough edge additions every initial graph ends up with cycles. The swarm that tests a simple, unlabeled and directed graph G for cycle freeness is depicted below. It gets the graph G as a parameter and we assume that the nodes are numbered from 1 to n. G is turned into the initial environment by adding an i-loop to each node [ ] i n ∈ . There are three kinds: (1) marker with a single rule markX which marks an edge outgoing of a node with an X-loop provided that there is no incoming unlabeled edge. The control condition ||markX|| requires that the rule be applied with maximum parallelism. The size is the number n of nodes. The member markeri for [ ] i n ∈ is obtained from marker by relabeling all occurring X with i. (2) resetter has a single rule that turns a marked edge into an unmarked one. The X-and Y-loop identify source and target yielding stationarity of the members resetteri,j where X and Y are relabeled by the node identifier , [ ] i j n ∈ . (3) adder has a rule that adds an edge between an X-and a Y-looped node. The control condition [addX,Y] requires that the rule may be applied or not. The cooperation condition requires that marker is applied as long as possible followed by an arbitrary number of repetitions of resetter followed by adder followed by marker and this again as long as possible. The goal is to reach a graph without unlabeled edges meaning that all unlabeled edges are changed into cmarked ones.

As the rule applications of the swarm members of kind marker change unlabeled edges into c-marked ones, the nodes and their loops are kept invariant so that the members are stationary and the match of the rule i mark is fixed by the unique i-loop and varies only in the outgoing edges. Two matches of i mark are independent if they access different outgoing edges which can be checked locally. Matches of i mark and j mark for i j ≠ are always independent. Consequently, a maximum parallel step of the swarm marks simultaneously all edges outgoing from nodes without incoming unlabeled edges. As long as there are such edges, their number decreases in each computational step of the marker-members such that -by induction -we always end up with the unlabeled edges on cycles. In particular, the number of such steps is bounded by the length of the longest simple path and cycles are never broken. Summarizing, the following result is shown.

Theorem 1. The swarm cyclefree(G) reaches its goal if and only if G is cycle-free. To decide this, the number of steps is bounded by the length of the longest simple path in G.

Moreover, the resetter-step returns the graph given before the markercomputations, and the adder-step adds new edges. The resulting graphs are tested by the marker-computations for cyclefreeness in the same way as the initial graph. Therefore, Theorem 1 holds for them, too.

Conclusion

In this paper, we have introduced the notion of graph-transformational swarms with stationary members, which establishes a connection between different areas of research: graph transformation, swarm computation and cloud computing. The idea is to model a cloud as a graph and to apply the concepts and results of graphtransformational swarms within the framework of cloud computing.

We have presented a case study that demonstrates how to apply the notion of stationary members to solve graph problems. The case study shows that such solutions take advantage of massive parallelism, can be visually represented and support correctness results. However, in order to prove the power of the concept, bigger and more difficult examples should be modeled in the future. In cloud computing specially, one can consider task scheduling problems which are in general NP-hard problems. Their solutions can profit from a combination of swarm heuristics and the massive parallelism within the proposed framework.

Acknowledgement. We are grateful to the anonymous reviewers for their valuable comments.


Kazimierz Krzywicki
email: k.krzywicki@weit.uz.zgora.pl

Marian Adamski
email: m.adamski@iie.uz.zgora.pl

Grzegorz Andrzejewski
email: g.andrzejewski@iie.uz.zgora.pl

EmbedCloud -Design and Implementation Method of Distributed Embedded Systems

Keywords: distributed embedded systems, embedded system design, hardware synthesis, process control, EmbedCloud method, CloudBus protocol

This paper presents a novel design and implementation methodology of the distributed embedded systems, called EmbedCloud. It defines structured implementation model for each module in the system. EmbedCloud forms the basis for the automatic code generation algorithm of the distributed embedded systems which accelerates and simplifies synthesis process of such systems. The EmbedCloud utilizes CloudBus protocol demonstrated in previous publications, which provides a process synchronization and control mechanism for a number of processing units distributed in a network. The CloudBus protocol allows to significant savings in the amount of transmitted data between end modules in the distributed embedded system, especially when compared with the other protocols used in the industry. To verify and evaluate the performance of the EmbedCloud, a concurrent process was described using Petri nets. Hardware tests and synthesis verification of the distributed embedded system was performed on the testing platform built with AVR, ATmega series microcontrollers. The tests confirmed the correctness of the developed source code and EmbedCloud method. Furthermore, resource requirements and reaction time analysis were performed.

Introduction

The dynamic development of the automatic industrial process control has caused an increased complexity and size of embedded systems. Typically, they are composed of execution units that are connected together in a logical way and form a distributed embedded system. The design and implementation of such systems is often complicated and requires long time for a large number of end modules operating in a system [START_REF] Marwedel | Embedded system design[END_REF][START_REF] Hsieh | Energy-saving cloud computing platform based on micro-embedded system[END_REF][START_REF] Adamski | Design of embedded control systems[END_REF]. Moreover, the operating costs of systems based on PLCs (Programmable Logic Controllers) networks is high.

Most of the currently available models and tools for automatic code generation provide synthesis to a single hardware execution unit without any internally implemented process synchronization and communication with external hardware units [START_REF] Nicolescu | Model-Based Design for Embedded Systems[END_REF][START_REF] Moreira | Automatic code generation for embedded systems: From UML specifications to VHDL code[END_REF][START_REF] Raghav | Model based code generation for distributed embedded systems[END_REF][START_REF] Babic | Introducing Model-Based Techniques into Development of Real-Time Embedded Applications[END_REF]. For a large number of end modules it is necessary to design them separately, e.g. using GALS (Globally Asynchronous Locally Synchronous) architecture [START_REF] Adamski | Design of embedded control systems[END_REF][START_REF] Bukowiec | Implementation of Algorithm of Petri Nets Distributed Synthesis into FPGA[END_REF][START_REF] Bukowiec | An FPGA synthesis of the distributed control systems designed with Petri nets[END_REF]. These problems have led us to develop a new method which significantly reduces the design and implementation time of distributed embedded systems.

This paper proposes a novel design and implementation method of the distributed embedded systems, called EmbedCloud. It allows a structured implementation for each module in a distributed embedded system. Furthermore, the EmbedCloud is the base for the automatic code generation algorithm which accelerates and simplifies synthesis process of such systems. The end module communication and process synchronization is achieved through the CloudBus protocol presented in [START_REF] Krzywicki | Data exchange methods in distributed embedded systems[END_REF].

In Section II relationship to Cloud-based Engineering System is described, Section III describes the CloudBus protocol. Section IV presents synthesis model and EmbedCloud method. Section V discuss verification and research results in the term of resource usage and reaction time. Section VI, concludes the paper.

Contribution to Cloud-based Engineering Systems

Large and complex distributed embedded systems form a cloud-based systems, due to large number of modules that perform various tasks and exchange data. However, such system is presented to an end-user as a single, complex, global system.

The proposed EmbedCloud accelerates and simplifies synthesis process of such systems and through the use of the CloudBus protocol provides a process synchronization and control mechanism for a number of processing units distributed in a network. The CloudBus protocol allows fast reconfiguration of the implemented system and allows to form the distributed embedded system with devices based on a different architectures.

The distributed embedded systems are able to overcome the limitations of singleunit environments and scatter the system into a various number of processing units.

CloudBus Protocol

The CloudBus protocol is one of the methods of the data exchange and concurrent process synchronization in the distributed embedded systems. It realizes distributed control method with a various number of end modules, where all of them are equal to each other and each of them implements a functional part of designed concurrent process. The CloudBus communication model allows the significant savings of the transmitted data between end modules [START_REF] Krzywicki | Data exchange methods in distributed embedded systems[END_REF]. Schematic diagram of the CloudBus protocol network topology is shown in Fig. 1.

The data transfer between end modules, necessary for process synchronization is executed only when one of the end modules requires information (input or variable state) from outside their own native resource variables. The end module broadcasts question to the system (other end modules) about the state of the specified variable, e.g. if p1 = 0?. The end module that natively controls this variable (e.g. p1) sends the answer to the system (other end modules) when it gets previously quested state. Basic data frame of the CloudBus protocol is shown in Fig. 2. The fields of the protocol corresponds to: CNT -entire frame length; FUNCcommand code (e.g. question/answer); VARS and DATA represents binary arrays of the variables and their states (values); CRC -the CRC error checksum.

In order to ensure safety and proper operation of the system, each module has a defined maximum time for receiving a response with quested variable. Alternatively, the CloudBus protocol allows to check presence of other end modules in the system.

The comparison of the CloudBus protocol with other protocols used in the industry (e.g. Modbus RTU, Profibus DP or DeviceNet protocol) showed significant savings in the amount of transmitted data between end modules in the distributed embedded system [START_REF] Krzywicki | Data exchange methods in distributed embedded systems[END_REF].

EmbedCloud -Design and Implementation Method

Hardware-Software Synthesis of Embedded Systems

The general requirements [START_REF] Marwedel | Embedded system design[END_REF][START_REF] Adamski | Design of embedded control systems[END_REF] of the distributed embedded system are listed below:

• concurrency -concurrent process execution,

• openness, flexibility, scalability -fast reconfiguration and development,

• resource sharing -ability to share data between end modules,

• platform independent model architecture -end modules may have different hardware architecture. A general diagram of the concurrent process synthesis of distributed embedded system is shown in Fig. 4. The first step is to Design (describe) concurrent process using one of the models e.g. Petri nets. The next step is Decomposition into individual sub-processes. The decomposition can be realized by different criteria imposed by the designer such as: system reaction time, hardware resource usage or designer's manual decomposition. After structural and behavioural Analysis of the decomposed process, IN/OUT assign is made -the designer assigns inputs/outputs for each end module. Finally, each module in the distributed embedded system is implemented.

EmbedCloud Structure

The proposed new design and implementation method (called EmbedCloud) of the distributed embedded system, defines an implementation model of ordered structure for each end module, Fig. 5. Implementation structure is the same for all end modules of the distributed embedded system. The main step in the EmbedCloud implementation flow is DATA STRUCT. It is responsible for storing the information about the state of the native I/O and the state of shared variables in the system. In the Read input block native I/O states are read and stored in DATA STRUCT. Afterwards FSM (Finite State Machine) block using the data from DATA STRUCT, executes a selected control process or some of its parts. In the next step (Set output) the native I/O states are set. After performing all process operations, the information is exchanged (Communication) between end modules using the CloudBus protocol. The CloudBus and EmbedCloud method are closely related, because the CloudBus protocol is responsible for obtaining and making available the necessary data from other end modules. Moreover, it provides a process synchronization mechanism. In the Communication step, the end module broadcasts to the system (other modules) messages about the state of specific variables that were asked. The received responses are stored in the DATA STRUCT and algorithm returns to the Read input and starts again.

Such structure of the EmbedCloud allows to implement end modules, which differ only in the following elements: the native I/O and implemented control model (FSM block). This allows to use different architecture of each end module, such as microcontroller, FPGA or DSP devices. Furthermore, it forms the basis for the automatic code generation algorithm.

The Conception of the Automatic Code Generation Algorithm

The EmbedCloud structure allows to propose a simplified version of the algorithm for the automatic code generation for the end modules, Fig. 6. After designing the concurrent model (Model design), the algorithm starts performing the decomposition. The Decomposition output are files in PNML or HPN format that contains divided sub-processes (represented by structured text) for each end module in the system. In the loop, files are parsed and processed for the structural and behavioural Analysis. After processing the code is generated using the EmbedCloud method. The process stops, when all files have been processed. The output of the algorithm is source code for each end module.

Experimental Results

To verify and evaluate the performance of the EmbedCloud method a concurrent process was designed with interpreted 1-bounded Petri net model, Fig. 3 (a). Fig. 3 (b) presents Petri net model after manual decomposition to three individual sub-processes for each end module. For the Module 1 and Module 3 it was necessary to add resting places (RP1) to preserve the proper functioning and synchronization of the end modules. The Module 2 executes the P1 place with y0 output. The transitions and allowing arc are described by logic equations e.g. x3*P7M2, which means: input x3 AND place P7 from Module 2. Hardware tests and synthesis verification of the distributed embedded system was performed on the testing platform built with AVR family, ATmega8 microcontrollers. Table 1 presents a comparison of the synthesis results in the terms of memory usage and reaction time. The results were obtained with EmbedCloud method to generate a source code for ATmega8 microcontrollers. All of the end modules were transmitting data with the RFM12 transceiver (manufactured by Hope Microelectronics) using the CloudBus protocol. The results demonstrated following memory usage for the ATmega8 end module: 25% of total (8k bytes) program memory, 6% of total (1k byte) data memory. The maximum reaction time (CPU clock set to 16MHz) is 0,07ms for CPU processing and less then 2ms when external communication (at 115,2kbit/s) is also performed. Concluding, the hardware resource usage and reaction time is negligibly small.

It should be noted, that memory usage and reaction time depends on the concurrent model and its decomposition. Incorrectly performed decomposition may negatively affect the obtained results, hence it is necessary to make appropriate optimization and decomposition process.

Conclusion

The paper presented the new EmbedCloud design and implementation methodology of the distributed embedded systems and formed the basis for the automatic code generation algorithm to accelerate and simplify the synthesis process of such systems.

Experimental results verified the proposed methodology and demonstrated a negligible memory usage (less than 2k bytes of program memory and 60 bytes of data memory usage) and minimal reaction time to the data requests (reaction time for CPU processing was 0,07ms; after including the data transmission to other modules -the result was less than 2ms for entire sub-process). However, it is necessary to implement and investigate various number of real distributed embedded systems with different wired and wireless network connections.

Current and further research focuses on developing the automatic code generation algorithm and graphic software tool where the embedded system designer, draws concurrent process model, assigns I/O and gets generated source code as output. Depending on the requirements, the software tool gives code in ANSI C language or one of the HDL (Hardware Description Language), such as VHDL or Verilog. Using the automatic code generator and design tool, allows the significant time savings in the design and implementation of the distributed embedded systems.

Fig. 1 .

 1 Fig. 1. Schematic diagram of the CloudBus protocol network topology.

Fig. 2 .

 2 Fig. 2. Data frame structure of the CloudBus protocol.

Fig. 3 .

 3 Fig. 3. Single module (a) embedded system vs. distributed (b) embedded system synthesis model.

Fig. 3

 3 Fig. 3 presents a comparison of two synthesis models of the embedded systems: (a) where one module performs the entire concurrent process, and (b) where the process has been decomposed into individual sub-processes and is implemented by three independent end modules.

Fig. 4 .

 4 Fig. 4. General diagram of the concurrent process synthesis of the distributed embedded system.

Fig. 5 .

 5 Fig. 5. General diagram of the EmbedCloud implementation method.

Fig. 6 .

 6 Fig. 6. Proposed algorithm for automatic code generation.

Fig. 7 .

 7 Fig. 7. Petri net model before (a) and after (b) decomposition.

Table 1 .

 1 Memory usage and reaction time for implemented distributed embedded system.

	End	Program	Data	Max.	Max.	Max. CPU	Max. Total
	Module	Memory	Memory	CloudBus	CloudBus	Reaction	Reaction
		Usage	Usage	Data	Reaction	Time	Time
		[Bytes]	[Bytes]	Transmit	Time	[ms]	[ms]
				[Bytes]	[ms]
	Module 1	1928	60	25	1,74	0,06	1,80
	Module 2	2134	60	25	1,74	0,07	1,81
	Module 3	1888	60	20	1,39	0,06	1,45

K. Krzywicki, M. Adamski and G. Andrzejewski


Fernando Pereira

Luis Gomes

Luís Gomes

Cloud Based IOPT Petri Net Simulator to Test and Debug Embedded System Controllers

Keywords: Embedded systems, Cloud based tools, Petri Nets

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

Introduction

The main goal of the IOPT-Tools integrated development environment [START_REF] Pereira | IOPT-Tools -Towards cloud design automation of digital controllers with Petri nets[END_REF] is to provide a rapid application development framework to the design of embedded system controllers and general purpose digital systems. In such framework, debug and simulation tools assume special importance, allowing the detection of mistakes during the early development phases, before reaching the prototype implementation, greatly contributing to reduce development time and cost and minimize the risk of prototype hardware damage due to controller design errors.

The tools offer a complete Cloud based tool-chain, including a graphical editor, a model-checking sub-system based on state-space computation, automatic code generation tools to produce software code or hardware descriptions, and the simulation and debug tool presented in this paper. All tools have a Web based user interface, with data storage and computing intensive operations executed on the Cloud, in the IOPT-Tools servers.

In this environment, embedded system controllers are modeled using IOPT nets [START_REF] Gomes | The Input-Output Place-Transition Petri Net Class and Associated Tools[END_REF], a subclass of Petri nets [START_REF] Reisig | Petri nets: an introduction[END_REF] specifically created for this purpose, with the addition of the concepts of input and output signals and events to the traditional Petri net place and transition nodes. This way, controller behavior is expressed using the standard Petri net concepts, but the interface between the controllers, the controlled systems and the user interface is defined using input and output signals and events.

Figure 1 presents the typical IOPT-Tools development work-flow, including all development stages. The first steps, starting with the model edition, debug and simulation, model-checking and property verification are performed inside the tools using a pure software solution. This way, designers can test and debug controllers, focusing exclusively on the controller behavior without distractions from hardware details. The final development stages are also assisted by the automatic code generation tools, minimizing the risk of low level coding mistakes and simplifying the migration to different hardware platforms.

The simulator is usually employed in the second development stage, immediately after a model is designed or suffers changes, the typical use case situations must be simulated to check if the model exhibits the expected behavior. After successful completion of the typical use case sequences, development can progress to the next stages, including model checking and property verification, automatic code generation and prototype implementation.

To better analyze the debug and simulation results, a simulation history table is automatically recorded, containing all system data for every execution step, including the net marking, input and output signals and events and internal variables. The history can be visualized as a spreadsheet table, exported to create waveform drawings or used to replay a graphical animations of the stored execution steps. The user can also navigate through the history and restart the simulation from any saved history step, to test the system behavior under different input sequences.

The tools can be used from the IOPT-Tools web service, located at http://gres.uninova.pt, and do not require any software installation on the user's personal computer or tablet computer, running directly on the Web browser. New users can log-in using a guest account to experiment the tools, but can also create personal user accounts to store private models. For more information about the tools and IOPT nets, a detailed user manual is also available online at the tools Web site [START_REF] Pereira | IOPT Tools User Manual -Version 1.1[END_REF]. The tools presented in this paper are a cloud-based solution. The simulator and the other tools run directly on the user's Web browser, using AJAX (Asynchronous Javascript and XML) principles [START_REF] Nicholas | Professional Ajax, 2nd Edition[END_REF]. All data files are stored on the cloud, in the IOPT-Tools servers, and all tasks requiring heavy duty computation, as state-space calculation and model-checking are also performed on the server, with a Web interface to display the results. This solution minimizes the computation requirements on the user's terminal equipment and can be used from low end personal computers, tablet computers or even smart-phones, as long as a W3C compliant Web browser is available.

On another way, the simulator is also a building block of a distributed architecture proposed in [START_REF] Pereira | Minimalist Architecture to Generate Embedded System Web User Interfaces[END_REF], intended to simplify the development of cloud-enabled embedded devices. This architecture minimizes the hardware resources required to implement embedded devices, greatly reducing costs, by storing all user interface data and code on the cloud and executing the user interface logic in the user's Web browser. The embedded device only needs to provide a minimal TCP/IP infrastructure to exchange data with the user interface code running on the browser, including information about the current system state and input and output signals, and receive feedback from the user interface logic.

Related Work

The simulator presented in this paper is integrated in a larger tool-chain, including a model editor [START_REF] Pereira | Web based IOPT Petri net Editor with an extensible plugin architecture to support generic net operations[END_REF], a model-checking infrastructure composed by a state-space generator and a query system [START_REF] Pereira | Model-checking framework for embedded systems controllers development using IOPT Petri nets[END_REF] and automatic code generation tools [START_REF] Pereira | Automatic synthesis of VHDL hardware components from IOPT Petri net models[END_REF]. Additional information about these tools has been published in [START_REF] Pereira | IOPT-Tools -Towards cloud design automation of digital controllers with Petri nets[END_REF] and a user manual in [START_REF] Pereira | IOPT Tools User Manual -Version 1.1[END_REF]. The underlying modeling formalism on which the tools are based, IOPT nets, has also been discussed in [START_REF] Gomes | The Input-Output Place-Transition Petri Net Class and Associated Tools[END_REF]. A direct connection to the HIPPO system [START_REF] Wiśniewski | Theoretical Aspects of Petri Nets Decomposition Based on Invariants and Hypergraphs[END_REF] provides additional tools, including the calculation of incidence matrices and analysis of place invariants, concurrency relations and sequential relations.

Computer simulation is widely disseminated over most engineering and scientific fields, and simulators can be found in many development environments [START_REF] Sadilek | Prototyping Visual Interpreters and Debuggers for Domain-Specific Modelling Languages[END_REF]. General purpose simulation software applications like Math-lab and Simulink [12] are often used to simulate diverse physical systems, covering a wide range of scientific fields. Among electrical and electronics engineers, simulators like SPICE are very popular for electrical circuit analysis. Like the tools presented in this paper, Matlab and Simulink are often used on the development of embedded system controllers, including automatic code generation tools to deploy models on hardware prototypes. IOPT nets are often used as a high level modeling formalism to the design of digital system circuits.

Simulators are usually employed to study the behavior of systems, in situations where it is not practical, costly or convenient to perform the corresponding experiments in the real world, like the effects of natural disasters, weather prediction, the behavior of sub-atomic particles, or the evolution of human demographics.

Traditionally, Petri nets have been used as a modeling language to run simulations. As the standard Petri net classes are autonomous and lack the capabilities to communicate with the external world, the purpose of these classes are the simulation by itself, and almost all Petri net tool-chains include a Simulator tool. For example, simulators can be found in CPN-Tools [START_REF] Jensen | Basic Concepts[END_REF], CPN-AMI [START_REF] Hamez | New features in CPN-AMI 3: focusing on the analysis of complex distributed systems[END_REF] and Renew [START_REF] Kummer | Renew -User Guide[END_REF].

Although existing simulators implemented in Java could be executed from Web browsers, the new simulator tool runs entirely inside the Web browser, without requiring any additional virtual machine. This way, simulator usage is not limited to PCs and can be executed on a wide range of hardware platforms and operating systems, from PCs and tablet computers to smart-phones, as long as a W3C compliant Web browser is available.

A previous Animator tool [START_REF] Gomes | Rapid Prototyping of Graphical User Interfaces for Petri-Net-Based Controllers[END_REF], could also be used to run animated simulations of Petri net models, but required the definition of a series of user interface «screens» containing graphic objects to visualize the system state and interact with the user. However, the tool and the simulations produced by this tool do not offer a Web interface and cannot be integrated in the IOPT-tools environment. The development of cloud-enabled version of the Animator tool is planned for the future and the new simulator tool already contains infrastructure code to interact with animated user interface windows build using the future Animator.

Research Innovation

The simulator presented in this paper should not be understood as a Petri net simulator, but as an embedded system controller simulator that uses IOPT Petri nets as the underlying modeling formalist. Due to the non-autonomous nature of IOPT nets, the new Simulator tool exhibits fundamental differences from the existing Petri net simulators for autonomous Petri net classes.

With traditional Petri net simulators, the user interaction with the simulator is limited to the definition of an initial marking before starting the simulation and during execution, the user can only choose the transitions that fire on each execution step, from a set of enabled transitions. In contrast, using the new embedded system controller simulator, the user interacts with the simulator by setting the value of input signals and autonomous input events. All enabled transitions will automatically fire in the next execution step, as IOPT nets use a maximal step semantics. In this regard, the IOPT simulator has more similarities with the tools found in the Ladder and Grafcet [START_REF]Programmable controllers -Part 3: Programming languages[END_REF] programmable logic controller tool-chains for industrial automation, than with the autonomous Petri net simulators.

As the user does not have to manually choose which transitions will fire, the Simulator is typically used in continuous run mode, as opposed to the traditional Petri net simulators that are often used in step by step execution mode. As a consequence, the concept of Breakpoints, popular in software development tools, has been introduced to the new Simulator, enabling the automatic interruption of continuous execution when selected transitions are fired.

As embedded system simulations typically run at very fast step rates, the user may not be able to notice all execution details in real time. To solve this problem, a simulation history mechanism has been added to enable the posterior analysis of the results and export data to draw waveform graphics. To help the user track the system evolution in real time, special attention was given to graphical feedback, dynamically changing the colors of input and output signals, triggered events, marked places, enabled transitions and transitions with guards ready.

From an implementation point of view, the new simulator also differs from traditional Petri net simulators, as it employs a compilation execution strategy instead of using a model interpreter: each time the simulator is called, the Javascript code responsible for implementing the model behavior is rewritten, according to the model in use. This strategy offers improved simulation performance, enabling simulations running at very fast step rates, comparable to the speeds employed in real embedded devices based in micro-controllers.

Finally, to reinforce the embedded system controller nature of the new simulator, it is important to notice that the tool was designed with an architecture ready to enable the implementation of a distributed IcE (In Circuit Emulator), to remotely debug embedded systems running on physical devices over the internet, using the same user interface of the simulator. To implement this solution, the code responsible for executing the IOPT semantics is replaced with proxy code that forwards executionflow commands to the remote embedded systems using HTTP requests. The status of the embedded devices is also read in real time using HTTP. The communication protocol presented in [START_REF] Pereira | Minimalist Architecture to Generate Embedded System Web User Interfaces[END_REF], and back-end HTTP server to run on the embedded devices are currently under development.

IOPT Petri Nets

The IOPT Petri net class is a non-autonomous Petri net class derived from Place-Transition nets [START_REF] Reisig | Petri nets: an introduction[END_REF], with the addition of input and output signals and events. In the same way as the traditional Petri nets, system behavior is expressed using places and transitions. However, the new input and output capabilities allows the definition of an interface with the external world, used to establish the communication between the controllers (IOPT models) and the controlled systems. Figure 2 9 -Transition priorities solve conflict situations where multiple transitions are simultaneously enabled, but there are not enough tokens to fire all of them. 10 -Test Arcs prevent the firing of transitions in the same way as normal Arcs, but do not consume the tokens and thus, do not cause transition conflicts. 11 -Maximal step execution semantics to provide deterministic execution, ensuring that all transitions ready to fire, will fire in the next execution step. Single server semantics is used, which means that even if a transition is enabled for multiple firings, only one firing will be produced per execution step. The model drawing reflects that status of the system, by changing the colors of the nodes. Places change colors according to the current marking: no tokens, one token or many tokens. Transitions change color according to the readiness: autonomously enabled, ready to fire or both. Boolean input and output signals change color according to the value, and input and output events also flash when triggered. This color scheme helps the user interpret the current system status, resulting in much faster debug sessions. For example, instead of manually calculating the value of guard expressions to check if a transition is ready to fire in the next execution step, the user can simply observe the transition color. The user can interact with the system both in the properties form and directly in the model drawing. For example, the value of an input signal can be changed on the corresponding item on the properties form, but it may also be changed by picking the corresponding signal on the graphic.

Simulator Functionality

Continuous execution can be automatically interrupted with Breakpoints associated with transitions. Picking on a transition sets or resets a Breakpoint. A red border is drawn around transitions with Breakpoints. Execution stops immediately after a transition with a Breakpoint is fired, and the user interface reflects the system status after the firing. In case the user desires to inspect the status of the system prior to the firing, it is possible to undo the last executed step or move one position backwards in the recorded history.

The simulator maintains a complete record of the system status during entire simulation sessions. Whenever a new step is executed, the entire system status is recorded, including the value of input signals, events triggered, and information about transitions fired. The user can navigate through the saved history, and the user interface will change to reflect the status of the selected history step. This way, it is possible to inspect the past system evolution to detect flaws that may have not been noticed by the user during the original execution.

To simplify the inspection of the past system evolution, it is possible to replay the recorded history with programmable speed, starting on the current history step. In alternative, the simulator history can also be presented in the form of a spreadsheet table, as displayed in figure 4. To simplify inspection, repeated execution steps with identical status are compressed in a single table line with indication about the number of repetitions.

Finally, the history table can be exported in CSV (Comma Separated Values) text file, suitable for spreadsheet edition, or to be imported by other software. Taking advantage of the graphing functionality offered by most spreadsheet applications, it is very easy to create waveform diagrams of the input and output signals, as well as the internal system status variables.

For more detailed information about the simulator usage, tool options, interaction and color schemes, a user manual can be downloaded from the tools web interface [START_REF] Pereira | IOPT Tools User Manual -Version 1.1[END_REF].

Simulator Architecture

The core of the simulator is a based on a new automatic code generator tool that produces Javascript code. Instead of relying on a model interpreter, the part of the simulator code that implements the model semantics is dynamically generated each time the simulator is executed, with code that implements the semantic rules of execution defined in each model.

The automatic code generator itself, is implemented using a XSLT Transformation [START_REF] Tidwell | XSLT -Mastering XML Transformations, 2 nd edition[END_REF] applied to the model's PNML [START_REF] Billington | The Petri Net Markup Language: Concepts, Technology, and Tools[END_REF] files. The code generator uses the same principles as the VHDL and C code generators and detailed information about the code generation techniques can be found in [START_REF] Pereira | Automatic synthesis of VHDL hardware components from IOPT Petri net models[END_REF]. The generated Javascript code contains the following items:

-A semantics execution function that runs a single execution step of the model being simulated -Several functions that evaluate the state of each transition, to check if it is autonomously enabled or the associated input events and guard functions are ready (to provide animated graphical feedback) -Several JSON [Javascript Object Notation] objects representing the net marking, the input signals, output signals, input events, output events and model arrays.

The user interface code calls another XLST transformation to create an SVG (Scalable Vector Graphics) [START_REF]Scalable Vector Graphics (SVG) 1.1[END_REF] document containing the graphical representation of the model, that is displayed in the central area of the simulator window. To process each execution step, the simulator executes the following tasks: a) Update the JSON objects representing input signals and autonomous input events b) Update the user interface color schemes, using the transition evaluation functions c) Call the Javascript function that executes a single execution step d) Update the user interface status form, according to the new values on the JSON objects e) Update the graphical model according to the new status and apply color schemes This architecture is ready to implement an in-circuit emulator used to remotely debug embedded systems designed using IOPT tools. To achieve this, the Javascript execution function in c) is replaced by a proxy function that communicates with the remove system, sending and receiving the JSON objects used in a) and d).

Conclusions and Future Work

The simulator has been developed and integrated in the IOPT tools service and has been used to debug and simulate numerous models. The behavior of the simulated models has been compared with real world implementations of the same models running on embedded hardware boards, and also with the state-space graphs, with no inconsistencies detected. As a consequence, the simulator can be used effectively to detect design flaws before reaching the prototype implementation phase. As the typical development cycle takes only a few seconds after completing a model edition to start a new simulation session, development time can be enormously reduced. The alternative solution, debugging models using prototype boards, generally impose much longer development cycles, as the FPGA synthesis tools usually take many minutes to generate the bit-stream files necessary to reconfigure the hardware devices.

The rapid detection of design flaws often requires the simulation of the entire embedded systems. Although IOPT nets have been designed to the development of controllers, the user can build enhanced models containing both the controller and also the controlled systems. With this solution, the user can simulate the entire embedded systems, including controlled hardware and can even calculate the statespace graphs of the entire system.

Future work includes the addition of a waveform editor, to pre-program sequences of input signals and graphically visualize the resulting output signal waveforms. A database of signal waveforms can be stored in the cloud, and used as an automatic unit-test framework to perform regression tests and compare results with previous executions. An in-circuit emulator to debug remote systems is currently under development. Integration with an Animator tool is planned and the Simulator is currently ready to interact with other windows that present Animator generated screens. These screens will add new user interface windows, bringing additional user friendliness and the ability to be used by persons without knowledge about Petri nets.

Fig. 1

 1 Fig. 1 The typical IOPT-tools workflow

  displays an example IOPT model. IOPT models support the usual places and transitions from P/T nets, plus the following characteristics: 1 -Input and output signals, can hold Boolean or integer range values, suitable to represent digital or analog I/O signals, respectively. 2 -Input events, representing instantaneous changes in input signals. 3 -Output events cause instantaneous changes in the value of output signals. Output events associated with transition firing, can increment or decrement the value of output signals by a specific amount. The signals hold the last values. 4 -Autonomous input and output events, not associated with I/O signals, are used to instantaneously propagate events between different component models. 5 -Guard expressions may be associated with transitions, containing logic conditions to inhibit transition firing according to the value of input signals 6 -Input events may also be associated with transitions to synchronize firing. 7 -Output actions may be associated with places, to define the value of output signals, when the places are marked. When no actions are active, the signals revert to a default value. 8 -Output actions associated to transitions, define the value of output signals when the transition fires. The affected signals memorize the last values.

Figure 3

 3 Figure 3 presents the IOPT simulator user interface, composed by a toolbox on the left, a properties form on the right and a drawing of the model on the center. The toolbox contains icons for step-by-step execution, undo the last executed step, continuous execution, reset to initial marking, define a new forced marking, history navigation, history replay and history file export. The properties form contains the entire simulator status, including the current net marking, input signals, output signals and input and output events.The model drawing reflects that status of the system, by changing the colors of the nodes. Places change colors according to the current marking: no tokens, one token or many tokens. Transitions change color according to the readiness: autonomously enabled, ready to fire or both. Boolean input and output signals change color according to the value, and input and output events also flash when triggered. This color scheme helps the user interpret the current system status, resulting in much faster debug sessions. For example, instead of manually calculating the value of guard expressions to check if a transition is ready to fire in the next execution step, the user can simply observe the transition color.

Fig. 2

 2 Fig. 2 IOPT Model -Quadrature decoder

Fig. 3

 3 Fig. 3 Simulator / Debugger User Interface

Fig. 4

 4 Fig. 4 Recorded history table

F. Pereira and L. Gomes

Acknowledgments. This work was partially financed by Portuguese Agency" FCT -Fundação para a Ciência e a Tecnologia" in the framework of projects PEst-OE/EEI/UI0066/2011 and PTDC/EEI-AUT/2641/2012.


Adrienn Dineva
email: 1dineva.adrienn@bgk.uni-obuda.hu

Annamária R Várkonyi-Kóczy
email: varkonyi-koczy@uni-obuda.hu

József K Tar
email: 3tar.jozsef@nik.uni-obuda.hu

Improved Denoising with Robust Fitting in the Wavelet Transform Domain

Keywords: wavelet shrinkage, robust fitting, nonparametric regression

In this paper we present a new method for thresholding the coefficients in the wavelet transform domain based on the robust local polynomial regression technique. It is proven that the robust locally-weighted smoother excellently removes the outliers or extreme values by performing iterative reweighting. The proposed method combines the main advantages of multiresolution analysis and robust fitting. Simulation results show efficient denoising at low resolution levels. Besides, it provides simultaneously high density impulse noise removal in contrast to other adaptive shrinkage procedures. Performance has been determined by using quantitative measures, such as signal to noise ratio and root mean square error.

Introduction

Many applications of signal representation, adaptive coding, image enhancement, radio astronomy, etc., require the development of highly efficient data processing techniques. Traditional approaches, such as linear filtering, can smooth the corrupted signal, but with weak feature localization and incomplete noise suppression. Nonlinear filters have been proposed to overcome these limitations. Among the classical signal processing methods, wavelet-based noise reduction has been successfully applied to filter data, because it provides information at a level of detail, which is not available with Fourier-based methods [START_REF] Mallat | Multiresolution Approximations and Wavelet Orthonormal Bases of L 2[END_REF]. The discrete wavelet transform analyses the signal at different frequency scales with different resolutions by reducing the signal into approximate and detail information [START_REF] Mallat | Multiresolution Approximations and Wavelet Orthonormal Bases of L 2[END_REF] [START_REF] Daubechies | The Wavelet Transform, Time Frequency Localization and Signal Analysis[END_REF]. For removing noise, wavelet shrinkage employs nonlinear soft thresholding functions in the wavelet domain [START_REF] Donoho | De-noising by Soft-thresholding[END_REF]. The popularity of this nonparametric method is due to the excellent localization and feature extracting behavior. The fast signal transform algorithms provide significant reduction in the computation time [START_REF] Mallat | Multiresolution Approximations and Wavelet Orthonormal Bases of L 2[END_REF] [START_REF] Daubechies | The Wavelet Transform, Time Frequency Localization and Signal Analysis[END_REF]. The effectiveness of wavelet shrinkage relies on that the wavelet transforms the additive white noise into white noise in the coefficient domain. Thus, fewer coefficients represent the signal which allows proper separation of the noise. Further, the wavelet-based technique requires only less assumption about the properties of the signal [START_REF] Donoho | De-noising by Soft-thresholding[END_REF]. On the other hand, by using higher decomposition levels, the signal loses more of its important features which degrade the result significantly. The specific choice of the wavelet function, decomposition level, and thresholding rule allows to construct many different shrinkage procedures. A number of advanced concepts have been introduced on defining the threshold estimator rule (see, e.g. [START_REF] Donoho | De-noising by Soft-thresholding[END_REF]

[4][5][6][7][8]
). It is desirable to construct shrinkage procedures that are robust to impulse noises, which can lead to data loss. The main motivation for the work presented in this paper is to show that by applying robust fitting technique in the wavelet domain, highly efficient denoising effect can be achieved. The proposed method is robust to high density impulse-type noises and requires only low resolution levels.

Basics on Wavelet Shrinkage

The two major approaches of the noise removal task are the denoising in the time or space domain and the denoising in the transform domain. The transform-domain denoising procedures assume that the original signal can be well approximated by a linear combination of some basis functions. The wavelet transform preserves the true signal in few high-magnitude atoms and the others can be associated with noise. Consider the classical noise suppression problem:

,s , 1 i , (t) f y i i … = ε + = (1)
where yi denotes the observed noisy data and i ε represents the random noise, which is an independent and identically distributed (iid) process, and (t) stands for time. Let f denote the unknown function. The sampling points are equally spaced s=2 n in order to allow to perform the discrete wavelet transform (DWT) [START_REF] Mallat | Multiresolution Approximations and Wavelet Orthonormal Bases of L 2[END_REF]

The first step of wavelet shrinkage is the decomposition of Eq. (1), as follows

n , 1, j , ε ω y i ij ij … = + = (3)
where ij ω are the wavelet (detail and approximate) coefficients on j th scale. The general idea behind wavelet shrinkage is to replace the coefficients with small magnitude to zero (hard thresholding ) [START_REF] Donoho | De-noising by Soft-thresholding[END_REF], [START_REF] Donoho | Ideal Spatial Adaptation via Wavelet Shrinkage[END_REF] or set their value to the threshold level [START_REF] Donoho | De-noising by Soft-thresholding[END_REF], the rule is given by

      λ > ω ω = λ ω η otherwise 0 if ) , ( ij ij ij
) 0 ), max(( ), sgn( ) , ( ij ij ij λ - ω ω = λ ω η (5) where ) , ( ij λ ω η
is a soft thresholding function applied to the ij ω transform coefficients and λ is the threshold value. Then, the reconstruction process performs the inverse discrete wavelet transform (IDWT).

Thresholding Operations in the Wavelet Domain

In this section we briefly summarize the prevalent shrinking concepts. The importance and advantages of wavelet shrinkage is discussed in several papers (see, e.g. [START_REF] Taswell | The What, How, and Why of Wavelet Shrinkage Denoising[END_REF]). Most of them construct nonlinear threshold functions based on statistical considerations. Shrinkage of empirical wavelet coefficient (RiskShrink) is firstly introduced in [START_REF] Donoho | De-noising by Soft-thresholding[END_REF]. Another effective and widely used level-dependent and smoothnessadaptive method (SureShrink) is proposed to thresholds each dyadic resolution level using the principle of Stein's Unbiased Estimate of Risk [4][10]. The universal bound thresholding rule also provides good results with low computational complexity [START_REF] Donoho | Adapting to Unknown Smoothness via Wavelet Shrinkage[END_REF]; the rule is defined, as follows . Later, the Heuristic Sure thresholding rule is introduced by a heuristic combination of the SureShrink and the universal bound [START_REF] Donoho | Adapting to Unknown Smoothness via Wavelet Shrinkage[END_REF];

q p if q p if ) , min( UB Sure UB    < ≥ η η η = η (7)
where

∑ = ω = = = k 1 i 2 i 2 3 2 m , k) log ( q and k m-k p
. The Minimax estimator is also a preferred technique [START_REF] Donoho | Minimax Estimation via Wavelet Shrinkage[END_REF], the rule is given by

32 if s 32 if s 0 ) s log 1829 . 0 3936 . 0 ( 2 MAD < >    + σ = η (8)
Regarding the shrinkage approaches concentrating on white noise modelling, another effective data-adaptive procedure for eliminating Gaussian noise from images is BayesShrink [START_REF] Chang | Spatially Adaptive Wavelet Thresholding with Context Modeling for Image Designing[END_REF]. It performs the noise variance estimation on the sub-bands with median estimator. NeighShrink employs an overlapped window on the neighboring coefficients, thus this method takes into account the relation between the atoms [START_REF] Cai | Incorporating Information on Neighboring Coefficients into Wavelet Estimation[END_REF]. The threshold value for each coefficient is determined by the principle, that when in the block the neighboring atoms represent the signal it is probable that the current element is also a part of the signal.

The other major approach in noise reducing applications is minimizing the effects of outliers (extreme values or elements that deviate from the observation pattern). Recent studies deal with eliminating the outliers during the signal pre-processing.

Several areas of engineering practice benefit from such algorithms, for instance monitoring and fault detection applications, data mining, feature identification in satellite images, etc., (see, e.g. [11][12]). It is proven, that the robust local polynomial regression technique detects outliers excellently [START_REF] Rousseeuw | Robust Regression and Outlier Detection[END_REF]. With this in mind, the present paper proposes an improved denoising method based on robust fitting in wavelet domain.

Contribution to Cloud-based Engineering

Cloud-based engineering has been a major discussion in the recent years [START_REF] Rudas | Cloud Computing in Intelligent Robotics[END_REF]. The basic concept is that by sharing dynamic and quickly expandable resources among users more computational power, storage, etc., are available at lower cost. The challenges of outsourced applications involve the development of advanced signal processing techniques. On the other hand, the increasing amount of data, and transmission processes, generate a lot more noise. Typically, in a wider sense, collaborative or adaptive filtering solutions maintain big databases including many different kinds of data, such as sensing and monitoring data, signals of environmental sensing over large areas or multiple sensors. Additionally, several industrial processes depend on outsourced adaptive controllers [START_REF] Tronsco-Pastoriza | Secure Signal Processing in the Cloud: Enabling Technologies for Privacy-preserving Multimedia Cloud Processing[END_REF]. In order to guarantee the proper performance, the signals need special care. Dealing with very sensitive data it is essential to ensure lossless processing even in nonstationary environments. The proposed denoising method can be applied in various scenarios where efficient noise removal is required especially when impulse-type disturbances may occur. Recent researches on cloud-based applications of multiple access communication highlight the construction of low probability of intercept signals [START_REF] Tronsco-Pastoriza | Secure Signal Processing in the Cloud: Enabling Technologies for Privacy-preserving Multimedia Cloud Processing[END_REF] [START_REF] Valsan | Wavelet Transform Based Digital Protection for Transmission Lines[END_REF]. Wavelet functions are proposed to employ as building blocks or atoms for the construction of communication signals. The theoretical and technical approaches and results presented in [START_REF] Teolis | Computational Signal Processing with Wavelets[END_REF], show that the wavelet communication scheme satisfies the main objectives of secure, high throughput and low bit error. Based on the proposed robust thresholding method further improvements can be achieved, e.g. in energy threshold detection and recovery problems in the transformed domain.

3 Improved Denoising with Robust Fitting in the Wavelet Transform Domain

Local Polynomial Regression

The local polynomial regression (loess) procedure originally described in [START_REF] Cleveland | Robust Locally Weighted Regression and Smoothing Scatterplots[END_REF], is also called locally weighted running line smoother. Extensions of the original method can be found in, e.g [START_REF] Cleveland | The Many Faces of Scatterplot[END_REF]. The principle of the method can be summarized as follows. Lets consider Eq.( 1). Function f(t) can be approximated by fitting a regression surface to the data by determining a local neighbourhood of an arbitrary (t0). These neighbouring points are weighted depending on their distance from (t0). The closer points get larger wi weights. The estimate f ˆ is obtained by fitting a linear or quadratic polynomial using the weighted values from the neighbourhood. Detailed description of the procedure and the loess curve construction can be found in [START_REF] Rousseeuw | Robust Regression and Outlier Detection[END_REF][18] [START_REF] Martinez | Computational Statistics Handbook with MATLAB[END_REF]. Loess relies on least squares regression and it is known that this is vulnerable to outliers that can significantly degrade the result. In order to introduce robustness in the procedure an iterative reweighting is proposed with bisquare method [START_REF] Fox | Nonparametric Simple Regression[END_REF]. The brief description of the simple bisquare method following the notation of [START_REF] Martinez | Computational Statistics Handbook with MATLAB[END_REF], is the next. The residuals can be obtained

i f ŷ ˆi - = ε
after fitting a linear regression. The weights are obtained by the bisquare function, the formula is given by

   < - = otherwise 1 x 0 ) x 1 ( ) x ( B i 2 2 i (9)
and the robust weights are calculated as

        ε = 5 . 0 i i q 6
B r [START_REF] Stein | Estimation of the Mean of a Multivariate Normal Distribution[END_REF] where 5 . 0 q ˆ denotes the median of i ε .

Wavelet Shrinkage with Robust Fitting

The proposed shrinkage approach includes the following steps. Firstly, the corrupted signal is decomposed with orthogonal wavelet functions, which separates correctly the detail and approximate coefficients of the signal. Then, the robust fitting is applied on the coefficients on each level. Afterwards, the signal is reconstructed with inverse discrete wavelet transform. Thus, the realization of the new shrinkage procedure is the following: 1.) perform the discrete wavelet transform, 2.) fit the local polynomial regression curve on the coefficients with the wi weights; 3.) get the residuals; 4.) get the median absolute value of the residuals; 5.) calculate the robust weights ri with Eq. (20.); 6.) repeat step 1 with riwi; 7.) repeat step 3 to 6 until it converges; 8.) perform the IDWT.

Simulation Results

The performance of the proposed procedure has been tested on a one-dimensional signal corrupted with additive white Gaussian noise and impulse noises (Fig. 1.). The results have been compared with two other shrinkage algorithms. The simulation has been built by using Matlab7. The performance is measured by the root mean square error (RMSE) and the signal to noise ratio (SNR), calculated by the formula below σ is the variation of the signal after denoising and n 2 σ is the variation of the eliminated noise. For the decomposition an orthogonal wavelet has been chosen from the Symlet family [START_REF] Daubechies | The Wavelet Transform, Time Frequency Localization and Signal Analysis[END_REF]. The results are summarized in Table1. The performance of the robust fitting-based method can be seen in Fig. 2. The procedure precisely removes the noise and smoothes the signal. Though, the HeurSure and the Minimax rule are faster (see Table 1.) and eliminate additive noise, but can not cope with impulse noise (Figs. 34). Since the reconstruction is not sufficient, further smoothing and impulse-eliminating processes are desired, which increase the total elapsed time. With this in mind, the speed of the proposed procedure is acceptable. Fig. 5. shows the denoising effect of the HeurSure method at 8 decomposition levels. Comparing Fig. 4. with Fig 5 . and the SNR and RMSE values, it can be seen, that in case of denoising with smoothness-adaptive shrinkage, the presence of impulse noises and the increase of resolution levels lead to data loss.

Conclusions

In this paper a new approach is proposed for shrinking the wavelet coefficients. There are various sources of perturbations that may occur in the coefficient domain. This procedure excellently removes both additive noise and impulse noise with retaining the important parts of the signal. The method requires only low resolution levels and is able to avoid data loss. Simulation results support, that the denoising efficiency can be significantly improved. Due to fitting a polynomial and calculating the robust weights on each point the performance is time-consuming. However, it is not necessary to use all the data points. Research into solving this limitation by introducing further data adaptive law in the proposed method is already underway. Future work also aims to reduce complexity, and to extend the procedure to nonorthogonal representation and investigate other types of signals.

Fig. 1 .Fig. 2 .Fig. 3 .Fig. 4 . 4 Fig. 5 .

 123445 Fig. 1. The original signal corrupted with additive white Gaussian noise and impulse noises

Table 1 .

 1 Simulation results.

		Shrinkage with	HeurSure	HeurSure Minimax
		Robust Fitting
	SNR [dB] before	2.2294	2.2294	2.2294	2.2294
	SNR [dB] after	23.5412	8.7601	3.6653	5.9276
	RMSE	0.04159	0.5372	0.7621	0.3293
	Level of decomposition 1	4	8	4
	Abs. max error	0.2289	0.8621	0.9535	1.1107
	Elapsed Time [s]	0.4196	0.0184	0.0127	0.0312

Acknowledgments. This work was supported by the Hungarian National Scientific Research Fund (OTKA 105846).