Open access peer-reviewed chapter

Modeling and Simulation of Task Allocation with Colored Petri Nets

By Mildreth Alcaraz-Mejia, Raul Campos-Rodriguez and Marco Caballero-Gutierrez

Submitted: November 7th 2016Reviewed: February 17th 2017Published: June 7th 2017

DOI: 10.5772/67950

Downloaded: 976

Abstract

The task allocation problem is a key element in the solution of several applications from different engineering fields. With the explosion of the amount of information produced by the today Internet-connected solutions, scheduling techniques for the allocation of tasks relying on grids, clusters of computers, or in the cloud computing, is at the core of efficient solutions. The task allocation is an important problem within some branch of the computer sciences and operations research, where it is usually modeled as an optimization of a combinatorial problem with the inconvenience of a state explosion problem. This chapter proposes the modeling of the task allocation problem by the use of Colored Petri nets. The proposed methodology allows the construction of compact models for task scheduling problems. Moreover, a simulation process is possible within the constructed model, which allows the study of some performance aspects of the task allocation problem before any implementation stage.

Keywords

  • colored Petri nets
  • task allocation problem
  • modeling and simulation
  • distributed computing

1. Introduction

The services provided by Internet-based modern applications require the execution of massively parallel processes in order to produce time-effective information for different requirements. The processing of these “Big Data” is very computing, demanding in almost all of the cases. Thus, vast server farms installed over the world are ready to process the requests from different users. The digital data available in the web are huge and diverse, therefore complex, and in a continuous growth rate.

Nowadays, most of the queries on Internet are produced from smartphones and personal computers. However, the data traffic on web is expected to grow in an exponential rate, as the technology related to the Internet of Things (IoT) allows the connection of other devices from the houses, smart warehouses, automated driving cars, machinery from the agriculture, UAV’s for goods delivering, or smart cities, to mention a few. In order to cope with the challenges related to a massive number of connected devices, new ways of computing emerged. Most of them are based on parallel and distributed computing, such as clusters, grids, and cloud computing paradigms.

At the core of these paradigms are the tasks scheduling and resources allocation problems. Adaptations of theory, methods, algorithms, tools, and others are arising in order to cope with the increasing number of cores per processor, as well as with the interconnected and heterogeneous computers, considering that, in many cases, those computing architectures are connected through the Internet. The tasks scheduling and resources allocation were well studied in the context of architectures with a relatively small number of processors. One of the fundamental concerns deals with designing algorithms for an efficiently allocation of the tasks among all the available processes and resources.

The answer to this question may lead to a hard work, since, in the worst case, it involves an exponential number of possible solutions [1]. Thus, a simulation process, for scenarios with a big number of computing elements, or cores, as in cloud and grid computing, is a valuable tool. In this context, the modeling and simulation are disciplines widely used to obtain feedback and statistics information, to improve associated applications and algorithms. Through experimentation in simulators, a fast prototyping process allows performance evaluation and parameter tuning for different workload conditions. To perform an efficient simulation process, a suitable modeling method is required. The Petri nets (PN’s) and its extension, such as colored PN (CPN), have been considered as an efficient modeling technique for concurrent and distributed systems.

The simulation and implementation stages of scheduling and resource allocation problems in distributed systems have been successfully addressed [29]. Moreover, variants of PN’s are used for modeling and simulation of other distributed concepts related to cloud services and computing [916], as well as in the field of the diagnosis of discrete event systems [1719], reconfiguration [2024], fuzzy inference [25] or identification [26].

This work proposes the modeling of the task allocation problem by the use of a methodology based on CPN’s. It also shows how to simulate these models in order to obtain relevant information for the design process. To illustrate the techniques, this work considers a tree structure and supposes that the set of tasks and the set of processes are fixed and defined before the task allocation is performed as in Ref. [27]. The proposed CPN modeling method represents the behavior of a set of processors, or working threads, that traverse a tree structure from the root to a single leaf in order to acquire a task. The processes decide what route to take at each node of the tree structure, by using a decision function. Then, it routes the tree backwards updating some global variables that serves as inter-process communication mechanism.

The proposed method allows obtaining a CPN, which is a compact representation of the problem, and at the same time, it allows simulating its behavior and obtaining performance graphics. The colored tokens represent the processes, tasks, and other variables of interest in the problem. A decision function is attached to some transitions of the CPN model. This function influences the behavior of the process or thread. Due to the graphical nature of the CPN, in addition to the mathematical fundamentals, this methodology provides a great framework to simulate and analyze the task allocation problem, avoiding the state space explosion, and thus, having a compact representation of a complex behavior. The flexibility of the modeling framework allows simulating different scenarios, using different decision functions, as well as varying the number of initial processes or threads. Additionally, the Petri Net model can be easily extended to simulate a wider number of tasks.

