Higher-order model composition can be employed as a mechanism for scalable model construction. By creating a description that manipulates model fragments as first-class objects, designers' work of model creation and maintenance can be greatly simplified. In this paper, we present our approach to higher-order model composition based on model transformation. We define basic transformation rules to operate on the graph structures of actor models. The composition of basic transformation rules with heterogeneous models of computation form complex transformation systems, which we use to construct large models. We argue that our approach is more visual than the traditional approaches using textual model descriptions. It also has the advantage of allowing to dynamically modify models and to execute them on the fly. Our arguments are supported by a concrete example of constructing a distributed model of arbitrary size.
(a) Top level of the MapReduce model (b) Internal design of the Split actor (c) Internal design of the Map actor (d) Internal design of the Reduce actor (e) Internal design of the WaitingStop actor
Fig. 1. MapReduce model with 2 Map machines and 3 Reduce machines
In recent practice we have seen large-scale models containing thousands or
even millions of actors. One concrete example is the model for distributed
wordcounting created using the MapReduce programming paradigm as described by
Dean and Ghemawat in Google [
It is hard to imagine manually constructing one such model for a large number of worker machines. The complexity of the work grows sharply as the number of actors increases. Even if the model can be constructed manually, it is still extremely difficult to modify or maintain the design. We are thus motivated to explore an approach to automated model construction and modification.
In our prior work, we have developed Ptalon as a declarative language for
higher-order model composition [
In our recent effort on higher-order model composition, we aim to provide a more straightforward and user-friendly mechanism for constructing models. We view models as attributed graphs, and employ graph transformation technique. We have implemented a tool that supports a visual language for specifying transformations. The visual language is very close to the language that model designers use to manually create models. This removes the need for requiring model designers to learn new languages.
We envision a variety of applications for our technique. In this paper, we present an example for automated model construction and execution. Other applications include model optimization, refactoring, structural parametrization, and workflow automation.
(AFRL), the State of California Micro Program, and the following companies: Agilent, Bosch, HSBC, Lockheed-Martin, National Instruments, and Toyota.
Top
C A
B (a) An example of a hierarchical model (b) Attributed graph representation 1. Models are constructed with graph transformation rules that have a visual representation, whereas in Ptalon, textual descriptions are used. 2. Transformations can be applied to existing models as incremental modifications statically or dynamically. 3. A hierarchical heterogeneous model can be used to control the application of multiple transformations.
The following sections are organized as follows. In Section 2, we present models as graphs and define basic transformations. In Section 3, we discuss using a model to control basic transformations to form a complex transformation. We construct a MapReduce model with transformation as an example in Section 4. We study the related work in Section 5, and conclude our discussion in Section 6. 2
(a) Pattern (b) Replacement
which is similar to a rewrite rule in a context-free grammar. It can be used to match a subgraph in a given graph, and to replace that subgraph with a replacement graph. We specify a transformation rule with three components: a pattern, a replacement, and the correspondence between objects in those two.
Fig. 3 shows a transformation rule designed for our MapReduce example, which we will further discussed in Section 4. This rule creates connections between the output ports of a Map actor and the input ports of a Reduce actor. Repeatedly applying the rule results in having all the Map actors and Reduce actors connected in this way. In the pattern, two matchers aim to match two distinct actors in the given model. The names of the matchers are insignificant and need not be the same as those of the matched actors. Without considering the constraint, the two matchers in the pattern match any two such actors: one with output ports named “outputKeys” and “outputValues,” and the other with input ports “inputKeys” and “inputValues.” The constraint requires that the ports of the two actors not be connected before the transformation is applied. This avoids creating excessive connections between the same pairs of ports.
In the replacement, the two matchers are preserved, meaning that the matched actors should be kept after transformation. Two connections are to be created between their ports, because those connections (along with the hidden relations on them) do not exist in the pattern. In general, designers of transformation rules can specify adding or deleting objects by editing the replacement as they wish. Note that the names of the matchers in the replacement need not be the same as those in the pattern, because the third component, the correspondence table, establishes the relations between the two graphs. In this case, the correspondence table states that the “Map” object in the pattern corresponds to the “Map” object in the replacement, and the “Reduce” object in the pattern corresponds to the “Reduce” object in the replacement. For brevity, we do not show correspondence relations between other types of vertices such as ports and relations. 2.2
Our graph transformation is defined as a modified version of the double-pushout
approach introduced in [
A graph G is a tuple hVG, EGi, where VG is the set of vertices in G and EG ⊆ VG × VG is the set of edges. Graph G is a subgraph of graph H if VG ⊆ VH and EG ⊆ EH .
A graph morphism, or simply morphism, from graph G to H is a total function m : VG → VH , such that for any v1, v2 ∈ VG, if (v1, v2) ∈ EG, then m m(v1), m(v2) ∈ EH . We denote this morphism with G −→ H. For any vertex v ∈ VG, we say v matches v′ in m if m(v) = v′. For any edge (v1, v2) ∈ EG, we say (v1, v2) matches (v1′, v2′) in m if m(v1) = v1′ and m(v2) = v2′. If m is an injective function, then we say G is isomorphic to a subgraph of H, or G matches a subgraph of H.
The composition of G −→ H with H −n→ I is G n−◦→m I, where n◦m : VG → VI m is the composition of function m : VG → VH and n : VH → VI .
G n I m m0 y
H n0
J z x
K m n Given graphs G, H, I, and morphisms G −→ H and G −→ I as depicted ′ n′ in Fig. 4, a pushout is a tuple hJ, I −m→ J, H −→ Ji, in which J is a graph and ′ n′ morphisms I −m→ J and H −→ J satisfy the following conditions: 1. n′ ◦ m = m′ ◦ n, and x y 2. For any graph K with morphisms H −→ K and I −→ K satisfying x ◦ m = z y ◦ n, there exists a unique J −→ K satisfying z ◦ n′ = x and z ◦ m′ = y. m n A transformation rule T , denoted by hP ←− K −→ Ri, consists of graphs m n P , K and R, and injective morphisms K −→ P and K −→ R. P is called the pattern graph (or left-hand side). R is the replacement graph (or right-hand side). K is the correspondence graph (or glue graph) that relates the vertices and edges in the pattern and those in the replacement.
P p I m In order to transform models using graph transformation, it is necessary to categorize vertices and edges of different types. (Recall that three types of vertices and two types of edges are used in Fig. 2.) It is also necessary to take into account other attributes that further differentiate vertices, such as the ones that decide whether a port is input port or output port. Therefore, we let A be a globally defined attribute set, and extend the definition of graph G to be hVG, EG, AGi, where AG : (VG ∪ EG) → 2A is a total function that returns a (possibly empty) set of attributes for each vertex and edge.
Our other definitions in the previous subsection remain unchanged, except that the definition of graph morphism is enhanced next to take into consideration the attributes. We define a subset of attributes U ⊆ A to be unchecked attributes. It contains attributes that need not be directly checked in the extended graph morphisms to be defined below. A subset of unchecked attributes, C ⊆ U , is called criteria. Let B be an auxiliary set that equals 2A × 2A. We require any criterion c ∈ C to be an element in 2B. Given two vertices or edges x ∈ VG ∪EG and y ∈ VH ∪EH , we say that criterion c is satisfied by x matching y if AG(x), AH (y) ∈ c.
We now extend the definition of graph morphism discussed in Sec. 2.2 to become the following. An attributed graph morphism from graph G to H is a graph morphism m : VG → VH satisfying the following additional conditions: 1. for any v ∈ VG,
(a) ∀a ∈ AG(v) \ U . a ∈ AH (m(v)) (b) ∀c ∈ AG(v) ∩ C . AG(v), AH (m(v)) ∈ c 2. for any (v1, v2) ∈ EG, (a) ∀a ∈ AG((v1, v2)) \ U . a ∈ AH ((m(v1), m(v2))) (b) ∀c ∈ AG((v1, v2)) ∩ C . AG((v1, v2)), AH ((m(v1), m(v2))) ∈ c Case (a) of the two conditions requires that all attributes belonging to a vertex or edge in G, except the unchecked ones, be associated with the matched vertex or edge in H. Therefore, the unchecked attributes of the latter form a superset of those of the former. Case (b) of the two conditions ensures that the criteria associated any vertex or edge in G be satisfied by the matching.
Practically, for a transformation depicted in Fig. 5, only the graphs P and R contain vertices and edges with criteria attributes. In particular, we call the criteria in the replacement graph R operations, since they essentially enforce restrictions on the output graph that may be satisfied by performing additional attribute adding or removal operations. (In this discussion, we assume that those criteria in R can be satisfied by adding or removing attributes in the output graph O.)
Notice that because of the criteria in P and R, it may not be possible to apply transformation rule T to input graph I even if it is applicable in the sense that the pattern P matches a subgraph of I. 2.5
The example in Fig. 2 shows a way to represent a model with an attributed graph. In the attributed graph, three special attributes are assigned to the vertices to distinguish their types: Actor (visually represented by big circles), Port (small hollow circles) and Relation (filled dots). Two additional attributes identify the types of the edges: Containment (dashed lines) and Connection (solid lines). The names of the vertices are unchecked attributes that are unique at each level of the hierarchy of a transformation rule. Names at different levels may be identical.
Input Model Transformation
Rule
Model-to-graph
Conversion Model-to-graph
Conversion
Graph Transformation
Graph-to-model
Conversion
Output Model
Using the graph representation, we establish a basic model transformation process as shown in Fig. 6. The inputs to the process consist of an input model and a transformation rule, both specified in the modeling language. (Fig. 1 and Fig. 3 provide examples of both in this language.) The two inputs are then converted into attributed graphs. To convert a model into an attributed graph, a vertex is created for each actor, port or relation, and an edge is created for each connection or containment relation. (We use two reversed edges with the same attributes to simulate an undirected edge in Fig. 2.)
The transformation rule is converted into multiple graphs. Its pattern and replacement contain model fragments and are converted into the P graph and the R graph in Fig. 5. The correspondence table simplifies the specification of the K graph. Its “Pattern” column shows the names of the actors in the pattern. (For clearer presentation, we hide the vertices corresponding to ports and relations as well as all edges.) For a hierarchical transformation rule, the names may contain parts separated by dots, referring to the unique identifiers at different levels. The “Replacement” column shows the names of the corresponding actors in the replacement. There is a one-to-one relationship between entries in both columns. Conceptually the conversion process computes a subgraph of P as K, such that K contains only vertices listed in the “Pattern” column. The one-to-one nature ensures that a subgraph exists in R that is isomorphic to this selection of K.
After the conversion, graph transformation can be applied. The transformation result is converted back into a model for output. 3
Basic transformations are limited in expressiveness. To locate a match in the input model, a subgraph isomorphic problem needs to be solved, which is known to be NP-hard. This complexity restricts the size of patterns that can be used in practice. Furthermore, because a basic transformation is context-free, it can only operate on a subgraph matched by the pattern each time, regardless of the rest of the graph.
To enhance expressiveness, a common practice is to employ an additional mechanism to control multiple applications of basic transformations. In our work, we leverage the heterogeneous models of computation provided by Ptolemy. We allow transformation designers to create higher-order models as compositions of basic transformations. Those basic transformations in the higher-order model operate on models that are considered as first-class objects. The output of a basic transformation can be passed to the next one via its output port. The communication is governed by the model of computation used. We call such a higher-order model a model-based transformation, as opposed to basic transformations that do no involve any control mechanism. 3.1
We consider any basic transformation T as a function FT : G → G, where G is the set of all graph representations of models. For any input graph I ∈ G, if T is applicable to I, FT returns the output graph obtained by applying T to I; otherwise, FT simply returns I. We then define the TransformationRule actor as a pure functional actor that computes FT . It has a single input port and two output ports. The input port accepts actor tokens, which contain models to be transformed. Its first output port sends the transformation results obtained by applying FT to the inputs. Its second output port (visually shown at the bottom of the actor’s icon) produces true or false values, which signify whether the transformation was applicable for those inputs.
When the TransformationRule actor is opened in the Ptolemy II GUI (Graphical User Interface), an interface appears to allow the designer to edit the basic transformation that this actor contains. This interface has a tab for each of the three components, as is shown in Fig. 3. (For better usability, the correspondence table is automatically maintained by the tool unless the designers explicitly specify it.) 3.2
In addition to TransformationRule, we have created other actors in an actor library for model-based transformation.
ModelGenerator is used to generate initial actor tokens. It has different usages. If an input string containing the description of a model in the Modeling Markup Language (MoML) is provided, it parses the string and sends the model via its output port. If only a model name is provided, it creates an empty model with the given name.
ModelCombine accepts multiple input models at each time. It merges those models and outputs a combined model. Suppose the n input models are represented with graphs G1, G2, · · · , Gn, then the output model can be represented with G = hVG, EG, AGi, where VG, EG and AG are the disjoint unions of the vertex sets, edge sets and attribute functions (considered as sets of argument-value pairs) of the input graphs. We take an extra step after the merging to update the name attributes so that they are unique at each level of the resulting model.
ModelView displays the input models in a separate window. It updates the window when a new actor token is received. After displaying the model in the actor token, it sends the token to downstream actors via its output port.
ModelExecutor executes the input models to completion. Inputs can be provided to the models being executed via user-customized input ports of ModelExecutor. The tokens available at those input ports are automatically transmitted to the input ports with the same names of the executed models that have the same names. Outputs from the models are also transmitted to the user-customized output ports.
MoMLGenerator exports the input models in the Modeling Markup Language (MoML). The exported strings can be written into files by FileWriter. 3.3
There is a large variety of applications for model-based transformation. We
sketch some of them here. A concrete example of the model construction
application will be discussed in the next section.
– Model construction. ModelGenerator can be used to generate empty
models, which are first-class objects manipulated by a higher-order model (the
one that contains the ModelGenerator). Arbitrary models can thus be
constructed by modifying empty models with transformations. The constructed
models can be executed by ModelExecutor on the fly, or be stored in files
by MoMLGenerator and FileWriter.
– Model optimization. When appropriate information about model behavior
is provided, model transformation can be used to optimize existing models
while preserving their behavior. One example is to partially evaluate a given
model by eliminating the parts of computation logic that output signals that
can be computed statically. The validity is based on the information about
whether the actors’ outputs are constant, or how actors’ outputs depend on
their inputs. This information may be provided in the actors’ behavioral
interface [
In this section we discuss a parametrized higher-order model that generates a MapReduce model and executes it. Fig. 7 shows part of the hierarchy of this higher-order model. A parameter at the top level, numberOfMachines, defines the preferred number of worker machines, which can be set by the user. For simulation, we use a FileReader to read the documents from disk and to output them in tokens via the upper output port. The lower output port produces true when all documents are sent, or false otherwise. When it outputs false, the document tokens are queued in the buffer for the ModelExecutor’s upper-left input port. When it outputs true, the Switch sends a token to the CreateMapReduce actor, triggering it to generate a MapReduce model in an actor token. (Fig. 1 shows the MapReduce model generated when numberOfMachines equals 5.) The model is then sent to the ModelExecutor for immediate execution. The buffered documents are provided to the model as inputs at its “document” input port, and its outputs to the “result” output port are automatically transmitted to the Display actor connected to the ModelExecutor’s output port. (a) Pattern (empty)
(b) Replacement 1
The CreateMapReduce actor contains an SDF (Synchronous Dataflow) model that controls several TransformationRule actors (each represented with a yolklike icon surrounded by a box). mapCount is defined to be the number of Map machines, and reduceCount is the number of Reduce machines. Fig. 8 shows the transformation rules in the CreateSplit actor. It creates a Split actor and a Merge actor, together with the input ports and output port of the MapReduce model. Its pattern is deliberately made empty so that the transformation rule is applicable to the empty model generated by the ModelGenerator. In Fig. 3, we have shown the transformation rule in the LinkMapAndReduce actor. It connects the ports of an arbitrary Map actor and an arbitrary Reduce actor, with a constraint to make sure that no duplicated connections are made in multiple applications of the same transformation rule. We set a special parameter, which is not shown in the interface, so that the transformation is applied exactly (mapCount × reduceCount) times for each input model, so that all the Map actors and Reduce actors in it are interconnected.
This example shows how we use model transformation as a tool to construct a complex model. The size of the dynamically generated model is parametrizable with an integer parameter, and has no impact on the size of the higher-order model that the designer manually creates. Each TransformationRule actor can be separately designed, documented and maintained. It can also be parametrized and reused to construct other models. 5
Model transformation has been under active research in recent years. In
recognition of the public interest, the OMG (Object Management Group) has issued
a request for proposal (RFP) on MOF (Meta-Object Facility) QVT (Query /
Views / Transformations) to seek a standardized approach to model
transformation [
Besides our model transformation tool developed in the Ptolemy II
framework, existing tools include AGG [
We present our approach to higher-order model composition based on model transformation. We provide a formal definition of graph transformation, which serves as the basis of our model transformation technique. We show that basic transformations can be used as actors in a hierarchical heterogeneous models. Our approach makes it easy to create complex transformations as composition of basic ones. We provide a word-counting model designed using the MapReduce programming pattern as a concrete example.