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