The rest of this chapter includes a background of the task allocation and several techniques that have been used for addressing this problem. The modeling framework based on colored Petri nets is next presented and the modeling methodology is detailed. This methodology highlights the main aspects of the task allocation problem, such as the concepts of task and process, as well as the balancing policies and how to capture them by CPN blocks. The simulation of the obtained CPN models is then presented and discussed. Some performance charts are provided. The charts allow the study of key aspects of task allocation problem such as the effective work done by a processor, the task contention, the effects of different balancing policies, to mention a few. With this information, the scientists and engineers are able to study different aspects of the problem prior any implementation stage in a particular field of interest.

2. Task allocation problem

Task allocation problem has been addressed for several purposes and using different techniques. Analytic solutions are in some cases prohibitive since they require the analysis of an exponential number of possible solutions. Thus, some designs use probabilistic approaches to produce good solutions in a reasonable time. Jevtić et al. [28] present a distributed bee’s algorithm for static task allocation inspired on the behavior of a colony of bees and based on the optimization of a cost function. They also show results using the Arena simulator. Delle Fave et al. [29] introduced a decentralized optimization for static task assignment based on a constrained utility function, firstly evaluated by simulations. Johnson et al. [30] state a distributed multi-agent algorithm for static multi-task allocation as an optimization problem based on mixed-integer programming. They also provide some results of Monte Carlo simulation. Zhao-Pin et al. [31] introduced a distributed and static task allocation algorithm for multi-agents that learn how to determine by themselves what tasks should realize and how to form coalitions for cooperation, via their proposed profit-sharing learning mechanism. Macarthur et al. [32] introduced a dynamic and distributed algorithm for multi-agent task allocation problems, based on fast-max-sum algorithm combined with a branch-and-bound technique, in order to reduce the execution time in the allocation of task to its respective agent. Alistarh et al. [27, 33] present a decentralized task allocation, static and dynamic, based on to-do trees, where decisions on every inner node are based on a probability function.

One of these most used techniques, due to its simplicity of implementation, is based on a rooted tree structure that the process traverses in order to acquire a task [7, 8]. The tree structure allows to the working processes for executing a non-deterministic behavior, which is quite suitable for real environments. Typically, in these tree structures, every reference to a task is allocated on the leaves. Thus, every internal vertex allows to a working process taking a decision based on a function over the number of tasks in every leaf of the subtrees from each child of the current vertex. Hence, the decision function, which could be a simple deterministic algorithm, or a sophisticated statistical or stochastic procedure, is a key element for which a process traverses through the tree structure, in this kind of task allocation techniques.

Figure 1 shows a binary tree that represents a scheduling problem where eight tasks have to be attended. The height of the tree is H=log2(8)=3, where the level of v2,2is 2, the vertex v1,0is said to be parent, or ancestor, of v2,0and v2,1, and the latter two are said to be children, or descendant, of v1,0. The vertex v0,0is the root, and every vertex is internal except for all of the level 3, i.e., v3,xwith x[0,7], which are known as leafs of the tree. The tree formed by the vertexes v2,1,v3,2,v3,3and the corresponding edges that connects them, is a subtree with v2,1as a root.

Figure 1.

A direct rooted full binary tree.

From the graph theory point of view, a DT is an acyclic graph in which a unique path connects every node to others, represented in a top-to-bottom fashion, where the root, i.e., initial node, is plotted at the top of the tree. The DT is a binary decision tree (BDT) if at every node is considered at most two possible decisions, as shown in Figure 1. For more information on trees see Ref. [34].

2.1. Task scheduling with DT

By using a tree structure like the one depicted in Figure 1, the task allocation algorithm is relatively simple. Each working process shares the tree structure and iterates in an infinite loop, trying to acquire a new task to execute, which is located at the leafs of the tree. Each working process starts at the root node of the tree and decides whether to go to the left or the right child node. The process knows an approximation of the total pending tasks at the left and right subtrees at every step. For example, in Figure 1, each working thread knows that at the beginning of the scheduling process, at the root node, that there exist four pending tasks at the left subtree and four pending tasks at the right one. Then, at every stage, the processes decide to traverse to the left or right in an asynchronous fashion. The total number of pending tasks is backward updated from the lower nodes to the uppers as the tasks are successfully executed by the threads. Notice that, the number of pending tasks at the left or right subtree is an approximation since this number may be not updated yet.

