Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Improving performance by strategy-independent program restructuring using bounded locality intervals Law, Bernard Ming-Ki 1981

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-UBC_1981_A6_7 L39.pdf [ 3.07MB ]
Metadata
JSON: 831-1.0051822.json
JSON-LD: 831-1.0051822-ld.json
RDF/XML (Pretty): 831-1.0051822-rdf.xml
RDF/JSON: 831-1.0051822-rdf.json
Turtle: 831-1.0051822-turtle.txt
N-Triples: 831-1.0051822-rdf-ntriples.txt
Original Record: 831-1.0051822-source.json
Full Text
831-1.0051822-fulltext.txt
Citation
831-1.0051822.ris

Full Text

IMPROVING PERFORMANCE BY STRATEGY-INDEPENDENT PROGRAM RESTRUCTURING USING BOUNDED LOCALITY INTERVALS by BERNARD MING-KI LAW B.Math., The U n i v e r s i t y of W a t e r l o o , 1978 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n THE FACULTY OF GRADUATE STUDIES (Department of Computer S c i e n c e ) We a c c e p t t h i s t h e s i s as c o n f o r m i n g t o the r e q u i r e d s t a n d a r d THE UNIVERSITY OF BRITISH COLUMBIA J u l y 1981 (c) B e r n a r d M i n g - k i Law, 1981 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t f r e e l y a v a i l a b l e for reference and study. I further agree that permission for extensive copying of t h i s thesis for s c h o l a r l y purposes may be granted by the head of my department or by his or her representatives. It i s understood that copying or p u b l i c a t i o n of t h i s thesis for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of COMPUTER £C(£/UC£ The University of B r i t i s h Columbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 Date /7CTW.r lift ABSTRACT An e f f i c i e n t s t r a t e g y - i n d e p e n d e n t program r e s t r u c t u r i n g a l g o r i t h m based on the e m p i r i c a l s t u d i e s of phases and t r a n s i t i o n s i n the s y m b o l i c r e f e r e n c e s t r i n g s of r e a l programs i s dev e l o p e d . The a l g o r i t h m i s f o r m u l a t e d on the b a s i s t h a t the m a j o r i t y of the page f a u l t s o c cur d u r i n g phase t r a n s i t i o n s . Thus emphasis i s p l a c e d i n g r o u p i n g those r e l o c a t a b l e b l o c k s r e f e r e n c e d d u r i n g phase t r a n s i t i o n s i n the same pages. Some parameters t o c h a r a c t e r i z e program b e h a v i o r a r e a l s o e s t a b l i s h e d . The purpose i s t o study the r e l a t i o n s h i p between t h e s e parameters and the performance of the program. An experiment t o compare the performance improvement of the proposed r e s t r u c t u r i n g a l g o r i t h m and o t h e r major e x i s t i n g a l g o r i t h m s i s conducted. The performance i n d i c e s chosen a r e the mean working s e t s i z e and the page f a u l t r a t e . The problem of d a t a dependency, the c o s t as w e l l as the p o r t a b i l i t y of program r e s t r u c t u r i n g p r o c e d u r e s a re d i s c u s s e d . TABLE OF CONTENTS ABSTRACT ." i i LIST OF TABLES AND FIGURES v ACKNOWLEDGMENT v i 1 I n t r o d u c t i o n 1 1.1 Program b e h a v i o r 1 1.2 Program L o c a l i t y 2 1.3 Program R e s t r u c t u r i n g 3 1.4 P r e v i o u s work on Dynamic R e s t r u c t u r i n g A l g o r i t h m . 4 1.4.1 Nearness M a t r i x 5 1.4.2 E x t e n s i o n of Nearness M a t r i x 5 1.4.3 C r i t i c a l L e a s t R e c e n t l y Used (CLRU) M a t r i x . . 6 1.4.4 C r i t i c a l Working Set (CWS) M a t r i x 6 1.5 Examples of C l u s t e r i n g A l g o r i t h m s 8 1.5.1 N u c l e u s - c o n s t r u c t i n g 9 1.5.2 H i e r a r c h i c a l C l a s s i f i c a t i o n . . 10 1 .6 O b j e c t i v e s 12 2 BLI R e s t r u c t u r i n g A l g o r i t h m 15 2.1 P h a s e / T r a n s i t i o n Model 15 2.2 Bounded L o c a l i t y I n t e r v a l 1V 2.3 The BLI R e s t r u c t u r i n g A l g o r i t h m 21 2.3.1 M o t i v a t i o n 21 2.3.2 The A l g o r i t h m 23 2.3.3 Examples of BLI R e s t r u c t u r i n g H e u r i s t i c 25 3 D e s c r i p t i o n of the Experiment 27 3 . 1 Overview 27 3 . 2 Approach 28 3.3 Parameters 29 3.3.1 Performance I n d i c e s 29 3.3.2 C o n t r o l l a b l e F a c t o r s 30 3.3.3 O b s e r v a b l e F a c t o r s 31 3.4 Measurement T o o l s 32 3.4.1 Data C o l l e c t i o n and R e d u c t i o n 32 3.4.2 R e s t r u c t u r i n g A l g o r i t h m s 34 3.4.3 Working Set P o l i c y S i m u l a t o r 35 3.5 D e s i g n and Implementation 35 4 D i s c u s s i o n of R e s u l t s 40 4.1 Performance Improvement 40 4.2 Data S e n s i t i v i t y 47 4.3 P o r t a b i l i t y 50 4.4 Cost • 51 5 C o n c l u s i o n and S u g g e s t i o n s f o r F u t u r e R e s e a r c h . . 55 5.1 C o n c l u s i o n 55 5.2 S u g g e s t i o n s f o r F u t u r e Research 56 BIBLIOGRAPHY 60 APPENDIX I : R e f e r e n c e S t r i n g s 64 APPENDIX I I : P a g i n g A l g o r i t h m s 65 APPENDIX H a : The L e a s t R e c e n t l y Used (LUR) paging a l g o r i t h m 69 APPENDIX l i b : The Working Set pa g i n g a l g o r i t h m 70 APPENDIX I I I : An Example t o i l l u s t r a t e the H i e r a r c h i c a l C l a s s i f i c a t i o n C l u s t e r i n g A l g o r i t h m 71 V LIST OF TABLES AND FIGURES T a b l e 3.1 F a c t o r s and L e v e l s f o r the Experiment 39 T a b l e 4.1 Comparsion of the 4 r e s t r u c t u r i n g a l g o r i t m s on p e r c e n t a g e r e d u c t i o n i n page f a u l t r a t e . 43 T a b l e 4.2 Comparsion of the 4 r e s t r u c t u r i n g a l g o r i t m s on p e r c e n t a g e r e d u c t i o n i n average working s e t s i z e 44 T a b l e 4.3 Average t r a n s i t i o n s e t s i z e s and phase s e t s i z e s ( b l o c k s ) 45 T a b l e 4.4 R e s u l t s of an experiment on i n p u t dependency 49 T a b l e 4.5 R e s u l t s of an experiment on i n p u t dependency 50 T a b l e 4.6 Sample Cost of the R e s t r u c t u r i n g P r o c e d u r e . 53 F i g u r e 2.1 H i e r a r c h y of B L I ' s f o r an example s y m b o l i c r e f e r e n c e s t r i n g 19 F i g u r e 4.1 Working s e t s i z e d i s t r i b u t i o n s of CWS and TC2 r e s t r u c t u r i n g a l g o r i t h m s 54 v i ACKNOWLEDGMENT I would l i k e t o thank Dr. S. Chanson f o r h i s i d e a s and guidance throughout t h i s work and f o r h i s c a r e f u l r e a d i n g s of the t h e s i s . I a l s o g r e a t l y a p p r e c i a t e the e f f o r t s of Dr. J . Peck i n h i s r e a d i n g of the d r a f t s and h i s comments. F i n a l l y , I would l i k e t o acknowledge my f a m i l y , e s p e c i a l l y my f a t h e r , f o r t h e i r moral and f i n a n c i a l s u p p o r t . I n t r o d u c t i o n 1 1 I n t r o d u c t i o n 1.1 Program B e h a v i o r In a v i r t u a l memory system, the performance of a program i n e x e c u t i o n depends, t o a l a r g e e x t e n t , on how i t s i n s t r u c t i o n code and d a t a a r e d i s t r i b u t e d between the l e v e l s of the memory h i e r a r c h y , and on how t h i s i n f o r m a t i o n i s a c c e s s e d . T h i s i s one of the reasons f o r the i n t e r e s t i n program b e h a v i o r the study of the mechanism u n d e r l y i n g the o b s e r v e d memory r e f e r e n c e p a t t e r n of a program. Because of the g r e a t i n f l u e n c e of program b e h a v i o r on the performance of systems as w e l l as programs r u n n i n g on them, the study of program b e h a v i o r i s e s s e n t i a l t o the d e s i g n of e f f i c i e n t systems and programs. V a r i o u s models of program b e h a v i o r have been d e v e l o p e d s i n c e the l a t e s i x t i e s , f o r examples: the Working Set Model d e s c r i b e d by Denning [ 1 1 ] , B e l a d y ' s l i f e t i m e f u n c t i o n [ 6 ] , the n o t i o n of Bounded L o c a l i t y I n t e r v a l (BLI) d e f i n e d by Madison and Batson [ 2 5 ] , the LRU Stack Model [31] and the p h a s e / t r a n s i t o n Model d e s c r i b e d i n Graham's Ph.D. t h e s i s i n 1976 [ 3 2 ] . I n t r o d u c t i o n 2 In o r d e r t o p r o v i d e the u l t i m a t e and i n d i s p e n s a b l e t e s t f o r the v a l i d i t y of models, measurement i s n e c e s s a r y , i n a l l c a s e s , t o g a t h e r i n f o r m a t i o n on how r e a l programs r e f e r e n c e t h e i r a d d r e s s spaces. From these measurement d a t a , we hope t o g a i n some i n s i g h t t o q u e s t i o n s such a s : What i s the r e l a t i o n s h i p between programming s t y l e such as s t r u c t u r e d programming and r e f e r e n c e p a t t e r n ? What i s the r e l a t i o n s h i p between program b e h a v i o r and program performance How s e n s i t i v e i s program b e h a v i o r t o i n p u t d a t a ? To t h i s end, i t was suggested by Batson [2] t h a t measurement and a n a l y s i s of program b e h a v i o r c o u l d be done a t the s y m b o l i c l e v e l r a t h e r than a t the l e v e l of machine language. T h i s approach g i v e s us a c l e a r e r p i c t u r e of the flo w of the program d u r i n g e x e c u t i o n c o r r e s p o n d i n g t o the program's h i g h - l e v e l c o n s t r u c t s . 1.2 Program L o c a l i t y Many measurement e x p e r i m e n t s have been performed t o stud y the memory r e f e r e n c e b e h a v i o r . A commonly ob s e r v e d p r o p e r t y i s t h a t a program i n e x e c u t i o n f a v o r s a subset of i t s segments ( b l o c k s ) d u r i n g extended p e r i o d s of time [ 1 8 ] . T h i s p r o p e r t y of r e f e r e n c e c l u s t e r i n g has come t o be known as program l o c a l i t y or l o c a l i t y of r e f e r e n c e . Numerous s t u d i e s [26,5,7,8,29] have i n d i c a t e d t h a t l o c a l i t y i s t o be found i n most programs t o a t l e a s t some degree. A l s o i t has I n t r o d u c t i o n 3 been r e p o r t e d [20,22,23,1] t h a t by i m p r o v i n g the degree of l o c a l i t y of the program through r e o r g a n i z a t i o n .(see s e c t i o n 1.2) of i t s r e l o c a t a b l e b l o c k s ( a r r a y s , p r o c e d u r e s e t c . ) , s u b s t a n t i a l improvements i n program and system performance can be o b t a i n e d . 1.3 Program R e s t r u c t u r i n g Programs w r i t t e n under the assumption t h a t main memory i s v i r t u a l l y u n l i m i t e d c a n, when e x e c u t i n g i n a paging system, r e s u l t i n s i t u a t i o n s when much more time i s spent p e r f o r m i n g p a g i n g I/O o p e r a t i o n s than e x e c u t i n g the program's i n s t r u c t i o n s . As the r a t e of pa g i n g I/O i n c r e a s e s , system performance degrades. I t i s o b v i o u s t h a t i t would be h i g h l y d e s i r a b l e t o m i n i m i z e the page f a u l t r a t e . For l a r g e programs, some a l t e r n a t i v e s t o complete r e w r i t i n g of the codes a r e c l e a r l y d e s i r a b l e . The i d e a of program r e s t r u c t u r i n g was i n i t i a t e d by the experiment performed i n 1967 by L.W. Comeau [ 1 0 ] . In h i s ex p e r i m e n t , Comeau p o i n t e d out t h a t the rearrangement of r e l o c a t a b l e s e c t o r s Of code over v i r t u a l pages can have a prof o u n d e f f e c t on pa g i n g performance. Changing the l o a d - t i m e o r d e r i n g of the modules i n a m o n i t o r system r e s u l t e d i n a f i v e - t o - o n e r e d u c t i o n i n the number of page f a u l t s g e n e r a t e d d u r i n g the c o u r s e of an assembly. I n t r o d u c t i o n 4 The program t o be r e s t r u c t u r e d i s d i v i d e d i n t o , r e l o c a t a b l e b l o c k s , such as a r r a y s , p r o c e d u r e s , f u n c t i o n s e t c . . We s h a l l assume t h a t the average s i z e of a r e l o c a t a b l e b l o c k ( the term " b l o c k " w i l l be used h e r e a f t e r t o mean a segment of r e l o c a t a b l e codes) i s s m a l l compared t o the s i z e of a page ( f o r example, between o n e - t e n t h and o n e - t h i r d of the page s i z e ) so t h a t s e v e r a l b l o c k s can be packed i n t o a page. The o b j e c t i v e of r e s t r u c t u r i n g i s t o r e o r g a n i z e the b l o c k s of a program such t h a t t h o s e t h a t a r e needed w i t h i n a r e l a t i v e l y s h o r t time of one another a r e found e i t h e r i n the same v i r t u a l page or i n pages t h a t would o t h e r w i s e tend t o be i n p h y s i c a l memory a t the same t i m e . T h i s has the e f f e c t of r e d u c i n g the page f a u l t r a t e . Program r e s t r u c t u r i n g can g e n e r a l l y be.broken down i n t o two phases: (1) A p r e p r o c e s s i n g phase which d e f i n e s and computes the " d e s i r a b i l i t y " of g r o u p i n g b l o c k s t o g e t h e r based on e x a m i n a t i o n of the s y m b o l i c b l o c k r e f e r e n c e s t r i n g . The i n f o r m a t i o n g a t h e r e d can be s t o r e d i n a d e s i r a b i l i t y m a t r i x M where each e n t r y m i j of the m a t r i x r e p r e s e n t s the d e s i r a b i l i t y of p u t t i n g b l o c k s i and j i n the same page. (2) A c l u s t e r i n g phase which groups the s t r o n g l y r e l a t e d b l o c k s w i t h h i g h d e s i r a b i l i t y i n t o common pages, I n t r o d u c t i o n 5 s u b j e c t t o the c o n s t r a i n t t h a t each c l u s t e r f i t s i n t o a s i n g l e page. 1.4 P r e v i o u s work on Dynamic R e s t r u c t u r i n g A l g o r i t h m s I n v a r i a b l y , dynamic r e s t r u c t u r i n g a l g o r i t h m s a r e based on a b l o c k r e f e r e n c e s t r i n g , (see Appendix I I ) c o l l e c t e d d u r i n g e x e c u t i o n , r e p r e s e n t i n g the dynamic b e h a v i o r of the program t o be r e s t r u c t u r e d . In the f o l l o w i n g examples, we assume t h a t a l l the e n t r i e s i n the d e s i r a b i l i t y m a t r i x v i n q u e s t i o n a r e i n i t i a l i z e d t o z e r o . 1.4.1 Nearness M a t r i x The Nearness M a t r i x was f i r s t i n t r o d u c e d by H a t f i e l d and G e r a l d i n 1971 [ 2 3 ] . M a t r i x A = [ a i j ], i s a symmetric nxn m a t r i x w i t h i n d i c e s l a b e l l e d by b l o c k numbers, where n i s the t o t a l number of b l o c k s i n the program. The element a i j i s the number of t i m e s a r e f e r e n c e t o b l o c k j i m m e d i a t e l y f o l l o w s a r e f e r e n c e t o b l o c k i . That i s t o say, a i j r e p r e s e n t s the d e s i r a b i l i t y of p l a c i n g two b l o c k s i and j i n the same page. 1.4.2 E x t e n s i o n of Nearness M a t r i x The a l g o r i t h m proposed by Masuda [ 2 7 ] , i s based on an extended d e f i n i t i o n of the n o t i o n of n e a r n e s s : two b l o c k s i I n t r o d u c t i o n 6 and j a r e near not o n l y when they are c o n s e c u t i v e l y r e f e r e n c e d , but a l s o when r e f e r e n c e t o them f o l l o w each o t h e r a t a s h o r t d i s t a n c e i n t i m e . The d e s i r a b i l i t y m a t r i x B = [ b i j ] i s a symmetric nxn m a t r i x w i t h rows and columns l a b e l l e d by the b l o c k numbers. At each new r e f e r e n c e t o b l o c k i , i s s u e d a t v i r t u a l time t by the program, b i j w i l l be i n c r e m e n t e d by one, f o r a l l j , where j has been r e f e r e n c e d d u r i n g the v i r t u a l time i n t e r v a l ( t - T , t ) where T i s a chosen c o n s t a n t known as the window s i z e . 1.4.3 C r i t i c a l L e a s t R e c e n t l y Used (CLRU) M a t r i x The CLRU r e s t r u c t u r i n g method [22] i s one of the r e s t r u c t u r i n g methods t h a t t a k e s the memory management p o l i c y i n t o a c c o u n t . They a r e a l s o known as S t r a t e g y - O r i e n t e d r e s t r u c t u r i n g methods. In t h i s c a s e , the LRU p o l i c y (see Appendix Ia) i s the memory p o l i c y i n q u e s t i o n . The CLRU m a t r i x C = [ c i j ] i s an nxn m a t r i x w i t h rows and columns l a b e l l e d by b l o c k numbers. By s i m u l a t i n g the demand paging LRU page replacement a l g o r i t h m on the page r e f e r e n c e s t r i n g , we c o u l d i d e n t i f y when the page - f a u l t s would occur and the s e t of pages t h a t a r e i n main memory a t those t i m e s . Assuming a program i s g i v e n m page frames i n main memory, the CLRU a l g o r i t h m w i l l increment a l l the r e l a t e d elements c i j by one, where i i s the b l o c k which has j u s t g e n e r a t e d a page f a u l t and j c o v e r s the s e t of m b l o c k s I n t r o d u c t i o n 7 at the t o p of the LRU b l o c k s t a c k a t the time of the page f a u l t . The i d e a i s t h a t i t i s d e s i r a b l e t o put b l o c k i i n the same page w i t h one of the b l o c k s a l r e a d y i n p r i m a r y memory as then the r e f e r e n c e t o b l o c k i w i l l not cause a page f a u l t . T h i s p h i l o s o p h y can be used on o t h e r memory management p o l i c i e s such as the w o r k i n g s e t p o l i c y d e s c r i b e d i n the next s e c t i o n . 1.4.4 C r i t i c a l Working Set (CWS) M a t r i x The CWS method [22] a l s o b e l o n g s t o the S t r a t e g y - O r i e n t e d r e s t r u c t u r i n g f a m i l y u s i n g the Working Set p o l i c y (see Appendix l b ) as the page replacement p o l i c y . A c r i t i c a l r e f e r e n c e i s one which causes a page f a u l t t o o c c u r . The d e s i r a b i l i t y m a t r i x D = [ d i j ] i s a symmetric nxn m a t r i x w i t h rows and columns l a b e l l e d by b l o c k names. S i m i l a r t o the CLRU a l g o r i t h m , the CWS a l g o r i t h m increments a l l the r e l a t e d elements d i j by one, where b l o c k i i s the c r i t i c a l r e f e r e n c e and j i s an element i n the b l o c k working set W(t,T), f o r a l l j i n W(t,T). ( A program's b l o c k w o r k i n g s e t W(t,T) a t v i r t u a l time t i s d e f i n e d t o be the se t of d i s t i n c t b l o c k s r e f e r e n c e d i n the time i n t e r v a l (t-T+1,t) where T i s the window s i z e . ) A l t h o u g h the Nearness M a t r i x i s v e r y s i m p l e , the main weakness of the a l g o r i t h m i s t h a t i t o n l y c o n s i d e r s a d j a c e n t I n t r o d u c t i o n 8 p a i r s of r e f e r e n c e s . Thus i t might have t r o u b l e i d e n t i f y i n g the major l o c a l i t i e s which r e q u i r e s a more g l o b a l e x a m i n a t i o n of the r e f e r e n c e p a t t e r n . The extended v e r s i o n of the Nearness M a t r i x t r i e s t o remedy t h i s . problem by c o n s i d e r i n g a l a r g e r window of T r e f e r e n c e s (T i s u s u a l l y much g r e a t e r than 2 ) . The d i f f i c u l t y here i s i n the c h o i c e of T. As l o c a l i t i e s have d i f f e r e n t s i z e s and a r e g e n e r a l l y d i f f i c u l t t o p r e d i c t ( o f t e n depend on the i n p u t d a t a ) , and the overheads of the a l g o r i t h m s i n c r e a s e a p p r o x i m a t e l y e x p o n e n t i a l l y w i t h T, i t i s easy t o see why i t w i l l be d i f f i c u l t t o choose a p r o p e r v a l u e of T. The S t r a t e g y - O r i e n t e d r e s t r u c t u r i n g a l g o r i t h m s work b e t t e r than the e x i s t i n g n o n - s t r a t e g y - s p e c i f i c ones. The major drawback i s t h a t f o r some complex memory management p o l i c i e s , i t may not be p o s s i b l e to f i n d the c o r r e s p o n d i n g , r e s t r u c t u r i n g a l g o r i t h m s . I f the s t r a t e g y assumed by the a l g o r i t h m i s d i f f e r e n t from the one a c t u a l l y used by the system, the r e s u l t c o u l d be worse than t h a t r e s u l t i n g from the use of a s t r a t e g y - i n d e p e n d e n t r e s t r u c t u r i n g a l g o r i t h m . 1 . 5 Examples of C l u s t e r i n g A l g o r i t h m s The f u n c t i o n of a c l u s t e r i n g a l g o r i t h m i s t o d e t e r m i n e , based on the d e s i r a b i l i t y m a t r i x , which b l o c k s s h o u l d be grouped i n t o common pages, so as t o m i n i m i z e the number of I n t r o d u c t i o n 9 page f a u l t s produced by the program. V a r i o u s methods used i n r e s t r u c t u r i n g e x p e r i m e n t s can be found i n the l i t e r a t u r e [23,27,19,1]. Most of them, as r e p o r t e d , are r e a s o n a b l y e f f i c i e n t a l g o r i t h m s a l t h o u g h none of them i s o p t i m a l and some c o s t l e s s than the o t h e r s . The major c o n s t r a i n t of a c l u s t e r i n g a l g o r i t h m i s t h a t the sum of s i z e s of a l l b l o c k s i n a c l u s t e r cannot exceed the page s i z e . T h i s g i v e s r i s e t o problems such as a l i g n i n g b l o c k s t o page b o u n d a r i e s , a v o i d i n g o v e r l a p s of b l o c k s over page b o u n d a r i e s and a v o i d i n g e x c e s s i v e f r a g m e n t a t i o n due t o wasted space a t the end of pages. Two ty p e s of c l u s t e r i n g a l g o r i t h m which have been used i n pa s t e x p e r i m e n t s are p r e s e n t e d i n the f o l l o w i n g s e c t i o n s . The f i r s t i s based on a s i m p l e method c a l l e d n u c l e u s - c o n s t r u c t i n g [ 1 ] , and the o t h e r i s a more s o p h i s t i c a t e d one based on h i e r a r c h i c a l c l a s s i f i c a t i o n [ 1 ] , 1.5.1 N u c l e u s - c o n s t r u c t i n g T h i s method presumes t h a t t h e r e e x i s t s a n u c l e u s of b l o c k s of the program more f r e q u e n t l y used than the o t h e r s and i t t r i e s t o i d e n t i f y such n u c l e u s . The method d e f i n e s a weight wi f o r each b l o c k i , such t h a t wi i s e q u a l t o the sum of a l l the elements i n row i and column i of the d e s i r a b i l i t y m a t r i x . In o r d e r t o t a k e i n t o account the s i z e of the b l o c k , a d e n s i t y f u n c t i o n d i f o r each b l o c k i i s de t e r m i n e d from the weight wi as I n t r o d u c t i o n 10 S d i = * wi s i where s i = s i z e of b l o c k i S = mean s i z e of a l l b l o c k s I t o r d e r s the b l o c k s i n a l i s t i n d e c r e a s i n g o r d e r of t h e i r d e n s i t i e s . Then i t p l a c e s the b l o c k s i n t o a page i n the same o r d e r except t h o s e which cause an o v e r l a p , u n t i l the page i s f i l l e d or the l i s t i s c o m p l e t e l y examined. The next page i s then f i l l e d i n the same way w i t h a new l i s t composed of the r e m a i n i n g b l o c k s o r d e r e d i n the same manner. T h i s p r o c e s s i s r e p e a t e d u n t i l the e n t i r e l i s t i s exh a u s t e d . The wasted space a t the end of a page, as r e p o r t e d i n [ l ] , w a s on the average 2 t o 8% w i t h the above a l g o r i t h m . In g e n e r a l , no compaction i s made i f the t o t a l waste i s l e s s than or e q u a l t o one v i r t u a l page. H a t f i e l d and G e r a l d [23] p o i n t e d out t h a t i t may be b e t t e r t o permit some o v e r l a p s t o a v o i d e x c e s s i v e f r a g m e n t a t i o n . A l t h o u g h t h i s i s a v e r y f a s t and i n e x p e n s i v e c l u s t e r i n g a l g o r i t h m a major p i t f a l l i s t h a t i t does not l e n d i t s e l f i n f i n d i n g the d i f f e r e n t n u c l e i of a program i f they e x i s t . T h i s i s because b l o c k s b e l o n g i n g t o d i f f e r e n t n u c l e i a r e mixed i f they happen t o have s i m i l a r d e n s i t i e s . I n t r o d u c t i o n 11 The h i e r a r c h i c a l c l a s s i f i c a t i o n t e c h n i q u e d e s c r i b e d i n the f o l l o w i n g s e c t i o n overcomes t h i s problem. 1.5.2 H i e r a r c h i c a l C l a s s i f i c a t i o n L e t J be the s e t of b l o c k s t o be c l a s s i f i e d . L e t D = [ d i j ] be the d e s i r a b i l i t y m a t r i x o b t a i n e d i n the p r e p r o c e s s i n g phase. Our g o a l i s t o c l a s s i f y J i n t o s u b s e t s , each of which r e p r e s e n t s a c l u s t e r of b l o c k s t h a t are s t r o n g l y a s s o c i a t e d t o each o t h e r based on the g i v e n d e s i r a b i l i t y measure. G i v e n a l i s t of b l o c k s b i , i=1,..,n w i t h s i z e s i and page s i z e P, the c l u s t e r i n g a l g o r i t h m works as f o l l o w s : The c o n s t r u c t i o n of the h i e r a r c h y i s t o be c a r r i e d out i n (n-1) s t e p s (n i s the t o t a l number of b l o c k s i n J ) . P r o g r e s s i n g from s t e p (m-1) t o s t e p m c o n s i s t s i n p a s s i n g from the s e t Jm-1 t o the s e t Jm such t h a t : Jm = Jm-1 - {A} - {B} + {A U B } where: A, B are elments of Jm-1 and s u b s e t s of J such t h a t dAB i s the l a r g e s t element i n the d e s i r a b i l i t y m a t r i x Dm-1 i n s t e p (m-1). JO = { { b i } | b i i s an element of J,i=1,..,n} In o t h e r words, JO i s a s e t of s u b s e t s of b l o c k ( s ) (a s e t of c l u s t e r s ) , w i t h each subset i n i t i a l l y c o n t a i n i n g a s i n g l e b l o c k . In each s t e p , we t r y t o merge two c l u s t e r s t o g e t h e r I n t r o d u c t i o n 12 based on the reduced d e s i r a b i l i t y m a t r i x Dm w i t h DO = D, t o form a new c l u s t e r under the c o n s t r a i n t t h a t the sum of s i z e s of a l l b l o c k s i n the new c l u s t e r cannot be g r e a t e r than the page s i z e P. In d e t a i l , s t e p m c o n s i s t s of the f o l l o w i n g o p e r a t i o n s : (1) From m a t r i x Dm-1, f i n d the l a r g e s t element dAB, where A and B a r e two elements of Jm-1. I f the l a r g e s t element e q u a l s t o z e r o then the p r o c e s s i s t e r m i n a t e d as t h a t i n d i c a t e s no new c l u s t e r can be formed based on Dm-1. (2) I f the sum of sA (sum of s i z e s of a l l b l o c k s i n c l u s t e r A) and sB (sum of s i z e s of a l l b l o c k s i n c l u s t e r B) i s s m a l l e r than or e q u a l t o P (the page s i z e ) then we merge A and B, i . e . A U B, t o form a new subset C and c o n t i n u e w i t h ( 3 ) . O t h e r w i s e , we r e p l a c e dAB of Dm-1 w i t h z e r o , i n d i c a t i n g t h a t the merge i s u n s u c c e s s f u l , and then c o n t i n u e w i t h (1) a g a i n . (3) C o n s t r u c t the reduced m a t r i x Dm from Dm-1 by d e l e t i n g a l l the rows and columns a s s o c i a t e d w i t h A and B. And then add row C and column C t o Dm, such t h a t : dCX = dAX + dBX and dXC = dXA + dXB I n t r o d u c t i o n 13 where dAX,dXA,dBX,dXB a r e elements of Dm-1, f o r a l l X i n Jm-1 except f o r A or B Note t h a t Dm i s now the new d e s i r a b i l i t y m a t r i x w i t h rows and columns l a b e l l e d by c l u s t e r names. In summary, we s t a r t o f f w i t h JO which i s a set of n c l u s t e r s , each of which c o n s i s t s of a s i n g l e b l o c k i n s e t J ; and e v e n t u a l l y we end up w i t h Jn which i s a s e t of new c l u s t e r s , each of which c o n s i s t s of a subset of b l o c k ( s ) and whose s i z e i s l e s s than or e q u a l t o the page s i z e . An example i l l u s t r a t i n g the method i s d e s c r i b e d i n Appendix I I I . O p t i m i z a t i o n of space usage s h o u l d be done i n o r d e r t o m i n i m i z e the wasted space a t the end of pages, e s p e c i a l l y f o r s m a l l c l u s t e r s . Placement i s made w i t h emphasis on the s i z e c o n d i t i o n r a t h e r than on the d e s i r a b i l i t y between two c l u s t e r s i n t h i s l a s t s t e p . 1.6 O b j e c t i v e s The main o b j e c t i v e of t h i s t h e s i s i s e f f i c i e n t r e s t r u c t u r i n g a l g o r i t h m s t r a t e g y - i n d e p e n d e n t . The work i s based on s t u d i e s of phases and t r a n s i t i o n s ( d e t a i l s t o d e v e l o p an which i s the e m p i r i c a l i n s e c t i o n 2.1) I n t r o d u c t i o n i n the s y m b o l i c r e f e r e n c e s t r i n g s of r e a l programs, ( s p e c i f i c a l l y P a s c a l p r o g r a m s ) . A l s o we wish to e s t a b l i s h some parameters t o c h a r a c t e r i z e program b e h a v i o r and t o a n a l y z e the r e l a t i o n s h i p between th e s e parameters and the performance of the program. T h i s b r i e f i n t r o d u c t i o n i n t h i s c h a p t e r h o p e f u l l y p r o v i d e s s u f f i c i e n t background on the m o t i v a t i o n of program r e s t r u c t u r i n g and some of the t e c h n i q u e s r e p o r t e d i n the l i t e r a t u r e . We then p r o c e e d , i n c h a p t e r 2, t o d e s c r i b e i n d e t a i l t he p h a s e / t r a n s i t i o n model and the Bounded L o c a l i t y I n t e r v a l (BLI) d e f i n i t i o n which l e d t o the c o n s t r u c t i o n of a new a l g o r i t h m which we c a l l the BLI r e s t r u c t u r i n g a l g o r i t h m , w i t h the emphasis on phase t r a n s i t i o n s . In c h a p t e r 3, we d e s c r i b e the setup of the e x p e r i m e n t , the measurement t o o l s i n v o l v e d and the i m p l e m e n t a t i o n of the BLI r e s t r u c t u r i n g a l g o r i t h m . A n a l y s i s and d i s c u s s i o n s of the e x p e r i m e n t a l r e s u l t s a r e p r e s e n t e d i n c h a p t e r 4. BLI R e s t r u c t u r i n g A l g o r i t h m 15 2 BLI R e s t r u c t u r i n g A l g o r i t h m T h i s c h a p t e r b e g i n s w i t h the i n t r o d u c t i o n of the p h a s e / t r a n s i t i o n model of program b e h a v i o r . The s t r e n g t h s and the weaknesses of the model a r e b r i e f l y d i s c u s s e d . The problem of i d e n t i f y i n g a l l the d i s t i n c t i v e phases i s r a i s e d and the concept of Bounded L o c a l i t y I n t e r v a l (BLI) i s d i s c u s s e d . A new a l g o r i t h m based on the concept of BLI i s d e s c r i b e d i n the l a s t s e c t i o n of the c h a p t e r . 2.1 P h a s e / T r a n s i t i o n Model From the v i e w p o i n t of program l o c a l i t y , a program's e x e c u t i o n time can be r e g a r d e d as a sequence of l o c a l i t y phases (or s i m p l y phases) s e p a r a t e d by t r a n s i t i o n s . I n f o r m a l l y , a phase i s an i n t e r v a l d u r i n g which the s m a l l s e t of b l o c k s b e i n g r e f e r e n c e d i s c o n s t a n t ; and a t r a n s i t i o n denotes the i n t e r v a l of m i g r a t i n g from one phase t o a n o t h e r . By s u b d i v i d i n g the program i n t o b l o c k s , the l o c a l i t y s e t of a phase (phase s e t ) i s the s e t of b l o c k s a c t i v e i n t h a t phase. (A g i v e n b l o c k i s c o n s i d e r e d a c t i v e i n a phase whenever p r o c e s s i n g of t h a t phase r e q u i r e s the presence of t h a t b l o c k i n main memory.) S i m i l a r l y , the t r a n s i t i o n s e t i s the s e t of b l o c k s a c t i v e d u r i n g the t r a n s i t i o n . As proposed BLI R e s t r u c t u r i n g A l g o r i t h m 16 by S p i r n [ 3 1 ] , the e x e c u t i o n of a program may be viewed as a sequence { (P1 ,11 ),.... ( P i , l i ) , } where P i i s the i t h l o c a l i t y s e t or phase s e t and l i i s the l i f e t i m e of the phase f o r P i ( i n f o r m a l l y , the l i f e t i m e of a phase i s the d i f f e r e n c e i n v i r t u a l time between e n t e r i n g and l e a v i n g of a phase.) The p h a s e / t r a n s i t i o n model of program b e h a v i o r has been s t u d i e d i n d e t a i l by Graham [32] i n h i s d o c t o r a l r e s e a r c h . H i s work d e a l s m a i n l y w i t h the model as a s y n t h e t i c g e n e r a t o r of r e f e r e n c e s t r i n g s . Though i t i s i n t e r e s t i n g and i m p o r t a n t i n i t s own r i g h t , the emphasis and a p p l i c a t i o n s of h i s work a r e q u i t e d i f f e r e n t from o u r s . One of the major p r o p e r t i e s of the p h a s e / t r a n s i t i o n model i s t h a t i t p e r m i t s a wide range of d e t a i l t o be i n c o r p o r a t e d w i t h the r e f e r e n c e s t r i n g g e n e r a t i o n p r o c e s s . In one extreme, the model may assume t h a t the l i f e t i m e s of a l l l o c a l i t y s e t s have l e n g t h one i n which case the model c o n s i s t s of the e n t i r e r e f e r e n c e s t r i n g . O b v i o u s l y t h i s w i l l p r e s e r v e a l l the d e t a i l s of the program b e h a v i o r . In the o t h e r extreme, the model may assume t h a t o n l y one l o c a l i t y s e t , namely the program space i t s e l f , e x i s t s d u r i n g e x e c u t i o n . In t h i s c a s e , a l o t of d e t a i l s w i l l be l o s t . C l e a r l y , n e i t h e r of t h e s e extremes i s r e a s o n a b l e i n g a i n i n g a b e t t e r u n d e r s t a n d i n g of l o c a l i t y . Madison and Batson [25] o f f e r e d a method f o r d i s c e r n i n g phases and t r a n s i t i o n s w i t h BLI R e s t r u c t u r i n g A l g o r i t h m 17 the n o t i o n of Bounded L o c a l i t y I n t e r v a l (BLI) and they undertook e m p i r i c a l s t u d i e s of phases and t r a n s i t i o n s i n the s y m b o l i c r e f e r e n c e s t r i n g s of r e a l programs. 2.2 Bounded L o c a l i t y I n t e r v a l A b a s i c d i f f i c u l t y w i t h the p h a s e / t r a n s i t i o n model i s the one of f o r m u l a t i n g a p r o c e d u r e which c o u l d i d e n t i f y a l l the d i s t i n c t i v e phases and t h e i r c o r r e s p o n d i n g l o c a l i t y s e t s g i v e n a r e f e r e n c e s t r i n g [ 1 5 ] . The n o t i o n of the Bounded L o c a l i t y I n t e r v a l (BLI) was i n t r o d u c e d by Madison and Batson [25] as a mechanism to overcome t h i s problem. The i n i t i a l i d e a of BLI was t r i g g e r e d by the o b e r v a t i o n t h a t the l e a s t - r e c e n t l y - u s e d (LRU) s t a c k (see Appendix Ia) c o n t a i n s , a t any time t , the b l o c k s a r r a n g e d i n the o r d e r of the t i m e s a t which they were l a s t r e f e r e n c e d , w i t h the m o s t - r e c e n t l y - u s e d b l o c k at the t o p of the s t a c k . I f the t o p i elements i n the LRU s t a c k a r e { P i } then we can a l s o r e c o r d f i , the time of f o r m a t i o n of t h i s s e t { P i } and e i , the l a s t time of r e f e r e n c e t o the b l o c k c u r r e n t l y o c c u p y i n g the i t h LRU s t a c k p o s i t i o n . At any i n s t a n t t , an a c t i v i t y s e t i s d e f i n e d as any { P i } i n which eve r y element of t h a t s e t has been r e f e r e n c e d more than once s i n c e the s e t has been formed at the top of the LRU s t a c k . BLI R e s t r u c t u r i n g A l g o r i t h m 18 The l i f e t i m e , l i , of such an a c t i v i t y s e t i s d e f i n e d t o be the d i f f e n c e between f i and e i where e i > f i . A BLI i s the p a i r ( A i , l i ) , such t h a t A i i s the a c t i v i t y s e t and l i i s i t s l i f e t i m e . The n o t i o n c o u l d be g e n e r a l i z e d by d e f i n i n g an a c t i v i t y s e t as one whose elements have been r e f e r e n c e d at l e a s t k times s i n c e the s e t was formed. In p a r t i c u l a r , the d e f i n i t i o n g i v e n i s f o r the case when k = 1. Moreover, k i s the o n l y parameter of the model and i t i s independent of any memory management p o l i c i e s . Another i m p o r t a n t c h a r a c t e r i s t i c of BLI i s the i m p l i c i t h i e r a r c h i c a l n a t u r e of l o c a l i t i e s embedded i n the d e f i n i t i o n . The h i e r a r c h y of B L I ' s i s i l l u s t r a t e d i n F i g u r e 2.1, which shows a segment of a r e f e r e n c e s t r i n g and the c o r r e s p o n d i n g BLI s t r u c t u r e , w i t h the parameter k = 1. The l e v e l of a BLI i s d e f i n e d as i t s d i s t a n c e down i n the h i e r a r c h y . Thus, i n F i g u r e 2.1, the " l e v e l one" BLI's are those a t the top of the h i e r a r c h i c a l s t r u c t u r e , p a r t i t i o n i n g the r e f e r e n c e s t r i n g i n t o the l o n g e s t p o s s i b l e s u b i n t e r v a l s of d i s t i n c t i v e r e f e r e n c i n g b e h a v i o r . BLI R e s t r u c t u r i n g A l g o r i t h m 19 (B/ {A,B,C,DJ ( l e v e l - o n e ) + r + + |B,C,D} IE} [D\ ( l e v e l - t w o ) + + + + + -- + {C,D} ( l e v e l - t h r e e ) + + F i g u r e 2.1. H i e r a r c h y of BLI's f o r an example s y m b o l i c r e f e r e n c e s t r i n g . The development of the concept of the BLI c o u l d be used t o s o l v e the problem of i d e n t i f y i n g d i s t i n c t i v e major phases i n a g i v e n r e f e r e n c e s t r i n g , e x c e p t t h a t we s t i l l have t o determine whether a phase i s r e a l l y a "major" phase. I n t u i t i v e l y one would expect t h a t a major phase s h o u l d have a r e a s o n a b l y l o n g l i f e t i m e . B a tson [3] p o i n t e d out t h a t the c r i t e r i o n of " r e a s o n a b l y l o n g " can o n l y be f o r m u l a t e d i n the c o n t e x t of the p a r t i c u l a r v i r t u a l memory system upon which the program w i l l be e x e c u t e d . He suggested t h a t the mean time r e q u i r e d t o t r a n s f e r a b l o c k from secondary s t o r a g e t o main memory can be used t o d e t e r m i n e a sequence of major phases and t r a n s i t i o n s . I f p i s the b l o c k t r a n s f e r t i m e , each BLI i s regarded as a major phase i f i t s l i f e t i m e i s BLI R e s t r u c t u r i n g A l g o r i t h m g r e a t e r than or e q u a l t o p. 20 B e s i d e s the importance of the b e h a v i o r of the major phases and t h e i r n e s t i n g c h a r a c t e r i s t i c s , t h e r e are s i g n i f i c a n t d i s r u p t i v e t r a n s i t i o n - i n t e r v a l s between major phases. W h i l e the major phases dominate v i r t u a l t i m e , the t r a n s i t i o n s account f o r a s u b s t a n t i a l p a r t of the page f a u l t s . I t was r e p o r t e d by Kahn [24] t h a t phases c o v e r e d a t l e a s t 98% of v i r t u a l time w h i l e the r a t e of page f a u l t s d u r i n g t r a n s i t i o n s was 100 t o 1000 t i m e s h i g h e r than t h a t d u r i n g phases. A s i m p l e way of a p p r o x i m a t i n g the BLI concept i n the i d e n t i f i c a t i o n of the l e v e l - o n e major and t r a n s i t i o n phases i s as f o l l o w . Scan the b l o c k r e f e r e n c e s t r i n g from the l e f t . The f i r s t r e p e t i t i o n of a b l o c k r e f e r e n c e i s the ( p o s s i b l e ) b e g i n n i n g of a major phase and a l s o the ( p o s s i b l e ) t e r m i n a t i o n of the c u r r e n t t r a n s i t i o n phase (depending on whether the e v e n t u a l l e n g t h of the phase exceeds p ) . A major phase t e r m i n a t e s i f a r e f e r e n c e i s made to a b l o c k not c o n t a i n e d i n the p r e v i o u s t r a n s i t i o n phase s e t . Our e m p i r i c a l data show t h a t t h i s w i l l o b t a i n almost i d e n t i c a l l e v e l - o n e major and t r a n s i t i o n phase s e t s w i t h much l e s s o verheads. Subsequent r e s u l t s r e p o r t e d i n t h i s t h e s i s were o b t a i n e d u s i n g t h i s a p p r o x i m a t i o n method. BLI R e s t r u c t u r i n g A l g o r i t h m 21 2.3 The BLI R e s t r u c t u r i n g A l g o r i t h m 2.3.1 Mot i v a t i o n I t was the l a s t remark, i n the p r e v i o u s s e c t i o n , about the e f f e c t of t r a n s i t i o n s on program performance t h a t l e d to the i d e a of the BLI r e s t r u c t u r i n g a l g o r i t h m . B a s i c a l l y , the g o a l of program r e s t r u c t u r i n g i s t o reduce the page f a u l t r a t e g e n e r a t e d by the program and t r a d i t i o n a l l y e x p e r i m e n t s on program r e s t r u c t u r i n g have c o n c e n t r a t e d on the major phases or l o c a l i t i e s . However, the s t u d i e s of Denning and Kahn [15] i n d i c a t e d t h a t , f o r e x e c u t a b l e memory s i z e g r e a t e r than the mean phase s i z e , performance was much more dependent on the c h a r a c t e r i s t i c s of phase t r a n s i t i o n s than e i t h e r the program b e h a v i o r w i t h i n phases or the memory management a l g o r i t h m i n use. The BLI r e s t r u c t u r i n g a l g o r i t h m i s c o n s t r u c t e d w i t h the f o l l o w i n g o b j e c t i v e s i n mind: (1) S t r a t e g y - i n d e p e n d e n t . The a l g o r i t h m s h o u l d be independent of any memory management p o l i c y thus h a v i n g the w i d e s t p o s s i b l e domain of a p p l i c a t i o n . BLI R e s t r u c t u r i n g A l g o r i t h m 22 (2) Emphasis on phase t r a n s i t i o n s . B e s i d e s t r y i n g t o p l a c e a l l b l o c k s i n the major phase i n t o common pages, we emphasize on the s t r e n g t h of "nearness" of b l o c k s d u r i n g t r a n s i t i o n i n t e r v a l s . T h i s w i l l a c h i e v e b e t t e r u t i l i z a t i o n of the i n f o r m a t i o n p r o v i d e d by the program b e h a v i o r model, and more i m p o r t a n t l y we hope t o o b t a i n b e t t e r performance by r e d u c i n g the page f a u l t r a t e . The BLI model i s the p e r f e c t c h o i c e f o r our p urposes. I t i s s t r a t e g y - i n d e p e n d e n t and i t p r o v i d e s a c l e a r d e f i n i t i o n of major phases and t r a n s i t i o n s g i v e n any r e f e r e n c e s t r i n g . In b u i l d i n g the d e s i r a b i l i t y m a t r i x , u n l i k e o t h e r a l g o r i t h m s d e s c r i b e d i n s e c t i o n 1.4, we put more w e i g h t s on t r a n s i t i o n s than on phases. We group the b l o c k s i n the t r a n s i t i o n i n t e r v a l the same way as the l o c a l i t y s e t s or the a c t i v i t y s e t s d e s p i t e t h e i r v e r y s h o r t l i f e t i m e s , as l o n g as the l i f e t i m e of each s e t i s g r e a t e r than the b l o c k t r a n s f e r time from secondary s t o r a g e t o main memory. In the c l u s t e r i n g s t a g e , the major c o n s t r a i n t i s t h a t the sum of the s i z e s of a l l b l o c k s i n a c l u s t e r cannot be g r e a t e r than the page s i z e . Wasted space a t the end of pages i s .reduced by combining c l u s t e r s t h a t may f i t i n t o a BLI R e s t r u c t u r i n g A l g o r i t h m 23 page as f o l l o w s : The c l u s t e r s a re l i s t e d i n d e c r e a s i n g o r d e r of t h e i r s i z e s . They are then p l a c e d i n t o a page i n the same o r d e r s k i p p i n g those which cause an o v e r l a p , u n t i l the page i s f i l l e d or the l i s t i s c o m p l e t e l y examined. The next page i s then f i l l e d i n the same way w i t h a new l i s t composed of the r e m a i n i n g c l u s t e r s o r d e r e d i n the same manner. T h i s p r o c e s s i s r e p e a t e d u n t i l the e n t i r e l i s t i s exha u s t e d . 2.3.2 The A l g o r i t h m In d e t a i l , the BLI r e s t r u c t u r i n g a l g o r i t h m c o n s i s t s of the f o l l o w i n g s t e p s : (1) U s i n g the d e f i n i t i o n of B L I , w i t h a chosen v a l u e f o r the parameter k (k i s used t o determine the a c t i v i t y s e t ) and g i v e n the b l o c k t r a n s f e r time p, a sequence of t r a n s i t i o n s and major phases can be o b t a i n e d from any g i v e n b l o c k r e f e r e n c e s t r i n g . In o r d e r t o keep the c o s t of the a l g o r i t h m w i t h i n r e a s o n a b l e l i m i t , we w i l l o n l y c o n c e r n o u r s e l v e s w i t h the " l e v e l one" BLI's of the h i e r a r c h y . (To o b t a i n an o p t i m a l path t h r o u g h the h i e r a r c h y i s too c o s t l y f o r program r e s t r u c t u r i n g . Moreover, the " l e v e l one" BLI's a r e tho s e a t the t o p of the h i e r a r c h i c a l s t r u c t u r e (see F i g u r e 2.1), BLI R e s t r u c t u r i n g A l g o r i t h m 24 p a r t i t i o n i n g the r e f e r e n c e s t r i n g i n t o the l o n g e s t p o s s i b l e s u b i n t e r v a l s of d i s t i n c t i v e r e f e r e n c i n g b e h a v i o r . ) (2) Each of the t r a n s i t i o n s and major phases composes of a s e t of d i s t i n c t b l o c k s which a r e o r d e r e d w i t h r e s p e c t t o t h e i r t imes of f i r s t o c c u r r e n c e . Now we have a c h o i c e of c o n s i d e r i n g (a) the phase s e t s o n l y (b) the t r a n s i t i o n s e t s o n l y (c) both the phase s e t s and the t r a n s i t i o n s e t s (3) Then we have t o d e c i d e how t o determine the " d e s i r a b i l i t y " of b l o c k p a i r i n g s i n each of the s e t s chosen from s t e p ( 2 ) . The d e s i r a b i l i t y m a t r i x M = [ m i j ] i s a symmetric nxn m a t r i x w i t h i n d i c e s l a b e l l e d by b l o c k numbers, where n i s t h e t o t a l number of b l o c k s i n the program. Two methods a r e d e s c r i b e d f o r the c o m p u t a t i o n of m i j , the d e s i r a b i l i t y of p l a c i n g two b l o c k s i and j i n the same page. (a) the Neighborhood method For each s e t of b l o c k s chosen from s t e p ( 2 ) , a r r a n g e the b l o c k s i n a l i s t i n the o r d e r of t h e i r o c c u r r e n c e w i t h i n t h a t phase or t r a n s i t i o n . Increment m i j by one f o r any two b l o c k s i and j i n BLI R e s t r u c t u r i n g A l g o r i t h m 25 the l i s t such t h a t b l o c k i i s f o l l o w e d by b l o c k j , f o r a l l i i n the l i s t . (b) the Combination method For each s e t of b l o c k s chosen from s t e p ( 2 ) , and f o r a l l c o m b i n a t i o n of b l o c k p a i r i n g s i and j i n the s e t , increment m i j by one where i i s d i f f e r e n t f r om j . 2.3.3 Examples of BLI R e s t r u c t u r i n g H e u r i s t i c In e f f e c t , we have d e s c r i b e d a whole c a t e g o r y of h e u r i s t i c s f o r program r e s t r u c t u r i n g based on the n o t i o n of B L I . The f o l l o w i n g a r e two examples of such h e u r i s t i c s from the c a t e g o r y which a r e found t o be p a r t i c u l a r l y i n t e r e s t i n g and hence they are chosen t o be used i n the e x p e r i m e n t s . Example 1: P h a s e - T r a n s i t i o n - N e i g h b o r h o o d - k = 1 (PTN1) T h i s method uses the BLI d e f i n i t i o n w i t h k=1. I t c o n s i d e r s both the phase s e t s and the t r a n s i t i o n s e t s . The e n t r i e s of the d e s i r a b i l i t y m a t r i x a r e determined by the Neighborhood method d e s c r i b e d i n 3 ( a ) . ( T h i s i s , i n e f f e c t , s i m i l a r t o H a t f i e l d ' s nearness m a t r i x except t h a t the w e i g h t s on b l o c k p a i r i n g s i n major phases are g r e a t l y reduced.) BLI R e s t r u c t u r i n g A l g o r i t h m 26 Example 2: T r a n s i t i o n - C o m b i n a t i o n - k = 2 (TC2) In t h i s method, we use k = 2 t o det e r m i n e the major phases and the t r a n s i t i o n s . However o n l y the t r a n s i t i o n s e t s a re examined. ( I t i s observed t h a t a t r a n s i t i o n s e t always i n c l u d e s the s e t of b l o c k s i n the next major phase. Hence, i n e f f e c t , we have a l r e a d y i m p l i c i t l y c o n s i d e r e d the b l o c k s i n the major phases though t h e i r w e i g h t s a r e f u r t h e r reduced, d e s p i t e t h e i r much l o n g e r l i f e t i m e s . ) The d e s i r a b i l i t y of b l o c k p a i r i n g s i s computed u s i n g the Combination method d e s c r i b e d i n 3 ( b ) . In the next c h a p t e r , we d e s c r i b e the d e s i g n of the experiment w i t h the BLI r e s t r u c t u r i n g a l g o r i t h m . The o b j e c t i v e s of the experiment a r e t w o - f o l d e d : (1) To e v a l u a t e the performance of the BLI r e s t r u c t u r i n g a l g o r i t h m compared t o o t h e r a l g o r i t h m s used i n the l i t e r a t u r e . (2) To study the r e l a t i o n s h i p between some proposed parameters of program b e h a v i o r and the performance of r e a l programs. D e s c r i p t i o n of Experiment 27 3 D e s c r i p t i o n of the Experiment 3.1 Overview In t h i s c h a p t e r , the experiment which was conducted w i l l be d e s c r i b e d i n d e t a i l . The main o b j e c t i v e of the experiment i s t o e v a l u a t e the performance of the . BLI r e s t r u c t u r i n g a l g o r i t h m compared t o the o t h e r major e x i s t i n g a l g o r i t h m s . A l s o we w i s h t o e s t a b l i s h some parameters t o c h a r a c t e r i z e program b e h a v i o r and h o p e f u l l y t o g a i n some i n s i g h t t h r o u g h the a n a l y s i s of the r e l a t i o n s h i p between these paramters and the performance of r e a l programs. Having d e c i d e d t o do a measurement e x p e r i m e n t , the f i r s t s t e p i s t o determine what performance measures t o use and then t o i d e n t i f y the major parameters r e l a t e d t o the program b e h a v i o r model which may i n f l u e n c e the s e l e c t e d performance i n d i c e s . The next s t e p i s t o d e v e l o p t o o l s t o c o l l e c t b l o c k r e f e r e n c e s t r i n g s from r e a l programs and to implement the v a r i o u s r e s t r u c t u r i n g a l g o r i t h m s ( i n c l u d i n g the Nearness M a t r i x , the C r i t i c a l Working Set r e s t r u c t u r i n g a l g o r i t h m and the BLI r e s t r u c t u r i n g a l g o r i t h m s ) . The performance of the r e s t r u c t u r e d program i s then e v a l u a t e d by r u n n i n g the r e f e r e n c e s t r i n g on the s i m u l a t e d memory D e s c r i p t i o n of Experiment 28 management program t o compute the performance s t a t i s t i c s and o t h e r p a r a m e t e r s . F o l l o w i n g t h i s , we d i s c u s s the type of program used i n the experiment and the v a r i e t y of d a t a i n p u t i n c l u d e d t o t e s t f o r d a t a dependency. F i n a l l y the d e s i g n and i m p l e m e n t a t i o n of the experiment a r e d i s c u s s e d i n the l a s t s e c t i o n of the c h a p t e r . 3.2 Approach The experiment i s based on b l o c k r e f e r e n c e s t r i n g s (see Appendix I I ) g a t h e r e d from r e a l p r o d u c t i o n programs r u n n i n g on an AMDAHL 470V/8 computer. These programs c o n s i s t of r e l o c a t a b l e b l o c k s such as p r o c e d u r e s and f u n c t i o n s . They were e x e c u t e d on the M i c h i g a n - T e r m i n a l - S y s t e m (MTS) Symbolic Debugging- System (SDS) from which s y m b o l i c t r a c e s of procedure c a l l s and r e t u r n s were c o l l e c t e d and e x t r a c t e d t o form the r e s u l t i n g b l o c k r e f e r e n c e s t r i n g s . At the same t i m e , the b l o c k s i z e s were r e c o r d e d f o r use i n the c l u s t e r i n g phase. The r e f e r e n c e s were then f e d t o the r e s t r u c t u r i n g programs based on the d i f f e r e n t r e s t r u c t u r i n g a l g o r i t h m s t o produce the c o r r e s p o n d i n g d e s i r a b i l i t y m a t r i c e s . Each m a t r i x was then i n p u t t o the c l u s t e r i n g program which output a s e t of v i r t u a l pages each of which c o n t a i n e d a c l u s t e r of D e s c r i p t i o n of Experiment 29 b l o c k s . The performance of the r e s t r u c t u r e d program was e s t i m a t e d by s i m u l a t i o n . The b l o c k r e f e r e n c e s t r i n g was f i r s t t r a n s f o r m e d i n t o the c o r r e s p o n d i n g page r e f e r e n c e s t r i n g a c c o r d i n g t o the mapping suggested by the r e s t r u c t u r i n g and c l u s t e r i n g p r o c e d u r e s . The page r e f e r e n c e s t r i n g was f e d t o a memory management s i m u l a t o r which g a t h e r e d the d e s i r e d performance s t a t i s t i c s . Because of i t s p o p u l a r i t y and the r e l a t i o n s h i p t o one of the major r e s t r u c t u r i n g a l g o r i t h m s ( i . e . , the C r i t i c a l Working Set a l g o r i t h m ) , the working s e t memory management p o l i c y was used throughout the s t u d y . 3.3 Parameters 3.3.1 Performance I n d i c e s T r a d i t i o n a l l y , the page f a u l t r a t e i s an i m p o r t a n t performance index i n v i r t u a l memory systems. The reason i s t h a t the t u r n a r o u n d time of a program i s s t r o n g l y i n f l u e n c e d by the number of page f a u l t s g e n e r a t e d d u r i n g i t s e x e c u t i o n . T h i s i s because the time needed t o t r a n s f e r a page from secondary, s t o r a g e t o main memory i s about f o u r o r d e r s of magnitude l a r g e r than the a c c e s s time of p r i m a r y s t o r a g e . D e s c r i p t i o n of Experiment 30 Apa r t from the s i z e of main s t o r a g e , the number of page f a u l t s g e n e r a t e d d u r i n g an e x e c u t i o n depends m a i n l y on the b e h a v i o r of the program b e i n g e x e c u t e d and on the memory management p o l i c y used by the system. S i n c e we have d e c i d e d t o use the working s e t p o l i c y as the replacement p o l i c y throughout the ex p e r i m e n t , the average working s e t s i z e i s a good i n d i c a t o r of memory usage d u r i n g the program's execut i o n . Thus, the performance i n d i c e s chosen a r e the page f a u l t r a t e and t h e mean working s e t s i z e which t o g e t h e r c o v e r , t o c e r t a i n e x t e n t , the space and time components of a c o m p u t a t i o n a l a c t i v i t y . 3.3.2 C o n t r o l l a b l e F a c t o r s A c o n t r o l l a b l e f a c t o r i s a f a c t o r whose l e v e l s (or v a l u e s ) a r e under the d i r e c t c o n t r o l of (and t h e r e f o r e can be chosen by) the e x p e r i m e n t e r . Parameters which may a f f e c t the b e h a v i o r of a g i v e n program a r e i t s i n p u t d a t a and the o r d e r i n which i t s b l o c k s a r e s t o r e d i n the v i r t u a l memory space. The i n f l u e n c e of the o r d e r i n g i s due t o the f a c t t h a t the page c o n t e n t s would g e n e r a l l y be d i f f e r e n t f o r d i f f e r e n t o r d e r i n g s . Thus, D e s c r i p t i o n of Experiment 31 d i f f e r e n t p a r t s of the program a r e m a i n t a i n e d i n main memory f o r d i f f e r e n t o r d e r i n g of b l o c k s i n the v i r t u a l a d d r e s s space. As d e s c r i b e d i n Chapter 1, the o r i g i n a l o r d e r i n g of b l o c k s i n the v i r t u a l s t o r a g e can be a l t e r e d by the use of a r e s t r u c t u r i n g a l g o r i t h m and a c l u s t e r i n g a l g o r i t h m . Thus, the t h r e e c o n t r o l l a b l e f a c t o r s s e l e c t e d f o r the experiment a r e : (1) i n p u t d a t a , (2) the r e s t r u c t u r i n g a l g o r i t h m , (3) the c l u s t e r i n g a l g o r i t h m . S i n c e we have d e c i d e d t o use the working s e t p o l i c y as the replacement a l g o r i t h m , we might i n c l u d e the window s i z e T (the o n l y parameter of the Working Set p o l i c y ) , as the f o u r t h c o n t r o l l a b l e f a c t o r . These c o n t r o l l a b l e f a c t o r s a r e s e l e c t e d w i t h the view t o compare the performance of the BLI r e s t r u c t u r i n g a l g o r i t h m w i t h the o t h e r s . The f o u r c o n t r o l l a b l e f a c t o r s and t h e i r l e v e l s s e l e c t e d a r e l i s t e d i n T a b l e 3.1 under s e c t i o n 3.5. 3.3.3 O b s e r v a b l e F a c t o r s An o b s e r v a b l e f a c t o r i s a f a c t o r whose l e v e l s can be D e s c r i p t i o n of Experiment 32 . measured d u r i n g the experiment but they a r e not under the d i r e c t c o n t r o l of the e v a l u a t o r . The o b s e r v a b l e f a c t o r s of our experiment depend v e r y much on the program b e h a v i o r model i n use. With the p h a s e / t r a n s i t i o n model and the n o t i o n of B L I , the n a t u r a l c h o i c e s a r e the average c a r d i n a l i t y of the phase s e t s and of the t r a n s i t i o n s e t s . I n t u i t i v e l y , we e x p e c t : (1) the average phase s e t s i z e t o be a p p r o x i m a t e l y e q u a l t o the mean working s e t s i z e ; and (2) l a r g e average t r a n s i t i o n s e t s i z e w i l l g i v e r i s e t o h i g h page f a u l t r a t e . I t i s one of our g o a l s t o see i f t h e r e i s any c o r r e l a t i o n between these parameters and the performance of the measured programs. 3.4 Measurement T o o l s 3.4.1 Data C o l l e c t i o n and R e d u c t i o n Data c o l l e c t i o n was done u s i n g the Symb o l i c Debugging System (SDS) on the AMDAHL 470V/8 computer which o p e r a t e s under the M i c h i g a n T e r m i n a l System (MTS). SDS i n c l u d e s a s i m u l a t o r ( o r i g i n a l l y d e s i g n e d f o r the IBM 370/168) which s i m u l a t e s the i n s t r u c t i o n s s t e p by s t e p . The SDS s i m u l a t o r p r o v i d e s a TRACE CALL command which can e s t a b l i s h b r e a k p o i n t s a t the base of a l l the c o n t r o l s e c t i o n s ( s u b r o u t i n e s ) and a t t h e i r e n t r y p o i n t s . D u r i n g the D e s c r i p t i o n of Experiment , • 33 s i m u l a t i o n of an i n s t r u c t i o n , i f a c a l l i n t e r c e p t ( i . e . , a b r e a k p o i n t ) i s e n c o u n t e r e d , the s y m b o l i c a d d r e s s of the r o u t i n e b e i n g c a l l e d and the r e t u r n a d dress of the c a l l i n g r o u t i n e a r e r e c o r d e d and a r e t u r n i n t e r c e p t i s e s t a b l i s h e d at the r e t u r n a d d r e s s . S i m i l a r l y , when a r e t u r n i n t e r c e p t i s e n c o u n t e r e d the a d dress of the r e t u r n i n g r o u t i n e and the r e t u r n a d d r e s s are r e c o r d e d and the r e t u r n i n t e r c e p t i s removed. Hence a f t e r the program's e x e c u t i o n (by the s i m u l a t o r ) , a t r a c e of s u b r o u t i n e c a l l s and r e t u r n s i s r e c o r d e d . The c o s t of t h i s TRACE CALL command i s f a i r l y h i g h due t o s i m u l a t i o n of the i n s t r u c t i o n s and f r e q u e n t i n t e r f e r e n c e f o r data c o l l e c t i o n a t the b r e a k p o i n t s . The c o s t i s , as e x p e c t e d , r o u g h l y p r o p o r t i o n a l t o the number of i n s t r u c t i o n s b e i n g s i m u l a t e d and the number of s u b r o u t i n e c a l l s made d u r i n g the e x e c u t i o n . A d a t a r e d u c t i o n program was w r i t t e n t o t r a n s f o r m the c o l l e c t e d i n f o r m a t i o n i n t o a more c o n c i s e and u s e f u l form. The program i n c l u d e s a mapping of each s u b r o u t i n e or b l o c k name i n t o an unique p o s i t i v e i n t e g e r and hence reduces the c o l l e c t e d t r a c e i n t o a sequence of p o s i t i v e i n t e g e r s which r e p r e s e n t s the f l o w of e x e c u t i o n of the measured program at the s y m b o l i c or s u b r o u t i n e l e v e l . T h i s sequence of b l o c k numbers i s known as the b l o c k r e f e r e n c e s t r i n g . D e s c r i p t i o n of Experiment 34 The SDS a l s o produced a l i s t of b l o c k names of the measured program and t h e i r c o r r e s p o n d i n g l e n g t h s . T h i s i n f o r m a t i o n was used i n the c l u s t e r i n g s t a g e . 3.4.2 R e s t r u c t u r i n g A l g o r i t h m s Three t y p e s • of r e s t r u c t u r i n g a l g o r i t h m s were implemented. They were H a t f i e l d ' s Nearness M a t r i x , F e r r a r i ' s C r i t i c a l Working Set and the BLI r e s t r u c t u r i n g a l g o r i t h m s . A l l of them were coded i n P a s c a l . Each a c c e p t s a sequence of p o s i t v e i n t e g e r s as i n p u t and scans the e n t i r e s t r i n g i n a s i n g l e p a s s , p r o d u c i n g the c o r r e s p o n d i n g d e s i r a b i l i t y m a t r i c e s . In the case of the BLI program, the user can s p e c i f y the r e q u i r e d o p t i o n s (such as PTN1, TC2, e t c . ) as d e s c r i b e d i n s e c t i o n 2.3.3. In a d d i t i o n to the d e s i r a b i l i t y m a t r i x , a sequence of phases and t r a n s i t i o n s , each c o n t a i n i n g a l i s t of d i s t i n c t b l o c k numbers and t h e i r l i f e t i m e s i s a l s o produced by the BLI a l g o r i t h m . Two c l u s t e r i n g a l g o r i t h m s , as d e s c r i b e d i n s e c t i o n 1.5, were implemented i n P a s c a l . Given a d e s i r a b i l i t y m a t r i x , the b l o c k s i z e s and the s i z e of a page, the c l u s t e r i n g program would, produce a s e t of pages and the b l o c k numbers a s s o c i a t e d w i t h each page. An a p p r o x i m a t i o n of wasted space i s a l s o d i s p l a y e d . D e s c r i p t i o n of Experiment 3.4.3 Working Set P o l i c y S i m u l a t o r 35 The f u n c t i o n of the s i m u l a t o r i s t o e s t i m a t e the performance of the r e s t r u c t u r e d program based on the o r i g i n a l b l o c k r e f e r e n c e s t r i n g c o l l e c t e d and the placement o r d e r i n g of b l o c k s suggested by the r e s t r u c t u r i n g a l g o r i t h m . G i v e n a s e t of pages ( c l u s t e r s ) and t h e i r c o r r e s p o n d i n g b l o c k numbers and the window s i z e , the s i m u l a t o r o u t p u t s the number of page f a u l t s and the average w o r k i n g s e t s i z e a s s o c i a t e d w i t h the r e s t r u c t u r e d program. Note t h a t the s i m u l a t o r implements the "pure" working s e t replacement p o l i c y which means o n l y the pages c o v e r e d by the window are r e g a r d e d as the program's w o r k i n g s e t a t any time i n s t a n t . The s i m u l a t o r was coded i n P a s c a l . 3.5 Design and I m p l ementation The program experimented on was a P a s c a l c o m p i l e r . I t was w r i t t e n i n P a s c a l and c o n s i d e r e d t o be w e l l s t r u c t u r e d . I t c o n s i s t e d of 336 b l o c k s ( p r o c e d u r e s and f u n c t i o n s ) and about 90% of t h e s e had s i z e s l e s s than 800 b y t e s . The average b l o c k s i z e was about 600 b y t e s . Thus f o r a page s i z e of 4K (4096) b y t e s , each page c o u l d h o l d about 7 b l o c k s D e s c r i p t i o n of Experiment 36 on the a v e r a g e . The c o m p i l e r c o n s i s t e d of about 54 pages of codes. In s e c t i o n 3.3 we i d e n t i f i e d the major f a c t o r s f e l t t o i n f l u e n c e the page f a u l t r a t e of a program. The d i f f e r e n t v a l u e s of a f a c t o r (both q u a n t i t a t i v e and n o n q u a n t i t a t i v e ) a r e c a l l e d i t s l e v e l s . The f o u r c o n t r o l l a b l e f a c t o r s s e l e c t e d and t h e i r c o r r e s p o n d i n g l e v e l s f o r the experiment are l i s t e d i n T able 3.1. The l e v e l s f o r the i n p u t d a t a were s e l e c t e d t o c o v e r a v a r i e t y of P a s c a l programs t o be c o m p i l e d w i t h r e s p e c t t o the number of s y n t a c t i c e r r o r s and the l e n g t h of the programs. Program P was d e s i g n e d t o i n c l u d e most of statement t y p e s i n P a s c a l and had about 25 s t a t e m e n t s . The f i r s t f o u r samples of the i n p u t d a t a were m o d i f i e d v e r s i o n s of program P r a n g i n g from z e r o t o 50 s y n t a c t i c e r r o r s . The f i f t h and s i x t h samples were both e r r o r - f r e e programs which had about 60 and 355 s t a t e m e n t s r e s p e c t i v e l y . H o p e f u l l y t h a t would a l l o w us t o t e s t f o r d a t a dependence on i n p u t of d i f f e r e n t n a t u r e as w e l l as s i z e s . F i v e r e s t r u c t u r i n g h e u r i s t i c s were s e l e c t e d f o r c o m p a r s i o n . The o r i g i n a l o r d e r i n g of the b l o c k s by the a u t h o r of the program went t h r o u g h no r e s t r u c t u r i n g and thus D e s c r i p t i o n of Experiment 37 s e r v e d as the c o n t r o l of the expe r i m e n t . H a t f i e l d ' s Nearness M a t r i x was i n c l u d e d p a r t l y f o r h i s t o r i a l reason and p a r t l y because i t i s s t i l l the s i m p l e s t , s t r a t e g y - i n d e p e n d e n t and yet the cheapest r e s t r u c t u r i n g a l g o r i t h m known. The CWS r e s t r u c t u r i n g method was chosen f o r o b v i o u s r e a s o n s : i t seems t o have the be s t performance among the a l g o r i t h m s r e p o r t e d i n the l i t e r a t u r e . I t i s a s t r a t e g y - o r i e n t e d a l g o r i t h m and was p u r p o s e l y chosen s i n c e we d e c i d e d t o use the working s e t p o l i c y f o r memory management. Both the PTN1 and TC2 a r e members of the BLI r e s t r u c t u r i n g a l g o r i t h m s . PTN1 resembles the Nearness M a t r i x but w i t h l e s s weights on the phase s e t s . W h i l e TC2 i s the n a t u r a l p r o d u c t of our i n t u i t i o n and p a s t e x p e r i e n c e t h a t d i s r u p t i v e phase t r a n s i t i o n s a re the major cause of page f a u l t s . S i x b l o c k r e f e r e n c e s t r i n g s were g a t h e r e d from d i f f e r e n t i n p u t d a t a . Each of them was then f e d t o the f i v e r e s t r u c t u r i n g programs and two c l u s t e r i n g programs. A t o t a l of 60 s e t s of c l u s t e r s was produced. The w o r k i n g set p o l i c y s i m u l a t o r went t h r o u g h a l l 60 s e t s of c l u s t e r s t w i c e , each time w i t h a d i f f e r e n t window s i z e . As a r e s u l t , 120 runs were made, each of which produced a p a i r of f i g u r e s D e s c r i p t i o n of Experiment 38 r e p r e s e n t i n g the number of page f a u l t s and the average w o r k i n g s e t s i z e . A d d i t i o n a l runs were performed t o t e s t the r e s u l t of r u n n i n g a l l the r e f e r e n c e s t r i n g s w i t h a p a r t i c u l a r s e t of c l u s t e r s chosen from TC2 and t o compare the r e s u l t s t o the ones u s i n g the CWS a l g o r i t h m . T h i s was done t o t e s t the r o b u s t n e s s of the two a l g o r i t h m s . D e s c r i p t i o n of Experiment 39 Table 3.1 F a c t o r s and L e v e l s f o r the Experiment Program: a P a s c a l c o m p i l e r Replacement p o l i c y : w o r k i n g s et p o l i c y FACTORS LEVELS NAME DESCRIPTION Input d a t a P1 program P, 25 s t a t e m e n t s , 50 e r r o r s (program t o P2 program P, 25 s t a t e m e n t s , 25 e r r o r s be c o m p i l - P3 program P, 25 s t a t e m e n t s , 5 e r r o r s ed) P4 program P, 25 s t a t e m e n t s , no e r r o r s P5 program Q u i c k s o r t , 60 s t t s , no e r r o r s P6 program BLI,355 s t a t e m e n t s , no e r r o r s R e s t r u c t u r - ORIG o r i g i n a l o r d e r i n g by author in g NEAR H a t f i e l d ' s Nearness M a t r i x A l g o r i t h m s CWS C r i t i c a l - W o r k i n g - S e t PTN1 P h a s e - t r a n s i t - n e i g h b o r - k = 1 (BLI) TC2 T r a n s i t - c o m b i n a t i o n - k = 2 (BLI) C l u s t e r i n g NUCL N u c l e u s - c o n s t r u c t i n g A l g o r i t h m s HIER H i e r a r c h i c a l c l a s s i f i c a t i o n Window s i z e 10 s m a l l ( r e f e r e n c e ) 50 l a r g e D i s c u s s i o n of R e s u l t s 40 4 D i s c u s s i o n of R e s u l t s S i x b l o c k r e f e r e n c e s t r i n g s were g a t h e r e d f o r a P a s c a l c o m p i l e r e x e c u t e d w i t h d i f f e r e n t i n p u t d a t a . A number of s i m u l a t i o n runs were performed t o e v a l u a t e the r e s t r u c t u r i n g p rocedure and s e v e r a l r e s t r u c t u r i n g a l g o r i t h m s as d e s c r i b e d i n s e c t i o n 3.5. In t h i s c h a p t e r , we s h a l l summarize what we f e e l t o be the most i m p o r t a n t r e s u l t s i n the f o l l o w i n g a r e a s : performance improvement, d a t a s e n s i t i v i t y , p o r t a b i l i t y and c o s t . 4.1 Performance Improvement Improvements i n page f a u l t r a t e and the average working s e t s i z e by program r e s t r u c t u r i n g are computed, i n terms of p e r c e n t a g e r e d u c t i o n i n those i n d i c e s as: Po - Pr % R e d u c t i o n = * 100 Po where Po, Pr a r e the o r i g i n a l and r e s t r u c t u r e d performance i n d i c e s r e s p e c t i v e l y . B e f o r e we d i s c u s s the performance of d i f f e r e n t r e s t r u c t u r i n g a l g o r i t h m s , we make the f o l l o w i n g o b s e r v a t i o n s : (1) Window S i z e D i s c u s s i o n of R e s u l t s 41 A r e a s o n a b l e range of window s i z e s , from 10 t o 100 page r e f e r e n c e s , was t e s t e d i n i t i a l l y f o r our performance e v a l u a t i o n . I t was found t h a t s m a l l e r window s i z e s produced s m a l l e r g a i n ( w i t h r e s p e c t t o % r e d u c t i o n i n page f a u l t r a t e ) . A window s i z e of f i f t y page r e f e r e n c e was found t o be the o p t i m a l f o r a l l r e s t r u c t u r i n g a l g o r i t h m s i n the experiment and was t h e r e f o r e chosen f o r performance comparsion among the r e s t r u c t u r i n g a l g o r i t h m s throughout the s t u d y . (2) C l u s t e r i n g A l g o r i t h m D e s p i t e the s i m p l i c i t y of the N u c l e u s C o n s t r u c t i n g method (NUCL), our r e s u l t s showed t h a t c l u s t e r i n g by H i e r a r c h i c a l C l a s s i f i c a t i o n (HIER) i s much s u p e r i o r t o NUCL i n a l l c a s e s . For the same r e f e r e n c e s t r i n g and r e s t r u c t u r i n g a l g o r i t h m , HIER o u t p e r f o r m s NUCL by an average of 20% i n our e x p e r i m e n t s . T h i s can be e x p l a i n e d by the i n a b i l i t y of i s o l a t i n g d i s t i n c t n u c l e i (a s e t of b l o c k s which a r e c l o s e l y r e l a t e d w i t h r e s p e c t t o the program's r e f e r e n c i n g b e h a v i o r ) by the NUCL method. Thus, we s h a l l c o n c e n t r a t e on the r e s u l t s g a t h e r e d from th e use of the HIER method. In almost a l l c a s e s and w i t h a l l f o u r r e s t r u c t u r i n g a l g o r i t h m s t e s t e d , s i g n i f i c a n t performance improvement was D i s c u s s i o n of R e s u l t s 42 o b t a i n e d i n both i n d i c e s (see T a b l e 4.1 and Table 4.2). The page f a u l t r a t e was reduced from 22% t o as much as 42.5%. The average working s e t s i z e was reduced t o about t w o - t h i r d s compared t o the performance a s s o c i a t e d w i t h the o r i g i n a l o r d e r i n g i n most c a s e s . In g e n e r a l , the o r i g i n a l l a y o u t of the program has g r e a t i n f l u e n c e on the magnitude of the improvement. S i n c e our t e s t program, a P a s c a l c o m p i l e r , i s c o n s i d e r e d t o be w e l l - s t r u c t u r e d , the performance improvement shown i s v e r y s i g n i f i c a n t . Among the f o u r r e s t r u c t u r i n g a l g o r i t h m s , TC2 (a member of the BLI r e s t r u c t u r i n g a l g o r i t h m ) works e x t r e m e l y w e l l i n r e d u c i n g the page f a u l t r a t e and o u t p e r f o r m s the o t h e r s by n o n - n e g l i b l e amounts. The r e s u l t s of TC2 c o n f i r m the c l a i m t h a t most page f a u l t s o c cur a t phase t r a n s i t i o n s . Hence p u t t i n g more w e i g h t s on the t r a n s i t i o n b l o c k s can reduce the page f a u l t r a t e s i g n i f i c a n t l y . W h i l e the CWS a l g o r i t h m comes second t o TC2 i n the r e d u c t i o n of page f a u l t s , i n some comparsions i t i s s l i g h t l y more e f f e c t i v e i n r e d u c i n g the average w o r k i n g s e t s i z e . As e x p e c t e d , CWS works best when the window s i z e s e l e c t e d f o r the working set p o l i c y s i m u l a t i o n matches w i t h the r e s t r u c t u r i n g parameter. As a matter of f a c t , both the NEAR and PTN1 a l g o r i t h m s , though i n f e r i o r t o TC2 and CWS, p e r f o r m r e a s o n a b l y D i s c u s s i o n of R e s u l t s 43 s a t i s f a c t o r i l y f o r t h e i r r e l a t i v e s i m p l i c i t y as w e l l as low c o s t . In the case of page f a u l t r a t e , NEAR and PTN1 manage t o o b t a i n an average r e d u c t i o n of 25% and 3.1% r e s p e c t i v e l y . The p e r c e n t a g e r e d u c t i o n i n the mean working s e t s i z e f o r a l l f o u r a l g o r i t h m s t u r n e d out t o have the same or d e r of magnitude. Table 4.1. Comparsion of the 4 r e s t r u c t u r i n g a l g o r i t h m s on p e r c e n t a g e r e d u c t i o n i n page f a u l t r a t e r e f e r e n c e r e s t r u c t u r i n g a l g o r i t h m s s t r i n g NEAR CWS PTN1 TC2 P1 23.4 32.3 32.0 37.8 P2 25.3 33.2 35.4 36. 1 P3 22.2 28.7 29.9 35.6 P4 26. 1 31 .5 31.0 41.8 P5 30.8 33.4 33.0 42.5 P6 25.9 35.2 33.7 40. 1 D i s c u s s i o n of R e s u l t s 44 T a b l e 4.2. Comparsion of the 4 r e s t r u c t u r i n g a l g o r i t h m s on p e r c e n t a g e r e d u c t i o n i n average working set s i z e r e f e r e n c e r e s t r u c t u r i n g a l g o r i t h m s s t r i n g NEAR CWS PTN1 TC2 PI 27.5 31.6 27.5 28.6 P2 27.2 27.8 27.2 23. 1 P3 25.2 28.7 25.7 25.6 P4 24.7 30.4 23.7 26.3 P5 28.2 25.2 25.6 30.5 P6 24.8 26.9 26. 1 28.9 D i s c u s s i o n of R e s u l t s 45 4.3 Average t r a n s i t i o n s e t s i z e s and average phase s e t s i z e s ( b l o c k s ) r e f e r e n c e average average s t r i n g phase t r a n s i t i o n set s i z e s e t s i z e PI 4.180 8. 109 P2 4.302 10.050 P3 4.550 10.027 P4 4.397 11.830 . P5 4. 445 10.336 P6 4.444 10.281 Next we examined the performance between TC2 and CWS by l o o k i n g a t the d i s t r i b u t i o n s of working s e t s i z e s d u r i n g the s i m u l a t e d e x e c u t i o n of the r e s t r u c t u r e d program (see F i g u r e 4.1). We observed the same k i n d of b e h a v i o r i n a l l c a s e s w i t h v a r i o u s r e f e r e n c e s t r i n g s . T h e i r p r o p e r t i e s a re d e s c r i b e d as f o l l o w s : (1) Both TC2 and CWS r e a c h almost the same maximum i n working s e t s i z e . They p e r f o r m b e t t e r than NEAR and PTN1 by 20% and n o n - r e s t r u c t u r i n g by 40%. D i s c u s s i o n of R e s u l t s 46 (2) In the CWS cu r v e (see F i g u r e 4.1), the working s e t s i z e w i t h the h i g h e s t f r e q u e n c y of o c c u r i n g were l e s s than or e q u a l t o f o u r pages. W h i l e TC2 had i t s m a j o r i t y ranges from 2 t o 5. (3) The CWS cu r v e drops a b r u p t l y a f t e r the f i r s t peak and then m a i n t a i n a g e n t l e s l o p e and forms a t i l t e d p l a t f o r m a t the end. While TC2 s t a r t s t o c l i m b v e r y s h a r p l y t o the l e f t of the peak, and s l i d e s down smoothly t o the bottom as the working s e t s i z e i n c r e a s e s . Thus the p r o b a b i l i t y of h a v i n g the v e r y l a r g e w o r k i ng s e t s i s l e s s i n TC2. The b e h a v i o r of the two c u r v e s can be b e t t e r u n d e r s t o o d by s t u d y i n g the d i f f e r e n t n a t u r e and o b j e c t i v e s of the two r e s t r u c t u r i n g a l g o r i t h m s . P r o p e r t y (2) can be e x p l a i n e d by the f a c t t h a t CWS tends t o p r e d i c t the major phases v e r y w e l l and i s thus a b l e t o m a i n t a i n the h i g h f r e q u e n c y working se t s i z e s t o be e q u a l t o or l e s s than the average s i z e of the major phase s e t s . D u r i n g phase t r a n s i t i o n s , the f a u l t r a t e as w e l l as the w o r k i n g s e t s i z e i n c r e a s e . S i n c e TC2 i s d e s i g n e d t o group t r a n s i t i o n b l o c k s t o g e t h e r , i t manages t o cu t down the page f a u l t r a t e and the f r e q u e n c y of l a r g e w o r k i n g s e t s i z e . T h i s i s i n d i c a t e d by p r o p e r t y ( 3 ) . D i s c u s s i o n of R e s u l t s 47 4.2 Data S e n s i t i v i t y As mentioned i n s e c t i o n 3.3, the dynamic b e h a v i o r of the program t o be r e s t r u c t u r e d i s a f f e c t e d by the i n p u t d a t a used. Thus i t i s not c l e a r t h a t a program r e s t r u c t u r e d based on a s p e c i f i c s e t of d a t a w i l l p e r f o r m e q u a l l y w e l l when the i n p u t d a t a a re d i f f e r e n t . We are i n t e r e s t e d t o see how s e n s i t i v e the improvement of program r e s t r u c t u r i n g i s w i t h r e s p e c t t o v a r i o u s i n p u t . In p a r t i c u l a r , we would l i k e t o study the r o b u s t n e s s of TC2 and CWS, i . e . , which one i s l e s s a f f e c t e d by the v a r i a t i o n of i n p u t d a t a . F i v e d i f f e r e n t b l o c k r e f e r e n c e s t r i n g s of the P a s c a l c o m p i l e r were o b t a i n e d u s i n g d i f f e r e n t s e t s of i n p u t d a t a . The P a s c a l c o m p i l e r was r e s t r u c t u r e d u s i n g f i r s t the CWS a l g o r i t h m and then the TC2 a l g o r i t h m based on one s e t of i n p u t d a t a ( P 2 ) . The performance of the r e s t r u c t u r e d program was s i m u l a t e d u s i n g the f i v e d i f f e r e n t b l o c k r e f e r e n c e s t r i n g s c o r r e s p o n d i n g t o the f i v e d i f f e r e n t s e t s of i n p u t d a t a . The r e s u l t s of the study a re summarized i n T a b l e 4.4 and Table 4.5. Both a l g o r i t h m s appear t o a d j u s t t o , v a r i o u s i n p u t v e r y w e l l and manage t o m a i n t a i n s a t i s f a c t o r y improvement on performance r e l a t i v e t o the o r i g i n a l o r d e r i n g . A l t h o u g h CWS appears t o be more r o b u s t D i s c u s s i o n of R e s u l t s 48 than TC2 i n terms of r e d u c t i o n i n page f a u l t r a t e , TC2 shows b e t t e r performance than CWS i n a l l c a s e s . CWS a l s o tends t o be more s t a b l e i n mean working s e t s i z e r e d u c t i o n . U s i n g the BLI d e f i n i t i o n of program b e h a v i o r we can o b t a i n from a b l o c k r e f e r e n c e s t r i n g a sequence of phase and t r a n s i t i o n s e t s . From the l a t t e r we can compute the average t r a n s i t i o n s e t s i z e of a p a r t i c u l a r b l o c k r e f e r e n c e s t r i n g . T h i s o b s e r v a b l e q u a n t i t y a l l o w s us t o p r e d i c t the performance improvement of the program t o be r e s t r u c t u r e d w i t h v a r i o u s d a t a i n p u t . We expect l a r g e average t r a n s i t i o n set s i z e t o g i v e r i s e t o h i g h e r f a u l t r a t e and a l s o h i g h e r f r e q u e n c y of l a r g e w o r k i n g s e t s i z e s . As shown i n T able 4.3, the average t r a n s i t i o n s e t s i z e s of the s i x r e f e r e n c e s t r i n g s tend t o be v e r y c l o s e t o each o t h e r . T h i s i s a rough i n d i c a t i o n t h a t the program i s r e l a t i v e l y i n s e n s i t i v e t o i n p u t d a t a . I t has been c o n f i r m e d i n the l i t e r a t u r e [20,23] and from our e x p e r i m e n t s t h a t most of the programs f o r which r e s t r u c t u r i n g i s c o n v e n i e n t (such as c o m p i l e r s ) are not v e r y data-dependent. However, t o f i n d an o p t i m a l l a y o u t f o r a p a r t i c u l a r program w i t h v a r i o u s i n p u t remains a n o n t r i v a l and e x p e n s i v e t a s k . The t a s k of s e l e c t i n g a " t y p i c a l " i n p u t f o r r e s t r u c t u r i n g r e l i e s v e r y much on the p a s t e x p e r i e n c e of D i s c u s s i o n of R e s u l t s 49 the e v a l u a t o r or the g e n e r a l . o p i n i o n of the u s e r s . o f the program t o be r e s t r u c t u r e d . T a b l e 4.4. R e s u l t s of an experiment on i n p u t dependency Performance i n d e x : % r e d u c t i o n i n page f a u l t s R e s t r u c t u r i n g A l g o r i t h m s : TC2 and CWS note: C i s t a n d s f o r c l u s t e r l a y o u t from r e f . s t r i n g P i where i=1 , 2 , . . , 6 TC2 CWS r e f e r e n c e s t r i n g C i C2 C i C2 PI 37.8 26. 1 32.3 30.4 P2 36. 1 33.2 P3 35.6 32.3 31 .8 28.7 P4 41.8 35.5 32.6 31 .5 P5 42.5 34.5 33.4 30.7 P6 40. 1 32.3 35.2 28.5 D i s c u s s i o n of R e s u l t s 50 Table. 4.5. R e s u l t s of an experiment on i n p u t dependency Performance Index: % r e d u c t i o n i n mean wo r k i n g s e t s i z e R e s t r u c t u r i n g A l g o r i t h m s : TC2 and CWS n o t e : C i s t a n d s f o r c l u s t e r l a y o u t from r e f . s t r i n g P i where i= 1,2,. . , 6 TC2 CWS r e f e r e n c e s t r i n g C i C2 C i C2 P1 28.6 17.4 31.6 23.2 P2 23..1 27.8 P3 25.6 21.4 28.7 26.4 P4 26.3 21.3 30.4 27.5 P5 30.5 23.9 25.2 24.4 P6 28.9 23.5 26.9 22.7 4.3 P o r t a b i l i t y Among the f o u r r e s t r u c t u r i n g a l g o r i t h m s , o n l y the CWS a l g o r i t h m i s dependent on the memory management p o l i c y i n D i s c u s s i o n of R e s u l t s 51 use. When a t a i l o r e d • program i s t r a n s p o r t e d t o an o t h e r system w i t h a d i f f e r e n t memory p o l i c y , i t i s almost c e r t a i n t h a t the performance w i l l be degraded. Both the NEAR and the BLI a l g o r i t h m s (TC2 and PTNT a r e members of BLI) a r e s t r a t e g y - i n d e p e n d e n t . They make use of o n l y the e x t r a c t e d i n f o r m a t i o n of the program r e f e r e n c e b e h a v i o r of the program and no system parameter i s i n v o l v e d . Thus these a l g o r i t h m s a r e a d a p t a b l e t o d i f f e r e n t environment f o r p r a c t i c a l use. Data c o l l e c t i o n at the s y m b o l i c (or s u b r o u t i n e ) l e v e l a l s o makes the work of r e s t r u c t u r i n g more p o r t a b l e . T h i s i s because we can d e a l w i t h the sour c e code of the program d i r e c t l y e s p e c i a l l y f o r thos e programs w r i t t e n i n h i g h - l e v e l languages which encourage s t r u c t u r e d programming. 4.4 Cost The c o s t s of r e s t r u c t u r i n g can be a n a l y z e d i n terms of the f o l l o w i n g a r e a s : d a t a c o l l e c t i o n , p r e p r o c e s s i n g phase ( c o n s t r u c t i n g the d e s i r a b i l i t y m a t r i x ) and c l u s t e r i n g phase. Data c o l l e c t i o n i s the most d i f f i c u l t and c o s t l y p a r t i n the p r o c e d u r e , p r i m a r i l y because i n most e x i s t i n g systems, t o o l s (hardware or s o f t w a r e ) f o r g a t h e r i n g the r e f e r e n c e t r a c e are not a v a i l a b l e . An a l t e r n a t i v e i s t o run D i s c u s s i o n of R e s u l t s 52 the program t o be r e s t r u c t u r e d i n t e r p r e t i v e l y by a s i m u l a t o r which, n e e d l e s s t o say, i s v e r y slow and e x p e n s i v e . N e v e r t h e l e s s the l a t t e r method was employed i n our e x p e r i m e n t . However, i n s t e a d of g a t h e r i n g a complete memory r e f e r e n c e s t r i n g , a t r a c e of s u b r o u t i n e c a l l s and r e t u r n s was r e c o r d e d . I t i s found t h a t r e s t r u c t u r i n g i s j u s t as e f f e c t i v e a t the s y m b o l i c l e v e l d e s p i t e the f a c t t h a t the l e n g t h of the r e f e r e n c e s t r i n g and the c o r r e s p o n d i n g c o s t a r e g r e a t l y reduced. The c o s t of r u n n i n g the r e s t r u c t u r i n g a l g o r i t h m v a r i e s r o u g h l y l i n e a r l y w i t h the l e n g t h of the r e f e r e n c e s t r i n g t o be examined. Among the f o u r a l g o r i t h m s , the c o s t ( i n terms of computer time) of NEAR i s the l e a s t and CWS c o s t s s l i g h t l y more than TC2 and PTN1. However, the c o s t of the r e s t r u c t u r i n g phase i s f a i r l y s m a l l compared t o the c o s t of da t a c o l l e c t i o n . The c o s t of c l u s t e r i n g depends q u a d r a t i c a l l y on the number of b l o c k s i n the program. The HEIR method i s much more s o p h i s t i c a t e d and e x p e n s i v e than NUCL but we s t i l l t h i n k i t i s more r e a s o n a b l e t o choose HIER f o r the s u b s t a n t i a l l y g r e a t e r improvement. D i s c u s s i o n of R e s u l t s T a b l e 4.6 Sample Cost of the R e s t r u c t u r i n g P r o c e d u r e c o s t (CPU sec) NEAR CWS PTN1 TC2 d a t a c o l l e c t i o n •<____ 900.188 > r e s t r u c t u r i n g phase 11.51 33.38 1 3.89 13. 05 c l u s t e r i n g phase 39.76 43.61 41 .06 42. 61 w o r k i n g s e t s i m u l a t i o n < 31.414 D i s c u s s i o n of R e s u l t s 54 5600 4800 4000 FREQUENCY 3200 2400 1600 800 00 0.0 * * * ** * * * * * * * * * * * * * TC2 + + + + + + + + + + * * * * * + * + + * + +* + * * + * + * . * * * * * * * * * * * * * * * * * * * * + + * + * + + +******* + * ++ * + + * . CWS + * + •• ++ ** 2.0 4.0 6.0 8.0 10.0 12.0 WORKING SET SIZES (PAGES) F i g u r e 4.1. Working s e t s i z e d i s t r i b u t i o n s of CWS and TC2 r e s t r u c t u r i n g a l g o r i t h m s C o n c l u s i o n and S u g g e s t i o n s 55 5 C o n c l u s i o n and S u g g e s t i o n s f o r F u t u r e Research 5.1 C o n c l u s i o n Program r e s t r u c t u r i n g has been shown t o be e f f e c t i v e t o improve program performance i n v i r t u a l memory systems. We have d e v e l o p e d a whole c a t e g o r y of h e u r i s t i c s f o r program r e s t r u c t u r i n g based on the n o t i o n of Bounded L o c a l i t y I n t e r v a l ( B L I ) . In p a r t i c u l a r , the TC2 a l g o r i t h m g i v e s v e r y good performance i n r e d u c i n g the page f a u l t r a t e (an average of 39% i n our e x p e r i m e n t s ) . I t o u t p e r f o r m s o t h e r a l g o r i t h m s i n c l u d i n g the s t r a t e g y - o r i e n t e d C r i t i c a l - w o r k i n g - s e t a l g o r i t h m by at l e a s t 20%. The r e s u l t s of our exp e r i m e n t s j u s t i f y the o b s e r v a t i o n made i n the l i t e r a t u r e t h a t phase t r a n s i t i o n s d u r i n g program e x e c u t i o n have s t r o n g i n f l u e n c e on the page f a u l t r a t e . The o b j e c t i v e of d e v e l o p i n g an e f f i c i e n t and s t r a t e g y - i n d e p e n d e n t r e s t r u c t u r i n g a l g o r i t h m i s a c h i e v e d . Two parameters, the mean t r a n s i t i o n s e t s i z e and the mean phase set s i z e , of the p h a s e / t r a n s i t i o n program b e h a v i o r model are s t u d i e d . U n f o r t u n a t e l y we a r e unable t o e s t a b l i s h any s t r o n g c o r r e l a t i o n between these parameters and the performance i n d i c e s i n our e x p e r i m e n t s . However, i t C o n c l u s i o n and S u g g e s t i o n s 56 i s o b s e r v e d t h a t i f the mean t r a n s i t i o n s e t s i z e s and the mean phase s e t s i z e s of a program r u n n i n g on v a r i o u s s e t s of i n p u t d a t a a r e s i m i l a r , we can expect the program t o be more or l e s s d a t a - i n d e p e n d e n t and v i c e v e r s a . Moreover, i f the wor k i n g s e t pag i n g a l g o r i t h m i s the memory p o l i c y i n use, c h o o s i n g a window s i z e which i s s l i g h t l y g r e a t e r than the mean t r a n s i t i o n s e t s i z e w i l l g e n e r a l l y r e s u l t i n good performance. That suggests t h a t , i f the window s i z e i s a l l o w e d t o v a r y f o r d i f f e r e n t programs, the mean t r a n s i t i o n s e t s i z e of the program i s a good g u i d e l i n e f o r the c h o i c e of the window s i z e . 5.2 S u g g e s t i o n s f o r F u t u r e R e s e a r c h Choosing the r i g h t parameters t o c h a r a c t e r i z e program b e h a v i o r remains one of the i m p o r t a n t r e s e a r c h t o p i c s t o be e x p l o r e d . The n o t i o n of Bounded L o c a l i t y I n t e r v a l (BLI) p r o v i d e s us w i t h r i c h i n f o r m a t i o n about major phases and t r a n s i t i o n s from a r e f e r e n c e s t r i n g . In our ex p e r i m e n t , we have s t u d i e d the e f f e c t of the mean t r a n s i t i o n s e t s i z e and mean phase s e t s i z e on performance improvement. An e x t e n s i o n t o the study would be a more d e t a i l e x a m i n a t i o n of the d i s t r i b u t i o n s of the t r a n s t i o n s e t s i z e s and the phase s e t s i z e s . An a p p l i c a t i o n of such r e s e a r c h would be t o p r o v i d e g u i d e l i n e s f o r memory management p o l i c y t o adapt t o C o n c l u s i o n and S u g g e s t i o n s 57 changes i n program b e h a v i o r so as t o o p t i m i z e performance. As mentioned i n the p r e v i o u s c h a p t e r , i n o r d e r t o make program r e s t r u c t u r i n g more e c o n o m i c a l , the c o s t of c o l l e c t i n g the r e f e r e n c e s t r i n g has t o be m i n i m i z e d . An a l t e r n a t i v e s o l u t i o n t o i n t r e p r e t i n g the program by a s i m u l a t o r i s t o i n s e r t measurement probes i n t o the program t o be r e s t r u c t u r e d and e xecute the program a f t e r the m o d i f i c a t i o n . The t a s k becomes even s i m p l e r i f we a r e i n t e r e s t e d i n o b t a i n i n g a r e f e r e n c e s t r i n g o n l y a t the s y m b o l i c l e v e l . Such m o d i f i c a t i o n can be done w i t h the a i d of a c l e v e r " c o m p i l e r " which w i l l reduce the c o s t of d a t a c o l l e c t i o n . T h i s i s because much of the work r e q u i r e d can be c a r r i e d out d u r i n g the c o m p i l a t i o n p r o c e s s w i t h o n l y minor a d d i t i o n a l e f f o r t . S p e c i f i c a l l y , an o p t i m i z a t i o n o p t i o n f o r programs t o be c o m p i l e d and e x e c u t e d can be p r o v i d e d by the c o m p i l e r . The user who wants r e s t r u c t u r i n g has t o submit the source code and a set of i n p u t d a t a i f needed by the program, and t u r n s on the o p t i o n s w i t c h . The c o m p i l e r would be e x p e c t e d t o do the f o l l o w i n g : (1) As u s u a l , g e n e r a t e assembler codes i f the program i s e r r o r - f r e e . ( I t i s p o i n t l e s s t o p e r f o r m program C o n c l u s i o n and S u g g e s t i o n s r e s t r u c t u r i n g i f the program c o n t a i n s e r r o r s . ) 58 (2) I n s e r t check p o i n t s (assembly language statements n e c e s s a r y t o update a c o u n t e r ) , a t the e n t r y p o i n t of every r e l o c a t a b l e b l o c k i n the program. (3) Run the m o d i f i e d program w i t h the g i v e n i n p u t and c o l l e c t the b l o c k r e f e r e n c e s t r i n g . (4) U s i n g the r e f e r e n c e s t r i n g from ( 3 ) , p e r f o r m the r e s t r u c t u r i n g p r o c e d u r e , s p e c i f i c a l l y the r e s t r u c t u r i n g phase and the c l u s t e r i n g phase. (5) R e o r g a n i z e the l a y o u t of the o b j e c t code of the program based on i n f o r m a t i o n o b t a i n e d i n (4) and remove the c h e c k p o i n t s . (6) Return the o b j e c t code t o the user and d i s p l a y o t h e r measurement i n f o r m a t i o n such as the d e s i r a b i l i t y m a t r i x , the r e s u l t i n g c l u s t e r s e t c . , i f r e q u e s t e d . The work of i n s e r t i n g measurement probes i n t o the o b j e c t code by the c o m p i l e r i s s t r a i g h t - f o r w a r d and easy t o do. The e n t i r e r e s t r u c t u r i n g p r o c e d u r e can be i n v o k e d by the c o m p i l e r as an independent p r o c e s s which t a k e s the m o d i f i e d program t o be r e s t r u c t u r e d and produces the C o n c l u s i o n and S u g g e s t i o n s 59 i n f o r m a t i o n f o r the c o m p i l e r t o r e o r g a n i z e the o b j e c t code a c c o r d i n g l y . C o n s i d e r i n g the reduced c o s t of d a t a c o l l e c t i o n and the r e l a t i v e l y low c o s t of r e s t r u c t u r i n g , such o p t i m i z a t i o n o p t i o n f o r programs t o be e x e c u t e d v e r y f r e q u e n t l y would be v e r y u s e f u l and. c o s t - e f f e c t i v e . Moreover, the near t r a n s p a r e n c y and e a s e - o f - u s e c h a r a c t e r i s t i c s of such f e a t u r e would be g r e a t l y a p p r e c i a t e d by the computer u s e r s . B i b l i o g r a p h y GO BIBLIOGRAPHY [1] M.S. Achard, J.Y.Babonneau, M . C a r p e n t i e r , G . M o r i s s e t , M.B.Mounajjed, "The C l u s t e r i n g A l g o r i t h m s i n the Opale R e s t r u c t u r i n g System," Performance of Computer I n s t a l l a t i o n , D. F e r r a r i ( e d . ) CILEA, N o r t h - H o l l a n d P u b l i s h i n g Co.,1978 . [2] A. P. Batson and W. Madison, "Measurements of major l o c a l i t y phases i n s y m b o l i c r e f e r e n c e s t r i n g s , " i n P r o c . I n t . Symp. Computer Performance M o d e l i n g , Measurement, and E v a l u a t i o n , ACM SIGMETRICS and I F I P WG7.3, Mar. 1976,pp.75-84. [3] A. P. Ba t s o n , "Program b e h a v i o r at the s y m b o l i c l e v e l , " Computer, vol.9,no.11,pp.21-28, Nov. 1976. [4] A. P. B a t s o n , W. E. B l a t t , and J . P. Kearns, " S t r u c t u r e w i t h i n l o c a l i t y i n t e r v a l s , " i n P r o c . Symp. M o d e l i n g and Performance E v a l u a t i o n of Computer Systems, H. B e i l n e r and E. Gelenbe, Eds. Amsterdam, The N e t h e r l a n d s : N o r t h - H o l l a n d , Oct. 1977, pp.221-232. [5] L. A. B e l a d y , "A study of replacement a l g o r i t h m s f o r v i r t u a l s t o r a g e computers," IBM S y s t . J . , v o l . 5 , no.2, pp.78-101, 1966. [6] L. A. B e l a d y , and C. J . Kuehner, "Dynamic space s h a r i n g i n computer systems," Commun. ACM, v o l . 1 2 , pp282-288, May 1969. [7] B. Brawn and F. G. Gustavson, "Program b e h a v i o r i n a pag i n g environment," i n 1968 AFIPS Conf. P r o c , F a l l J o i n t Comput. Conf., v o l . 3 3 , Washington, DC: Thompson, 1968, pp.1019-1032. B i b l i o g r a p h y [8] W. W. Chu and H. Opderbeck, "The page f a u l t f r e q u e n c y replacement a l g o r i t h m , " P r o c . FJCC, 1972, pp.597-609. [9] W. W. Chu and H. Opderbeck, "Program b e h a v i o r and the page f a u l t f requency a l g o r i t h m , " IEEE Computer 9 11, Nov. 1976, pp.29-38.. [10] L. W. Comeau, "A study of the e f f e c t of user program o p t i m i z a t i o n i n a pag i n g system," i n P r o c . ACM Symp. O p e r a t i n g Systems P r i n c i p l e s , Oct. 1967. [11] P. J . Denning, "The wor k i n g s e t model f o r program b e h a v i o r , " Commum. ACM, v o l . 1 1 , pp.323-333, May 1968. [12] P. J . Denning and S. C. Sch w a r t z , " P r o p e r t i e s of the working s e t model," Commum. ACM, v o l . 1 5 , pp.191-198, Mar. 1972. [13] P. J . Denning, "On modeling program b e h a v i o r , " i n 1972 AFIPS Conf. P r o c , S JCC, v o l . 4 0 , M o n t v a l e , NJ: AFIPS P r e s s , 1972, pp.937-944. [14] P. J . Denning and G. S. Graham, "Multiprogramming memory management," IEEE P r o c , v o l . 6 3 , pp.924-939, June 1975. [15] P. J . Denning and K. C. Kahn, "A study of program l o c a l i t y and l i f e t i m e f u n c t i o n s , " i n P r o c 5th ACM Symp. O p e r a t i n g Systems P r i n c i p l e s , Nov.1975, pp.207-216. [16] P. J . Denning and K. C. Kahn, "An L=S c r i t e r i o n f o r o p t i m a l multiprogramming," i n P r o c . I n t . Symp.Computer Performance M o d e l i n g , Measurement, and E v a l u a t i o n , ACM SIGMETRICS and I F I P WG7.3, Mar. 1976,pp.219-229. [17] P. J . Denning, K. C. Kahn, J . L e r o u d i e r , D. P o t i e r , and R. S u r i , "Optimal multiprogramming," A c t a I n f o r m a t i c a , v o l . 7 , no.2, pp.197-216, 1976. B i b l i o g r a p h y 62 [18] P. J . Denning, "Working S e t s Past and P r e s e n t " IEEE T r a n s , on Software E n g i n . Vol.SE-6,No.1, Jan 1980. [19] D. F e r r a r i , "Improving L o c a l i t y by C r i t i c a l Working s e t s , " CACM, v o l . 1 7 , Nov. 1974, pp.614-620. [20] D. F e r r a r i , "Improving Program L o c a l i t y by S t r a t e g y - O r i e n t e d R e s t r u c t u r i n g , " . I n f o r m a t i o n P r o c e s s i n g 74, P r o c . I F I P Congress 74, N o r t h - H o l l a n d , Amsterdam, 1974, pp266-270. [21] D. F e r r a r i , " T a i l o r i n g Programs t o Models of Program B e h a v i o r , " IBM J o u r n a l of Research and Development, v o l . 1 9 , 3, May 1975, pp.244-251. [22] D. F e r r a r i , "The improvement of program b e h a v i o r , " IEEE Computer 9 11, Nov. 1976, pp.39-47. [23] D. J . H a t f i e l d and J . G e r a l d , "Program r e s t r u c t u r i n g f o r v i r t u a l memory," IBM Sys. J . v o l . 1 0 , pp.168-192, 1 971 . [24] K. C. Kahn, "Program b e h a v i o r and l o a d dependent system performance," Ph.D. D i s s e r t a t i o n , Dep. Computer S c i . , Purdue U n i v . , W. L a f a y e t t e , IN, Aug. 1976. [25] A. W. Madison and A. P. Ba t s o n , " C h a r a c t e r i s t i c s of program l o c a l i t i e s , " CACM, v o l . 1 9 , pp.285-294, May 1976. [26] T. Masuda, H. S h i o t a , K. Noguchi, and T. O h k i , " O p t i m a z t i o n of program l o c a l i t y by c l u s t e r a n a l y s i s , " i n P r o c . I F I P Congress, 1974, pp.261-265. [27] T. Masuda, "Methods For the Measurement of Memory U t i l i z a t i o n and the Improvement of Program L o c a l i t y " , IEEE Trans. on So f t w a r e E n g i n . , vol.SE-5,NO.6, Nov 1979. [28] A. J . Smith, "A m o d i f i e d working s e t pag i n g B i b l i o g r a p h y a l g o r i t h m , " IEEE T r a n s . Comput., v o l . C - 2 5 , pp.907-914, Sept.1976. [29] J . R . S p i r n and P. J . Denning, "Experiments w i t h program l o c a l i t y , " i n AFIPS Conf. P r o c , FJCC, v o l . 4 1 , M o n t v a l e , NJ: AFIPS P r e s s , 1 9 7 2 , pp.61 1-621. [30] J . R. S p i r n , " D i s t a n c e s t r i n g models f o r program b e h a v i o r , " Computer, v o l . 9 . , pp.14-20, Nov. 1976. [31] J.-R. S p i r n , Program B e h a v i o r : Models and Measurement. New York: E l s e v i e r / N o t h - H o l l a n d , 1977. [32] G. S. Graham, "A Study of Program and Memory P o l i c y B e h a v i o u r , " (Ph.D. T h e s i s ) , Purdue U n i v e r s i t y , Computer S c i e n c e Dept, 1976. [33] R. L. M a t t s o n , J . - G e s c e i , D. R. S l u t z and I . L. T r a i g e r , " E v a l u a t i o n t e c h n i q u e s f o r s t o r a g e h i e r a r c h i e s , " IBM Sys. J . 9 2 (1970), pp.78-117. Appendix I . R e f e r e n c e S t r i n g s Appendix I . ° R e f e r e n c e S t r i n g s The r e f e r e n c e s t r i n g i s d e f i n e d as the c h r o n o l o g i c a l sequence of the v i r t u a l a d d r e s s e s ( a j ) r e f e r e n c e d by the program, each w i t h (or w i t h o u t ) an i n d i c a t i o n of the CPU (or v i r t u a l ) time t j t o the next r e f e r e n c e : { a j ( t j ) } ( j = 1,2,...,k) where k i s the number of r e f e r e n c e s g e n e r a t e d by the program. S e v e r a l o t h e r c h a r a c t e r i z a t i o n s can be d e r i v e d from a r e f e r e n c e s t r i n g . For example, we may group v i r t u a l a d d r e s s e s i n t o b l o c k s . Given a s e t of b l o c k s B = {b1,b2,...,bn], we may d e f i n e d a many-to-one mapping from the s e t A of v i r t u a l a d d r e s s e s t o B, so t h a t each a j i s a s s o c i a t e d w i t h one and o n l y one b l o c k b i . T h i s mapping when a p p l i e d t o each element of the a d d r e s s t r a c e ( a j ( t j ) } , t r a n s f o r m s i t i n t o the b l o c k t r a c e or b l o c k r e f e r e n c e s t r i n g : { b i ( t j ) } (j=1,2,...,k) Each b l o c k u s u a l l y c o n s i s t s of i n f o r m a t i o n items h a v i n g c o n t i g u o u s a d d r e s s e s i n v i r t u a l space, so t h a t b l o c k s a r e t r e a t e d as s i n g l e e n t i t i e s d u r i n g t r a n s f e r s and f o r a l l o c a t i o n p u r p o s e s . Appendix I I . Paging A l g o r i t h m s Appendix I I . P a g i n g A l g o r i t h m s A paged system t r a n s f e r s i n f o r m a t i o n t o and from main memory i n f i x e d s i z e u n i t s , c a l l e d pages. The paging a l g o r i t h m i n such systems i s r e s p o n s i b l e f o r the f e t c h i n g , placement and replacement of pages i n main memory. A pr e p a g i n g a l g o r i t h m t r i e s t o a n t i c i p a t e page r e f e r e n c e s of a t a s k i n the near f u t u r e (and b r i n g s i n those pages b e f o r e they a r e r e f e r e n c e d ) i n an attempt t o reduce the page f a u l t w a i t i n g t i m e . However, such p r e d i c t i o n s a re d i f f i c u l t t o make a c c u r a t e l y . Thus, except f o r a few systems ( p a r t i c u l a r l y those t h a t use the wo r k i n g s e t p o l i c y f o r memory management), most v i r t u a l memory systems use demand pagi n g ( i . e . , pages a r e brought i n t o main memory o n l y when r e f e r e n c e d ) . L e t N = { 0 , 1 , 2 n - 1 } be the s e t of pages of a t a s k , and l e t M (t) = { 0 , l , 2 , . . . . m ( t ) - l } be the s e t of page frames i n main memory a l l o c a t e d t o the t a s k . We s h a l l assume t h a t n i s c o n s t a n t w i t h 1<=m(t)<n. We c a l l m(t) the memory a l l o c a t i o n of the ta s k a t time t . I f m(t) i s a c o n s t a n t t h i s i s c a l l e d f i x e d a l l o c a t i o n . When m(t) i s a l l o w e d t o v a r y w i t h t i m e , we have a v a r i a b l e or dynamic a l l o c a t i o n scheme. Appendix I I . Paging A l g o r i t h m s ^5 Le t the memory r e f e r e n c e s . of a t a s k be r (1 ) r (2) r (3)..... . r ( K ) , where r ( t ) i s the page r e f e r e n c e d a t v i r t u a l time t . We s h a l l use S ( t ) t o denote the s e t of pages i n main memory j u s t a f t e r the r e f e r e n c e a t time t (the S sta n d s f o r " s t o r a g e " ) . For a l l t , we have S ( t ) a subset of N and |S(t)|<=m(t). We s h a l l use S(0) t o i n d i c a t e the i n i t i a l c o n t e n t of memory, b e f o r e the f i r s t r e f e r e n c e . F o r m a l l y , the d e f i n i t i o n of a s t r i c t demand paging a l g o r i t h m g i v e s S(t+1) as a f u n c t i o n of S ( t ) : S ( t ) i f r( t + 1 ) i n S ( t ) S(t+1) = S ( t ) + r ( t + 1 ) - Z ( t + 1 ) i f r(t+1) not i n S ( t ) where Z(t+1), the r e p l a c e d page s e t , i s a subset of S ( t ) . In o t h e r words, i f no page f a u l t o c c u r s , the memory c o n t e n t i s unchanged. I f r(t+1) i s not i n S ( t ) , a page f a u l t o c c u r s and the m i s s i n g page i s brought i n t o memory, r e p l a c i n g the set of pages Z(t+1). I f |S(t)|=m (a c o n s t a n t ) f o r a l l t , then Z ( t ) c o n s i s t s of e x a c t l y one page z ( t ) , the r e p l a c e d page. Stack a l g o r i t h m s [33] a r e a p a r t i c u l a r l y i n t e r e s t i n g c l a s s of f i x e d - a l l o c a t i o n p a g i n g a l g o r i t h m s . At each i n s t a n t of t i m e , a s t a c k a l g o r i t h m defines, a v e c t o r (the " s t a c k " ) on some or a l l of the pages of a t a s k . The s t a c k a t time t i s v s ( t ) = [ s 1 ( t ) , . . . , s k ( t ) ] , w i t h k<=n, (n i s t o t a l number of pages needed by a t a s k ) such t h a t i f the a l g o r i t h m Appendix I I . P a g i n g A l g o r i t h m s o p e r a t e s w i t h memory a l l o c a t i o n m, then the memory w i l l c o n t a i n e x a c t l y the s e t of pages { s i ( t ) , sm(t)} i f m<=k S(m,t) = { s i ( t ) , .... . s k ( t ) } i f m>k a t time t . By c o n v e n t i o n , s 1 ( t ) , the f i r s t element i n the s t a c k v e c t o r , i s t o be a t the t o p of the s t a c k , and s k ( t ) a t the bottom. We say t h a t s i ( t ) i s lower i n the s t a c k than s j ( t ) i f i > j . The s t a c k d i s t a n c e d ( t ) i s d e f i n e d t o be the p o s i t i o n (or index i n the s t a c k ) of r ( t ) i n s t a c k v s ( t - l ) . I f r ( t ) = s i ( t - l ) then d ( t ) = i , w i t h 1<=i<=k. I f r ( t ) does not appear anywhere i n v s ( t - l ) , then d ( t ) i s e q u a l t o " i n f i n i t y " . At each page r e f e r e n c e , the s t a c k v e c t o r i s updated a c c o r d i n g t o the f o l l o w i n g t h r e e r u l e s : (1) The page j u s t r e f e r e n c e d i s moved t o the t o p of s t a c k . (2) An u n r e f e r e n c e d page never moves up the s t a c k . That i s t o say, pages above the one r e f e r e n c e d can e i t h e r remain a t t h e i r c u r r e n t p o s i t i o n or be d i s p l a c e d downwards a c c o r d i n g t o t h e i r p r i o r i t i e s . (3) Pages below the r e f e r e n c e d page remain f i x e d i n the s t a c k . G iven a memory a l l o c a t i o n of m page frames, the t o p m Appendix I I . Paging A l g o r i t h m s ••€•§>' pages i n the s t a c k a r e always m a i n t a i n e d i n main memory. The s t a c k a l g o r i t h m s have two b a s i c advantages. F i r s t , the page f a u l t b e h a v i o r of a g i v e n r e f e r e n c e s t r i n g can be computed e f f e c t i v e l y f o r a l l memory s i z e s i n one scan of the r e f e r e n c e s t r i n g . The o t h e r advantage i s t h a t f o r any g i v e n r e f e r e n c e s t r i n g , the number of page f a u l t s produced by a s t a c k a l g o r i t h m does not i n c r e a s e as memory a l l o c a t i o n (m) i n c r e a s e s . Due t o the i n c l u s i o n p r o p e r t y of s t a c k a l g o r i t h m s , the top (m+k) pages (k>0) on the s t a c k always i n c l u d e the top m pages. T h i s i n t u r n i m p l i e s t h a t i f a page f a u l t o c c u r s when the memory a l l o c a t i o n i s (m+k) where (k>0), then a page f a u l t must occur i f the memory a l l o c a t i o n i s reduced t o m. The same may not be t r u e f o r o t h e r page replacement a l g o r i t h m s . Appendix I I . Paging A l g o r i t h m s Appendix I l a . The L e a s t R e c e n t l y Used (LRU) p a g i n g a l g o r i t h m The LRU pag i n g a l g o r i t h m i s a s t a c k a l g o r i t h m . T h i s a l g o r i t h m chooses f o r replacement t h a t page i n memory which has not been r e f e r e n c e d f o r the l o n g e s t p e r i o d of t i m e . The s t a c k v s ( t ) f o r the LRU a l g o r i t h m c o n s i s t s of a l l pages of the t a s k o r d e r e d by d e c r e a s i n g time of t h e i r most r e c e n t r e f e r e n c e . Thus, s l ( t ) i s the most r e c e n t l y used page (which i s r ( t ) ) , s 2 ( t ) i s the next most r e c e n t l y used page, and s n ( t ) i s the l e a s t r e c e n t l y used page. Pages which have never been r e f e r e n c e d a re grouped t o g e t h e r at the bottom of the s t a c k i n any a r b i t r a r y o r d e r . The p r o c e d u r e f o r u p d a t i n g the LRU s t a c k i s c o n c e p t u a l l y q u i t e s i m p l e . I f d ( t ) = i , then s l ( t ) = r ( t ) , and s j ( t ) = s j - 1 ( t ) f o r a l l j such t h a t 1<j<=i. Each e n t r y i n the s t a c k above the p o i n t of r e f e r e n c e i s moved down by one p o s i t i o n . Pages below the p o i n t of r e f e r e n c e do not move i n the s t a c k . The s t a c k v e c t o r f o r t h i s a l g o r i t h m i s time v a r y i n g , and must be updated a t eve r y r e f e r e n c e . Suppose v s ( t ) = [ x 1 x n ] , and r ( t + l ) = x i , t h e n : v s ( t + l ) = [ x i , x 1 , . . . , x i - 1 , x i + 1 , . . . , x n ] . Appendix I I . Paging A l g o r i t h m s Appendix l i b . The Working Set p a g i n g a l g o r i t h m The working s e t W(t,T) of a t a s k a t time t has been d e f i n e d by Denning [11,12] t o be the s e t of d i s t i n c t pages i n the T most r e c e n t r e f e r e n c e s r ( t - T + 1 ) . . . r ( t ) . Parameter T i s known as the window s i z e . The w o r k i n g s e t a l g o r i t h m r e t a i n s e x a c t l y the working s e t i n memory a t a l l t i m e s . Pages can j o i n or l e a v e the working s e t at o t h e r than page f a u l t t i m e s , so t h i s i s not a s t r i c t demand pag i n g a l g o r i t h m but a l o o s e one. S i n c e S(t)=W(t,T) a t a l l t i m e s , a page can be removed from main memory o n l y when i t has not been r e f e r e n c e d i n T c o n s e c u t i v e time i n s t a n t s . Appendix I I I . Example of the HIER C l u s t e r i n g A l g o r i t h m p i . Appendix I I I . An example t o i l l u s t r a t e the H i e r a r c h i c a l C l a s s i f i c a t i o n C l u s t e r i n g A l g o r i t h m . L e t J =• { b1 , b2, b3, b4 } be the s e t of b l o c k s t o be c l a s s i f i e d and the d e s i r a b i l i t y m a t r i x D be g i v e n by: ( b U {b2} {b3} {b4} 0 1 7 47 24 ( b U 0 0 12 68 {b2} 0 0 0 8 ( b 3 l 0 0 0 0 {b.4} Our g o a l i s t o c l a s s i f y J i n t o s u b s e t s , each of which r e p r e s e n t s a c l u s t e r of b l o c k s t h a t a r e s t r o n g l y a s s o c i a t e d t o each o t h e r based on the g i v e n d e s i r a b i l i t y measure. To s i m p l i f y the problem, we s h a l l assume t h a t the s i z e s of the b l o c k s are the same and e x a c t l y two b l o c k s can f i t i n t o a page. Step 1 : We s t a r t o f f w i t h JO = { { b i } , {b2}, {b3}, {b4} }, a se t of 4 c l u s t e r s each c o n t a i n i n g a s i n g l e b l o c k i n i t i a l l y . L e t DO = D, the d e s i r a b i l i t y m a t r i x . (1) F i n d . t h e l a r g e s t element i n DO, which i s d(2,4)=68. (2) S i n c e the sum of s i z e s of the 2 c l u s t e r s , {b2} and {b4}, i s equal t o the page s i z e , we merge {b2} and {b4} Appendix I I I . Example of the HIER C l u s t e r i n g A l g o r i t h m t o form a new c l u s t e r C={b2,b4}. Now J1 = { (b1}, {b3}, {b2,b4} }. (3) C o n s t r u c t the reduced m a t r i x D1 from DO as f o l l o w s : — d e l e t e a l l the rows and columns a s s o c i a t e d w i t h {b2} and {b4} -- and add row C ({b2,b4}) and column C t o D1 such t h a t d d , C ) (of D1) = d d , 2 ) + d(1,4) (of DO) d(2,C) (of D1) = d(2,3) + d(3,4) (of DO) {bi} {b3} {b2,b4} DO ==> D1 = 0 0 0 47 0 0 41 20 0 {bi} (b3) {b2,b4} Step 2: (1) From D1, d(l,2)=47 i s found t o be the l a r g e s t (2) We merge {bi} and {b3} t o form {b1,b3} (3) 32 = { {b1,b3], {b2,b4} } {b1,b3} {b2,b4} D1 ==> D2 = 108 0 {b1,b3] {b2,b4} Step 3: (1) 108 i s the l a r g e s t i n D2 (2) S i n c e the sum of s i z e s of the 2 c l u s t e r s exceeds the page s i z e , we can not merge the c l u s t e r s t o g e t h e r . Hence we r e p l a c e d(1,2) of D2 by z e r o t o i n d i c a t e the Appendix I I I . Example of the HIER C l u s t e r i n g A l g o r i t h m -\7p. merge i s u n s u c c e s s f u l . As a r e s u l t D3 becomes a z e r o m a t r i x and .J3 = J 2 . S t e p 4: The l a r g e s t element of D3 e q u a l s t o z e r o , the p r o c e s s i s h a l t e d s i n c e no new c l u s t e r can be formed based on D3. The f i n a l r e s u l t i s J3 which i s a s e t of c l u s t e r s each of which c o n s i s t s of a s e t of 2 b l o c k s and whose s i z e i s e q u a l t o the page s i z e . 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051822/manifest

Comment

Related Items