VIATRA/DSE/UserGuide/BPMNExample

The BPMN example of the VIATRA-DSE framework

This page gives an introduction to the usage of the VIATRA-DSE framework based on the BPMN domain.

Description of the problem

As an example a simplified business process of a web shop is presented, see the image below. After authorization (i.e. the user is signed in) the request can be either about purchasing (e.g. editing user information, paying with a bank card, etc.) or about browsing items. In the later case recommendations are calculated in parallel with fetching item data and logging. All tasks need a particular resource either a web server, a SQL or a NoSQL database.

Resources can have multiple variants, which have different characteristics. For example the SQL and the NoSQL resources hava a second variant which perform better (i.e. they have shorter execution time) but has extra costs:

Resource Type	Variant 1 (factor/cost)	Variant 2 (factor/cost)
Web server	1 / 1	-
SQL	1 / 3	0.75 / 5
NoSQL	1 / 3	0.75 / 5

The problem is to optimize the business process on response time, resource utilization and cost by assigning resource variants to each task and create enough resource instances for the variants' pools. Furthermore the business process can suffer from bad design which could pull back the performance of the system. For example, the Fetch data and Log tasks could be executed in parallel.

However, optimizing a process with respect to multiple objectives (e.g. response time, resource usage, etc.) is a time consuming and erroneous task. Running simulations with different parameters is required to find an optimal solution, while evaluating results to identify a promising configuration is essential. In addition, contradicting objectives may be present (e.g. increasing resource utilization can lead to reduced throughput) and design flaws could prevent better performance. VIATRA-DSE can automate the process to go through different design candidates and find the optimal one.

Modeling the problem

This section gives an idea how to model a design space exploration problem and prepare it for using the VIATRA-DSE framework.

Domain model

The first step it to model the domain in the Eclipse Modeling Framwork by creating a metamodel. A simplified metamodel of the BPMN domain can be found in the following figure. There is an existing EMF metamodel of the BPMN domain which is compatible with the OMG standard (link) but we wanted to keep it simple.

The second step is to define the instance model (i.e. any business process workflow), the previously shown web shop example with the resource variants can be an ideal example for that. This will be the initial model of the exploration process.

Transformation rules

The transformation rules specify how the exploration process can modify the initial model. For this example four rules is specified, namely:

• Assign a resource variant to a task (priority: 3)
  • Condition: a task without resource variant and a resource variant of the task's required resource type
  • Operation: assign the resource variant to the task
• Create resource instance (priority: 2)
  • Condition: a resource variant
  • Operation:: create a resource instance for the resource variant
• Make a sequential task execution parallel (priority: 1)
  • Condition: two sequential task, the first has exactly one out flow, the second has exactly one in flow
  • Operation: create two parallel gateway, organize flows
• Make a parallel task execution sequential (priority: 1)
  • Condition: two parallel task, which are between two gateways; the gateways don't have any more tasks between them
  • Operation: delete the two gateway, organize flows

Priorities of the rules (if used by the exploration strategy) can be found in brackets.

Objectives

There are three main objectives and a fourth objective is defined to help the traversal strategies:

• Average response time: The BPMN model is simulated by sending tokens through the system. It will be defined as a hard objective by checking if the simulation is executable and if not it won't be satisfied. In this case it will return an "infinite" number as this objective is to minimize. It is measured in millisecond.
• Minimum resource utilization: Along the simulation utilization of the resource instances is also calculated averaged to resource variants and normalized to a number between 0 and 1. The minimum of this number will give the fitness value of this objective, which should be maximized.
• Cost: Creating resource instances have costs depending on the resource type variant (see the table above) which should be minimized.
• Guidance objective: This soft objective will guide the exploration to a valid solution (so it can be simulated) by checking for unassigned tasks and absence of required resource instances. The fitness value will be calculated by the following expression: (unassignedTasks*10) + (absenceOfResourceInstance*1), which should be minimized (to 0). Note that unassigned tasks have a higher weight as assigning the tasks to a variant is more important than creating resource instances.

Global constraints

To prevent the exploration to create an unrequired resource instance a global constraint can be defined for it: the exploration strategy should backtrack if the actual model state dissatisfies this global constraint. Note, that this can be also modeled by adding it to the guidance objective (e.g. ..+unrequiredResourceInstance*100), but in this case using a global constraint is a more sophisticated approach. The reason is that we would like to avoid unrequired resources entirely in the model, while assigning tasks is a real objective of the exploration.

Exploration strategies

In this example all of the currently available exploration strategies will be shown:

• Breath first search - explores the design space systematically until it founds a solution which satisfies the hard objective(s).
• Depth first search - explores the design space systematically with a depth limit, stops if the hard objective is satisfied.
• Fixed priority search - explores the design space as the depth first search, but uses the priorities assigned to the rules: in a given state it tries the rule activations only with the highest priority.
• Hill climbing search - tries all the rule activations from the current state and chooses the best one based on the objectives (chooses randomly if there are more than one). Stops if the actual state is better than all of the neighbours.

Using the VIATRA-DSE framework

Download the example

The VIATRA project has a separate repository on Eclipse for the examples. The BPMN example projects can be found under the dse/bpmn folder after cloning the git repository:

• git://git.eclipse.org/gitroot/viatra/org.eclipse.viatra.examples.git
• ssh://git.eclipse.org/gitroot/viatra/org.eclipse.viatra.examples.git
• http://git.eclipse.org/gitroot/viatra/org.eclipse.viatra.examples.git
• Browse: http://git.eclipse.org/c/viatra/org.eclipse.viatra.examples.git/

Structure of the example

This example is structured into three projects:

• org.eclipse.viatra.dse.examples.bpmn.model
• org.eclipse.viatra.dse.examples.bpmn.patterns
• org.eclipse.viatra.dse.examples.bpmn.dse

The model project contains the EMF metamodel: the .ecore, .aird, .genmodel files and the generated code.

The patterns project contains the IncQuery patterns (.eiq file) and the generated code.

The dse project contains all of the manual code for the dseign space exploration.

The dse project contains the following packages:

• .problems
  • SimplifiedBpmnBuilder.java is a helper class for creating BPMN instance models.
  • BpmnProblems.java contains a few example instance models, such as the webshop business process.
  • BpmnProblemSaver.java is helper class to save the example instance models into .sbpmn files.
• .simutalor package contains code for the simulation of any bpmn instance model.
• .serializer package contains code for the state coder.
• .rules package contains the transformation rule definitions in four classes.
• .objectives contains two objectives: response time and resource utilization.
• .dse contains a BpmnExamples class with the definition of the DSE problem.

Running the example

To run the example, find the org.eclipse.viatra.dse.examples.bpmn.dse.BpmnExample class and run it as JUnit plug-in test'. Please see this link, if you are unfamiliar with this run configuration: VIATRA/DSE/UserGuide/API#Run_configuration

References

Text and figures from András Szabolcs Nagy. Parallel algorithms in design space exploration. Master's thesis, Budapest University of Technology and Economics, Budapest, 12/2015