Since the processes are asynchronous among them, it is possible that they arrive to the leaf nodes that may occur at different rates. Every time that a process reaches a leaf, it asks for the execution of the task. If such a task is free, then the process blocks this task, executes the activity, and marks the task as executed. Then, it goes back to the root node to seek for a new task to execute, while the information of the remaining tasks is backward updated from the leaf to the root node. It is possible that when a process reaches a leaf node, the corresponding task was already executed by another process. In this case, the process goes back to the root node, and this miss is counted to measure the effectiveness of the algorithms.

r<xx+yE1

In Eq. (1), it represented a decision rule that a working process may execute at every level of the BDT. Let x be the total number of pending tasks in the left subtree and y be the total number of pending tasks in the right subtree, while r is a random number. Thus, the probability to go to the left subtree in a flip coin is given by r. As greater the ratio, it is greater the probability to go to the left child of the current node. One of the main objectives of this work is to measure the effectiveness of a decision rule as Eq. (1) by means of a simulation process.

3. Colored Petri nets

PN’s are a modeling framework that combines a graphical visualization with a mathematical model [35]. The CPN’s are one of the extensions to PN’s [9, 17, 3542], which allow the construction of compact representations of big models. In this section, basic notions of CPN are presented.

The main characteristic that differentiates CPN from other type of nets resides in the token definition. In a CPN, the tokens can stand for complex data besides of a single value, such as an integer, a real, Boolean or strings. This characteristic allows for the representation of elaborated data types, similar to those used by high-level programming languages. This ability exploits the multi-set cardinality to construct compact models that otherwise are in the power set of the colored tokens. The formal definition of a CPN is as follows [35].

Definition 1. A Colored Petri Net (CPN) is a tuple

  N=P,T,Pre,Post,B,F,Cp,Ctwhere its elements are described as:

  • P is a finite set of places of N, with m=|P|,

  • T is a finite set of transitions of N, such that TP=, with n=|T|,

  • B is finite set of color classes,

  • F is a set of conditions,

  • Cp:PBis the color domain mapping,

  • Ct:TFis a conditional color mapping, and

  • Pre,PostS|P|×|T|are matrices representing the input and output incidence matrices of N, such that Pre[p,t]:Ct(t)Bag(Cp(p))and Post[p,t]:Ct(t)Bag(Cp(p))are mappings for every pair (p,t)P×T; where Bag(S)=b(si)for all siS, such that b(si)=siS.

The incidence matrix is C=PostPre. The mapping given by Pre[p,t]:Ct(t)Bag(Cp(p)), defines for each conditional color mapping f of t (i.e. fi Ct(t)), the token bag to be removed from p, in the occurrence of t, under color condition f. In the same way, Post[p,t](f)specifies the token bag to be added to p, in the occurrence of t, under color condition f.

  1. Definition 2. A marking M of a CPN Nis a vector of size m=|P|, such that M(p)Bag(Cp(p))for every pP. The vector M0denotes the initial marking of the net Nand the pair (N,M0)is known as a CPN System.

  2. Definition 3. A transition in a CPN System (N,M0)is said to be enabled for a color condition f in a marking M iff MPre[,t](f), denoted as Mt,f.

  3. Definition 4. The marking evolution w.r.t a color condition f is given by M=M+Post[,t](f)Pre[,t](f)= M+C[,t](f), denoted by Mt,fM'. For a general color condition, it is denoted as MtM'where fis implicit in a context.

The net in Figure 2 represents a very simple CPN System (N,M0)where:

Figure 2.

A CPN example.

  • P={p1,p2,p3},

  • T={t1,t2},

  • B=or, where o={o1,o2}and r={r1,r2}are variables,

  • F={f1,f2},

  • Cp(p1)=Cp(p2)=o, Cp(p3)=r,

  • Ct(t1)=f1, Ct(t2)=f2,

  • Preand Postare as depicted, and

  • M0=[{o1,o2},,{r1,r2}]', where o1=1, o2=2, r1=a, r2=b.

Notice that, at the initial condition, M0  Pre[,t1](f1). That is [{o1,o2},,{r1,r2}]'[{o1,o2},,{r1,r2}]:{(o1,r1)(o2,r2)}, thus, t1 can be fired for any color binding {(o1,r2)(o2,r1)}due to the condition in f1. Suppose that, t1 fires for color condition f1 with (o2,r1), then M0t1,(o2,r1)M1, with M1=[{o1},{o2},{r2}]', where o1=1, o2=2, r2=b, by Post[,t1](f1)={(s1)}as detailed in the figure. Now, M1t1,(o1,r2)and M1t2,(o2), in such a way, that if t2is fired, then M1t2,(o2)M2, with M2=[{o1,o2},,{r1,r2}]', where o1=1, o2=4, r1=a, r2=b. However, if t1is fired from M1for the color condition (o1,r2), then M1t1,(o1,r2)M3, with M3=[,{o1,o2},], where o1=1, o2=2.

