UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A new approach to program restructuring and clustering Yap, Tuan-Bin 1983

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

Item Metadata

Download

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

Full Text

A NEW  APPROACH TO PROGRAM RESTRUCTURING AND  CLUSTERING  by TUAN-BIN £YAP  B.Sc,  U n i v e r s i t y Of S y d n e y , 1979  A THESIS SUBMITTED IN PARTIAL FULFILMENT THE REQUIREMENTS FOR THE DEGREE OF MASTER OF  SCIENCE  in THE FACULTY OF GRADUATE STUDIES D e p a r t m e n t Of C o m p u t e r S c i e n c e  We a c c e p t t h i s t h e s i s a s c o n f o r m i n g to the r e q u i r e d  standard  THE UNIVERSITY OF B R I T I S H COLUMBIA October  ©  1983  T u a n - B i n Y a p , 1983  OF  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 available for reference  and study.  I further  agree that permission for extensive copying of t h i s thesis for scholarly purposes may  be granted by the head of  department or by his or her representatives.  my  It i s  understood that copying or publication 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 permission.  Department of  Comy^d-ex  ^CftZnC-C  The University of B r i t i s h Columbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 Date  DE-6 (2/79)  (Jobber  \ f c? 3  written  II  ABSTRACT A new  program r e s t r u c t u r i n g a l g o r i t h m aimed at reducing  working set s i z e  of  a  program  environment i s developed. The of  locality  as  executing  in  a  a l g o r i t h m makes use  working  the set  of the concept  d e f i n e d in the Bounded L o c a l i t y  Interval  (BLI)  program behaviour model to d i s c e r n program r e f e r e n c i n g p a t t e r n s . The  b a s i c p r i n c i p l e of t h i s as w e l l as a l l  algorithms  is  to  put  relocatable  referencing  pattern  experiments  were  new  r e l a t i v e to  scheme  a l g o r i t h m was  in  the  conducted the  a l s o evaluated  same  other  restructuring  blocks  having  a prominent  virtual  pages.  Simulation  to evaluate other  the performance of  existing  on a r e a l  algorithms.  the The  system which uses a c l o c k  page replacement s t r a t e g y . A new  c l u s t e r i n g scheme used i n the r e s t r u c t u r i n g procedure  i s a l s o developed. The problem The  new  technique  i n t o subproblems which can  decomposes  then be s o l v e d  c l a s s i c a l h i e r a r c h i c a l c l u s t e r i n g algorithm  complexity program  of n  to be  3  the  clustering  individually.  yields  a  time  where n i s the number of d i s t i n c t b l o c k s i n the r e s t r u c t u r e d . The  the time-complexity  decomposition approach reduces  of the a l g o r i t h m to  S e v e r a l other p r a c t i c a l aspects are a l s o d i s c u s s e d  i n the  thesis.  of  n . 2  program  restructuring  Ill TABLE OF CONTENTS 1. I n t r o d u c t i o n 1.1 R e s t r u c t u r i n g p r o c e d u r e 1.2 C l u s t e r i n g p h a s e 1.3 P r e v i o u s e x p e r i m e n t a l r e s u l t s 1.4 O b j e c t i v e s o f t h e t h e s i s  1 1 3 4 5  2. A s u r v e y o f r e s t r u c t u r i n g t e c h n i q u e s 2.1 N e a r n e s s method 2.2 C r i t i c a l - s e t a l g o r i t h m s 2.3 M i n i m a l - s e t a l g o r i t h m s  6 10 11 11  3. B L I - b a s 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 3.1 ASI a l g o r i t h m 3.2 B L I a l g o r i t h m  13 14 15  4. C l u s t e r i n g a l g o r i t h m s 4.1 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 method 4.2 A d e c o m p o s i t i o n a p p r o a c h t o c l u s t e r i n g p r o b l e m 4.2.1 M e t h o d A 4.2.2 G r a v i t a t i o n a l c l u s t e r i n g scheme 4.2.3 G r a v i t a t i o n a l - 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 method 4.2.4 A n a l y s i s o f t i m e c o m p l e x i t y 5. D e s c r i p t i o n o f e x p e r i m e n t 5.1 P a r a m e t e r s .5.1.1 P e r f o r m a n c e i n d i c e s 5.1.2 F a c t o r s 5.2 P r o c e d u r e o f e x p e r i m e n t 5.3 R e s t r u c t u r i n g a n d measurement t o o l s 5.3.1 D a t a c o l l e c t i o n 5.3.2 R e s t r u c t u r i n g a l g o r i t h m s 5.3.3 C l u s t e r i n g a l g o r i t h m s 5.3.4 Memory management p o l i c y s i m u l a t o r s 5.3.5 L i n k a g e e d i t o r 5.4 D e s i g n and i m p l e m e n t a t i o n 5.4.1 S e l e c t i o n o f l e v e l s f o r e x p e r i m e n t 5.4.2 I m p l e m e n t a t i o n d e t a i l s 6. D i s c u s s i o n o f e x p e r i m e n t a l r e s u l t s 6.1 E v a l u a t i o n o f B L I a l g o r i t h m 6.1.1 D i s c u s s i o n o f s i m u l a t i o n r e s u l t s 6.1.2 D i s c u s s i o n o f e m p i r i c a l r e s u l t s 6.1.3 C o s t 6.2 E v a l u a t i o n o f GHC c l u s t e r i n g scheme 6.3 C o n c l u s i o n s REFERENCES  17 ....18 21 21 23 24 26 28 28 28 29 30 32 .32 33 33 34 34 35 35 37 43 43 43 45 47 47 48 K C  IV  L I S T OF TABLES AND  T a b l e 5.1 T a b l e 5.2  FIGURES  S e l e c t i o n of l e v e l s f o r the r e s t r u c t u r i n g experiment  42  S e l e c t i o n of l e v e l s f o r the c l u s t e r i n g experiment  42  T a b l e 6.1a C o m p a r i s o n o f t h e r e s t r u c t u r i n g a l g o r i t h m s on t h e number o f page f a u l t s g e n e r a t e d i n a working s e t environment  ...52  T a b l e 6.1b C o m p a r i s o n o f t h e r e s t r u c t u r i n g a l g o r i t h m s on a v e r a g e w o r k i n g s e t s i z e i n a working s e t environment  52  T a b l e 6.2a C o m p a r i s o n o f t h e c l u s t e r i n g a l g o r i t h m s on t h e CPU p r o c e s s i n g t i m e ( i n msec.) d u r i n g the c l u s t e r i n g phase  53  T a b l e 6.2b C o m p a r i s o n o f t h e c l u s t e r i n g a l g o r i t h m s on t h e CPU p r o c e s s i n g t i m e ( i n msec.) d u r i n g the r e s t r u c t u r i n g phase  53  T a b l e 6.2c C o m p a r i s o n o f t h e c l u s t e r i n g a l g o r i t h m s on t h e CPU p r o c e s s i n g t i m e ( i n msec.) d u r i n g 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 phases  53  T a b l e 6.3  T a b l e 6.4  C o m p a r i s o n o f t h e c l u s t e r i n g a l g o r i t h m s on t h e number o f page f a u l t s g e n e r a t e d i n a working set environment Performance  of the r e s t r u c t u r e d P a s c a l  c o m p i l e r on MTS F i g u r e 3.1 A h i e r a r c h y o f bounded l o c a l i t y F i g u r e 5.1 L a y o u t  54  54 interval  of a P a s c a l nested r o u t i n e  14 41  F i g u r e 6.1 P a g i n g c h a r a c t e r i s t i c s o f r e f e r e n c e s t r i n g P3 ...55  V  ACKNOWLEDGEMENTS I would l i k e to thank assistance  Dr. S.  Chanson  for h i s valuable  in the research and in the writing of this thesis,  and for spending generous portions of his time in discussing i t s progress.  I am also grateful to John Stevens  for many  discussions and for his time in reading the thesis.  helpful  1  Chapter J _ I n t r o d u c t i o n R e d u c i n g t h e page f a u l t paged The  virtual  memory  s i m p l e s t way  However,  r a t e t o improve t h e performance  s y s t e m s c a n be a c h i e v e d  i s to  increase  the  computer a r c h i t e c t u r e l i m i t s  of  i n s e v e r a l ways.  size  of  main  memory.  t h e maximum memory s i z e a  s y s t e m may assume. F u r t h e r m o r e , t h e e v e r  g r o w i n g demand o f  main  memory h a s c o n s t a n t l y o u t p a c e d memory i n c r e a s e s i n new m a c h i n e s . Thus  r e s e a r c h e r s have w o r k e d on o t h e r methods a s w e l l .  i n page  replacement  received and  algorithms  to  minimize  paging  performance  locality known  can  also  be  of t h e programs r u n n i n g  as  property  program  of  programs.  'locality'  The  basic  program b l o c k s  another  over  virtual  by  in  the  Various  algorithm  thesis,  a  of  time  restructuring  new  i s described.  improving  technique,  because  of of  the most  are  put  in  algorithms  strategy-independent As w e l l ,  r e f e r e n c i n g one the have  same been  r a t e by 20-40%. restructuring  several practical  aspects of  p r o g r a m r e s t r u c t u r i n g i n c l u d i n g a new a p p r o a c h t o c l u s t e r together  the  of program r e s t r u c t u r i n g i s t o  d e v i s e d a n d h a v e been shown t o r e d u c e page f a u l t this  near-optimal.  behaviour  i n s u c h a way t h a t b l o c k s  extended periods  pages.  improved  i s viable  exhibited principle  be  on t h e s y s t e m . T h i s  restructuring,  arrange  In  activity  much a t t e n t i o n i n t h e l a t e s i x t i e s a n d e a r l y s e v e n t i e s  t h e c u r r e n t s t r a t e g i e s h a v e been shown t o  System  Research  blocks  are also discussed.  1.1 R e s t r u c t u r i n g p r o c e d u r e  R e s t r u c t u r i n g p r o c e d u r e u s u a l l y c o n s i s t s of steps :  the  following  1)  The  program  blocks  t o be  which  are  instructions.  restructured is divided into relocatable either  Address  contiguous  blocks  trace collected  program i s transformed  into  of  data  from e x e c u t i o n  i t s corresponding  block  or  of  the  reference  string.  2)  The  string  i s processed  between b l o c k s can  be  the  i s computed and  thought  b l o c k s and  and  of  labels  as  of  strength  of  connectivity  stored in a matrix.  The  matrix  a graph w i t h nodes r e p r e s e n t i n g  edges  representing  the  the  connectivity  between b l o c k s .  3) •  A c l u s t e r i n g a l g o r i t h m i s a p p l i e d t o t h e b l o c k s b a s e d on  . .connectivity  information  o b j e c t i v e of m i n i m i z i n g  s t o r e d i n ..the. inter-page  p a g e s i z e c o n s t r a i n t . The  result  s p e c i f y i n g which blocks are  4 ) The  program  is  is  t o be  matrix  references  .with the.  subject  a block-to-page  placed  restructured  according  restructuring  algorithms  in  they  i n the  to  the  to  mapping  same p a g e .  the  resulting  layout.  The  various  procedure)  differ  connectivity algorithm (i,j)th follows  between  the  way  blocks.  An  i s t h e n e a r n e s s m e t h o d [10]  e n t r y of the m a t r i x a  reference  (step  define  example  of  2  of  and  the  compute  a restructuring  which increments  by  1  the  w h e n e v e r a r e f e r e n c e made t o b l o c k  to block  i . Thus t h e v a l u e  of t h e  j  (i,j)th  3  element expresses  the d e s i r a b i l i t y  the  A  same  page.  algorithms  1.2  description  i s presented  of p u t t i n g b l o c k s of  in Chapter  some  major  i and  j  in  restructuring  2.  C l u s t e r i n g phase In terms of t i m e c o m p l e x i t y ,  expensive  step  There are  several  optimal and  clustering  clustering  been shown t o be NP  differ  in their  simple  The  hierarchical method  one  iterates  1) F i n d two  Step e n t r y and Thus  the  order  n  3  that  the  1  t h a t they  two  [5,11,13].  The  time complexity.  are The  Those w h i c h  with  hierarchical two  blocks  the  various  generally  concerned  is  give is  are  poorer based  on  classification  steps u n t i l  inter-cluster  is n i l .  strongest connectivity with  f i t i n t o one  n  2  scanning  operations.  time complexity (See  which  the  page.  clusters.  requires  takes  of  methods  following two  none  hard  we  c l u s t e r s having  2) Merge t h e  most  problem  c o n s t r u c t i n g [1])  b e t w e e n any  constraint  the  i s basically a combinatorial  classification.  connectivity  probably  algorithms,  e f f i c i e n c y and  (e.g., nucleus  results.  is  i n t h e w h o l e p r o c e d u r e of p r o g r a m r e s t r u c t u r i n g .  since  has  this  section  A more e f f i c i e n t  t h e nxn  Step 2  matrix  requires  of the c l u s t e r i n g  f o r the l a r g e s t 4n  operations.  p r o c e d u r e i s of  the  4.1). c l u s t e r i n g method has  been d e v e l o p e d .  The  4  performance  of  the  new  method  hierarchical  classification  but  i s comparable i s only  to  that  quadratic  of  in  time  complexity.  1•3 P r e v i o u s e x p e r i m e n t a l r e s u l t s Numerous perform better  studies  have  shown  that  restructured  programs  t h a n n o n - r e s t r u c t u r e d ones by a n y w h e r e between  t o 40% i n t e r m s o f page f a u l t  20  r a t e . However, a l m o s t a l l o f t h e s e  r e s u l t s were b a s e d on s i m u l a t e d r e s t r u c t u r i n g . T h i s  is  because  many v i r t u a l memory s y s t e m s u s e g l o b a l L R U - l i k e page r e p l a c e m e n t algorithms  whose  replacement  decision  d e p e n d s on t h e d y n a m i c  behaviour of a l la c t i v e p r o c e s s e s , not j u s t Thus  i t is difficult  meaningful comparisons  to  i n an a c t u a l  global LRU-like strategies proposed Index  [ 2 ] . I n t h i s model  ( P S I ) i s used  control  to  the  a  single  workload  an  time  , a parameter c a l l e d  Page  about  Survival  c h a r a c t e r i z e the i n f l u e n c e of system  unreferenced  page r e s i d e n t  the  number  experiments  nothing  performed  in  conclusive a  system f l u c t u a t e s w i t h t h e system  Unless  could  simulated  e n v i r o n m e n t w i t h a f i x e d P S I s i n c e t h e number in a real  of  a  3) t e r m i n a t i o n o f a  q u a n t u m . T h i s model h a s been s u c c e s s f u l l y v e r i f i e d [ 2 ] . However,  of  i n t h e memory c a n  1) g e n e r a t i o n  2) c o m p l e t i o n o f an I/O o p e r a t i o n  CP-67 s y s t e m  obtain  i n t i m e - s h a r i n g e n v i r o n m e n t s h a s been  s u r v i v e . The i n t e r r u p t i o n s n o r m a l l y i n c l u d e page f a u l t  to  system. A s i m u l a t e d model of  w o r k l o a d on a s i n g l e p r o c e s s . P S I i s d e f i n e d a s interruptions  process.  of  f o r the be  global  said LRU  interruptions  load.  one h a s c o n t r o l o f t h e e n t i r e s y s t e m  (and hence i t s  5  workload),  the  established of  times  statistically on  restructuring results  1 .4  1)  are  a  real  of  develop  restructuring  restructuring  by r e p e a t i n g The  was  the  thesis  a  more  on  3)  To  package  restructuring  procedure  restructured  program  memory management  and t o  policy.  of  the  new  s y s t e m and  the  strategy-independent its  clustering  a  be  6.  performance.  algorithm.  which automates the  on  only  e x p e r i m e n t s a number  a real  efficient  To d e v e l o p a more e f f i c i e n t  can  performance  a l g o r i t h m and e v a l u a t e  a  the  tested  in Chapter  2)  develop  of  system.  algorithm  reported  Objectives  To  effectiveness  test real  the  four  steps  performance  system which uses a  of of  the the  global  6  2 A survey  Chapter  o f some r e s t r u c t u r i n q  T h e r e a r e two b r o a d 1)  techniques  c a t e g o r i 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 :  Strategy-independent  restructuring  algorithms  Strategy-dependent  restructuring algorithms.  of  Gerald  Hatfield  and  category.  The  suggests,  takes  the  category  i n t o account  of  the  first  first  2)  The n e a r n e s s method example o f t h e f i r s t  algorithms,  as  the  name  t h e memory management s t r a t e g y o f  s y s t e m on w h i c h t h e program  algorithms, of  second  [10] i s a classic  and  introduced  will  be  run.  by F e r r a r i ,  category  because  of  memory  systems  which  This  class  of  a r e s u p e r i o r t o those  the  use  of  additional  informat ion.  In  virtual  strategies  t o manage main  index  is  the  there  is  a  working  All  working  set size  trade-off  between  time  strategy w i l l  reduce both  r e s t r u c t u r i n g algorithms  likely  t o be r e f e r e n c e d  We  shall  use  it  the  on  how  notion  close  one a n o t h e r .  i s understood  under  which  example,  of  set-like  performance  of t h e program. space  t h e page  but fault  restructured  putting  Often  a  good  r a t e and  to  effectiveness  of nearness  size  refer  of  to capture  an  blocks  program  such  algorithm which a r e  o f t h e memory management  T,  which  to  i s meaningless  unless policy  i s t o be e x e c u t e d .  of a program e x c u t i n g  window  blocks  i n t h e same p h y s i c a l p a g e s .  'nearness'  i s able  i n the context  the  with  i t  The n o t i o n  i n the course  environment  useful  and  aim a t  together  r e l a t i o n s h i p among b l o c k s . The  'near'  working  set size.  are  depends  another  average  restructuring the  memory,  use  in  two b l o c k s  a  working  For set  i , j i n t h e same  7  window a r e s a i d the  t o be ' n e a r ' e a c h o t h e r  putting  them  in  same page may a v o i d a page f a u l t . However, t h e same b l o c k s i  and  j  may  not  be  'near' each o t h e r  management p o l i c y  or  different  s i z e . Since  and of  since  window  even  in  the  same  environment  t h e page s i z e  j i n t h e same page may p r e v e n t i with another block  under a d i f f e r e n t  a more  k. I t s h o u l d  memory with  a  i s fixed, putting i  desirable  now be c l e a r  clustering  that  perform b e t t e r than t h e other  Strategy-  dependent  algorithms  algorithms  since the notion of nearness p e r t a i n s t o a p a r t i c u l a r  main memory management It  should  optimal  in d i f f e r e n t respect  a  the  little  an  program  absence  of the  appropriate  more d e s i r a b l e p r o v i d e d  after  executing  paging  behaviour  restructuring  'nearness'. two b l o c k s  block  in  j  or  of  a  is  excuting with  particular  the  program,  a l g o r i t h m may p r e s e n t  strategy-independent  The  algorithms are  that  have  been  used  i  block  i , during  execution.  An  algorithm  'nearness'  is  the  to  n e a r n e s s method o f H a t f i e l d a n d G e r a l d  i a n d j ' n e a r ' when b l o c k  one  a  ones.  us now e x a m i n e some c r i t e r i a  considers  algorithm  t h e i r performance i s comparable t o those  of t h e s t r a t e g y - d e p e n d e n t  decide  single  memory management i n f o r m a t i o n o r when  problem. In such s i t u a t i o n s ,  Let  no  system.  i s known a b o u t  choosing  that  t h e page f a u l t r a t e o f t h e p r o g r a m  particular  v i r t u a l memory In  obvious  e n v i r o n m e n t s . An a l g o r i t h m c a n o n l y be o p t i m a l  to  of  policy.  a l s o be  i n reducing  category  j immediately  after  based  broader  on  a  is  referenced program  definition  p r o p o s e d by Masuda [ 1 6 ] . The  of  rationale  8  behind  t h e b r o a d e r view of d e f i n i t i o n  are :  1) A page o f t e n c o n t a i n s more t h a n two b l o c k s and t h a t a i s u s u a l l y g i v e n more t h a n  1 page memory. T h e r e f o r e  two b l o c k s o f t h e same p r o c e s s a t t h e same  more t h a n  c a n be r e s i d e n t i n m a i n memory  time.  2) The o b s e r v e d p a t t e r n o f r e f e r e n c i n g i s blocks.  process  The  so-called  locality  not  limited  to  two  s e t s o f t e n c o n t a i n more t h a n  two b l o c k s .  The e x t e n d e d v i e w o f ' n e a r n e s s ' r e f e r s t o b l o c k s w h i c h a  short  distance  a p a r t . The d i s t a n c e  i s d e f i n e d by a window  w h i c h c o n s i s t s o f t i m e i n t e r v a l s o r number algorithm  generally  have v a r y i n g l o c a l i t y captured  if  exponential of  the  of  references.  performs b e t t e r than the o r i g i n a l  method but t h e p r o b l e m l i e s  i n the choice  sizes,  fixed  time-complexity  not  window  T  This  nearness  o f T. As a p r o g r a m may  a l l the size  are  localities  T  is  of the a l g o r i t h m  too  may  small.  be The  i s a n o t h e r drawback  the algorithm. The c o n c e p t o f Bounded L o c a l i t y  Madison  and  Batson  [15]  provides  Interval a  localities  i n a n a t u r a l way. The d e t a i l s  found  Chapter  in  3.  Besides  which  of  this  to determine are  n o t n e e d i n g any p a r a m e t e r s ,  this  The h i g h e r  t h e l e v e l of  the s m a l l e r the s e t i s . At the t o p a r e l e v e l - o n e  correspond  lifetimes.  mechanism  The  to  the  activity  l e v e l s of other  by  concept  model d e f i n e s a h i e r a r c h y of l o c a l i t i e s . locality,  (BLI) proposed  sets  having  the  BLI's  longest  B L I ' s a r e numbered a c c o r d i n g  to  9  t h e i r d i s t a n c e from t h e t o p B L I ' s . Using  level-one BLI's, a  partitioned  into  phase o r a t r a n s i t i o n d i s r u p t i v e behaviour The  An i n t e r v a l  set  of  of these  (ASI)  increments  j by an amount e q u a l  set  t o which they  blocks the  After the  be  either  be  a  locality  restructuring  [ 1 4 ] i s b a s e d on t h e c o n c e p t o f i s the A c t i v i t y  Set  algorithm  t h e l a b e l o f t h e edge b e t w e e n b l o c k s i t o the l e v e l of the  belong.  smallest  activity  One d r a w b a c k o f t h i s a l g o r i t h m i s t h a t  weight t o b l o c k s  i n t h e same l o c a l i t y  interval  can  strategy-independent  algorithms  and  gives l i t t l e  can  o f a p r o g r a m m i g r a t i n g f r o m one l o c a l i t y t o  B L I . The b e s t  it  string  p h a s e . The t r a n s i t i o n p h a s e r e p r e s e n t s t h e  a l g o r i t h m s p r o p o s e d by K o b a y a s h i  which  reference  the l a r 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  referencing behaviour.  another.  block  i n adjacent  are considered  intervals,  'near'  that i s ,  but not across  boundary. discussing  the  s t r e n g t h s a n d w e a k n e s s e s o f some o f  r e s t r u c t u r i n g a l g o r i t h m s , we s h a l l d e f i n e some t e r m s u s e d i n  this 1)  thesis. The  block  reference  chronological where  string  {  b ,b ,..b 1 2 r  sequence of r e f e r e n c e s g e n e r a t e d  r = t o t a l number o f r e f e r e n c e s  program. Each b  represents  }  denotes  a  by t h e p r o g r a m  i n the execution  a relocatable instruction  of the or data  i s e c t o r . Another b  1  (tl)....b  i  c h a r a c t e r i s a t i o n of  (ti)..  records  r e f e r e n c e as w e l l . C o l l e c t i n g  execution  the  reference  time  reference times  o p e r a t i o n and i t i s o f t e n n o t done. B l o c k  of  string  each  block  i s an  expensive  reference  string i n  1 0  this thesis w i l l  2)  refer to the f i r s t type.  R(t) denotes the set of blocks resident in the memory at time t. Thus in a working set environment,'R(t) would contain a l l block  references  during the time i n t e r v a l ( t - T , t ) where T i s  the window size.  3) A block referenced at time t i s said to be c r i t i c a l  i f i t is  not in R ( t ) .  4) R(t) i s said to be c r i t i c a l  i f a block reference b  at time t i  e R(t).  5)  C  denotes the ( i , j ) t h entry of the connectivity matrix. A l l  entries are i n i t i a l l y set to 0 .  We  shall  now  describe some of the existing restructuring  algorithms.  2 .1 Nearness method C  i s incremented by 1 whenever a reference to block j i s  made following reference to block i . Thus C  records the number ij  of  times  string.  block  i immediately  follows block j in the reference  11  2.2  Critical-set  algorithms  Examples of t h i s c l a s s of a l g o r i t h m s are Set  (CWS), C r i t i c a l - l e a s t - r e c e n t l y - u s e d  In-First-OUT  (CFIFO),  s p e c i f i c memory management  R(t).  from The  critical page  one  r e f e r e n c e may  the b l o c k s where  by  in  reference  will  p u t t i n g the c r i t i c a l  a  s e t . In  a  critical  be  the  of the  algorithms resident set  algorithms (and  block  a  i s that a  thus a v o i d i n g  i n the  same page  a as  t h e number o f  when  a l g o r i t h m can  hence  to  m a p p i n g d o e s not a f f e c t window,  become c r i t i c a l  contains  tailored  and  environment,  t h e m a p p i n g . I n f a c t , CWS  a  (CSWS)  working-set  working-set  not  Critical-First-  is  u n d e r l y i n g these  after  page  and  be made n o n c r i t i c a l  block-to-page  references  Each  i n the d e f i n i t i o n  i n the c r i t i c a l  the  (CPSI). policy,  another  basic philosophy  fault)  (CLRU),  Critical-Sampling-Working-Set  Critical-Page-Survival-Index  differ  Critical-Working-  has  a  i n t h e page r e f e r e n c e been  shown  exactly 2 blocks  briefly  described  reference to block  noncritical  to  [ 1 7 ] . The  as  follows.  j i s i s s u e d at time  be  block string optimal  critical-set Whenever  t , then  a  a l l C i j  such t h a t b l o c k  i e R(t) are  2.3  algorithms  Minimal-set  Minimal-Working-Set (MSWS)  and  incremented  (MWS),  by  1.  Minimal-Sampling-Working-Set  Minimal-page-Survival-Index  (MPSI) a r e e x a m p l e s o f  t h i s c l a s s of a l g o r i t h m s . T h e i r o b j e c t i v e i s t o m i n i m i z e occupancy application algorithm  of of  restructured the  algorithm  belongs to the  first  programs.  MWS  proposed  by  category  is  memory  actually  Masuda.  an  Masuda's  of a l g o r i t h m s s i n c e  the  12  window  size  T  reasonableness  i s chosen  according  to  that  increments  used C  and  and therefore the program i s not t a i l o r e d to any  p o l i c y . On the other hand, the window size T with  convenience  by  the  working  in MWS  set policy.  The  coincides algorithm  by 1 a l l pairs i and j such that blocks i  belong to the current resident set of blocks R(t).  and  j  13  C h a p t e r 3_ B L I - b a s e d r e s t r u c t u r i n g 'Locality  of  reference'  by most p r o g r a m s .  It  phenomenon  a  that,  r e f e r e n c e d over  refers small  algorithms  i s a n a t u r a l phenomenon to  the  subset  experimentally  of  a r e l a t i v e l y long time  program e x e c u t i o n can  concept  i n t e r v a l . The  be v i e w e d , a s a s e q u e n c e o f  of  BLI  proposed  course  and  transitions.  extended Least-Recently-Used ordered  vector  L(t)=(L  The (LRU)  of  blocks  in  the  concept  (t),..L i  Batson  [15]  string  into  i s b a s e d on  LRU  (t))  each  phase.  reference  s t a c k . The  (t),..,L 1  number  BLI  of  intervals,  by M a d i s o n and  p r o v i d e s a mechanism t o p a r t i t i o n a b l o c k localities  observed  a program's segments i s  of which i s e i t h e r a l o c a l i t y phase or a t r a n s i t i o n The  exhibited  stack  where  n  the  is  an  i s the  n  program  and  L  (t)  is  the  block  I  identifier The  LRU  f o r the stack  b l o c k s were l a s t locality and  sets  B ( t ) were  i t h most-recently-referenced  thus  contains  referenced f r o m t h e LRU  at  b l o c k at time  i n f o r m a t i o n about the order time  t.  s t a c k , two  In  new  order  ordered  LRU  stack, that  corresponds time  to the  i s , S (t)={ L ( t ) , i 1  formation  of t h e most r e c e n t  activity  the  define  vectors F(t)  introduced.  L e t S ( t ) denote the s e t c o n t a i n i n g the t o p i the  to  t.  set i s then  ,L  i  elements  of  ( t ) }. Then F i  (t) i  time  of the  set S ( t ) . B ( t ) i s the i i  reference  t o the  i t h member o f S ( t ) . An i  d e f i n e d a s any  S (t) i  having  its  B (t) i  >  14  F (t), i  that  i s , a l l i t s members h a v e been r e f e r e n c e d  once s i n c e t h e t i m e o f f o r m a t i o n . activity  set  i s defined  The  at least  1 ( t ) of i  lifetime,  the  t o be t h e d i f f e r e n c e b e t w e e n B ( t ) a n d i  F ( t ) w h e r e B ( t ) > F ( t ) . A B L I i s t h e p a i r (A ( t ) , l ( t ) ) i i i i i that  A  i s the  i  concept  allows  hierarchical  activity  a  natural  nature  such  s e t a n d l i i s i t s l i f e t i m e . The B L I way  of l o c a l i t i e s  of  defining  localities.  The  i m p l i c i t i n the d e f i n i t i o n i s  shown i n F i g u r e 3 . 1 .  J A B C D C D A B J E G H G H A B C D C D A B E G H G H I E G H I  1  I  1  I 1  I  1  level 2 level 3  3.1 A h i e r a r c h y  This algorithm  is  BLI's,  blocks  o f bounded l o c a l i t y i n t e r v a l s  algorithm i n c r e m e n t s by one  edges between t h e b l o c k s belong  established.  of  the  whenever t h e a c t i v i t y s e t t o w h i c h  they  Because  a l l the  and  D  will  labels  of the h i e r a r c h i c a l  a r e i n c r e m e n t e d by an amount e q u a l  s m a l l e s t a c t i v i t y s e t t o which C  level 1  1  I  3. 1 ASI r e s t r c ' t u r i n g  blocks  1  1  Figure  the  1' I  they  belong.  be i n c r e m e n t e d by 5 a f t e r  nature of  t o t h e l e v e l of For  example,  t h e segment o f  15  reference  string  hierarchical definition  and  the  of 'nearness'. In F i g u r e 'near'  in  mentioned  recognize  course  in  of  several  has  been  processed.  BLI's  allows  a  very  3.1,  blocks  C  and  locality  phases,  The broad D  are  i n a broader J,A,B  D i s observed.  particular  be  3.1  the l e s s prominent r e f e r e n c i n g p a t t e r n of blocks  As to  Figure  property  considered context,  in  i n the l a s t chapter,  some n e i g h b o u r i n g observed  of e x e c u t i o n .  t h i s a l g o r i t h m may  phases as  referencing  related  pattern  is  For example, t h e c l u s t e r  s u g g e s t e d by t h e a l g o r i t h m  although  prevalent  string  the  i n the  o f E,G,H w i l l  f o r the reference  fail  not  depicted  F i g u r e 3.1. The  next s e c t i o n d i s c u s s e s  remedy t h e p r o b l e m d e s c r i b e d , simply  a new a l g o r i t h m w h i c h  the algorithm  tries  to  s h a l l be r e f e r r e d  to  as BLI a l g o r i t h m .  3.2 B L I a l g o r i t h m This  algorithm  i s b a s e d on t h e o b s e r v a t i o n  phases have f a r g r e a t e r phases.  This  phase w i l l brought  more  page  faults  to blocks as  i n t o t h e memory. Kahn [ 1 2 ] r e p o r t e d  phases dominated the v i r t u a l during  transitions  locality  transition  i m p a c t on p a g i n g a c t i v i t y t h a n  i s because any r e f e r e n c e  not incur  that  time,  the  was 100 t o 1000 t i m e s  they  locality  in a locality are  already  that while l o c a l i t y  rate higher  of  page  than that  faults during  phases.  Using  t h e l e v e l - o n e B L I , t h e program e x e c u t i o n  t i m e c a n be  16 divided by T T  i  1)  i n t o t r a n s i t i o n and  and  i  and  L  L  locality  r e s p e c t i v e l y . An  i  approximation  g i v e n by C h a n s o n and  i  I f the c u r r e n t repetition locality  interval  of a b l o c k  phase L  (and  i n t e r v a l s which are  [4]  Law  method  i s as  to  thus  estimate  follows :  i s a t r a n s i t i o n phase, then reference  denoted  the  s i g n a l s the b e g i n n i n g  t h e end  of t h e  first of  transition  the  phase  i T  2)  ).  Otherwise, locality beginning  any  reference  to  p h a s e s s i g n a l s t h e end of the next  a  block  of t h e  is clear  i n the  locality  t r a n s i t i o n phase  current  p h a s e and  the  i s a subset  of  T 1 +  It  not  1  from the above p r o c e d u r e t h a t L i  T  i  , therefore i t i s  phases.  The  new  not  necessary  to  a l g o r i t h m increments  the edges between the b l o c k s w h i c h a r e  consider by  one  the  locality  a l l the l a b e l s  i n the union  s e t of  of  T i- 1  and  T  i  .  This hopefully captures  blocks which e x h i b i t  prominent  referencing pattern. The  n e a r n e s s n o t i o n between b l o c k s  in adjacent  phases  can  be e x t e n d e d t o p h a s e s w h i c h a r e T d i s t a n c e a p a r t , where T i s t h e number of t r a n s i t i o n p h a s e s . The  window s i z e u s e d i n t h i s t h e s i s  17  Chapter 4 C l u s t e r i n g algorithms Phase  2  connectivity  of  the  restructuring  procedure  i n f o r m a t i o n i n a m a t r i x C. E a c h e n t r y  stores  the  of  the  C ij  nXn  connectivity  two  blocks  matrix  represents  the d e s i r a b i l i t y  i a n d j i n t h e same p a g e .  In  of p l a c i n g  graphical  sense,  C ij  represents The  t h e w e i g h t o f t h e edge c o n n e c t i n g  task of t h e c l u s t e r i n g a l g o r i t h m i s thus  into c l u s t e r s with the  objective  of  node i a n d node j . t o group the b l o c k s  minimizing  inter-cluster  references. In  assigning  constraint  the  blocks  to  pages,  in  a  additional  page  is  impose t h e  blocks  fragmentation  are  in  caused  While the ordering of  immaterial  algorithms  overlapping  required  the  by  in  the  to  first  second a l t e r n a t i v e .  clusters  not  b e t t e r when  a  overlapping  blocks.  proper  algorithm In  this  was  used  to  the  best  Because of t h e  filling  t h e s e c o n d a l t e r n a t i v e was r e p o r t e d  the  alternative,  determine  completely,  the  may  t h a t t h e b l o c k s must f i t i n t o a p a g e , o r we may a l l o w  some b l o c k s t o c r o s s page b o u n d a r i e s . blocks  we  the  pages  [10] t o perform determine  the  t h e s i s , we a r e n o t c o n c e r n e d  with  'gaps' i n t h e p a g e s . F i n d i n g an o p t i m a l s o l u t i o n t o t h e  the  problem  in  general case r e q u i r e s enumerating e x h a u s t i v e l y a l l p o s s i b l e  l a y o u t s and t h e c o s t of e x e c u t i n g high.  clustering  In  expensive  most  practical  such  situations,  a l g o r i t h m i s s o u g h t . Many  e f f i c i e n c y and time c o m p l e x i t y  an  algorithm  a near-optimal  algorithms  with  is  very  and l e s s different  e x i s t . We s h a l l d e s c r i b e a  fairly  18  efficient  algorithm  which  in  most  cases  gives  near-optimal  solut ion.  4.1  Hierarchical classification The  c o n n e c t i v i t y matrix  may  of c l u s t e r s of p o i n t s w i t h t h e w e i g h t of  the  entry C  . An  (HC) be  method viewed as a space c o n s i s t i n g  s i z e of e a c h p o i n t  optimal  algorithm  reflecting  i s thus  the  one  that  i j finds  a  layout  clusters  which  the  total  w e i g h t of  the f i x e d - s i z e  i s maximized.  The located  in  HC  method p r e s u m e s t h a t  i n the v i c i n i t y  the  h e a v i l y weighted points  o f d e n s e a r e a s and  h e n c e t h e y may  are  be  the  p o s s i b l e n u c l e i of t h e p o t e n t i a l c l u s t e r s . At e a c h i t e r a t i o n of are is  most  the a l g o r i t h m ,  the  two  clusters  s t r o n g l y c o n n e c t e d a r e merged i n t o one  reduced a c c o r d i n g l y .  The  procedure  is  and  which  the  described  matrix  formally  below. Let  C  be  m  the  connectivity matrix,  c l u s t e r s of b l o c k ( s ) , w i t h the iteration. is,  J  0  subscript  Each c l u s t e r i n i t i a l l y  = { { 1 } , { 2 } , . . , { n } }. The  then e n t a i l s 1) F i n d i n g  contains  mth  B are  m  J  m  be  the  denoting  set  of  the  mth  a single block,  that  iteration  of  the  algorithm  C  , where A  : the  l a r g e s t element C  i n the m a t r i x AB  and  and  two  elements of  J m-1  m-1  19  2) R e d u c i n g t h e m a t r i x C  to C m-1  columns  associated  labelled  by D,such t h a t :  C C  DX  = C + C AX BX  XD  = C + C XA XB  for where J  In  by  combining  the  rows  and  m  with  A  and  B  t o a new row a n d c o l u m n  a l l X in J m- 1 = J  m  - {A} - {B} + {D}  m-1  the i n i t i a l  matrix C  and t h e subsequent  reduced  ones,  0  each e n t r y C i  and  i s assigned  ij  j exceed a page.  zero  i f t h e combined  c l u s t e r - s i z e s of  I n a more g e n e r a l c a s e where some b l o c k  s i z e s may e x c e e d a p a g e , C  i s assigned  zero  i f the  smaller  ij cluster(j  say)  could  not  f i t into the remaining  space of t h e  cluster i . In  the actual  implementation,  each e n t r y C  of the i n i t i a l ij  matrix The  i s recomputed  new v a l u e C  t o take  i n t o account of  the  block  sizes.  ' i s d e f i n e d t o be ij  C  where W  ij  = C  and W i  /(W +W ) i j i j  are respectively j  t h e b l o c k s i z e s of i and j .  20  This  definition  performance  of  the  substantially  better  take the block  sizes  The p r o c e d u r e two are  clusters  introduced  modified than  by  method  the  Masuda[l6]  has  been  and  shown  to  be  o r i g i n a l method w h i c h does not  into consideration.  t e r m i n a t e s when t h e c o n n e c t i v i t y b e t w e e n  is nil,  the  t h a t i s , a l l e n t r i e s of the reduced  any  matrix  zeros. For  2  was  each i t e r a t i o n  requires  4j  , step  operations,  1 requires j  2  o p e r a t i o n and  where j i s t h e s i z e of t h e  step reduced  m a t r i x . Thus t h e number o f o p e r a t i o n s T i s g i v e n by : T = { n  2  + ( n - l )  2  + . . + 1  2  } +  4 { n + n - 1 + . . + l } = n ( n + 1 ) ( 2 n + 1 ) / 6 + 2n(n+1) = n(n+1)(2n+13)/6  A  common  approach  to  a l g o r i t h m .. i s t o decompose on  which  some  connectivity can  algorithm  matrix  be p a r t i t i o n e d  does  reducing  time  the o r i g i n a l problem can  be  connectivity submatrix  matrix  a  simple into  connectivity  method i s t h e n  is  of  an  subproblems  However,  the  n o t c o n t a i n i n f o r m a t i o n a s t o how i t  into submatrices;  describes  into  applied.  any a r b i t r a r y  have s t r o n g c o n n e c t i v i t y w i t h t h e o t h e r section  complexity  and  a p p l i e d t o each  submatrices.  The  may next  f a s t method t o p a r t i t i o n t h e  submatrices small.  submatrix  such  that  Hierarchical  submatrix.  the  intra-  classification  21  4.2  A decomposition The  i d e a of  a vector This  approach to c l u s t e r i n g  representing  i s taken  algorithm  the c o n n e c t i v i t y between b l o c k s  from the c l u s t e r i n g finds  its  problem  scheme of Yu  application  in  a  in  et  al.[l9].  large  c l a s s of  p r o b l e m s s u c h as  record c l u s t e r i n g , a t t r i b u t e  partitioning  and  file  i n d i s t r i b u t e d d a t a b a s e s . We  shall describe  the  allocation  algorithm  (which  i s d e n o t e d as  method  A)  in  the  context  of  program r e s t r u c t u r i n g problem.  4.2.1  Method A The  c o n n e c t i v i t y between b l o c k s  V where t h e  i t h e l e m e n t of t h e v e c t o r  i s represented (V  ) records  by a  the  vector  position  i of  the  ith  block  blocks gives  an  a line.  approximate  b e t w e e n them. The t o be  (b ) on i  The  indication  d i s t a n c e b e t w e e n two  the a b s o l u t e  d i s t a n c e b e t w e e n any of  blocks  d i f f e r e n c e between V  and  Initially the  line.  the  During  blocks  p h a s e two  connectivity vector  some  of  the  i s u p d a t e d as  1) A f t e r d e t e r m i n i n g by  are assigned  the  connectivity  i and  j i s defined  V  i  . j  arbitrary  restructuring  two  blocks  i and  j  restructuring algorithm, blocks  i and  j  blocks  i s defined  t o be  amount (V +V i  2)  Two  randomly  the  follows :  a r e moved t o w a r d s t h e i r c e n t r o i d by a s m a l l c e n t r o i d of the  p o s i t i o n s on  procedure,  t h e c o n n e c t i v i t y b e t w e e n two  appropriate  two  selected  blocks  are  moved  A'.  The  )/2. j  away f r o m  their  22  c e n t r o i d by a n o t h e r  Step 2 i s  applied  bunching  up  of b l o c k s  i and  j'. and  j , i ' and  not  a situation  connected  where t h e other  from  centroids  blocks  i '  j ' , then  e v e n t u a l l y the  four blocks w i l l  has  and  i s no c o n n e c t i v i t y between t h e the c l u s t e r s  is a  converge  pairs.  straight-forward  procedure.  blocks w i t h i n a d i s t a n c e 6 are c l u s t e r e d together.  simplicity it  blocks  j c o i n c i d e w i t h t h a t of two  Identifying two  avoid  i s a s t r o n g c o n n e c t i v i t y w i t h i n each of t h e p a i r s i  even i f t h e r e  Any  to  together. Consider  If there  A".  s m a l l amount  of the a l g o r i t h m i s i n t u i t i v e l y  several  drawbacks  when  appealing.  applied  The  However,  t o the r e s t r u c t u r i n g  problem. It is  t h a t the c h o i c e of the parameters A',A"  i s clear  critical  in isolating  the c l u s t e r s .  For  and  5  example, a l a r g e  A'  v a l u e w o u l d c a u s e t h e b l o c k s t o move c l o s e r t o one  i n many l a r g e c l u s t e r s . A s m a l l A'  quickly,  resulting  the other  hand c a u s e s slow  valid clusters. cluster correctly  to  between  cluster,  frequency  not  a l l  i f a single A value  clusters any  two  the one-dimensional towards  convergence  Because the  W h i l e t h e p o i n t s on where t h e  block  j  another  the  are,  be  produces  no  of r e f e r e n c i n g v a r i e s f r o m  l i n e present  representation  not  value,on  be  identified  i s used.  blocks i s lost.  o t h e r b l o c k s w h i c h may  hence  the c l u s t e r s w i l l  information  inevitably  and  too  an a p p r o x i m a t e v i e w of  about  the  connectivity  This i s a problem i n t r i n s i c because  results related  moving  in block to  a  block  in i  i being c l o s e r to  block  i . Since  not  23  every out  cluster  will  f i t i n t o a page, i t i s n e c e s s a r y  the a p p r o p r i a t e b l o c k s from the c l u s t e r .  reconfiguration  of  the  points  is  insufficient  information contained  We  d e s c r i b e our  a  s h a l l now  better  name,  clustering  4.2.2  will  scheme i n t h i s  section  is  A"  and  not  performed using  to  the  vector.'  called  the  gravitational  scheme  6, t h e a l g o r i t h m  range  finer  due  to s e l e c t appropriate values  suitable a  possible  a  thesis.  i t is difficult  parameters A',  However,  a l g o r i t h m , which, f o r l a c k of  be  Gravitational clustering  Since  i n the  new  simply  not  to- f i l t e r  for of  described  our  in  application.  parameter  values  for  the  the  last  Experiments  did  not  show  n o t i c e a b l e r e d u c t i o n i n page f a u l t r a t e . The moving  a l g o r i t h m we blocks  another.  which  Phase  2  have d e v e l o p e d  u s e s t h e same p r i n c i p l e  are  connected  of t h e  strongly  r e s t r u c t u r i n g procedure  f o l l o w s . When a b l o c k r e f e r e n c e s a n o t h e r left of  i s moved t o t h e moving past  except  separation  between  t o be  b l o c k . The reasonably  the  are  often  points w i l l pulling  jointly be  away  be  referenced  located in of  two  l a r g e so  the  randomly  that  have m i n i m a l  clear  that  together, proximity selected  of  one  blocks  the  possibility critical  the  initial  e f f e c t on  i f a s e t of their  one  i s r e v i s e d as  c h o i c e of d i s not  blocks w i l l  r a t e of c o n v e r g e n c e . I t s h o u l d  to  b l o c k , t h e b l o c k on  r i g h t by an amount d, w i t h t h e  the other  t h a t i t has  closer  of  the  blocks  corresponding another. is  No  necessary  24  b e c a u s e c l u s t e r s o f b l o c k s o f t e n move However,  due  to  representation,  the  some  away  limitation  clusters  may  from  of  a  still  one  another.  one-dimensional  have  their  members  intermixed.  4.2.3  Gravitational-hierarchical classification Although  filter  the  gravitational  o u t t h e most  provides  a  basis  connected  clustering  blocks  for partitioning  from  (GHC)  method  scheme may each  fail  to  cluster,  i t  a problem i n t o  subproblems.  The c o n n e c t i v i t y v e c t o r p r o v i d e s a means t o r e o r d e r  t h e rows a n d  columns of the c o n n e c t i v i t y connectivity  between  any  matrix  both  and  the  matrix  vector.  another  are l i k e l y  Initially, the  is  HC  Thus  rows/columns  blocks  t o be  first  (1<=  on  a  sorted  order  having  row  the  kxk  is  nxn.  submatrix,  of the submatrix  of  the  row/column  are  along  in  the  applying  i t h and  ( j say)  jth  t o form a is  not  a l l the e n t r i e s  moved t o t h e j t h r o w / c o l u m n . I n  row/column matrix  After  a r e merged  row/column of t h e updated m a t r i x , then  reduced  decreasing  that  the  first  the  size k i s  numbers c l o s e t o one  the  Therefore  the  related.  i , j <=k)  the f i r s t  in  as  r o w / c o l u m n . I f t h e r o w / c o l u m n t o be d e l e t e d  e i t h e r case,  that  resonable  new  first  way  t o have t h e b l o c k s  same  the s i z e of the m a t r i x  process  of  i s rearranged  t h e rows and c o l u m n s i n t h e  sorted  such  submatrices  s m a l l . The c o n n e c t i v i t y v e c t o r order,  in  of  C  the  after  matrix  t h e mth  is  deleted.  iteration  i s of  m size  (n'-m-1 )x(n-m-1 ). A t  a p p l i e d on t h e f i r s t  each  iteration,  the  HC  process  k rows and c o l u m n s o f t h e r e d u c e d  matrix.  is  25  The  choice of k c l e a r l y depends on the d i s t r i b u t i o n of the  positions of the blocks on the l i n e . A good approximation for is  k  the average number of 'blocks in a c l u s t e r . This value can be  obtained by scanning  the connectivity vector and  keeping  count  of the number of blocks in each c l u s t e r . We  s h a l l describe a procedure to identify the c l u s t e r s . Let  d ...d 1 n-1  be  the distance between the adjacent p a i r s of points  (V ,V ),(V ,V ) , .. , (V 12 2 3 n-1  ,V ). n  Assuming  b i-1  belongs  to  some  c l u s t e r , and d i s the maximum distance between any two points in that  cluster.  Then  b  belongs  to  another  cluster  if  the  i following conditions are s a t i s f i e d . 1) d  >. d .and  .  . . . . . .  i-1 2) d  > d i—1  for a l l 1<=j<=q  where q  >=1  i-1+j  The second condition i s to ensure that the c l u s t e r s are not terminated prematurely. In other words, one next q separations to ensure that d  'looks ahead' at the  i s a resonable  separation.  i Looking  ahead  isolate  the  conservative  at  the  major  next  clusters  separation (q=1) in  most  i s s u f f i c i e n t to  cases.  However,  a  approach would choose a large q value r e s u l t i n g in  large c l u s t e r s i z e s . In summary, the revised restructuring procedure consists of the following steps :  26  1) P a r t i t i o n blocks.  the program t o Transform  program i n t o  2) P r o c e s s  be  restructured  the t r a c e c o l l e c t e d  i t s corresponding  the  block  connectivity  block  reference  into  from e x e c u t i o n  reference  string  b e t w e e n t h e b l o c k s . The  relocatable  and  of  the  string.  determine  the  connectivity matrix  and  the c o n n e c t i v i t y v e c t o r are updated a c c o r d i n g l y .  3) S o r t  the  connectivity  rearrange  the  vector  connectivity  in  decreasing  matrix  i n the  t h e 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 method kxk  submatrix,  starting  from  the  order  and  same o r d e r .  Apply  successively top  on'  the  of  the  produced  in  l e f t corner  matrix.  4) R e s t r u c t u r e the l a s t  4.2.4  the program a c c o r d i n g  GHC  complexity  p r o c e d u r e 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) S o r t i n g t h e c o n n e c t i v i t y v e c t o r and 2) R e o r d e r i n g 3) R e c o m p u t i n g  t h e rows and each  t h e HC  computing a value  columns of the  element  c o n s i d e r a t i o n the block 4) A p p l y i n g  layout  step.  A n a l y s i s of time  The  t o the  of  the  for  matrix. matrix  to  take  sizes.  method s u c c e s s i v e l y on  k.  t h e kxk  submatrix.  into  27  The number o f o p e r a t i o n s r e q u i r e d bounded  the  HC  no r e a r r a n g e m e n t o f t h e m a t r i x  method,  the zero  the matrix  1  step  is  i s necessary  in  i s made more c o m p a c t by e l i m i n a t i n g  rows a n d c o l u m n s . Thus t h e t i m e c o m p l e x i t y o f t h e p r e -  h i e r a r c h i c a l process analyze  execute  3 i s common i n t h e GHC method a n d t h e HC  by n l o g n . S t e p  method. A l t h o u g h  to  i n b o t h methods  t h e time c o m p l e x i t y  Assume processing  the  i s o f t h e o r d e r n . We 2  will  o f t h e GHC method b a s e d on s t e p 4.  submatrix  S  has  constant  size  k x k . The  t i m e o f s t e p 4 c a n be d i v i d e d i n t o two c o m p o n e n t s .  1) F i n d i n g t h e maximum e n t r y S  and merging t h e c l u s t e r s  i  and  ij j.  The  number  iteration  of  operations  requires a  processing  time  the  matrix.  initial  constant  r e q u i r e d = k +4k. Since 2  processing  of  the  the  first  row/column  be  deleted  with  of the reduced.matrix.  This  t a k e s m o p e r a t i o n s where m i s t h e s i z e o f t h e r e d u c e d Note t h a t t h i s s t e p i s not e x e c u t e d number  of  total  i s thus l i n e a r l y p r o p o r t i o n a l t o t h e s i z e of  2) R e p l a c i n g t h e e n t r i e s o f t h e r o w / c o l u m n t o that  time,  each  operations  required  a t every  matrix.  iteration.  for n iterations  The  i s of the  order n . 2  Therefore  the 'total  c l u s t e r i n g procedure  processing  time  of  the  entire  ( s t e p 1 t o s t e p 4) i s o f t h e o r d e r n . 2  28  Chapter 5 D e s c r i p t i o n Several  s e r i e s o f e x p e r i m e n t s were c a r r i e d o u t t o t e s t t h e  performance of the clustering The  first  restructuring  algorithm  via of  with  simulation  the  p e r f o r m a n c e was  the  GHC  GHC  2)  experiment  verifying  algorithm.  identify  the  performance  develop  the  Following  t e s t e d on a  compared w i t h  time  complexity  the s i m u l a t i o n  real  system  the non-restructured  indices  parameters  to  runs,  and  its  program.  procedure c o n s i s t s of the f o l l o w i n g  major  BLI  the major e x i s t i n g r e s t r u c t u r i n g  1) To d e t e r m i n e what p e r f o r m a n c e  2) To  and  T h e r e were two p a r t s t o t h e e x p e r i m e n t s .  r e s t r u c t u r e d p r o g r a m was  The  algorithm  p a r t a i m e d a t 1) c o m p a r i n g t h e p e r f o r m a n c e o f t h e  algorithms  the  BLI  algorithm.  restructuring  analysis  of e x p e r i m e n t  use  and  affecting  steps.  then  the  to  chosen  indices.  the  appropiate  restructuring  and  measurement  tools.  3) To p e r f o r m s i m u l a t i o n  4) To e v a l u a t e  5.1 5.1.1  t h e r e s t r u c t u r e d p r o g r a m on a r e a l  system.  Parameters Performance For  algorithm, were  runs.  the  indices  purpose  of e v a l u a t i n g  t h e page f a u l t  chosen  r a t e and  t o be t h e p e r f o r m a n c e  the  t h e p e r f o r m a n c e o f t h e BLI mean  working  indices for their  set  size  respective  29  i n f l u e n c e on t h e t u r n a r o u n d t i m e a n d t h e the  virtual  applicable  memory  system.  requirement  The mean w o r k i n g s e t s i z e  of  i s only  i n the working s e t environment.  To e v a l u a t e t h e e f f i c i e n c y the performance fault  space  rate  o f t h e GHC c l u s t e r i n g  i n d e x u s e d was t h e  was  algorithm. This  also is  used  to  to  processing  algorithm,  time.  The  page  measure t h e p e r f o r m a n c e o f t h e  ensure  that  the  efficiency  and  the  e f f e c t i v e n e s s o f t h e a l g o r i t h m a r e m a i n t a i n e d a t t h e same t i m e .  5.1.2 F a c t o r s The  performance  the f o l l o w i n g  a r e s t r u c t u r e d p r o g r a m i s a f f e c t e d by  factors.  1) I n p u t d a t a . Therefore  of  This a  affects  the  restructuring  several reference strings behaviour. D i f f e r e n t  behaviour  algorithm which  of  should  represent  the  program.  be  t e s t e d on  various  program  t y p e s o f i n p u t d a t a were c h o s e n t o c o v e r  a range of v a r i a b i l i t y .  2)  Restructuring  algorithms.  i n f l u e n c e d by t h e virtual  3)  Memory  The  placement  order  of  rate  the  i s directly  blocks  i n the  i n Chapter  1, t h e  to  memory  pages.  management  restructuring  policy.  algorithms  management p o l i c y  As  are  tested  on  mentioned sensitive  of the computing  case of the working s e t p o l i c y ) . was  page f a u l t  different  the  s y s t e m a n d window s i z e ( i n  Each r e s t r u c t u r i n g  memory  algorithm  management e n v i r o n m e n t i n  30  order  to e s t a b l i s h  i t s robustness.  For the purpose of a n a l y z i n g the p r o c e s s i n g time of the method, the f o l l o w i n g f a c t o r s are  1)  Input  considered.  data. Since the p r o c e s s i n g time i s a  number of d i s t i n c t consisting  GHC  function  of  r e f e r e n c e d b l o c k s , block r e f e r e n c e  of d i f f e r e n t number of d i s t i n c t  the  strings  referenced  blocks  were chosen.  2) S i z e of the submatrix k. T h i s a f f e c t s the p r o c e s s i n g time well  as  results  the  page  fault  r a t e . The GHC  ( i n terms of page f a u l t  r a t e ) than  i s too s m a l l , s i n c e blocks belonging not  method g i v e s  as  poorer  the HC method i f k  to the same c l u s t e r  be recognized as such. An a p p r o p r i a t e value  may  f o r k can  be  computed using the procedure d e s c r i b e d in s e c t i o n 4.2.3.  5.2  Procedure of experiment After  execution  choosing trace  of  debugging package. The block  reference  to  the  program  was  f o r use  be  r e s u l t i n g output consisting  of  restructured,  collected was a  then  by  the  using  reduced  to  a a  sequence of numbers  in which the r e l o c a t a b l e  were r e f e r e n c e d . The  a l s o recorded The  program  string  r e p r e s e n t i n g the order program  the  blocks  of  s i z e of each r e l o c a t a b l e block  the was  i n the c l u s t e r i n g phase.  block r e f e r e n c e s t r i n g was  then  input to a  program  in  31  which  several  restructuring  and  i n c o r p o r a t e d . B a s e d on a s p e c i f i e d connectivity  matrix  clustering  algorithms  restructuring algorithm,  phase  of t h e b l o c k s page  which output  i n the v i r t u a l  to  the  a layout s p e c i f y i n g the ordering  pages w h i c h would  performance  minimize  o f t h e r e s t r u c t u r e d p r o g r a m was  s i m u l a t i o n . The s i m u l a t o r  string the  passed  was  inter-  references. The  by  the  (and p o s s i b l y the c o n n e c t i v i t y v e c t o r )  p r o d u c e d . The c o n n e c t i v i t y i n f o r m a t i o n was t h e n clustering  were  into the corresponding  restructuring  paging  transformed  activity  policy.  The  layout.  the  page r e f e r e n c e At  block  reference  string according to  t h e same t i m e ,  i t simulated the  o f t h e p r o g r a m u n d e r a c h o s e n memory  appropriate  evaluated  management  p e r f o r m a n c e s t a t i s t i c s were o u t p u t a t  the end of t h e s i m u l a t i o n . The number  experiment procedure described of  times,  each  restructuring algorithm,  time  with  memory  above  was  a different  management  repeated  a  f a c t o r such as  policy  and  input  data. Finally, and  the  actual  r e l i n k e d by a l i n k e r .  p r o g r a m was t h e n The  b l o c k s o f t h e p r o g r a m were The p e r f o r m a n c e  t e s t e d on a r e a l  software  of  the  reordered  restructured  system.  t o o l s were a l l coded i n P a s c a l . A d e s c r i p t i o n  of t h e t o o l s i s p r e s e n t e d  i n the next  section.  32  5.3 R e s t r u c t u r i n g a n d m e a s u r e m e n t 5.3.1  Data  The  c o l l e c t ion  Symbolic  execution  trace  provides  a  subroutine  calls  also  TRACE  The  f o r debugging  written to transform  form.  Using  the l i s t  maps e a c h b l o c k reduced  reference  name  form  restructuring  trace  of  execution.  It  and  a  a listing  their  i n the clustering  collected  was i n r e a d a b l e  purposes.  A data  the data  produced  into  from  of a l l  corresponding phase.  (and hence  reduction  a more c o n c i s e  program  and u s e f u l  t h e MAP c o m m a n d , t h e p r o g r a m  i n the trace t o a unique p o s i t i v e of the c o l l e c t e d  data  SDS p r o v i d e s  i s  procedure  of c o l l e c t i n g  the  trace  most  because  program  integer.  i s known a s t h e b l o c k  Working  Activity  set  reference  string  set  and  SDS  step  of  i s not customized extensive  but expensive  tool  the  f o r the  facilities to use.  algorithms  restructuring  Critical  expensive  t r a c e s . The  makes i t a v e r s a t i l e  5.3.2 R e s t r u c t u r i n g  The  SDS  string.  Collecting  purpose  The  records  the program's  names  to collect the  restructured.  which produces  was u s e d  trace  be which  during  data)  information  form  to  command  or  execution  verbose)  The  MAP  (SDS) was u s e d  command  and r e t u r n s a  This  System  program  CALL  (instruction  lengths.  was  Debugging  of the  provides  block  tools  the  algorithms and  Minimal  BLI.  Each  implemented Working accepts  were  set,  Kobayashi's  as input  and t h e r e s t r u c t u r i n g parameter  Ferrari's  (such  the block a s window  33  size) the  i f any.  The  block  connectivity  processing  the  procedure  which  cluster  5.3.3  the  GHC  matrix  string,  GHC  requires  in  and  section  required phase the  4.2.3.  the  GHC  order  as  size  (k)  matrix zero  the  that  Before  and  the  a  the  GHC  end  of  clustering method  to  (size  of to  phase, were  the The  the  the  and  the  procedure  are  the  a page.  The  size  : the c o n n e c t i v i t y  eliminate from  the the  I/O  operation  same  i s then  sorted vector.  A  value  method,  in  the  t o a more compact m a t r i x  sorted  copied the  f o r the  and  program.  is first  columns arranged  HC  described  restructuring  i n the  connectivity matrix  the  as  restructuring algorithms  connectivity vector  In  of  submatrix)  implemented  i t s rows and  i n the  HC  input  connectivity matrix  also copied  rows and  size  order  i s a l s o computed. is  or  clustering  additional  k  In  order. with  the  two  method,  matrix  method  to  implemented were the  block  algorithms  descending  another  the  clustering  clustering  the  to  parameter  to pass  to  In in  the  passed  the  and  pages.  Input  matrix,  vector  HC  processed  a c c o r d i n g l y . At  is  the  algorithms  connectivity method  matrix  i s then  algorithms  clustering  methods.  the  into  string  i s updated  uses e i t h e r  blocks  Clustering  The  reference  to  same  submatrix  connectivity  e l i m i n a t i n g the  columns.  applying  the  HC  method,  each  element  C  of  the  i j matrix sizes  is i and  divided j .  by  an  amount e q u a l  to  the  sum  of  the  block  34  5.3.4  Memory management p o l i c y  simulators  T r a c e - d r i v e n memory management for  the  replacement  Working  Set  strategy.  Input to  and  the  simulators  'are  procedure,  the block s i z e s and the s i z e of a page. information  are  blocks because some c l u s t e r s exceed  a page.  the c l u s t e r  specified  Based on  5.3.5  block  produced from the r e s t r u c t u r i n g The l a s t  two  needed to determine the overlapped may  contain  blocks  the  page  reference  of the r e s t r u c t u r e d program i s  memory  management  performance i n d i c e s printed  the  whose  sizes  The blocks are mapped i n t o pages as s p e c i f i e d  layout.  paging a c t i v i t y  developed  Least-recently-used  string,  of  layout  the  were  reference  pieces  the  Policy  simulators  associated  policy  and  string,  in the  simulated under a the  appropriate  with the r e s t r u c t u r e d program are  out.  Linkage e d i t o r The l i n k a g e e d i t o r p r o v i d e s f a c i l i t i e s  modules  i n t o pages a c c o r d i n g to a s p e c i f i e d  to p l a c e the  object  o r d e r i n g . A program  was w r i t t e n to produce a p p r o p r i a t e l i n k e d i t commands when the  following  input  1)  r e s t r u c t u r i n g procedure and 2) actual  object  module  the the  layout map  produced  which  from  identifies  given the the  names with the block numbers used i n the  layout.  5.4  Design and implementation The experiment  was performed on an AMDAHL 470 V/8  which operates under the Michigan Terminal System  computer  (MTS) [ 3 ] .  The  35  p r o g r a m e x p e r i m e n t e d on was a P a s c a l c o m p i l e r . P a s c a l and has about the P a s c a l c o m p i l e r  13000 l i n e s are given  5.4.1  o f c o d e . The c h a r a c t e r i s t i c s o f  below.  no.  of r e l o c a t a b l e b l o c k s  =  461  no.  o f b l o c k s > 1 page  =  4  av.  s i z e o f b l o c k s > 1 page  = 5282  av.  s i z e o f b l o c k s <=  s i z e o f a page = 4K  I t was w r i t t e n i n  1 page = 617  bytes bytes  bytes  S e l e c t i o n of l e v e l s f o r t h e experiment In  section  performance of values  5.1.1 an  the  major  algorithm  factors  were  felt  identified.  The  i t s l e v e l s . The f a c t o r s s e l e c t e d a n d t h e i r  levels  f o r the experiment are l i s t e d  The  levels  for  the  input  i n Tables  data  of  syntactic  5.1 and 5.2.  the  e r r o r s , t h e t y p e o f i n s t r u c t i o n s and  data  five  with  block  to the f i v e d i f f e r e n t  respect  a  to  s t r u c t u r e s o f t h e p r o g r a m s . The c o l l e c t e d correspond  corresponding  were s e l e c t e d t o c o v e r  v a r i e t y o f P a s c a l p r o g r a m s t o be c o m p i l e d  Pascal  different  o f a f a c t o r ( b o t h 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  called  number  t o a f f e c t the  reference  strings  input programs t o the  compiler.  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 i s o n . The no  original  o r d e r i n g o f t h e b l o c k s by t h e a u t h o r  restructuring  experiment. placed  in  In one  and  the  thus  served  original  contiguous  as  the  went  control  through of  the  o r d e r i n g , the o b j e c t modules a r e  block  spanning  several  pages.  36  K o b a y a s h i ' s ASI the  best  for  existing  reducing  because  page  i t  algorithm.  The  combination blocks it  algorithm  reducing  the  Two policy the  fault still  the  MWS  method  [8]  computing  window to  i s very  be  the  mean w o r k i n g  a  window  popularity  of  Least-Recently-Used represents  a size  robustness  of  of  its  usage  from  algorithm.  a  relationship  obtain  the  size  of  Three  the  reference  other  reference  appending  different  of  consisting of  50  of  values  reference  strings  the  of  4 to  24  was  matrix  n,  i n the  to  because  block  used to  test  time  reference  blocks  their  policy.  of  for  of The  order  to  30  a  fixed  value  the  the  used.  length extended  in  A  strings  were  s i z e ( k ) computed  50,  2)  set  literature.  processing  them  working  submatrix to  and  of  s e l e c t e d because i t  distinct had  BLI,  chosen  management  the  pairs  algorithm  The  p a g e s was  between  strings  v a r i e d from  the  1) i t s  r e s t r u c t u r e d program.  s t r a t e g y was memory  chosen  reasons:  of  were u s e d .  strings  The  the  was  between  that  reported  number o f  f o r n.  to  references  replacement  ranging  f o r two  strategy-dependent  size  size  the  method and  range  set  of  strategy-dependent  connectivity  best  [8]  best  chosen  similar  fixed-partition  partition  GHC  of  method  current was  i t i s one  restructuring algorithms  CWS  memory management p o l i c i e s  with  To  i n c l u d e d because  r a t e . The  is  i s considered  was  strategy-independent  method  i n the  [14]  get for  (30)  by a the was  used.  5.4.2  Implementation d e t a i I s  In  the  5  block  reference  strings  we  collected,  we  found  37  that s l i g h t l y  over  unreferenced in  200 d i s t i n c t  b l o c k s were  recorded.  For  the  b l o c k s , t h e r e s t r u c t u r i n g p r o c e d u r e s i m p l y p u t them  t h e same o r d e r  as the o r i g i n a l  ordering i n several  contiguous  pages. Initially generated tested  we  found  that the r e s t r u c t u r e d pascal  more page f a u l t s t h a n  on  a  real  system.  the  non-restructured  Careful investigation  compiler one  when  revealed the  c a u s e o f t h e p o o r p e r f o r m a n c e . We s h a l l d i g r e s s t o d e s c r i b e structure  of  a  Pascal  nested  routine i n order  the  to explain the  cause. The which  P a s c a l language a l l o w s d e c l a r a t i o n of a nested  takes  t h e f o r m a s shown i n F i g u r e 5.1. The d e c l a r a t i o n o f  t h e r o u t i n e s P1,..,Pn w i t h i n t h e r o u t i n e P i n a program  is  not a r b i t r a r y .  Instead,  well-structured  such c o n s t r u c t  a l l o w many o f t h e r o u t i n e s P1..Pn t o s h a r e  a common  (B  high  in  1  blocks  our  example).  B ..B 2 n+2  instruction  blocks  blocks a r e loaded coded  Consequently,  referencing  Furthermore, the data  are  block  into v i r t u a l  another  i s chosen t o data  i n c i d e n c e of the is  expected.  In a non-restructured  memory i n t h e same o r d e r  program, as  program,  the  B ..B will 1 n+2  be p r e s e r v e d  original  only  string.  ordering  i f there Any  they  t h e b l o c k s B ..B have a 1 n+ 2  i n m a i n memory a t t h e same t i m e .  restructured  block  be h e a v i l y r e f e r e n c e d by t h e  i n t h e program. T h e r e f o r e  i n the reference  a  one  B1 w i l l  B2..B(n+2).  high p r o b a b i l i t y of being  blocks  routine  of  the  In. a blocks  i s no r e f e r e n c e t o s u c h  reference  to  the  block  38  B(n+2)  will  inevitably  result  B(n+2) a n d i t s d a t a b l o c k w i l l because  data  blocks  were  i n a l a y o u t i n which  the block  n o t be i n t h e same p a g e . T h i s  not recorded  t h e y w o u l d be p u t i n t h e same page a s  is  i n t h e t r a c e and hence  some  other  unreferenced  blocks. The  solution  references  as  collection  stage.  t o t h e above problem  well  as  instruction  e n c l o s i n g data and i n s t r u c t i o n method  experiment. Pascal  only  works  The p r o p o s e d  compiler  either  f o r the  to ensure layout.  to  or  collected  in  data  facility,  generate  block  convention  symbolic  t h e same p r e f i x  data  that  P a s c a l c o m p i l e r used i n t h e  be c l o s e t o  belonging  one  another  the  names. I n t h i s  names were  names  t o a nested  t h e same b l o c k in  the  new  b l o c k r e f e r e n c e s t r i n g were s c a n n e d a n d  t h e b l o c k numbers were mapped t o some o t h e r u n i q u e result  the  r o u t i n e and i t s  t h i s r u l e , t h e s e were a l l p u t i n t o  that they w i l l The  the nested  method made u s e o f t h e  employed  instruction  routine. Using  in  data  b l o c k s i n t o one b l o c k . N o t e  c o n v e n t i o n , a l l symbols h a v i n g of  references  S i n c e t h e SDS d i d n o t p r o v i d e s u c h  an a d - h o c method was d e v i s e d t o . g r o u p  this  w o u l d be t o c o l l e c t  numbers. As a  o f t h e many-to-one m a p p i n g , t h e number o f d i s t i n c t b l o c k s  t h e new  reference  string  was  d e r i v e d s t r i n g has the f o l l o w i n g  reduced  substantially.  characteristics.  no.  o f d i s t i n c t r e l o c a t a b l e b l o c k s = 278  no.  o f b l o c k s > 1 page  = 13  av.  s i z e o f b l o c k s > 1 page  = 8116 b y t e s  av.  s i z e o f b l o c k s <=  = 681  1 page  bytes  The  39  In  the s i m u l a t i o n experiment,  s t r i n g s were u s e d t h r o u g h o u t would the  give  rise  the o r i g i n a l  because  the  block  block  size  t o more c o n t r a s t i n g p e r f o r m a n c e r e s u l t s  among  r e s t r u c t u r i n g a l g o r i t h m s so t h a t more  smaller  reference  definite  conclusions  c o u l d be made. In  testing  the  r e s t r u c t u r e d p r o g r a m on a r e a l s y s t e m , we  were f a c e d w i t h t h e p r o b l e m restructured  and  the  of  the t o t a l  page  while  workload  programs  in  is  a  controlled  d r i v e n by some r e c o r d e d t o ' c o n s t r u c t , and they experiment.  Failing  t h e number o f  submitted  The  i n which the system i s  Such w o r k l o a d s  are  t o meet t h e r e q u i r e m e n t s , In  order  to  test  the jobs comprising  simutaneously  the  programs  as i n t e r a c t i v e  are  running  the  The  programs  under  j o b s f r o m two t e r m i n a l s .  during  n o t be the  workloads identical.  short  time  i s small. restructuring  execution trace having different  means o f  t h e t e s t i n g p r o g r a m s were  would s t i l l  H o p e f u l l y , the f l u c t u a t i o n of workloads interval  expensive  a crude  S i n c e t h e CPU c a n o n l y s e r v i c e one j o b a t a t i m e , t h e when  ideal  r e q u i r e t h e s y s t e m t o be d e d i c a t e d t o t h e  t e s t i n g was e m p l o y e d . workloads,  Since  the program i n d i f f e r e n t  environment  workloads.  non-  dynamic  made.  system workload,  running  the a  c o n d i t i o n s c a n n o t be m e a n i n g f u l l y c o m p a r e d .  solution  similar  evaluate  a s s e s s m e n t c o u l d be  we h a v e no c o n t r o l o v e r produced  to  restructured  e n v i r o n m e n t f r o m w h i c h no f a i r  faults  trying  of the P a s c a l compiler as i t s input a  types of syntax  rate of e r r o r i s expected  errors.  program  was b a s e d on i t s which  Being a student  contained  compiler, the  t o be h i g h e r t h a n n o r m a l a n d t h u s  the  40  chosen  trace  compiler.  \  would  represent  the  general  behaviour  of  the  PROCEDURE P; I—Var . . .  Block  B 1  Procedure  P1;  —.  Block  B 2  Var... Begin  End;  I  Procedure  Pn ; —>  Block  B n+1  Va r . . . Begin  End; —Begin  1  Block  B n+2  . Codes f o r . Procedure  P  —End;  F i g u r e 5.1  Layout  of a P a s c a l n e s t e d r o u t i n e  Table 5.1.Select ion of l e v e l s f o r the R e s t r u c t u r i n g Experiment Program : P a s c a l C o m p i l e r Clustering Algorithm : 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 FACTORS NAME Input data (program t o be c o m p i l e d )  PI  LI2VELS  DESCRIPTION  P4 P5  student program p o i n t e r m a n i p u l a t i n g program p o r t i o n of the r e s t r u c t u r i n g p r o g r a m w i t h 21 s y n t a x e r r o r s data p r o c e s s i n g program n u m e r i c a l program  Restructuring Algor ithms  ORIG ASI CWS MWS BLI  o r i g i n a l o r d e r i n g by a u t h o r Activity-Set Critical-Working-Set Minimal-Working-Set Bounded-Locality-Interval  Memory Management Policy  WS LRU  Working-Set Least-Recently  P2 P3  Used  T a b l e 5.2 S e l e c t i o n o f l e v e l s f o r t h e C l u s t e r i n g Experiment Program : P a s c a l Compiler R e s t r u c t u r i n g A l g o r i t h m : CWS S i z e o f t h e S u b m a t r i x k : 30 Memory Management P o l i c y : WS (window s i z e FACTORS NAME Block reference Strings  SI S2 S3 S4 S5  50 r e f e r e n c e s )  LEVELS DESCRIPTION 1 42 d i s t i n c t 171 d i s t i n c t 195 d i s t i n c t 208 d i s t i n c t 252 d i s t i n c t  blocks blocks blocks blocks blocks  43  C h a p t e r 6 D i s c u s s i o n of e x p e r i m e n t a l In t h i s c h a p t e r , the  actual  runs  p e r f o r m a n c e of t h e with  the  other  experimentally The  BLI  results obtained  are  presented.  BLI  restructuring  the time complexity i s assessed  of a p r o g r a m ' s b e h a v i o u r  working  attribute  of  set  the  size  not  be  investigated in this  6.1  E v a l u a t i o n of the  BLI  the  As page  expected, fault  rate  restructuring management the  t h e CWS  policy.  f i g u r e of m e r i t The  CWS  a l g o r i t h m on  method.  The  rate  cost.  The  input data  is  input  data  a  will  results.  programs 6.1a  the average under  and  with  when the the  the window BLI  working  a working  set  6.1b.  algorithm outperforms  However,  the  window size  others  in  used  in  size of  the  memory  a l g o r i t h m works best  i s the average working set  when  size. BLI  r a t e r e d u c t i o n by a p p r o x i m a t e l y  the other  fault  performance of  a l g o r i t h m performs b e t t e r than the  t e r m s o f page f a u l t  clustering  to d i f f e r e n t  in Tables  reduction  matches  analyze  algorithm  restructured  environment are presented  comparison  will  to d i f f e r e n t  number o f page f a u l t s g e n e r a t e d and of  the  thesis.  D i s c u s s i o n of s i m u l a t i o n  size  in  r e d u c t i o n and  program.  r e s t r u c t u r e d program w i t h r e s p e c t  set  algorithm  and  discuss  i n t e r m s of page  sensitivity  The  first  o f t h e GHC  average  6.1.1  will  simulation  r e s t r u c t u r i n g a l g o r i t h m s . Then we  algorithm  an  from the  We  reduction,  largely  results  algorithm 3%.  in  The  BLI  hand r e d u c e s the a v e r a g e w o r k i n g s e t  size  44  13%  more  than  significant  the  CWS  algorithm.  d i f f e r e n c e between  Although  there  the p e r f o r m a n c e of  the  MWS  t h e BLI a l g o r i t h m s , t h e h i g h c o s t o f e x e c u t i n g t h e MWS (at  least  10 t i m e s more t h a n t h e o t h e r s  is  no and  algorithm  i n o u r s t u d y ) makes i t  an u n a t t r a c t i v e a l g o r i t h m t o u s e . I n a g l o b a l - L R U e n v i r o n m e n t , t h e memory s p a c e a l l o c a t e d a  single  process  is  time-variant.  To  get  an  idea  r e s t r u c t u r i n g would improve the performance of a program an e n v i r o n m e n t , t h e r e s t r u c t u r e d p r o g r a m partition curves  LRU  in  for d i f f e r e n t  6.1  how  i n such  i s executed i n a  fixed-  e n v i r o n m e n t o v e r a w i d e r a n g e o f page f r a m e s .  Figure  to  The  show t h e number o f page f a u l t s g e n e r a t e d  number o f page f r a m e s  in  a  fixed-partition  LRU  e n v i ronment. When  t h e number o f page f r a m e s a l l o c a t e d  i s s m a l l , t h e BLI  a l g o r i t h m o u t p e r f o r m s t h e o t h e r by a s u b s t a n t i a l amount. As more page f r a m e s a r e a l l o c a t e d , BLI r e l a t i v e performance frames Consider  could a  to of  the the  be  t h e amount o f improvement  other, BLI  best  algorithms  diminishes.  algorithm at the higher explained  by  the  1,2  and 4,3  than the p a t t e r n contains  two  The  following  each  example. pattern of  the  i s r e p e a t e d many more t i m e s c o n s e c u t i v e l y  1,3,5,6. A s s u m i n g  blocks.  where  poor  r a n g e o f page  block reference s t r i n g having the reference  {1,2,..,1,2,4,3,..,4,3,1,3,5,6,..,1,3,5,6}, patterns  p r o d u c e d by  The  layout  o p t i m a l i n a f i x e d - p a r t i t i o n LRU  i n a simple case that a  page  {(1 , 2 ) , (3 , 4) , ( 5 , 6)} w o u l d  e n v i r o n m e n t w i t h t h e number  of  page f r a m e s = 1. However, i f t h e number o f page f r a m e s = 2, t h e n the l a y o u t { ( 1 , 3 ) , ( 5 , 6 ) , ( 2 , 4 ) } would produce b e t t e r  results.  Thus  be  45  it  i s clear  that  no  layout which i s optimal available  to  the  a v a i l a b l e memory references transition  is  over t h e whole  restructured  i s large, a required.  result,  range  program.  wider  o f " memory  space  general,  i f the  In  observation  In our reference  set size detected  the c o r r e s p o n d i n g a  r e s t r u c t u r i n g a l g o r i t h m c o u l d produce a  of  the  strings,  by t h e B L I method i s  the average  smaller  of e m p i r i c a l  Due t o t h e h i g h  results  f l u c t u a t i o n of workload  i n t h e system under  w h i c h t h e e x p e r i m e n t was c a r r i e d o u t , t h e e x p e r i m e n t a l be v e r y  experiment a large  high.  I t i s hoped t h a t a f t e r  number o f t i m e s ,  the  p r o g r a m o v e r a n o t h e r c a n be e s t a b l i s e d The  error  superiority  of  in  the  restructuring  process  p a s c a l program c o n t a i n i n g s e v e r a l syntax input  used t o t e s t t h e c o m p i l e r s  lengths type  and  programs  were t e s t e d on MTS  difficult a  high  uncertainty  h i g h degree of c o n f i d e n c e .  faults  show t h a t t h e r e  The  different  i n c l u d e d programs of d i f f e r e n t  w i t h and w i t h o u t  t o draw c o n c l u s i o n s  reference  had as i t s input a  errors.  syntax  o f i n p u t , t h e e x p e r i m e n t was r e p e a t e d Due t o t h e  one  statistically.  two v e r s i o n s o f t h e P a s c a l c o m p i l e r  used  is  repeating the  [ 3 ] w h i c h u s e s a g l o b a l memory management p o l i c y . The string  range  allocation.  6.1.2.Discussion  to  than  a v e r a g e w o r k i n g s e t s i z e o f t h e CWS method. As  t h e BLI a l g o r i t h m p e r f o r m s b e t t e r a t t h e lower  o f page f r a m e s  expected  block  in  e r r o r s . F o r each  at least  the  i s a definite  times.  experiment,  from t h e e x p e r i m e n t a l Nevertheless,  30  i t is  results  with  t h e c u m m u l a t i v e page  improvement of  performance  46  in  the  restructured  presented of o v e r the  i n Table  30  runs.  p r o g r a m . The  6.4  i s b a s e d on  B e c a u s e of t h e  f i g u r e s do n o t  i n any  r e s u l t s upon r e p e t i t i o n The  discrepancy  a c t u a l and  the  restructuring data  has  a l l  The  combined  enclosing blocks  regrouping  blocks  after  high  frequency  global data block  that  The  data  activity  procedure  (see  it  is  not  source  the  ideal  s i z e s and  Moreover,  in  block  s e c t i o n 5.4.2)  many  thus  of  the  a p a g e . Some o f  contain subblocks our  the  which are  reference  not  strings  ones.  c o d e shows t h a t t h e r e  is a  of p r o c e d u r e s r e f e r e n c i n g g l o b a l d a t a . S i n c e  b l o c k c a n n o t be p l a c e d references not  saved through  i n the  i t , i t i s clear be  no  results  paging  the nested  t h e more h e a v i l y r e f e r e n c e d  restructuring will faults  the  span over  r e l a t e d . A l s o , the o v e r s i z e d b l o c k s  of t h e c o m p i l e r ' s  explanation.  i n larger block  regrouping  the  string.  somewhat,  results  between  simulation  i n t o a block  p a g e s o f t h e o v e r s i z e d b l o c k may  A study  same  s t r i n g which c o n t a i n s  because  the r e f e r e n c e  rate  experiment,  not a c c o u n t f o r t h e  b e n e f i t s of r e s t r u c t u r i n g .  h a p p e n e d t o be  some  does  improvement  r e d u c e d page f a u l t  reduces.the  it  t h e method o f g r o u p i n g  its  solution.  r e d u c t i o n of page f a u l t  the r e f e r e n c e  hence  of the  faults  experiment.  be h e a v i l y r e f e r e n c e d . The  i s b a s e d on  Although and  and  substantial  simulated  i n the  random n a t u r e  page  rate  g u a r a n t e e r e p r o d u c t i o n of t h e  of t h e  i s b a s e d on  b l o c k s w h i c h may a  way  the cummulative  s i m u l a t i o n runs r e q u i r e s  references  show  r e d u c t i o n o f page f a u l t  substantial  if  same  page  t h a t the the  as  the  every  improvement  number  of  r e s t r u c t u r i n g i s s m a l l compared t o the  of  page high  47  page  fault  6.1.3  cost  method  program. and  method  I t i s p r o p o r t i o n a l t o t h e number transition  performance  6.2  The  average  30 t o 5 0 . A f i x e d  the  relation  time  The  the  GHC  methods  processing  c  t h e HC  ratio time  of  phases  transition  measurement to execute  the  a  shows  than  the  was  used  in a cluster in  order  i s defined to  that CWS  be  n  method  of  n  i s indeed  n . 2  23  Thus  i f n  times.  establish  lower  in  and  increasing  indicates  i s =  of  processing  o f t h e HC  The  the improvement r a t i o  0.0235.  (k) v a r i e s  method.  complexity and  3  time  clustering  to  the  the  strings  a n d t h e number  b y t h a t o f t h e GHC  the time  and  processing  entire  improvement r a t i o  function  i s approximately  the  time  reference  b l o c k s . The  of b l o c k s  that  In f a c t ,  processing  execute  k value  o f t h e GHC  method.  the  respectively  i s c o m p u t e d t o be ^  improvement  to  number  shows  as  of the  scheme  of d i s t i n c t  method d i v i d e d  are  using the  of the l o c a l i t y  algorithms using  improvement r a t i o  analysis  improvement  than  between  o f t h e HC  Our  show  taken  from  blocks.  clustering  6.3  number  i s the time  procedure.  i s cheaper  of the c l u s t e r i n g  different  measured  and  Our  matrix  18%.  by a p p r o x i m a t e l y  Tables  set size.  t h e BLI method  E v a l u a t i o n o f t h e GHC  with  references.  d e p e n d s on t h e c h a r a c t e r i s t i c s  the average  6.2  data  of c o n s t r u c t i n g the c o n n e c t i v i t y  the average  on  to the global  Cost  The BLI  r a t e due  that  the  complexity  i s = cn  1000, t h e  where  expected  48  However, the construction phase.  of  scheme  will  constant  of  a matrix  of  advantage  which  string  and  efficiency  208  string  x  208,  the  the  which  computation  comparable  to  that  cheaper  degradation  of  the  of  solution  in  of and  the  HC  to  the  a  new  is  the  matrix  of  as  the  extrapolation, for  method  course  will  have  block  to  a  machine  experiment, time  no  references  pertains  a particular  in processing  GHC  the  method decreases  In our  the  linearly  overhead  for  number o f  executed.  i s considered  performance  Thus  GHC  This  is  string,  i n c r e a s e s . By  m e t h o d when t h e  is  time  major  new  HC  algorithm  (S4)  the  account  the r e s t r u c t u r i n g  reference  i f  of  into  during  vector.  non-negligible saving  The  6.3  matrix  reference  the  the  suitable  take  processing  restructuring algorithm  the a  be  the  150000.  particular  l e n g t h of  the  size  over  exceed  much  of  the  additional  the  not  size,  length  connectivity vector  the  to  construction  still  the  Since  proportional  above a n a l y s i s does not  on  there  for a  is  reference  long.  method as  shown  algorithm.  Thus  clustering  in Table the  GHC  problem  6.3  is  offers with  a no  performance.  Conclusion  There improving  is the  no  performance  memory  system.  weighed  against  obtainable  doubt  However, the  depends  that of  r e s t r u c t u r i n g has a  cost  of  benefits gained.  The  on  the  program  several  the  running  in  potential a  restructuring amount  factors,  of among  of  virtual must  be  improvement which  the  49  following: of  the  choice  The  the  choice  improvement  of t h e  rate be  program,  index  i f the  input  s o u g h t and  on  depends  the  best  in  memory  produced  from  might c o n j e c t u r e well  in  a  BLI  global-LRU  s u b s t a n t i a t e d by  concrete  been  our  large  one  algorithm  Due  our  to  in  Therefore to the  claim  r e s u l t s from a r e a l  each a  improvement  likely  we  perform lack  cannot  of be  system.  i s true to a c e r t a i n extent  though  i s n e e d e d . A b a d l y - w r i t t e n p r o g r a m may e x t r e m e i t may  c o n s i s t of  or  r e s t r u c t u r i n g would c e r t a i n l y  i l l - s t r u c t u r e d program c o u l d does  j u s t one  not  behaviour  p a t t e r n and  r e s t r u c t u r i n g i n such a case would s i n c e no p a r t i c u l a r  exhibit  also  execution  improvement  frames  highest.  is  the  Although  the a b s o l u t e  i s the  experiment,  p r o g r a m s e g m e n t s and  e f f e c t i v e . An  environment,  s a i d t h a t r e s t r u c t u r i n g i s most e f f e c t i v e on  clarification  many f o r m s . On  6.1),  environment.  b a d l y - w r i t t e n programs. T h i s some  better  algorithm  t h a t the  of  has  a  (see F i g u r e  controllability  It  be  BLI  page  reduction  o v e r a c e r t a i n r a n g e o f page  the  the  improvement sought i s the  choice.  environment  executed.  strategy  BLI  f i x e d LRU  the  management  set  i s optimal  be  reducing  of a v e r a g e w o r k i n g s e t s i z e i n a w o r k i n g to  on  t h e memory management p o l i c y o f  are  knowledge of  algorithm  restructured  r e s t r u c t u r e d program w i l l  algorithms  seems  quality  use.  e x p l o i t e d . When t h e  algorithm  the  t o the  restructuring algorithms  system i n which the  fault  restructuring algorithms,  f r e q u e n c y of  Strategy-dependent  can  the  non-restructured  p r o g r a m and  the  of  be  distinct  s e t of b l o c k s  not are  take  a  few  not  one  be  whose  referencing yield favoured.  much Yet  50  a n o t h e r form of frequency  of  i l l - s t r u c t u r e d p r o g r a m i s one global  data  references.  every  p r o c e d u r e makes r e f e r e n c e  size  of  the  conceivable will  i n t h i s case.  time,  referenced  the  during  resulting  i n low  Perhaps  either  restructuring  a good memory management  of  i n main memory  block  being  time  c o r r e c t t o say  could  most  frequently be  small,  that r e s t r u c t u r i n g i s  well-structured  good l o c a l i t y ,  experiments  program.  two  essential  A  good to  ingredients  first  type  on page f a u l t  data  references  hence c o u l d not is  supposed t o r e p r e s e n t i t will  insensitive  i n f l u e n c e of r a t e has  s t r u c t u r e s i s not  Restructuring  constitute a  the  o n l y be  to d i f f e r e n t  not  very  on  one  beneficial  programs  references  been d i s c u s s e d .  recorded  general  of c o m p i l e r s ,  data  in  to data  the  is of  Reference  trace  of  a  be a c c o u n t e d f o r i n r e s t r u c t u r i n g .  based  the behaviour is  that  o r d y n a m i c . The  dynamic data  Therefore  show  amount o f page f a u l t s . Memory a l l o c a t i o n  static  p r o g r a m and  is  large. It i s  a w e l l - s t r u c t u r e d program would g i v e r i s e  s i z e s and  considerable  to  the  of m a i n memory.  more a  very from  block  period  block,  effective restructuring. Our  the  is  in  resulted  Although  data  be  of the d a t a  short  on  modularization  for  portion  utilization  it  could  the g l o b a l data  a  effective  small block  block  high  I n t h e w o r s t c a s e where  t o the g l o b a l  improvement  would m a i n t a i n  the  most  data  t h a t the  be m i n i m a l  policy of  global  containing a  execution  behaviour i f the  input data.  of  the  program.  r e s t r u c t u r e d program  Studies  a s s e m b l e r s and  trace which i s  have shown t h a t  other  s e n s i t i v e to d i f f e r e n t  large  system  input data.  Such  51  programs a r e a l s o cost  of r e s t r u c t u r i n g  The  amount  size  the input  of  resident  will  for  be p a i d  restructuring  o f f through  data  information,  is  a  such  i n main memory may  program a s symbol  increase  to  be  6.4  large  (several  improvement  shows  hundred  Kbytes)  of the input  required  proportionally  the t o be  with  i s perhaps  the  minor;  p r o g r a m would have t o be v e r y to  reduce  the  new c l u s t e r i n g  the  percentage  scheme p r o v i d e s a much c h e a p e r  to the c l u s t e r i n g problem with  performance. insignificant However,  the input  usage.  t o below 6 % .  Lastly, solution  that  the  compiled,  tables,  o f t h e p r o g r a m . The e f f e c t o f t h i s f a c t o r  Table  since  frequent  improvement a l s o may depend on t h e l e n g t h  d a t a . When  the  good c a n d i d a t e s  this  The  reduction  compared t o t h e scheme f i n d s  s i z e of the m a t r i x  in  cost  its application  i s the dominating When  reduction  time c o u l d  degradation  processing  overall  time of the a l g o r i t h m . i n execution  little  time  of  may  seem  restructuring.  i n many a r e a s  factor  in  where  i n the execution  the s i z e of the matrix be s u b s t a n t i a l .  i s huge,  the  T a b l e 6.1a C o m p a r i s o n o f t h e r e s t r u c t u r i n g a l g o r i t h m s on t h e number o f page f a u l t s i n t h e working s e t environment String  Original  CWS  MWS  ASI  BLI  PI P2 P3 P4 P5  369 8032 5698 4946 1690  1 70 3565 2769 231 5 738  1 58 3599 2765 2254 826  202 3565 3465 2306 921  159 3607 2706 2465 898  mean  4147  1911  1 920  2092  1 967  T a b l e 6.1b C o m p a r i s o n o f t h e r e s t r u c t u r i n g a l g o r i t h m s the average working s e t s i z e ( i n t e r m s o f 4K b y t e p a g e s ) i n t h e working s e t environment String  Or i g i n a l  CWS  MWS  ASI  BLI  PI P2 P3P4 P5  1 0.40 1 2.68 1 3.42 10.89 1 1 .65  7.16 7.66 8.21 6.52 6.72  5.34 7.25 7.68 6.21 6.93  6.42 7.66 8.91 6.50 6.92  4.87 6.86 7.11 6.26 6.50  mean  11.65  7.25  6.68  7.28  6.32  T a b l e 6.2a C o m p a r i s o n o f t h e c l u s t e r i n g a l g o r i t h m s on t h e CPU p r o c e s s i n g t i m e ( i n msec*) d u r i n g the c l u s t e r i n g phase String  n  HC  SI S2 S3 S4 S5  1 42 171 195 208 252  1823 3026 4299 5100 8704  GHC(k=30) 554 739 938 1057 1 448  Improvement 3.29 4.09 4.58 4.82 6.01  T a b l e 6.2b C o m p a r i s o n o f t h e c l u s t e r i n g a l g o r i t h m s on t h e CPU p r o c e s s i n g t i m e ( i n msec*) d u r i n g the r e s t r u c t u r i n g phase String 51 52 53 54 55  no.of  references 21304 9950 40832 59396 15375  HC 1892 852 4469 6169 3015  GHC(k=30) 21 24 931 5662 7621 3581  T a b l e 6.2c C o m p a r i s o n o f t h e c l u s t e r i n g a l g o r i t h m s on t h e C P U ' p r o c e s s i n g t i m e ( i n msec*) d u r i n g 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 phases String  HC  GHC(k=30)  SI S2 S3 S4 S5  371 5 3878 8768 1 1269 11719  2678 1 670 6600 8678 5029  A l l t i m e s q u o t e d i n T a b l e s 6.21 from an Amdahl 470 V/8 s y s t e m .  t o 6.2c were m e a s u r e d  54  T a b l e 6.3  Comparison of t h e c l u s t e r i n g a l g o r i t h m s t h e number o f page f a u l t s g e n e r a t e d in the working s e t environment  String  n  si  142 171 195 208 252  S2 S3 S4 S5  •  T a b l e 6.4  HC 882 358 2593 3565 1510  I  prog, prog, prog, prog,  GHC(k=30) 928 353 2697 3629 1 603  E v a l u a t i o n of t h e r e s t r u c t u r e d P a s c a l on MTS  restructuring algorithm  n  P  u  t  programs  on  compiler  : BLI  % reduction  w i t h 7 e r r o r s , size=13 pages w i t h no e r r o r s , s i z e = 1 3 p a g e s w i t h 209 e r r o r s , s i z e = 8 0 p a g e s w i t h no e r r o r s , s i z e = 8 0 p a g e s  i n page f a u l t 14 12 6 3  rate  Figure  6.1  Paging  Characteristics  of  reference  string  P3  56  REFERENCES [1]  M.S. A c h a r d , J . Y . B a b o n n e a u , M . C a r p e n t i e r , G. M o r i s s e t , M.B. Mounajjed, "The clustering algorithms i n the Opale restructuring system," Performance of Computer Installation, D.Ferrari(ed.) CILEA, North-Holland P u b l i s h i n g Co.,1978.  [2]  Y, B a r d , " C h a r a c t e r i z a t i o n o f p r o g r a m paging i n a timesharing environment," IBM Journal of R e s e a r c h and D e v e l o p m e n t , 1973, p p . 3 8 7 - 3 9 3 .  [3]  D. Boettner a n d M. A l e x a n d e r , "The M i c h i g a n Terminal System," I n IEEE P r o c e e d i n g s , S p e c i a l i s s u e on i n t e r a c t i v e c o m p u t e r s y s t e m s , pp. 912-918, J u n e 1975.  [4]  S. C h a n s o n a n d B. Law, " I m p r o v i n g p e r f o r m a n c e by strategyindependent program restructuring u s i n g Bounded L o c a l i t y I n t e r v a l s , " , T e c h n i c a l R e p o r t 8 1 - 9 , D e p t . o f Computer S c . , U n i v e r s i t y o f B r i t i s h C o l u m b i a , 1981.  [5]  S. Cook, The c o m p l e x i t y o f t h e o r e m p r o v i n g p r o c e d u r e s , " SIGACT, 1970, pp.151-158.  [6]  D. F e r r a r i , "Improving program locality by strategyoriented restructuring," Information Processing 74, P r o c . IFIP C o n g r e s s 74, N o r t h - H o l l a n d , Amsterdam, 1974, p p . 2 6 6 270.  [7]  D. Ferrari, "Tailoring programs t o models of b e h a v i o r , " IBM J o u r n a l o f R e s e a r c h a n d D e v e l o p m e n t , 3, May 1975, p p . 2 4 4 - 2 5 1 .  [8]  D. F e r r a r i , "The i m p r o v e m e n t of program b e h a v i o r , " Computer 9 11, Nov. 1976, p p . 3 9 - 4 7 .  [9]  D. F e r r a r i a n d M. K o b a y a s h i , "Program restructuring algorithms f o r global-LRU environments," Conf. Proc. of Int. Computing Symp. 1977, L i e g e , B e l g i u m , pp.277-283, A p r i l , 1977.  [10]  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 S y s t e m Journal vol.10, pp.168-192, 1 971 .  [11]  E. Horowitz a n d S. S a h n i , "Fundamental of a l g o r i t h m s " , Computer S c i e n c e P r e s s , I n d . , 1978.  [12]  K.C. Kahn, " P r o g r a m 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 , Dept. Computer S c . , P u r d u e U n i v . , W. L a f a y e t t e , I N , A u g . 1976.  [13]  R. K a r p , " R e d u c i b i l i t y among c o m b i n a t o r i a l problems," In Complexity o f Computer C o m p u t a t i o n s , R. M i l l e r a n d J . T h a t h e r E d . , P l e n u m P r e s s , N.Y. 1972, p p . 85-104.  ACM  program vol.19, IEEE  computer  57  [ 1 4 ] M. K o b a y a s h i , "A s e t o f s t r a t e g y - i n d e p e n d e n t restructuring algorithms" S o f t w a r e - P r a c t i c e a n d E x p e r i e n c e , V o l . 7, 5 8 5 594 ( 1 9 7 7 ) . [ 1 5 ] A.W. M a d i s o n a n d A.P. B a t s o n , " C h a r a c t e r i s t i c s of l o c a l i t i e s , " CACM, v o l . 19, p p . 2 8 5 - 2 9 4 , May 1976.  program  [ 1 6 ] T. Masuda, H. S h i o t a , K . N o g u c h i , a n d T. O h k i , " O p t i m a z a t i o n of program locality by c l u s t e r analysis," Proc. IFIP C o n g r e s s , 1974, p p . 2 6 1 - 2 6 5 . [17] J . - F . P a r i s a n d D. F e r r a r i , "An a n a l y t i c a l study of 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 , " Progres Report 82.1 ,Dept. o f EECS, U n i v e r s i t y o f C a l i f o r n i a , B e r k e l e y , 1982. [ 1 8 ] J.R. S p i r n a n d P . J . D e n n i n g , locality," AFIPS Conf. P r o c , 621 .  "Experiments with program F J C C , v o l . 4 1 , 1972, pp.61 1-  [ 1 9 ] C.T. Y u , M.R. S i u , K. Lam, F . T a i , " Adaptive clustering schemes : general framework," Proceeding o f COMPSAC c o n f e r e n c e , C h i c a g o , 1981, p p . 8 1 - 8 9 .  

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}]}"
                            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:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051842/manifest

Comment

Related Items