Performance Analysis of Software
4. Software Execution Model
Yong Deng (Ph.D.)
Assistant Professor
Department of Software Engineering
Lakehead University
Thunder Bay, Ontario, Canada
Email: yong.deng@lakeheadu.ca
Winter, 2025
Outline
• Execution graph used for SPE
• Build software execution model with execution model
• Solve the software execution model
• An ICAD (interactive CAD) case study
1
Winter, 2025
Software Execution Model
! Constructed early in the development phase
! Ensure the software architecture achieves expected performance
! Capture essential performance characteristics of the software
! Provide statistic analysis of the mean, best, and worst case response time
o
! Characterize the resource requirements of the software alone
• in absence of other workloads, multiple users, delays due to contention
! Generally su!cient for identifying serious performance problems caused by
the architecture design
• in the early phase
! We can refine the software model in critical areas
• in later development phase
The absence of problems in the software model does not mean that
there are none.
2
Winter, 2025
Execution Graph
! Execution graphs are one type of software execution model
! Visual representation that helps to communicate execution behavior
An execution graph is constructed for each performance scenario.
! The graphs consist of nodes and arcs
• nodes represent processing steps
• processing steps are a collection of operation invocations and program statements that
perform a function in the software system
ID
executiongraph
• arcs represent the order of execution PE
object object
step
If
3
Winter, 2025
Execution Graph: Nodes
Basic nodes represent processing steps at the lowest level of detail that is
appropriate for the current development stage.
Expanded nodes represent processing steps elaborated in another subgraph.
! It is used to show additional processing details that are identified as the
design evolves
WE
4
Winter, 2025
Execution Graph: Expanded nodes
5
Winter, 2025
Execution Graph: Nodes
Repetition nodes represent one or more
nodes that are repeated.
! Repetition factor associated with the node
En
that specifies the number of times the pro-
cessing steps repeat
! An arc connects the last node repeated with
the repetition node n Illustration of repetition nodes
Case nodes represent conditional execution of
processing steps.
! Attached nodes represent the steps that
may be executed
• a case node has more than one attached
• each attached node has an execution Illustration of case nodes
probability
6
Winter, 2025
Execution Graph: Nodes
Pardo nodes represent parallel execution within a scenario.
o
! Referred to as ”Parallel Do”
7
Winter, 2025
Execution Graph: Nodes
8
EIII
Winter, 2025
Execution Graph Restrictions
60
Initial node restriction: Graph and subgraph can have only one initial node.
Loop restriction: Graph and subgraph can have only one initial node.
loop
18
LED agitation
9
SPED 1 use case diagram identify performancescenarios
Winter, 2025 2 UMLdiagram foreach performancescenario
3 Example
execution graph based UML diagram
execution graph
step
processing
! Email receiving performance scenario
• left: UML sequence diagram
• right: software execution model (execution graph)
10
Winter, 2025
Software Execution Model Analysis
Primary purposes of software execution model analysis are
! Make a quick check of the best-case response time in order to ensure the
architecture and design will lead to satisfactory performance
! Assess the performance impact of alternatives
! Identify critical parts of the system for performance management
! Derive parameters for the system execution model
Formulate algorithms to evaluate the execution graphs.
11
Winter, 2025
Basic Solution Algorithms
The algorithms are ”easy” to understand
F
! Examine graphs and identify a basic structure
! Compute the time of a basic structure and reduce the basic structure to a
”computed node”
0
! Continue until only one node left
final time
Basic structures are:
! Sequences
! Loops
! Cases
12
Winter, 2025
Model Solutions: Graph Reductions
Graph reduction for sequential structures
t.tt
Graph reduction for loop structures tFI
On I
title
13 ti tent
Winter, 2025
Model Solutions: Graph Reductions
Graph reduction for case nodes
! The computation for case nodes di”ers for shortest path, longest path, and
average analyses
! Shortest path: the time for the case node is the minimum of the times for
the conditionally executed nodes
! Longest path: the time for the case node is the maximum of the times for
the conditionally executed nodes
! Average analysis: the time is multiplying each nodes time by its execution
probability
shortest is t.tt
if tists longest is tott
14 average is to Pitt Pat
Winter, 2025
Example: Best, Worst, Average Times
50202130507100
An ATM scenario
! Top: Execution graph(left) & Subgraph
for processTransaction
! Bottom: Execution time of the nodes
============================
First use the sequential-path and
conditional-path reduction rules to com-
pute the time for processTransaction.
! Shortest path: 20 2 100
50 30 50
! Longest path:
! Average path: 0299 50
900 500 07 200
Second use results for processTransac-
tion to compute the general case.
! Again shortest, longest, and average
15
Winter, 2025
Model Solutions Techniques
We have relatively simple algorithms so far.
i
! Because we have been focused on basic structures
In previous example:
! Best case: Assumes all the parallel paths are complete when the longest one
is complete
• longest of concurrent paths
! Worst case: The parallel path serialized. One path begins after one finishes
• sum of concurrent paths
In practice, the contention e!ects will complicate the analysis.
! But this simplification is su!cient for early cycle estimations
• and is easy to do
16
Winter, 2025
Analysis Procedures
! Use both the best- and the worst-case estimates of resource requirements
for each basic node
! Begin with a simplistic analysis of the best case and introduce more
sophisticated analyses of realistic cases as more detailed information
becomes available
17
507rem
Winter, 2025
Software Resource Requirements
Each basic node has specified software resource requirements
18
Winter, 2025
softwareresourcemated
Processing Overhead Matrix
! A chart of the computer resource requirements for each software resource request
are
! Solution for ”validateUser”
exeatprocessingtime
of a
1 20 2 500 ox 0
txootoxo.at
19
my y ytchc
Winter, 2025
Computing the Total Execution Time
Step 1: Uses the processing overhead matrix to calculate the total computer
resources required per software resource for each node in the graph.
! E.g.: ”sendResults” needs 2 → 20 + 1 → 500 + 1 → 10 = 550 CPU units
! What about ”validateUser” and ”validateTransaction”?
1. How many I/O’s and Network messages needed by ”sendResults”?
8
20
Winter, 2025
Computing the Total Execution Time
Step 2: Computes the total computer resource requirements for the graph.
Step 3: Compute the best case elapsed time.
! Use the Processing Overhead Matrix:
(3110 ↑ 0.00001) + (14 ↑ 0.02) + (1 ↑ 0.01) = 0.3211
E
seconds
! Processing Overhead Matrix
21
Winter, 2025
Types of Software Resource
22
Winter, 2025
Types of Software Resource
23
Winter, 2025
Software Resource Estimation
! One of the most di!cult resources to estimate is CPU usage
• we use work units that focus on the relative amount of work performed in
a processing step
! Early in development, models typically will use two to five types of software
resource specifications
! Later, you may include more software resource types, such as
synchronization and lock requests
• the process of translating a sequence disgram to an execution
diagram is similar
24
Winter, 2025
Case Study: ICAD
Interactive Computer-Aided Design (ICAD) system
! Support computer-aided design (activities)
! Engineers will use the application to construct and view drawings that
model structures
• e.g., aircraft wings
! The system also allows users to store a model in a database, and
interactively assess the design’s correctness, feasibility, and suitability
! The model is stored in a relational data, and several versions of the model
may exist within the database
! Use cases include Draw (draw a model), Solve (solve a model) , ...
! We will deescribe Draw use case
25
Winter, 2025
ICAD: Drawing
Drawing consists of nodes and elements
! Node is defined by its position in three-dimensional space (x, y, z)
! Elements include
• beams: connect two nodes
• triangles: connect three nodes
• plates: connect four nodes
! Also including additional info necessary for the performance model
• for both nodes and elements, by using proper UML components
26
Winter, 2025
ICAD: General Architecture
! ICAD deployment diagram
! The system is made up of:
! ICAD processes
• GUI, application, database
• executed on same processor
27
Winter, 2025
ICAD: Use Cases and Scenarios
! Use cases: Draw (draw a model), Solve (solve a model)
! Scenario: DrawMod (Draw models) -> see the figure below
! A typical model:
• contains only nodes and beams
• consists of 2,000 beams
! Performance goal: Draw (on screen) a typical model in 10 seconds or less
28
Winter, 2025
ICAD: Architecture 1
Class diagram:
29
Winter, 2025
Expanded DrawMod Scenario (Sequence Diagram)
beams
2.000
p
Ef te
30
Winter, 2025
Expanded DrawMod Scenario (Execution Graph)
1 2000 n
31
Winter, 2025
Software Resource Requirements
We now specify the software resource requirements for the established
execution graph.
! EDMS – The number of calls to the ICAD Database process
! CPU – An estimate of the number of instructions executed
! I/O – the number of disk accesses to obtain data from the database
! Get (Allocate)/Free – the number of calls to the memory management
! Screen – the number of times graphics operations ”draw” to the screen
We may also need the probability of each case alternatives and the
number of loop repetitions. – To be covered later.
32
Winter, 2025
Software Resource Requirements
33
Winter, 2025
Processing Overhead Matrix
34
Winter, 2025
Compute the Solution for Each step
initialize:
35
Winter, 2025
Compute the Solution for Each step
findBeans:
36
Winter, 2025
Compute the Solution for Each step
drawBeam: Assume 2000 beams
iteration
1 How many
0.4837 per
EDMS are needed
16,5
i 4
0
2 21270350
EDMOS tot
s CPU to Getfree screen 1518 155
212 804
twice
088 4.03 0 41
0 to to
0 0 79 bg
Getfree 1
s eniotototo
a.osxltibt Y
cpu.at E3 16 17 16178
190684 1 002
37
161,78 sk 4 0
0
1 183
Winter, 2025
Compute the Solution
sc
table4
o
each iteration
ex2000 iterations
0.4864
O O
0.48642000 967.48
Table4.4 creations 8eaachcreateneedszcpusonly also
38
2 Cpus hardware
means
save 12,000 Cpu units
12000 0.000005 006
Winter, 2025
ICAD: Analysis of Architecture 1
! 900+ running time not good (at all)
! Uses an object for each beam and node
• one object created for each beam/node
• mode flexible, also mode expensive
39
Winter, 2025
ICAD: Architecture 2
Reduce overhead by Flyweight pattern:
! Allows sharing of the beam and node objects
! Only create one beam/node object
! Each object contains intrinsic info
• independent of a particular beam/node
• has draw functionality
! Extrinsic info stored separately
• e.g.: coordinates of the nodes
• e.g.: store in the database
• passed to the object when needed
Instead of using an object for each beam and node, we propose to use a
shared object.
40
Winter, 2025
ICAD: Architecture 2
Class diagram:
! Constructors for Node and Beam are executed only once
! Node and Beam classes still part of the DrawMod process
• but only one of each
! Change to the execution graph: Move the createBeam to after initialize
41
Winter, 2025
ICAD: Architecture 2 (Execution Graph for DrawMod)
42
Winter, 2025
ICAD: Architecture 2 (Sequence Diagram for DrawMod)
Computation time reduction:
! Only two objects (one beam and one node objects) created after
initialization
create only 2 objects
! For Architecture 1, with 2000 beam, 6000 new objects created
• one beam object and two node objects for each beam
43
ICAD: Architecture 20.060s different
Winter, 2025
The over all response time is reduced to 969.29 to 969.23 seconds.
! Still not a significant reduction
! Constructor overhead is not a significant factor for the DrawMod scenario
• only for this scenario.
• maybe significant of the number of beams & nodes are significantly larger
Takeaways:
! Modifying performance models to evaluate the alternatives is relatively easy
! It is important to quantify the e”ect of design alternatives rather than
blindly follow a ”guideline” that may not apply
But, if the constructor overhead reduction is not su”cient, what else
we can do?
! Look for more significant computation consumption in the architecture.
44
Winter, 2025
ICAD: Main Bottleneck within Architecture 1&2
Left: resource demand for architecture 1&2;
Right: Resource demand for drawBeam submodel
oo
Observations:
! Left: Time spend at the Disk devices for drawBeam is significant
• 965 out of the 969
! Right: Time spend on Disk is evenly spread in the drawBeam submodel
45
Winter, 2025
ICAD: Architecture 3
Key idea: Add a new operation to retrieve a block of data with one call.
! retrieveBlock(): Retrieve the beams and nodes once at the beginning
! Store the data values for all beam and node objects
• instead of retrieving the value each time it is needed (Architectures 1&2)
! If a retrieveBlock() can fetch 64 beams, only 33 database accesses are needed
46
Winter, 2025
Execution Graph and Solution
! Significant time reduction
• was 900+
47
Winter, 2025
Other Possible Improvements to the ICAD
It is relatively easy to create the initial models, and the revisions to
evaluate alternatives are straightforward.
Simple software execution models are su”cient to identify problems and
quantify the performance feasible alternatives.
Once a suitable architecture is found, SPE studies continue to evaluate
design and implementation alternatives.
! It is important to continue the SPE modeling throughout the development
! Do not get complacent when the preliminary results indicate the
performance is satisfactory.
• the evolving software may be di”erent
48
Winter, 2025
Modeling Hints
! It is not necessary to include all of the details of the software’s processing
flow in the performance model
• the model is only an abstraction of software
• ignore the unnecessary items
! Use hierarchy to help make your models easier to understand and modify
• hide processing details in subgraphs
! Use best- and worst-case estimates of resource requirements to help
compensate for uncertainty early in the process
• proceed if the worst-case has no problem
• fix the problem if there is one in the best-case
49
Winter, 2025
Modeling Hints
! Study the sensitivity of the performance results to the input parameters
! If small change in resource requirements causes large change in results
• software is sensitive to those specifications
• those are tend to be critical resources need to be monitored
Scenarios a sudden decrease of performance may happen
! Device have high utilization (e.g., 99%)
! Processing is in a loop
• small increase multiplied by a large repetition factor
! Significant synchronization and resource sharing delays
• contention, waiting for the resources
50
Winter, 2025
Summary
Software execution model
! Sequence diagram (UML) to execution graph
! Solution to the execution graph model
• graph reduction
• software requirement table
• processing overhead matrix
• execution time computation
! Case study: ICAD
• three structures
• how to use performance modeling to improve the architecture design
! Some modeling hints
51
Winter, 2025
Contact and O”ce Hours
Email: yong.deng@lakeheadu.ca
O”ce: 5008 ATAC Building
Thank you!
52