Roughly speaking, the CPN binds the even number in p1to the character “a” in p3and the odd number to character “b.” This is defined by the guard function f1attached to t1. The function s1discards the relement of the token bound to the firing of t1, while the firing of t2adds two to the oelement of the token and recovers the r element that is put back to the place p3. Thus, the tones in p1changes to o1=1,3,5,and o2=2,4,6,, while the characters “a” and “b” in p3remain the same all the time. The “R” in the place p3stands for “resources,” which is the function intended for the characters in this CPN model.

Notice that, the bindings (o1,r1)and (o2,r2)are discarded by the function f1. This is one of the advantages of the CPN modeling tool, since otherwise, the combinatorial explosion of possible bindings turns untreatable under some circumstances that typically arises in real applications. For more information about the CPN modeling formalism and related analysis and tools, see Ref. [36].

4. Modeling and simulation of task scheduling

The construction of a generalized model for a BDT based on CPN considers ddifferent features and nTclasses. The procedure includes the identification of the transitions and places of the model, the arcs and its labeling, as well as the multi-set of colored tokens. The remaining of this section is devoted to detail the methodology and illustrate it by short examples.

4.1. Structure of the task allocation as a CPN

Consider the following steps for the construction of a CPN model that captures the structure of a BDT. It is supposed that the BDT is a full binary tree with a complete set of tasks represented by a structure called Task Array. Thus, the size of the Task Array is 2H, where the height of the tree is H.

Step 1. Labeling nodes in the BDT

Firstly, suppose that the DT is a full binary tree. Then, assign “0” to every left edge and “1” to every right edge. This labeling represents the result of the flip coin in the task allocation procedure of a BDT discussed in the previous section.

After that, some information is used to label every node with a pair (depth,position), where depthis the level of the node, and positionis the corresponding position from left to right. For example, consider the root node (0,0)in the section of the BDT depicted in Figure 3. It is a fraction of the tree of height H=3of Figure 1. Then, to label the children of the root node proceed as follows:

Figure 3.

Relation BDT and CPN.

  • Let be depth=depthoftheparent+1and position=2*positionoftheparent+h, with h=0if this node is the left child, h=1 otherwise.

Therefore, the label of the left child is (depth=0+1,position=0*2+0)=(1,0), while the label of the right child is (depth=0+1,position=0*2+1)=(1,1).

Step 2. Building the CPN System

