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