1\"	@(#)equations.me	1.1 03/11/82
2.EQ
3delim ##
4.EN
5.sh 1 "Notation"
6.pp
7Given a program, #P#, and an ordered list of instructions, #I#,
8composing #P#,
9.EQ
10P ~ = ~ {I sub 1} ^ {I sub 2} ^ ... ^ {I sub m}
11.EN
12define the address of an instruction to be its index in the program.
13Given a namelist, #N#,  that associates names with distinguished
14addresses, called entry points, sorted by increasing entry point values,
15.EQ
16N ~ = ~ "{" ( n sub 1 , ~ e sub 1 ) ,..., ( n sub r , ~ e sub r ) "}"
17.EN
18#N# partitions the addresses of #P# into ranges, called routines,
19such that
20.EQ
21R sub 0 ~ mark = ~ "{" 1 ,..., {e sub 1} - 1 "}"
22.EN C
23.EQ
24R sub i ~ lineup = ~ "{" e sub i ,..., {e sub i} - 1 "}" ~
25for ~ 1 <= i < r
26.EN C
27.EQ
28R sub r ~ lineup = ~ "{" e sub r ,..., m "}"
29.EN
30.(q
31<<<watch out.  we have only one entry point per routine.  not
32everybody does.>>>
33.)q
34A profilable program consists of the instructions and a namelist.
35.pp
36Given a histogram of address samples, #H#, ordered such that the
37#i sup th# sample is the count for the #i sup th#
38instruction, define the #selftime#, #S#, of each of the #r# routines
39as
40.EQ
41S sub i ~ = ~ sum from {j ~ \(mo ~ {R sub i}} {H sub j}
42.EN
43.pp
44Given a set of arcs, #A#, gathered during the profiled execution of
45the program, where #A# consists of ordered triples,
46#(tail, ~ head, ~ count)#, giving the address of the
47tail and head of the arc, and a count of the number of times the
48execution of the program traversed this arc from instruction
49#I sub tail# to instruction #I sub head#,
50the number of calls to the #i sup th# routine can be calculated
51as
52.EQ
53C sub i ~ = ~ sum from { ( tail , ~ head , ~ count ) ~ \(mo ~ A }
54                       "{" count | head ~ \(mo ~ R sub i "}"
55.EN
56and the number of calls to the #i sup th# routine from the
57#j sup th# routine as
58.EQ
59C sub i sup j ~ = ~ sum from { ( tail , ~ head , ~ count ) ~ \(mo ~ A }
60                                  "{" count | tail ~ \(mo ~ R sub i ,
61                                  head ~ \(mo ~ R sub j "}"
62.EN
63.pp
64If there is an arc with #tail ~ \(mo ~ R sub i# and
65#head ~ \(mo ~ R sub j#, then #R sub j# is a child of
66#R sub i#, denoted #R sub i ~ Child ~ R sub j#.
67#R sub i# has as a child #R sub j#.
68The transitive closure of the #Child# relation is called the
69#Descendants# relation.
70The inverse of the #Child# relation is the #Parent# relation.
71For example, if #R sub i ~ Child ~ R sub j# then
72#R sub j ~ Parent ~ R sub i#.
73The transitive closure of the #Parent# relation is called the
74#Ancestor# relation.
75.pp
76We are interested in computing the following recurrence, which
77gives the time for a routine based on its selftime and an
78appropriate fraction of the time of its descendants.
79.EQ
80T sub i ~ = ~ S sub i + sum from {i ~ Child ~ j}
81                        {T sub j \(mu {C sub i sup j} over {C sub i}}
82.EN
83This recurrence can be trivially solved for leaves of the call
84graph, e.g. those with no children.
85In the general case, however, it is necessary to order the nodes
86of the graph so that the times for all children of a routine
87are known before computing the time for the routine itself.
88Such an order could be imposed by a depth-first numbering of the
89routines with a single traversal of each of the arcs in #A#.
90<<<this falls off here because i don't know if we want to continue
91with this, and it's hard to type.>>>
92