Let (N,M0)be a CPN System for a dynamic binary decision tree for nTclasses and dfeatures with N=P,T,Pre,Post,B,F,Cp,Ctconstructed as follows:

  • P=POPRPA, where POis the set of places with assigned tokens of type O, PRis the set of places with assigned tokens of type R, PAis the place with assigned tokens of type A. |PO|=2(H+1), |PR|=Hand |PA|=1, where H=log2nT. Places of type O represent every level from the root to the leaves, forward, and backwards, i.e., a token in one of those place contains the information of pos, depth, val. Places of type R represent the state of every subtree from every node at that level, i.e., the value of the datafunction for every node of the same level given by posand depth. Place of type A represent the Task Array state, i.e., the information of the availability of the task.

  • T is the set of transitions with |T|=|PO|.

  • B=ora,for o=oi, r=rj, and a=alwhere oi=depthi,posi,vali,successi, rj=depthj,posj,dataj, al=posl,readylfor i[1,d], j[1,2H+12], and l[1,nT], with depthi, posi, vali,successi, dataj, existlvariables and depthj,posj, poslconstants.

  • F={f1,f2,f3,f4}, such that f1:(oi,rj,rk)|depthi+1=depthj=depthkposi*2=posjposi*2+1=posk, f2:(oi,rj)|depthi=depthjposi=posj, f3:(oi,aj)|posi=posj, f4:(oj).

  • Cp(pi)=ofor all i[1,|PO|], Cp(pi)=rfor all i[|PO|+1,|P|]and Cp(pi)=afor i=2(H+1)+H+1.

  • Ct(ti)=f1for i[1,H], Ct(ti)=f2for i[H+2,|PO|1], Ct(ti)=f3for i=H+1and i=|PO|+1.

  • Pre[pi,ti](f1)=si1|f1, for i[1,H], Pre[pi,ti](f2)=si1|f2, for i[H+2,|PO|1], Pre[pi,ti](f3)=si1|f3, for i=H+1, Pre[pi,ti](f3)=si1|f4, for i=|PO|+1, Pre[pi,tj](f3)=qi1|f3, for i=|PO|+|PR|+1, j=H+1, Pre[pu+i,ti](f1)=2ri1|f1, for i[1,H], Pre[pu+i,tui](f2)=2ri2|f2, for i[1,H], where:

    • si1:oo, such that si1(depthi,posi,vali,successi)=depthi,posi,vali,successi.

    • qi1:aa, such that i1(posl,existl)=(posl,existl).

    • ri1:r×rr, such that ri1(depthj,posj,dataj,depthk,posk,datak)=depthj,posj,datajdepthk,posk,datak.

    • ri2:rr, such that ri2(depthj,posj,dataj)=depthj,posj,dataj.

  • Post[pi+1,ti](f1)=so1|f1, for i[1,H], Post[pi+1,ti](f2)=so2|f2, for i[H+2,|PO|1], Post[pi+1,ti](f3)=so3|f3, for i=H+1, Post[p1,ti](f3)=so4|f4, for i=|PO|, Post[pi,tj](f3)=qo1|f3, for i=|PO|+|PR|+1, j=H+1Post[pu+i,ti](f1)=ro1, for i[1,H], Post[pu+i,tui](f2)=ro2, for i[1,H], where:

    • so1:oo, such that so1(depthi,posi,vali,successi)=depthi+1,posi*2+hi,vali+(hi)*2Hdepthi+1,successi, withhi=0 ifαholds,otherwise 1. αis a decision function.

    • so2:oo, such that so2(depthi,posi,vali,successi)=depthi1,posi2,vali,successi.

    • so3:oo, such that so3(depthi,posi,vali,successi)=depthi,posi,vali,successi=1ifExist(posi,al)=1 otherwise 0, where Exist(posi,al)returns 1 if for a color class al=posl,existlwith posl=posi, existl=1, otherwise 0.

    • so4:oo, such that so4(depthi,posi,vali,successi)=0,0,0,0,

    • qo1:aa, such that qo1(posl,existl)=(posl,existl=0 ifExist(posl,al)=1,otherwise1).

    • ro1:r×rr, such that ro1(depthj,posj,dataj,depthk,posk,datak)=depthj,posj,datajdepthk,posk,datak.

    • ro2:rr, such that ro2(depthj,posj,dataj)=depthj,posj,dataj1 ifsuccessi=1,otherwisedataj.

  • The initial marking, assuming that the Task Array is initially full, is M0defined as follows:

    • M0[1]={o1,,od}, where oi=depthi=0,posi=0,vali=0,successi=0=0,0,0,0for i[1,d].

    • M0[|PO|+i]=i=1Hj=02i1r2i2+j=i,j,2Hiassuming that the Task Array is initially full, as mentioned.

    • M0[2(H+1)+H+1]=i=1nTaiwhere ai=posi=i,existi=1.

    • M0[i]=for i[2,|PO|].

Figure 4 shows the relation of the tree structure with the proposed CPN as stated by the previous definition. Observe that places of type O represent every level from the root to the leaves, forward, and backwards, i.e., a token in one of those place contains the information of pos, depth, and val. Places of type R represent the state of every subtree from every node at that level, i.e., the value of the datafunction for every node of the same level given by posand depth. Place of type A represents the Task Array state, i.e., the information of the availability of the task.

Figure 4.

DS CPN with nT=8.

4.2. Dynamics of the task allocation as a CPN

Typically, in these tree structures, every reference to a task is allocated on the leaves. Thus, every internal vertex allows to a working process taking a decision based on a function over the number of tasks in every leaf of the subtrees from each child of the current vertex. Hence, the decision function, which could be a simple deterministic algorithm, or a sophisticated statistical or stochastic procedure, is a key element for which a process traverses through the tree structure, in this kind of allocation techniques. The following definitions allow capturing these dynamics aspects of the task allocation based on a BDT.

  1. Definition 5. The posis a position function defined from a set of vertexes Vof a tree Tto the set of natural numbers Nas pos:VN, such that pos(v)=j,where jis the numeric position of vertex vwith respect to all the vertexes in the same level and counting from left to right.

  2. Definition 6. The depthis a function defined from a set of vertexes Vof a tree Tto the set of natural numbers Nas depth:VN, such that depth(v)=#edgesfrom the root node to v.

