The person charging this material is re- sponsible for its return to the library from which it was withdrawn on or before the Latest Date stamped below. Theft, mutilation, and underlining of books are reasons for disciplinary action and may result in dismissal from the University. To renew call Telephone Center, 333-8400 UNIVERSITY OF ILLINOIS LIBRARY AT URBANA-CHAMPAIGN m 4 «93 L161— O-1096 1U jbi ''Report No. UIUCDCS-R-80-1043 UILU-ENG 80 1744 Cdp & SOME RESULTS ON THE WORKING SET ANOMALIES IN NUMERICAL PROGRAMS by Walid A. Abu-Sufah and David A. Padua November 1980 NSF-OCA-MCS76-81686-000053 DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN •v URBANA, ILLINO % "&/ Digitized by the Internet Archive in 2013 http://archive.org/details/someresultsonwor1043abus Report No. UIUCDCS-R-80-1043 SOME RESULTS ^ ON THE WORKING SET ANOMALIES IN NUMERICAL PROGRAMS by Walid A. Abu-Sufah and David A. Padua November 1980 Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois 61801 * This work was supported in part by the National Science Foundation under Grant No. US NSF MCS76-81686. Abstract This paper shows that the Working Set parameter-real memory and real memory-fault rate anomalies mentioned by Franklin, Graham, and Gupta in [FrGG78] do occur in traces generated by real programs. The results of the detailed investigation of this anomalous behavior in four Fortran programs are presented. In some cases, a drop of a factor of two in the average memory allotment is observed when the window size is increased. In some instances, a bigger memory allotment means an order of magnitude increase in page faults. Keywords : Memory Management Multiprogramming Working Set Working Set Anomaly Program Behavior 1. Introduction Franklin, Graham, and Gupta have shown in [FrGG78] that the page fault frequency policy of memory management can exhibit anomalous behavior for some reference strings. They gave short example reference strings to illustrate their ideas and pointed out that real programs exhibit this anomalous behavior [Grah76] , [Gupt74] . For the working set policy, WS, they gave an example reference string to demonstrate that certain anomalous behavior is also possible. However, nothing was mentioned about encountering these anomalies of the WS in real programs. The WS anomalies were encountered experimentally in the spring of 1978 by one of us while working on the development of automatic program transformations to improve program behavior in a virtual memory environment [AbuS78], [AbKL79] , [AbKL80]. Before proceeding, we will describe the notation used in this paper, and will define the two types of anomalies to be considered. The WS policy keeps in memory the pages referenced during the previous x memory references, where T is the WS control parameter. This set of pages is the working set and is denoted by W(x,t) at time t. Its size is w(T,t). The average memory allocated to a program during its execution is given by R f(T) M(T,L) = ( Z w(T,t) + L • I w (x,t ))/(R + L • f (T)) (1) t=l i=l where R = the length of the reference string L = the mean page fault service time f(x) = the number of page faults w. (x,t.) = the working-set size at the ith page fault, We say that there is a parameter-real memory anomaly when M (t-i>L) > M(x ,L) for some T.. < T„ and some L, and a real memory-fault rate anomaly when, for some T ^ T„ and some L ,M(x ,L) < M(t ,L) and f(T 1 ) < f(x 2 ) [FrGG78]. In the 1978 experiments mentioned above, some of the trans- formed programs and some of the untransformed ones showed both anomalies. In those experiments only references to array elements were considered. The page size was 64 words and we used three values for L: 32, 320, and 3200 references. Table 1 summarizes our findings for these programs, and Table 2 shows some of their characteristics. In Table 1, we can see that the two anomalies defined above arise in all the programs listed for at least one value of L. Consider, for example, the program BASE when L = 32. When T is 6, the average memory used is 2.33 pages and the number of page faults is 681. When T is increased to 8, the average memory decreases to 1.96 pages and the number of page faults decreases drastically to 374. The decrease in average memory when T increases illustrates the parameter-real memory anomaly, and the decrease in the number of page faults when the average memory decreases, illustrates the real memory-fault rate anomaly. Recently, Denning in [Denn80] argues that it is unlikely that any nonlookahead policy better than the WS will be discovered. Thus, it seems that WS dispatchers should be widely used in future computer sys- tems. However, load control of a multiprogrammed system which is based on an anomalous memory management policy may be unstable since a change CO u XI a U O •H > cO 43 r«. 00 O 00 v£> o «tf m CM T-i CM CM CO <* 00 CM CO co CM m 00 o m o CM o> o CM CM CM CO . m r^ o> CO o r- rH o r- vO + Q W M Pn 00 <* O vO CM CO X, CU PQ co o § O c < CO s U oo o >h Ph cu x: 4-1 o CO CO x: cj a> I CO CN CU H X H CO 4-1 a cu o o CO TJ a) 01 00 a tO C Ph a) h M-l cu o M-l cu = £fc: Pi >^ CO to cu i-i o u e < cu IH M-l cu o 4-1 cu =fe cd CO >, tj to 0) M u u c < cu l-l mh cu o IH cu =S= 04 b to u OO o H Ph 4J pH CO * (3 co * 1-3 ^ ^ o z Ph % CO o 9 u MH B B M 00 M-l H o CO < f3 H o 00 B IH* p u Ph u o cO Ph hJ MH M-l M-l l-l I-i Ph 1 a CO Ph 00 B S3 B a o TJ e o l-l cO tO •H ^H tO 00 l-l o B U 1-1 4-> CU u PS Ph M-l 00 00 •H •H 00 •H CO l-l o o CO Ph o rH CO C M-l l-l u o l-l a •H CO Ph Ph a CJ Ph 3 CO I-i •~s a •H o ^ H CO P3 CO o 4J CO CJ rH 4-1 O a CJ CU o CO I-i CJ •H •H cu a •H CU ^ CU •H 4-1 CO Q 00 CO XI •H O CO !>> CO So o }H P< N X >-. a X S I-i 3 •H Ph ^ OK Ph CO O ^r rH CO |H J X O Ph CN cO TJ cu 4-1 3 T) •H •rH o •H 3 rH CJ Ph 3 l-l B 4-1 rH 4-1 o O cu < O 4-1 cu CO **~s •H iH Xl H rH tO x cO C cj o W cj s CJ Ph H rH co CN O m o CN \£) co ^O O CO CM 00 rH CN <2 + oa a 3 w M Ph -ci- in CN o co O O 00 CN r^ m co CM O s 04 CJ PJ H O Ph Pd H 2 00 s H 2 H o S5 S Q Ph M + >. JH o 4-) CO IH O X CO r-1 X o M CO CU CO CU Ph CJ •H I-i CU X a CO >. o IH B o 4-> 4J >. CO TJ •H >H > cu a •H cO 1 o 13 -5 a 1 1 i MH CO r-1 cO 9 d r-l IH H HH g H & <: z •H cO ■u QJ Q 0) •H X) =J 4J co en I M too O Ph 0) Xi +J MH O CO o •H 4J Cfl •H !-i 0) >-i 4-> CD O (X CO CO M PH cd X! CJ> en •H X! 6 o CO CO 0) rH CO H ■a rJ Pi Z >> e 4J O •H >-l O MH O rH S QJ CO CD > H 4J 60 fl QJ o QJ rH U a Pi •H O CN CM CN 4J H CJ r< O QJ 0) QJ CO 4-1 H rH rH Ph CO X XI rQ >-l CO CO CO B QJ H H H O C XI QJ QJ QJ 0) c o QJ QJ QJ CO CO CO CO Pi X) CO 0) QJ o toO c cO vO co CN *o qj Cu m CO O CN r4 CM rH CN m qj -H 14-1 t-i CO < Pi CO 0) bO CO Pi en QJ UH bO o CO p^ rH vD m o u m r-» ON CM QJ >N CN rH T~\ m rQ CO 6 l-i d u ss < .. CO ao QJ C O •H fl ■> c CO QJ u hJ H «3 I Pi hJ V4 H < toO w Pi H O O CO ;=> h- 1 4 >H N M O 4J CO o CO rJ CJ J-l CO QJ cn QJ Pi CO > CO of a given sign in the parameter might not produce changes of corre- sponding sign in the controlled variable [FrGG78], This has convinced us of the importance of making a thorough investigation 1 and analysis of the WS anomalies in real programs which is the subject of this paper. Specifically, we will study in detail four of the untransformed programs used in our previous experiments, namely: BASE, FOURTR, INIT, and PAPUAL. Table 3 shows some of their characteristics. 2 In our crude previous investigations, BASE and PAPUAL did not show any anomalies while INIT and FOURTR did. We start Section 2 of this paper with a brief discussion of the trace generation and processing method. Then we present the results of our experiments and their analysis. In Section 3, we make some concluding remarks . The investigation whose results are displayed in Table 1 was not thorough. The values in Table 3 assume column major storage for two-dimensional arrays, whereas those in Table 2 assume the square-block storage scheme 2. The Results and Their Analysis 2.1 The Experimentation Method The page size in our experiments was 256 8-bit bytes. The main memory access time was taken as the time unit and the average access time to secondary memory was defined as L time units. The instruction set was assumed to be the IBM 370' s. We assumed the use of segments [Denn70], each consisting of one or more pages. For each program, one segment was allocated to the code, one to each array, and one to the scalar variables. Each variable was assumed to be four bytes long, and two-dimensional arrays to be stored in column-major order. The tool we used to do the experiments is sketched in Fig. 1. It consists of two components; a trace generator and a simulator, both written in PL/I. The trace generator reads a source Fortran program, and the output from the Fortran G compiler for the same source program. The source program is interpreted to generate the address trace. The object program is used only to determine which and how many machine instructions are fetched for each Fortran statement. This approach to trace generation has some advantages. It allows us to generate subsets of the addresses in the trace; for example, we can generate array addresses only, or instruction addresses only. Also, the storage strategy can be changed without having to change the compiler; for example, two-dimensional arrays can be stored by rows, columns, or square blocks [McCo69]. For performance reasons, not all assignment statements in the source program are interpreted, only those that determine the address trace. For example, in the program DIMENSION A(IOO), B(IOO) DO 1 I = 1, 100 1 A(I) = B(I) + C STOP END the assignment statement does not have to be interpreted; the address trace will be the same whatever the value of A. The information on which assignment statements to interpret is supplied to the trace generator by the user. The simulator of the WS policy is fairly straightforward; it takes a range of values and an increment for T, and produces all the information required to compute the average memory for those values of T. Since the average working-set size at fault time does not satisfy the inclusion property, we were not able to use a stack algorithm [MGST70]. This made the simulation costly in terms of computer time. In contrast, the trace generation was so cheap that we decided not to store the trace in a tape but to regenerate it each time a new simulation was done. The simulator was used as a subroutine of the trace generator. 2.2 The Results 2.2.1 The Page Faults vs. Window Size Curves Fig. 2(a) shows the page faults vs. the window size, x, curve for the array reference string of program BASE. Fig. 2(b) shows this curve when references to scalar variables, constants, and instructions are included in the reference string. Figs. 3, 4, and 5 show similar curves for the rest of the programs. We notice that the graphs for all the programs share some common characteristics. The general shape of the page fault curves does not change when 9 references to scalar variables and instructions are included. This is obvious when comparing Figs. 2(a) and 2(b). Thus the paging behavior of our programs, and numerical programs in general, is mainly controlled by references to array variables (see also Figs. 6-9). This same argument was made in [MaBa76] . This is expected because the number of array pages referenced in numerical programs is much larger than the number of scalar and instruction pages (Table 3). However, there is around one order of magnitude difference between the total number of references in a string and the references to array elements. This explains the order of magnitude shift along the window size axis between the curves in Figs. 2(a) and 2(b). The curves are not smooth curves. This can simply be explained by the fact that numerical programs mainly execute loops. Thus, when the window size is increased to the point where all the pages referenced in an iteration of a loop are included in the same working set, a sudden drop in the number of page faults will occur. 2.2.2 The Average Memory Allotment vs. Window Size and the Page Faults vs. Average Memory Curves Figs. 6-9 show the average memory allotment vs. window size curves for L = and L ->■ °° . The average memory allotment, at a given T = T , can be either an increasing or decreasing function of L. We have R f(T ) M(x L) = ( Z w(T t) + L • E ■ w.(T 1 ,t.))/(R + L • f (T )) t=l i-l = (A( Tl ) + B(T 1 ) • L)/(R + C(T 1 ) • L) (2) Thus, 3M(T 1 ,L)/3L = (B(T 1 ) • R - C(T 1 ) • A(T 1 )/(R + C^) • L) 2 The solid curves are for L = and the dashed curves are for L -*■ °° 10 Therefore, M(t,,L) will always fall between M(t-. ,0) = A(t,)/R and M(t, ,°°) = B(t,)/C(t, ). Thus, the curves for L = and L ■* °° are envelopes to all other curves for < L < °° . Fig. 10 shows M(x,0), M(t,20), M(t,200), M(t,2000), and M(t,«) for program BASE (array references only). We observe that the curves for M(t,2000) and M(t,°°) are fairly close to each other. This is also true for all the other programs. Thus, the M(T,°°) curve is a good approximation to the M(x,L) curves when L > 2000 . Figs. 11-14 show the page faults vs. average memory allotment for the programs (L = and L -*■ °°) . From Figs. 6-14 , we see that the parameter-real memory, and the real memory-fault rate anomalies occur in all programs. Table 4 shows the points at which the anomalies are most significant. Fig. 15 shows a typical section of the memory allotment curve where an anomalous behavior is seen. We note that the line M = M„ intersects the curve at t = x and M = M, at T = T, . If we let T = It j and alb j a T, = [t, 1 , then we observe the following (i) There will be anomalies between t, and all t's in the open interval (t, ,t, ) (ii) There will be anomalies between t« and all t's in the open interval (t_, t~) (iii) When generating the data for plotting the curve, if the increment in T, At , was greater than or equal to T. - T„ , then the anomalous behavior in this section 4 J of the curve will not show up. We remark that if every s o o o CM CM o o o CM S o o CM CM o o CM o CM CM o CM CM O CM CM CO CM CM CO CM O co 00 00 o CO CM m CM CO as 00 00 as CO CM CO 00 OS CO CO co o H sr 00 m CO CM CM CO co CM co v£> UO co LO m oo co OS CO ON co CM co m tH co co oo CM CO CO 00 co CO o o CM CM CM ^O OS as CM as ON o CM vO o CO CO CO . VD O CM Os co vO m CO 00 m CO OS m CO co CM CO 00 m CO co o 00 00 00 m -d- m CM co CM CM O 00 CTi CM m o^ oo rH co m CM m CM O vO CO CO m CM o Os CM CM CM O CM CTi CM CM 00 CM O o CM OS CM m CM o o 00 r^- O CM CO o «* a\ H m vO rH tH rH CO CM co CO CO 00 co r>s as rH CM -3- m CM CM r^ r^ o CO m v£3 co CT> cr> \D o co m o CM 00 co o o rH CM m CM v£> vO 00 H o m as O O o m o o O vO CM o> m Os 00 m sa- m m o o as H CM OS H co h- in CM CM CM m CO #* 00 O m m O O m o o m m rH Os as r^- <* CM r^» OS CM as ot as H CM rH CO r-^ CO rH CM r-\ ^r oo B cd P4 kJ >-l H < 60 H Pi H C3 O CO tD M 3 U < O (2i Pn pq fa M Cl, 11 / — V 8^ o vD ON O T-i o r^ r^ ^D r-{ CO CN CO CN H CN co CO u-1 r^. 00 CTl r^- m m T-i * — • tH CO CO CO co co r^ rH o r-^ r-{ H en ro OO o o r^ vO rH CN H m co co uO on -CT o v£) ON oo vO vO rH v**' co co CO co en r^ m o O O r^ n-x 00 CO co CO O 00 -H rH o CN o m m rH <£> m T-\ O o <* m ON rH m O v£> m r~-« VO O r^ 00 co ON m H r^ r^ CN r-\ r-\ CN 4-l iH r^. CN r~» 00 rH 00 on » -d- m CT. r~ CO ON yo >H CN CO r-\ m vO O 00 CN CN t- CO r^ CO m r-i O o 00 r^. 00 00 o> co f I vD r-i CN m tH CN r-\ CO CO CO co CO H m m i-H 00 m CO O O m m m m o H r-~ <* o «* M Si u 3 O Z P-, U. rH Ph 12 13 possible anomalous section of the curve is to show, then At must be taken to be 1. Table 5 shows x„, x, , and Ax for the anomalous regions of the average memory allotment curves for program INIT. We note that in the array reference string, no anomalies will be discovered if X is always changed by increments greater than 946 references. For the mixed string, no anomalies will be discovered if the increments of X are greater than 12375. We note that for this program the maximum anomalous change in the average memory allotment is 20.5 pages. Program FOURTR shows a more complicated anomalous behavior. We notice that there are overlapping anomalous regions. Thus, for array references, no anomalies will be discovered if x is incremented by values greater than 2320 - 60 = 2260 (the largest x minus the smallest x„ of the regions). For the mixed reference string, this number is 17205 Each one of the eight traces considered in detail in this paper was studied for a limited range of the window size, as can be seen in the figures. In Table 6, we show the minimum space- time 5 product inside this range, and the window size where this minimum is reached. A lower bound on the space-time product for window sizes beyond the range studied is also shown. This lower bound was computed with the following formula. LB(X ,L) = ST(X ,L) - (f(x*) - w(R,R)) * w(R,R) * L where x is the largest value of the window size used in the experiments. These numbers and those presented in the rest of the discussion are for L -> °° . When calculating the space-time cost, we use the expression R f(T) ST(X,L) = E w(t,x) + L • £ w.(t.,x) t=l i=l (footnote continued on page 16) 14 a 0) S o M O g cu s 0) oo CO In a) ^ td •- *-> 3 CO CJ H 4 H r«. 3 H H rH m IT) H -H u-1 n n fk >> * CTi * >4 S3 S >H >4 >H >4 O CD (-4 4-1 O CD 14-1 Q CO CD < H •H H B V H 2 13 >H r* r* [H S3 05 o c H < O 4-4 XI fi CD 3 00 O C PQ 5 OS vO vO vC vO ^D vO vD vO M o O O O o O O O CD X> rH rH rH rH rH rH rH rH 5 CD O M X X X X X X X X ►J 3 CO m v£> vO CiJ O CD r^ O ro CM 00 O^ r^ 00 3 g- vO O CM ro rH CM 00 m XI rH CM rH O XI rH H PI PL| O ^1 H CD C/) PQ 4-1 vD ^D \£> vO v£> vO vO v£> a a) /-~s O O o o O o o O 3 00 O H rH rH rH rH rH rH rH xi d o O CTJ o X X X X X X X X n Pd CM Pm * 00 «tf CN -) H CO r~ rH rH v£> o 3 W m CO 2 « S CD •H S c rH o O o rH vO rH vO •H C 00 O o o 00 f\ • • • • CO /--\ CO /"> CO /"s CO s^. m • 4-4 • 4-4 • 4-1 • CD CO CD CO CD CO CD CO ptf 4-4 CD ffi 4-1 CD Pi! <4-l CD Pi 14-4 CD >1 Pi >■> Ptf >% Pi >, Pi rd cd CO rd r4 rH r4 rH u rH }-i rH !-i rH r-l rH u rH S-i rH < < < < < < < ^ T , ST(x,L) > LB(x ,L) . From the previous information, we can see that anomalies occur for window sizes both smaller and larger than those where the minimum space- time product occur. 17 3. Conclusion The results of the experiments reported in this paper show that the anomalous behavior of the WS policy is not insignificant. A change in the window size of a given sign can cause more than 200% change in the average real memory allotted to a program in the unexpected direction and a corre- sponding change in the page fault rate of one order of magnitude (see Table 4) , Thus, this anomalous behavior of the WS policy cannot just simply be ignored. In real computer systems, people are interested in the turnaround time, throughput, and multiprogramming degree. The turnaround time of a job is related to its CPU execution time and paging rate. The window size of the WS policy controls the paging rate with no problems. In other words, the WS policy does not have the parameter-fault rate anomaly. Thus, the turnaround time of a job can be safely controlled under the WS policy. The throughput of a system, however, is dependent on its multi- programming degree [Denn78], which itself depends on the average real memory allotted to programs during their execution. Thus, the results in this paper cast some doubts on the reliability of the window size as a control of the multiprogramming degree. However, the limited scope of this work precludes making any final statement on this subject. More experiments, including experiments with nonnumerical programs, are required before such a final statement can be made. Acknowledgments We would like to thank Professor D. J. Kuck for his encouragement and support provided to this study. The excellent job done by Mrs. Vivian Alsip in typing this manuscript is gratefully acknowledged. 18 L L 600 2Ct K>£T£Ai3 C\ CoM?iLE£ k. StHOLAJOe SlAjIbTlCS Fig. 1. Trace Generation and Simulation Facility 19 p io 5 ; A G E F A u L L T s 10 4 -+■ icr 10' io 1 T 10 -U 10° 10" WINDOW SIZE 10 c 10' 10 Fig. 2(a). The Page Fault Curve for Program BASE (Array References) 20 ,6 ~ 10- 10' 10 1 -- 10 . 10 J io- JINDOW SIZE 10' 10- 1C Fig. 2(b). The Page Fault Curve for Program BASE (All References) 21 10 l — lcr io u io- WINDOW SIZE 10' 10' 10 Fig. 3(a). The Page Fault Curve for Program FOURTR (Array References) 22 P A G E F A U L T S .7000E-h6 t 6000E+6 . 5000E-h6 .400QE+6 .3000E-.-8 2000E-h6 1000E-k6 WINDOW SIZE Fig. 3(b). The Page Fault Curve for Program FOURTR (All References) P 10 A G E 5 T 10 10* - 10 £ " 10 1 "- 23 10* 10* 10" WINDOW SIZE 10' 10* 10* Fig. 4(a). The Page Fault Curve for Program INIT (Array References) 24 10 a. - 10 l T 10 10" 10" JDOW size 10' 10' 10 10- Fig. 4(b). The Page Fault Curve for Program INIT (All References) 25 p 10 A G E F A U L T S 5 T 10 10 3 " 10' 10" 10 l 10 l 10" WINDOW SIZE 10' 10' 10 Fig. 5(a). The Page Fault Curve for Program PAPUAL (Array References) 26 P 10 A G E F A u : io6 7 — \ 10 ' \ 10 A — 10 3 ~ I0 S1 10 1 -- 10 u 10" JDOW SIZE 10' 10" 10 10' . 5(b). The Page Fault Curve for Program PAPUAL (All References) 27 A 24 °" V E R A G £20 . E 200 S I 180 Z E 160 140 120 . 100 . ao 80 AQ 20 . 10 u 10 WINDOW SIZE 10 10' 10 Fig. 6(a). The Average Memory Allocation Curves for Program BASE (Array References) 28 240 . T A V E R A G £20 . E M E M 20 °- R v S 1 ISO. z E 160 140 . .20. 100 . ao. 60 40 20 10 J 10 WINDOW SIZE 10 io- 10 4 Fig. 6(b). The Average Memory Allocation Curves for Program BASE (All References) 29 10" 10 WINDOW SIZE 10' 10 N Fig. 7(a). The Average Memory Allocation Curves for Program FOURTR (Array References) 30 WINDOW SIZE Fig. 7(b). The Average Memory Allocation Curves for Program FOURTR (All References) 31 WINDOW SIZE Fig. 8(a). The Average Memory Allocation Curves for Program INIT (Array References) 32 55 50 i / i\ 45 i i 40 \ i I 35 \ i / J i i 30 / / / / I as / / // i 20 H i i 15 1 i // 10 / / / / 5 ^^r^^ 1 1 — i — i 1 10 u 10" WINDOW SIZE 10 £ 10 ; 10 10- Fig. B(b). The Average Memory Allocation Curves for Program INIT (All References) 33 450 *00 350 300 250 200 150 100. 50. 10 ,J 10 WINDOW SIZE 10 10' 10 Fig. 9(a). The Average Memory Allocation Curves for Program PAPUAL (Array References) 34 *50 400 . - 350. t- 300 350 300 . + 150 100. 50 . 10 J 10 WINDOW SIZE Fig. 9(b). The Average Memory Allocation Curves for Program PAPUAL (All References) 35 A £4 ° V E R A G £20 E M E M <20 ° R v S 1 ISO. z E 160 . 140 120 . - 100. SO . 60 . iQ . T 20 . 10 ( io- 10' L = L = 20 L = 200 L = 2000 L -> °° 10" 10 WINDOW SIZE Fig. 10. The Average Memory Allotment Curves for Program BASE foi Different Values of Page Fault Service Time 36 P 10 A G E F A U L T i n* S 10 5 T 10 3 -" 10 2 _. 10 1 "■ 10 G ,0 10^ io- 1 - AVERAGE MEMORY SIZE 10' 10" Fig. 11(a). The Page Faults vs. Average Memory Curves for Program BASE (Array References) 37 P 10 A G E F A U L T S 6 T 10 5 ~- 10' 10' 10' 10 1 -- 10' io u io- 1 - AVERAGE MEMORY SIZE 10' 10' Fig. 11(b). The Page Faults vs. Average Memory Curves for Program BASE (All References) 38 P 10 5 A G E "^-^^^^ F A U L S 10 1 10 3 " 1 |\ ^ 10 2 " 10 1 " 1Q°- 1 1 10 u 10 AVERAGE MEMORY SIZE 10' Fig. 12(a). The Page Faults vs. Average Memory Curves for Program FOURTR (Array References) 39 P 10 A G M 6 F A U L T S 10 5 " 10 10' 10 2 "- 10 1 -~ 10' 10 u 10 AVERAGE MEMORY SIZE 10' Fig. 12(b). The Page Faults vs. Average Memory Curves for Program FOURTR (All References) 40 P 10 A G E F A U L T S 5 T 10' 10 3 " 10 2 " 10 1 -" 10' io 1 -* 10 average memory size 10' Fig. 13(a). The Page Faults vs. Average Memory Curves for Program INIT (Array References) 41 icr io- AVERAGE MEMORY SIZE 10' Fig. 13(b). The Page Faults vs. Average Memory Curves for .Program INIT (All References) 42 P 10 A G E F A U L T S 5 T 10 4 -" 10" 10 2 "- 10" 10 G 10 u 10 x AVERAGE MEMORY SIZE 10 ( 10' Fig. 14(a). The Page Faults vs. Average Memory Curves for Program PAPUAL (Array References) 43 P 10 A G E 7 T U 10 L T S 10 6 " 5 " 10 4 "- 10 3 " 10 2 " 10 1 " 10' 10° 10 x AVERAGE MEMORY SIZE 10 ( 10' Fig. 14(b). The Page Faults vs. Average Memory Curves for Program PAPUAL (All References) 44 A V E R A G E M E M R Y S I Z E M, M, WINDOW SIZE Fig. 15. Section of a Memory Allotment Curve Showing the Parameter- Real Memory Anomaly 45 R E L A T I V E S T / P R D U c T E R R R - .1 - .a T - . 5 - - .6 - . 7 i- 10' 10" 10' 10 v 10 WINDOW SIZE Fig. 16(a). Space-Time Product Relative Error Curves for Program BASE (Array References) 46 / p R D D "■ U c T E So R -. 5 -.8 2 - .3 - - . ^ "*■ 10 u 10- WINDOW SIZE 10' 1CT 10 Fig. 16(b). Space-Time Product Relative Error Curves for Program BASE (All References) 47 .3 S T / P R a D u .a c j E R R a o. - . i t - .a ■+■ -3 t / / hi / io u ic- WINDOW SIZE 10' 10' 10 Fig. 17(a). Space-Time Product Relative Error Curves for Program FOURTR (Array References) 48 10~ 10 WINDOW SIZE Fig. 17(b). Space-Time Produce Relative Error Curves for Program FOURTR (All References) 49 lO" 10 WINDOW SIZE 10' 10' 10 Fig. 18(a). Space-Time Product Relative Error Curves for Program INIT (Array References) 50 10" 10 WINDOW SIZE Fig. 18(b). Space-Time Product Relative Error Curves for Program INIT (All References) . 1 E R 0- R - .a 51 - . l - .3 _ A -.5 10 l id- ler icy 10 WINDOW SIZE Fig. 19(a). Space-Time Product Relative Error Curves for Program PAPUAL (Array References) 52 25 .2 .15 . 1 05 -.05 - . 1 - . 15 + lO*" 1 10 J WINDOW SIZE 10' 10' 10 10' Fig. 19(b). Space-Time Product Relative Error Curves for Program PAPUAL (All References) 53 References [AbuS78] W. Abu-Sufah, "Improving the Performance of Virtual Memory Computers," Ph.D. thesis, University of Illinois at Urbana-Champaign, Dept. of Computer Science Rpt. No. 78-945, Nov. 1978. [AbKL79] W. Abu-Sufah, D. Kuck and D. Lawrie, "Automatic Program Transformations for Virtual Memory Computers," Proc. of the 1979 Nat'l. Computer Conf . , pp. 969-974, June 1979. [AbKL80] W. Abu-Sufah, D. J. Kuck and D. H. Lawrie, "On the Performance Enhancement of Paging Systems through Program Analysis and Transformations," to appear in IEEE Trans, on Computers , 1981. [BDSM80] R. Budzinski, E. Davidson, H. Stone and W. Mayeda, "DMIN— An Optimal Algorithm for Dynamic Allocation in a Virtual Memory Computer," to appear in IEEE Trans, on Software Engineering , 1980. [BuDa80] R. Budzinski and E. Davidson, "A Comparison of Dynamic and Static Virtual Memory Allocation Algorithm," to appear in IEEE Trans, on Software Engineering , 1980. [Denn70] P. J. Denning, "Virtual Memory," Computing Surveys , Vol. 2, No. 3, pp. 153-189, Sept. 1970. [Denn78] P. J. Denning, "Optimal Multiprogrammed Memory Management," in Current Trends in Programming Methodology III , K. M. Chandy and R. Yeh, Eds., Englewood Cliffs, NJ: Prentice- Hall, pp. 298-322, 1978. [Denn80] P. J. Denning, "Working Sets Past and Present," IEEE Trans . on Software Engineering , Vol. SE-6, No. 1, pp. 64-84, Jan. 1980. 54 [DKLP76] P. J. Denning, K. C. Kahn, J. Leroudier, D. Potier and R. Suri, "Optimal Multiprogramming," Acta Informatica , Vol. 7, Fasc. 2, pp. 197-216, 1976. [FrGG78] M. A. Franklin, G. S. Graham and R. K. Gupta, "Anomalies with Variable Partition Paging Algorithms," Comm. of the ACM , Vol. 21, No. 3, pp. 232-236, Mar. 1978. [Grah76] G. S. Graham, "A Study of Program and Memory Policy Behavior," Ph.D. thesis, Purdue Univ., Dept. of Comput. Sci., Dec. 1976. [GrDe77] G. S. Graham and P. J. Denning, "On the Relative Controllability of Memory Policies," in Computer Performance , K. M. Chandy and M. Reiser, Eds., Amsterdam, The Netherlands: North- Holland, pp. 411-428, Aug. 1977. [Gupt74] R. K. Gupta, "Program Reference Behavior and Dynamic Memory Management," D.Sc. thesis, Washington Univ., St. Louis, MO, Dept. of Elect. Eng. , Dec. 1974. [MaBa76] A. W. Madison and A. P. Batson, "Characteristics of Program Localities," Comm. of the ACM , Vol. 19, No. 5, pp. 285-294, May 1976. [McCo69] A. C. McKellar and E. G. Coffman, "Organizing Matrices and Matrix Operations in Paged Memory Systems," Comm. of the ACM , Vol. 12, No. 3, pp. 153-165, Mar. 1969. [MGST70] R. L. Mattson, J. Gecsei, D. R. Slutz and I. L. Traiger, "Evaluation Techniques for Storage Hierarchies," IBM Systs . Journ. , Vol. 9, No. 2, pp. 78-117, 1970. 55 [PrFa76] B. G. Prieve and R. S. Fabry, "VMIN — An Optimal Variable- Space Page Replacement Algorithm," Comm. of the ACM , Vol. 19, No. 5, pp. 295-297, May 1976. BIBLIOGRAPHIC DATA SHEET 1. Report No. UIUCDCS-R-80-1043 2. 3. Recipient's Accession No. 4. Title and Subtitle SOME RESULTS ON THE WORKING SET ANOMALIES IN NUMERICAL PROGRAMS 5- Report Date November 1980 6. 7. Author(s) Walid A. Abu-Sufah and David A. Padua 8. Performing Organization Rept. No. UIUCDCS-R-80-1043 9. Performing Organization Name and Address University of Illinois at Urbana- Champaign Department of Computer Science Urbana, Illinois 61801 10. Project/Task/Work Unit No. 11. Contract /Grant No. US NSF MCS76-81686 12. Sponsoring Organization Name and Address National Science Foundation Washington, D. C. 20550 13. Type of Report & Period Covered Technical Report 14. 15. Supplementary Notes 16. Abstracts This paper shows that the Working Set parameter-real memory and real memory-fault rate anomalies mentioned by Franklin, Graham, and Gupta in [FrGG78] do occur in traces generated by real programs. The results of the detailed investigation of this anomalous behavior in four Fortran programs are presented. In some cases, a drop of a factor of two in the average memory allotment is observed when the window size is increased. In some instances, a bigger memory allotment means an order of magnitude increase in page faults. 17. Key Words and Document Analysis. 17a. Descriptors Memory Management Multiprogramming Working Set Working Set Anomaly Program Behavior 17b. Identifiers/Open-Ended Terms 17c. COSATI Field/Group 18. Availability Statement T?l?T IT ACT? TT\IT TMTTT?T» 19. Security Class (This Report) UNCLASSIFIED 21. No. of Pages 59 KLLLAbL UlNLlMllhD 20. Security Class (This Page UNCLASSIFIED 22. Price FORM NTIS-35 (10-70) USCOMM-DC 40329-P71