Appendix - B
The pseudo code of constraint decomposition phase is described in Appendix – B.
In this Pseudo code, three matrices are used. They are M, S and T. The input workflow is given through the matrix M. The matrices S and T are used to store intermediate results during decomposition. The constraints computed for individual tasks are updated in M.
Let M be a matrix of order where ‘n’ denotes the total number of tasks in W. Let 1st column of M denote the task id, 2nd column denote the type of execution unit in which the task is present (2nd column can take 4 values, 1, 2, 3 and 4. If the value is 1, the execution unit is and unit, if the value is 2, the unit is or, if the value is 3, the unit is Loop and if the value is 4 then the task in an individual sequential task in W), 3rd column denote the id of execution unit of the task, 4th column denote the id of sequential path of the task, 5th column denote the minimum response time of the task, 6th column represents the maximum response time of the task, 7th column denote the number of iterations of the task if it were in a Loop, 8th column denote the lower bound constraint of response time and 9th column denote the upper bound constraint of response time. Let ‘grt’ denote the global constraint of response time. Now, the problem is to find 8th and 9th column for each task for the given values of first 7 columns of all tasks and grt.
Let S be a matrix of order where ‘x’ denotes the total number of sequential paths present in the workflow. S is an intermediate matrix which stores the details of sequential paths present in AND, OR and Loop units of the workflow. Let 1st column denote id of the execution unit, 2nd column denote the type of execution unit, 3rd column represent the id of sequential path, 4th column denote the minimum response time of sequential path, 5th column denote the maximum response time of sequential path, 6th column denote lower bound constraint of response time of the sequential path, 7th column denote the upper bound constraint of response time of the sequential path.
Let T be a matrix of order where ‘y’ denotes the total number of tasks (both old and new-tasks) present in the converted workflow. Each new_task denote a converted AND unit or converted OR unit or converted Loop structure. Let 1st column denote whether the task is old task of new task. For old task, the value of the first column will be taskid and for new task the value of first column is 0. Let 2st column denote the type of execution pattern corresponding to new_task, 3nd column denote id of execution pattern, 4th column represent the minimum response time of the task, 5th column denote the maximum response time of the task, 6th column denote lower bound constraint of the task, 7th column denote the upper bound constraint of the task.
Definitions of Functions
decompose – is the main algorithm used for decomposing the given global constraints into task level constraints to individual tasks in the given workflow. This algorithm takes the matrix M and the global constraint of response time denoted by ‘grt’ as input. It decomposes ‘grt’ into local constraints and updates the values of local constraints in the matrix M
transform_and_or(int nof_units, int type) – is a function used to transform the AND/OR units present in a workflow into their corresponding new tasks. It takes number of units and type as arguments. It updates the matrices S and T
transform_lp(int nof_units, int type) - – is a function used to transform the Loop units present in a workflow into their corresponding new tasks. It takes number of Loops and unit-type as arguments. It updates the matrices S and T
add_old_task() – is a function used to add an entry in T, for each individual sequential task in the workflow
new_task_fix() – is a function used to find and assign lower bound constraint of response time and upper bound constraint of response time for new-tasks in the matrix T
sp_fix() – is a function used to find and assign lower bound constraint of response time and upper bound constraint of response time for all sequential paths from the constraints of their corresponding new-tasks. It updates the matrix S. (Please note that for each new-task, there will be a corresponding simple unit. The constraints of a simple unit are same as that of its corresponding new-task.)
task_fix() - is a function used to find and assign lower bound constraint of response time and upper bound constraint of response time for all tasks from the constraints of their corresponding sequential paths. It updates the values in matrix M
old_task_fix() – is a function used to find and assign lower bound constraint of response time and upper bound constraint of response time for old tasks in the matrix M.
Thus, task level constraints are updated in Matrix M which will be used by Service Selection Phase.
Algorithm: decompose
Inputs: M, grt
Outputs: updated M
Begin:
//finding the maximum number of AND, OR and Loop units
Set maxau to 0
Set maxou to 0
Set maxlp to 0
For row=0 to m.length-1
if(m[row][1] equals 1) then
set nof_and to m[row][2]
if(nof_and greater than maxau) then
set maxau to nof_and
endif
endif
if(m[row][1] equals 2)
set nof_or to m[row][2];
if(nof_or greater than maxou) then
set maxou to nof_or
endif
endif
if(m[row][1] equals 3) then
set nof_lp to m[row][2]
if(nof_lp greater than maxlp) then
set maxlp to nof_lp
endif
endif
Endfor
//conversion of AND units into new-tasks
call transform_and_or with maxau and type set to 1
//conversion of OR units into new-tasks
call transfor_and_or with maxor and type set to 2
//conversion of Loop units into new-tasks
call transform_lp with maxlp and type set to 3
//adding an entry in the matrix T for sequential task in the given workflow
call add_old_task
//finding minimum response time and maximum response timeof aconverted workflow
Set wfminrt to 0
Set wfmaxrt to 0
For row=0 to t.length-1
add t[row][3] to wfminrt
add t[row][4] to wfmaxrt
EndFor
//fixing constraints for new_tasks
Call new_task_fix
//fixing constraints for different sequential paths from the constraints of their corresponding new_tasks
Call sp_fix
//fixing constraints for tasks from the constraints of their corresponding sequential paths
Call task_fix
//fixing constraints for old tasks
Call old_task_fix
End
Function transform_and_or(parameters: maxu, type)
for u=1 to maxu
set new_taskid to 0
set maxsp to 0
for row=0 to m.length-1
if((m[row][1] equals type) and (m[row][2] equals u)) then
if(m[row][3] greater than maxsp) then
set maxsp to m[row][3]
endif
end if
EndFor
set index to 0
set unitminrt to 0
set unitmaxrt to 0
for nsp=1to maxsp
set spminrt to 0
set spmaxrt to 0
for row=0 to m.length-1
if((m[row][] equals type) and (m[row][3] equals nsp)) then
taskid[index]=m[row][0]
endif
EndFor
Set tid to 0
For k=0 to taskid.length-1
Set tid to taskid[k]
For row=0 to m.length-1
If(m[row][0] equals tid) then
Add m[row][4] to spminrt
Add m[row][5] to spmaxrt
Endif
EndFor
EndFor
Set sprow to s.length+1
Set s[sprow][0] to u
Set s[sprow][1] to type
Set s[sprow][2] to nsp
Set s[sprow][3] to spmin
Set s[sprow][4] to spmax
Set s[sprow][5] to 0
Set s[sprow][6] to 0
If(spminrt is greater than unitminrt) then
set unitminrt to spminrt
endif
If(spmaxrt is greater than unitmaxrt) then
set unitmaxrt to spmaxrt
Endif
Endfor
Set trow to t.length+1
Sett[trow][0] to 0
Set t[trow][1] to type
Set t[trow][2] to u
Set t[trow][3] to unitminrt
Set t[trow][4] to unitmaxrt
Set t[trow][] to 0
Set t[trow][6] to 0
EndFor
Endfunction
Function transform_lp(parameters: maxu, type)
Set lpminrt to 0
Set lpmaxrt to 0
For u=1 to maxu
Set spminrt to 0
Set spmaxrt to 0
Set iteration to 0
For row=1 to m.length-1
If(m[row][1] equals type) and (m[row][2] equals u)) then
Add m[row][4] to spminrt
Add m[row][5] to spmaxrt
Set iteration to m[row][6]
Endif
Endfor
Set srow to s.length+1
Set s[srow][0] to u
Set s[srow][1] to type
Set s[srow][2] to 1
Set s[srow][3] to spmin
Set s[srow][4]= to pmax
Set s[srow][5] to 0
Set s[srow][6] to 0
Compute iteration * spminrt and set to lpminrt
Comput iteration*spmaxrt and set to lpmaxrt
Set trow to t.length+1
Set t[trow][0] to 0
Set s[srow][1] to type
Set s[srow][2] to u
Set s[srow][3] to lpminrt
Set s[srow][4]= to lpmaxrt
Set s[srow][5] to 0
Set s[srow][6] to 0
Endfor
Endfunction
Function add_old_task()
For row =0 to m.length-1
If(m[row][1] equals 4) then
set trow to t.length+1
set t[trow][0] to m[row[0]
set t[trow][1] to 4
set t[trow][2] to 0
set t[trow][3] to m[row][4]
set t[trow][4] to m[row][5]
set t[trow][5] to 0
set t[trow][6] to 0
Endif
Endfor
Endfunction
Function new_task_fix()
Read grt
Compute ratio_rt as grt dividedby wfmaxrt
For row=0 to t.length-1
Set t[row][5] to t[row][3]
Set t[row][6] to t[row][4] ratio_rt
Endfor
Endfunction
Function sp_fix()
For row=0 to t.length-1
Set temp_utype to t[row][1]
Set temp_uid to t[row][2]
For sprow=0 to s.length-1
If((s[sprow][0] equals temp_uid) and (s[sprow][1] equals temp_utype)) then
Set s[sprow][5] to t[row][5]
Set s[sprow][6] to t[row][6]
Endif
Endfor
Endfor
Endfunction
Function task_fix()
For row=0 to m.length-1
Set tsk to m[row][0]
Set type to m[row][1]
Set temp_uid to m[row][2]
Set spid to m[row][3]
If(spid is not equals 0) then
For sprow=0 to s.length-1
Set uid to s[sprow][0]
Set sptype to s[sprow][1]
Set spno to s[sprow][2]
If((uid equals temp_uid) and (spno equals spid) and (sptype equals type)) then
If((type equals 1) or (type equals 2))
Set m[row][7] to m[row][4]
Set m[row][8] to (m[row][5]/s[sprow][4]) s[sprow][6]
Else if(type equals 3)
Set iteration to m[row][6]
Set modified to s[sprow][6]/iteration
Set m[row][7] to m[row][4]
Set m[row][8] to (m[row][5]/s[sprow][4]) modified
Endif
Endif
Endfor
Endif
Endfor
Endfunction
Function old_task_fix()
Set tid to 0
For row=0 to m.length-1
If(m[row][1] equals 4) then
Set tid=m[row][0]
For trow=0 to t.length-1
Set tno to t[trow][0]
If(tid equals tno)
Set m[row][7] tot[trow][5]
Set m[row][8] to t[trow][6]
endif
endfor
endif
Endfor
EndFunction