Notice that, in Figure 2, the identification of a vertex vis given by vi,jwhere i=depth(v)and j=pos(v).

  1. Definition 7. The wis a weight function defined from the set of edges Eof a tree Tto the set containing 0 and 1 as w:E{0,1},such that w(e)=0if e connects a parent vertex to its left child, and 1 if it connects to its right child. Let consider a vertex vof a tree Tdenoted as vi,jsuch that i=depth(v)and j=pos(v). Then, for vi,xparent of left child vj,yand right child vj,z, with their respective edges ei,j,yand ei,j,z, with y<z, by definition of depth, then w(ei,j,y)=0and w(ei,j,z)=1.

Notice that, the weight function wprovides a zero for an edge connecting a father with its left child and a one for the edge connecting it with the right child. In the modeling methodology here introduced, it is assumed that there exists a data structure called Task Array, which may have a reference to a task, if it is initially inserted, and the task has not been taken yet. This Task Array is mapped to the location of the leaves of a tree of height Hfrom left to right, i.e., the array has a capacity for referencing a maximum of The quaternion semi-wideltasks. Figure 1 shows a tree of height 3, with 8 leaves that are associated with the location in the Task Array, where references to task are T0,T1,T7. Accordingly, the following functions are defined.

  1. Definition 8. The datafunction is defined from the set of vertexes Vof a tree Tto the set of natural numbers Nas data:VN, where data(v)=#of leaves in the subtree of root vwith a task ready to be taken.

  2. Definition 9. The parentis a function defined from the set of vertexes of a tree Tto itself as parent:VV, such that parent(v)=y, if vis child of y.

  3. Definition 10. The valis a recursive function defined from the set of vertexes Vof a tree Tof height H, to the set of natural numbers Nas val:VN, such that:

    • (Base): val(v0,0)=0.

    • (Induction): val(vi,j)=val(parent(vi,j))+w(epos(parent(vi,j),depth(vi,j),j)*2Hi, for every pair (i,j), where 1 i  H, 0j<2i.

In Figure 2, for example, val(v)is shown in the left of every vertex vas val(v)/, e.g., val(v2,3)=val(parent(v2,3))+w(epos(parent(v2,3),depth(v2,3),3)*232=val(v1,1)+w(epos(v1,1),2,3)*21=val(parent(v1,1))+w(epos(parent(v1,1),depth(v1,1),1)*231+ w(epos(v1,1),2,3)*21=val(v0,0)+=0+w(e0,1,1)*4+w(e1,2,3)*2=0+1*4+1*2=6.

Observe that function valgenerates the value of a node based on the value of his parent. Notice that, there are 8 leaves in level 3, and then, every node value is exactly one entry in the Task Array. For example, the value 4/at v3,5points to the entry T4. Now, consider the nodes in level 2, which are 4, exactly the half of those at level 3. Every vertex at this level, points to the first entry in a range of 2, i.e., v2,0has a value of 0, v2,1 and has a value of 2. Thus, every vertex at level 1, points to the first entry of the two partitions of the Task Array, and therefore, v0,0points to the first entry of the whole of the Task Array.

For illustration purposes, suppose that there is one node with two threads and eight tasks to be executed. Accordingly, d=2and nT=8. The CPN System (N,M0)for modeling this problem is shown in Figure 4.

Notice that accordingly to the proposed method, a full binary tree is obtained when nT=2nfor some n, since, in this case, H=log2nTis exactly equal to log2nT. In the particular example, H=3, since nT=23=8. Then, |PO|=2(H+1)=8, with PO={p1,p2,,p8}; |PR|=H=3, with PR={p9,p10,p11}; |PA|=1with PA={p12}; |T|=|PO|=8, with T={t1,t2,,t8}; o={o1,o2}since d=2; r={r1,r2,,r14}, since 2H+12=232=14, and a={a1,a2,,a8}.

The following functions complement the CPN model:

  • oi=depthi,posi,vali,successi=0,0,0,0, for i{1,2}. This marking represents the current state of every process, i.e., at the beginning, processes are at root node v0,0with a value 0. Successbeing 0 means that no task has been assigned to the current process.

  • rj=depthj,posj,dataj, such that j[1,|r|], where: r1=1,0,4, r2=1,1,4, r3=2,0,2, r4=2,1,2, r5=2,2,2, r6=2,3,2, r7=3,0,1, r8=3,1,1, r9=3,2,1, r10=3,3,1, r11=3,4,1, r12=3,5,1, r13=3,6,1, r14=3,7,1. These markings provide the information about the dataavailable for every subtree constructed from the node identified as vdepth,pos.

  • al=posl,tyl, such that l[1,nT], where: a1=1,1, a2=2,1, a3=3,1, a4=4,1, a5=5,1, a6=6,1, a7=7,1, a8=8,1. These markings provide the information about the availability of the task located at pos, i.e., ty=1if the task is available, 0 otherwise.

The color mapping is Cp(pk)=ofor k[1,8], Cp(pk)=rfor k[9,11]and Cp(p12)=a. That is, the places p1,,p8accept tokens of type O, the places p9,p10,p11accept tokens of type R, and p12accept tokens of type A. The conditional color mapping is Ct(tk)=f1for k[1,3], Ct(tk)=f2for k[5,7], and Ct(tk)=f3for k=4and k=9. The Pre- and Post matrices for the net of this example are shown in Figure 5.

Figure 5.

Pre and postmatrices for CPN DS nT=8.

Thus, Figure 4 represents a CPN that captures the structure of a BDT and the behavior of the working threads over the tree of height  H=log2nT=log28=3. They represents the places and transitions for the traveling from the root down to a leaf, and the reverse way from the leaf up to the root, on the left and right side of the CPN, respectively. Additionally, the central places, marked as “R,” represent the “resources” in the system, i.e., the shared memory registers and the tasks.

Consider an initial token in place p1=0,0,0,0as described by the initial marking M0. Now, the binding for t1requires two tokens from p9, besides one initial token in p1, subject to conditions given by f1:(oi,rj,rk)|depthi+1=depthj=depthkposi*2=posjposi*2+1=posk. Since in this case oi=o1=pos1=0,depht1=0, val1=0,success1=0due to si1, then the required tokens from p9are rj=r1=depth1=0,pos1=1,data1=2H1=4and rk=r2=depth2=1,pos2=1,data2=231=4, where data1=data2=4, assuming that the Task Array is full of tasks to be attended. Thus, the output of t1due to so1is o1=depth1=depth1+1,pos1=pos1*2+h=1, val1+h*22=4,success1=0=1,1,4,0, assuming h=1.

The sketches of CPN in Figure 6 show the three main marking evolutions in the CPN subject to the binding functions f1,f2,f3. The marking evolution subject to f1from the current state is shown in (a). In (b), the tokens oi,rj,rkare taken by the depicted transition, since f1:(oi,rj,rk)|depthi+1=depthj=depthkposi*2=posjposi*2+1=posk, then oi=<1,1,0,0>,rj=<2,2,2>,rk=<2,3,2>.In (c), the transition has fired, then o1=<2,3,6,0>, since so1(depthi,posi,vali,successi)=depthi+1,posi*2+hi,vali+(hi)*2Hdepthi+1,successiassuming that hi=1. The tokens rj,rkremain the same, since success=0. In (d), the marking evolution subject to f3from the current marking <3,6,6,0>is updated to the marking <3,6,6,1>as shown in (f), since the task reference represented by the marking <6,1>is available as shown in (e). Notice that, this marking is updated to <6,0>as shown in (f), as expected. In (g), the input state of the transitions subject to f2is represented with the marking <3,6,6,1>. Then, it is binding by f2with the token <3,6,1>, as illustrated in (h). Thus, the input token <3,6,6,1>is updated to <2,3,6,1>by so2, as well as, <3,6,1>is updated to <3,6,0>by ro2, as shown in the section (i) of the figure.

Figure 6.

Binding and firing of a CPN transition.

One of the main advantages of modeling the task allocation problem by using CPN’s is the possibility of varying the parameters during the simulation process, as well as the flexibility of the net structure in order to cope with a greater number of task to be attended. One of the key parameters for the simulation of the problem is the number of tokens of type O, which represents the number of processes or threads in a specific problem. The other important parameter is the decision function α, which is related to the spreading of processes or threads through the tree, by updating of depth and posfunctions. It is clear, for example, that the distribution of the processes or threads at every level in the tree structure directly influences the contention at the acquisition of the tasks.

The next section explains the simulation process that is possible to execute with the proposed modeling methodology and how these simulations can help explore different parameters in order to optimize the task allocation problem.

5. Simulation of the CPN model

This section shows how to simulate a CPN model as that obtained by the methodology detailed in the previous subsection. The simulation process allows to investigate the performance of the model under parametric variations. First, the general characteristics of the simulation framework are introduced. Then, the simulation and results of a CPN model, representing a problem with 1024 tasks, are given.

In order to simplify the construction of the CPN model by using the herein proposed methodology, and thus, simulate its behavior, a CPN tool is used [43]. This environment allows editing, simulating and analyzing CPN models [3642] and was successfully used for a variety of applications areas [4448].

The model parameters that have to be considered are a number of initially available tasks (nTasks), the height of the tree with respect to the number of tasks (H), and the decision function (α). For this example, those values are nTasks=1024, H=log21024=10, and α=(r<dataj/(dataj+datak))for a given oi,rj,rksuch that depthi+1=depthj=depthkposi*2=posjposi*2+1=poskand where ris a randomly generated number. These parameters are fixed during every simulation process. However, the number of threads is varying between simulations, with d=2n, 1nnTasks, for a total of 10 simulations runs.

In the simulation framework, there are different measurements of parameters that can be obtained. For illustrative purposes, in this example, the attention is focused on study the impact on the performance of the task allocation procedure when the number of processes, or working threads, is increasing.

Table 1 summarizes some results obtained from the simulations performed on the CPNtools framework for a model with model described previously. The number of tasks was constant, while the number of processes was increased by a power of two, represented in the first column. The second column represents the average of events required per process to complete all the tasks. It provides a measure of the speed by increasing the number of processes. The third column represents the total number of readings to the task array. The forth column represents the total number of read collisions, i.e., when a process reads a task that was previously attended by other process. The fifth column represents the average of the reads to the task array executed by each process. The sixth column shows the average of the failed reads or collisions executed by each process. The seventh column shows the proficiency of the execution by the total amount of processes. Finally, the eighth column represents the average of total reads, including the failed ones, to the task array required per task.

Processes (d)Average eventsReadsCollisionsReads per processFails per processProficiencyRead per task
122528.001024.000.001024.000.001.001.00
211293.251027.003.00513.501.501.991.00
45667.001030.676.67257.671.673.971.01
82853.021038.0014.00129.751.757.891.01
161443.811051.3327.3365.711.7115.581.03
32743.341081.6757.6733.801.8030.291.06
64384.671117.3393.3317.461.4658.651.09
128202.771175.00151.009.181.18111.551.15
256108.851265.67241.674.940.94207.121.24
51255.391271.00247.002.480.48412.501.24
102427.701285.50261.501.260.26815.701.26

Table 1.

Simulation results for nTasks=1024.

The plot in Figure 7 shows the average of event, in the simulation framework, that each process required for completing all the tasks in the array. Notice that, as the number of processes increases exponentially, the number of events per processes decreases almost logarithmically.

Figure 7.

Average of events per process.

The plot in Figure 8 shows the average of reads that each process has performed to the task array for the completion of all the tasks. As in the previous figure, notice that the number of reads decreases almost logarithmically as the number of processes increases exponentially.

Figure 8.

Average of reads per process.

The plot in Figure 9 shows the average of collisions, i.e., a process’s read of a task that was previously attended by other process, as the number of processes increases. The figure shows that the maximum number of average collisions occurs when the number of processes is 32 in these experiments. The collisions, or failed reads, are highly influenced by the decision rule α.

Figure 9.

Average of collisions per process.

The plot in Figure 10 shows the proficiency of attending all the tasks in the array as the number of processes increases. The proficiency increases almost exponentially as the number of processes increases to 256. The ideal behavior is to double the proficiency as the number of processes also double. However, the collisions at reading the tasks undermine this proficiency, as expected. Notice that, the plot is logarithmic.

Figure 10.

Average of proficiency.

The plot in Figure 11 shows the average of work that each process has to do for completing a task, measured as the number of reads. This number slightly increases as the number of processes increases due to the growth in the number of collisions.

Figure 11.

Average of reads per task.

6. Conclusions

This work presented a framework, based on Colored Petri nets, for the modeling and simulation of task allocation problems, which arises in environments such as grid or cluster of computers. The framework allows the construction of complex problems in a compact way. Additionally, a simulation process of the constructed models permits the study of different key aspects of the allocation strategies. Some analysis that could be performed includes the impact of different decision rules of the processes for allocating the tasks, the effect of a greater number of processes in the contention of the task’s acquisition or the ration of the increased speed to the attention of tasks by a greater number of processes, among others. Additionally, the methodology allows with ease the construction of structures for an incremental model construction and its respective simulation process.

The proposed methodology allows with ease the extension to narytree structures as well as tree structures with a greater number of tasks and their respective simulation process.

© 2017 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Mildreth Alcaraz-Mejia, Raul Campos-Rodriguez and Marco Caballero-Gutierrez (June 7th 2017). Modeling and Simulation of Task Allocation with Colored Petri Nets, Computer Simulation, Dragan Cvetkovic, IntechOpen, DOI: 10.5772/67950. Available from:

chapter statistics

976total chapter downloads

1Crossref citations

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Multi-Criteria Decision-Making in the Implementation of Renewable Energy Sources

By Dejan Jovanovic and Ivan Pribicevic

Related Book

First chapter

Gamesourcing: Perspectives and Implementations

By Ivan Zelinka, Martin Němec and Roman Šenkeřík

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us