UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A Petri net formulation for the general scheduling problem Imai, Michael Kenji 1981

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

Item Metadata

Download

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

Full Text

A PETRI NET FORMULATION FOR THE GENERAL SCHEDULING PROBLEM  by  MICHAEL K E N J I IMAI B.Eng.Mgt., M c M a s t e r U n i v e r s i t y ,  1979  A THESIS SUBMITTED I N PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF A P P L I E D SCIENCE in THE FACULTY OF GRADUATE STUDIES (Department of E l e c t r i c a l  We a c c e p t  this  thesis  to the required  Engineering)  as conforming standard  UNIVERSITY OF B R I T I S H COLUMBIA S e p t e m b e r , 1981  © Michael  K e n j i I ma i  1981  In p r e s e n t i n g  this  thesis i n partial  r e q u i r e m e n t s f o r an a d v a n c e d  degree a t the U n i v e r s i t y  of B r i t i s h Columbia, I agree that it  fulfilment of the  the Library  f r e e l y a v a i l a b l e f o r r e f e r e n c e and study.  agree t h a t p e r m i s s i o n f o r extensive  s h a l l make I further  copying of t h i s  thesis  f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e h e a d o f my d e p a r t m e n t o r by h i s o r h e r r e p r e s e n t a t i v e s . understood that for financial  copying or p u b l i c a t i o n of t h i s  gain  M i c h a e l K. Imai  E l e c t r i c a l Engineering  The U n i v e r s i t y o f B r i t i s h 2075 W e s b r o o k P l a c e V a n c o u v e r , Canada V6T 1W5 Date  October 2,  thesis  s h a l l n o t be a l l o w e d w i t h o u t my  permission.  Department of  It is  1981  Columbia  written  i i  Abstract This  thesis  the g e n e r a l  introduces  scheduling  concerns  the  Petri  formulation  net  of  of  coloured  P e t r i n e t s . The  problem  begins  nets,  with  strategy  p a r t of t h i s  Petri  net  general  the  construction general  In  the  formulation scheduling a  task  second is  part  of  for  p r o b l e m . The  this  the  a s e t of p r o c e s s o r s  heuristic  is  levels  proposed  for  the  proposed h e u r i s t i c  first  the  scheduling  heuristic  The  of  a  i s the  by  the  analysis. Petri  net  of  speeds.  scheduling.  longest  for  scheduling  o r d e r i n g of t h e  the  The  particular  of d i f f e r e n t  combines n o t i o n s  and  which  problem.  generated  is list  and  the a l g o r i t h m  thesis,  problem addressed  s t r a t e g y t o be a n a l y z e d  The  is  The  three  of a P e t r i n e t  analysis  scheduling  list.  from  net model under the m o d i f i e d  used  s y s t e m on  to  i s m o d e l e d by m o d i f y i n g  of t h e P e t r i  thesis  P e t r i nets  scheduling  the a n a l y s i s of P e t r i n e t s . A s c h e d u l e execution  concepts  approach  for  formulation.  marked g r a p h s , timed  s t r u c t u r e of t h e  scheduling  the  formulation  first  i s a s y n t h e s i s of  classes  models the  P e t r i net  p r o b l e m . The  development  Petri  a new  tasks  from the  The  A  new  into  a  highest  processing  time  heuristic. The a  p e r f o r m a n c e of t h e p r o p o s e d h e u r i s t i c  comparision  with  schedules  which are  compared  to  the  other  list  g e n e r a t e d by  schedules  ordering  the  which are  proposed  i s evaluated  by  heuristics.  The  heuristic  are  g e n e r a t e d by  the  highest  levels  first  a random l i s t heuristic tested heuristic is  heuristic,  t h e C o f f m a n and Graham A l g o r i t h m A  f o r f i f t e e n precedence  generated a better for  the  15  c o n s t r a i n t s . The  schedule  precedence  in  98  constraints.  g e n e r a t e d a s c h e d u l e a s good as t h e  generated  by any  other l i s t  in a further  39  of  proposed  160  The  cases  proposed  schedule cases.  and  which  iv  Table  of  Contents  Abstract Table  i i  of Contents  List  of F i g u r e s  List  of T a b l e s  iv vi viii  Acknowledgement  ..  ix  1 Introduction 1.2  1  Overview of the T h e s i s  2 Petri  4  Nets  6  2.1  B a s i c C o n c e p t s and  2.2  A n a l y s i s of P e t r i  Ideas  6  Nets  18  2.2.1  Structural Analysis  18  2.2.3  Behavioral Analysis  22  2.3  C l a s s e s of P e t r i  Nets  25  2.3.1  Marked Graphs  27  2.3.2  Timed P e t r i  28  2.3.3  Coloured  3 The  Petri  Net  Petri  Nets  35  Formulation  3.1  The  General  3.2  The  Petri  Scheduling  Net  3.2.1  The  3.2.2  Modeling  3.3  Nets  41 Problem  Formulation  45  C o n s t r u c t i o n of t h e P e t r i  R e l a t e d Work  41  the Behavior  Net  Model  of a S c h e d u l i n g  Strategy  46 63 67  4 The  A n a l y s i s of a S c h e d u l i n g P r o b l e m  75  4.1  The  77  4.2  Algorithms for L i s t Ordering  81  4.3  Experimental Outline  95  4.4  R e s u l t s and  98  S c h e d u l i n g Model  5 C o n c l u s i o n s and  Discussion Suggestions  f o r Further Research  109  5.1  Summary and  Conclusions  109  5.2  Suggestions  for Further Research  111  Bibliography A p p e n d i x A D e f i n i t i o n s and A p p e n d i x B Sample R e s u l t s  114 Notation  123 128  vi  List simple  of  Figures  2.1  A  Petri  net  .  2.2  A marked P e t r i  net  2.3  T4  fired  11  2.4  T3  fired  11  2.5  2 consumer  2.6  A persistent  2.7  Structural  analysis  20  2.8  Behavioral  analysis  24  2.9  A  9  - single Petri  reachability  7  producer  14  net  17  tree  26  2.10  A marked g r a p h  29  2.11  Firing a  31  2.12  A  timed  2.13  A  timed t r a n s i t i o n  2.14  A producer-consumer  2.15  A coloured  2.16  Similar  2.17  A  timed t r a n s i t i o n transition  Petri  ....... . .... . . . . . . . . . . . . . . . . . . . . . system  net  38 40  scheme  3.1  A  3.2  Algorithm  3.3  The  3.4  Colour  3.5  A dynamically  3.6  T a s k s ,T3  3.7  GRID A l g o r i t h m  3.8  A capacitated  3.9  Algorithm  40  system  44  1  47  marked g r a p h a f t e r  Step 6  — . .  —  ...  sets  and  to  32 36  transitions  transition task  32  49 51  reconfigurable  architecture  ...........  T7  58 ....  computation find  53  s(k)  65  graph  70  ...  72  vii  3.10  Resource c o n f l i c t  4.1  Colour  4.1  Example  4.3 E x a m p l e  resolution  set f o r processors  of d i f f e r e n t  73 speeds  79  1  82  1 levels  84  4.4 C o f f m a n Graham A l g o r i t h m A  85  4.5 E x a m p l e  1 - CG A l g o r i t h m  86  4.6 E x a m p l e  1 chain  4.7 O r d e r e d l i s t s  A  length  89  of t a s k s f o r Example 1  92  4.8  S c h e d u l e s f o r Example  1  93  4.9  S c h e d u l e s f o r Example  1  94  B.1  E x a m p l e 8 - <:most c o n s t r a i n e d  128  B.2  Example 9 - < : l e a s t  129  constrained  vi i i  List 3.1  Transition  of  Tables  scheme, T4  3.2 T a s k p r o c e s s o r  requirements  51 and e x e c u t i o n times  55  3.3 T r a n s i t i o n  scheme, T3  57  3.4 T r a n s i t i o n  scheme, T7  57  3.5 T r a n s i t i o n  scheme, T4  57  3.6 An a d m i s s a b l e 4.1  schedule  Bounds f o r l i s t  4.2 C o l o u r  70  scheduling  76  set f o r experiments  97  4.3 Summary o f R e s u l t s  99  4.4 A v e r a g e w/w*  101  4.5 R e s u l t s f o r E x a m p l e 1  104  B.1  Example  1 longer execution times  slower processors  ..130  B.2 E x a m p l e 1 s l o w e r p r o c e s s o r s  131  B.3 E x a m p l e 1 l o n g e r e x e c u t i o n t i m e s  132  B.4 E x a m p l e  133  1 u n i t execution times  ix  Ac knowledqement I  would  like  both the t o p i c s scheduling  to  involved  theory.  I  encouragement thoughout I gratefully the  National  University  thank  D r . Mabo R.  in  also  the thank  Ito for introducing  reseach, him  acknowledge the f i n a n c i a l  of B r i t i s h  and  Columbia'.  nets  f o r h i s guidance  the c o u r s e of t h i s  Sciences  Petri  Engineering  and and  work. support  of  both  Council  and  the  1  CHAPTER 1 INTRODUCTION  A Petri nets  are  n e t i s a f o r m a l model of i n f o r m a t i o n f l o w .  particularly  a n a l y s i s of  systems  behavior.  Petri  representation natural  and  graphical to  useful  which nets  f o r the  exhibit provide  f o r asynchronous compact  natural  concurrent  concurrent and  ability  nets are e a s i l y  t o model s y s t e m s .  compact  systems.  representation i s reflected  representation. Petri  increase their  d e s c r i p t i o n and t h e  asynchronous a  Petri  i n a simple  extended  This  The  so as  extendibility  a l l o w s compact and n a t u r a l d e s c r i p t i o n s f o r a wide v a r i e t y  of  systems. An both of  important  the  i s the s t a t i c  restrictions  nets  i s the a b i l i t y  conditions  p r o p e r t i e s i n a system  on t h e b e h a v i o r o f t h e s y s t e m .  i s t h e s e t of in  become v a l i d . Thus,  actions  the ' system.  since the occurrence  occur.  of P e t r i  s t r u c t u r e and t h e b e h a v i o r of systems.  a system  system  aspect  which  occur  The b e h a v i o r  o f an a c t i o n  causes  t o model  The s t u c t u r e which  impose  The b e h a v i o r o f a as  a  result  of  i s dynamic i n n a t u r e new  conditions  to  The new c o n d i t i o n s i n t u r n a l l o w more a c t i o n s t o Petri  systems i n which  the  n e t s a r e a p o w e r f u l method o f d e s c r i b i n g structure  and  behavior  are  of  equal  importance. The  g e n e r a l s c h e d u l i n g problem  i s that of s c h e d u l i n g the  2  execution  o f a s e t of t a s k s on a s e t  purposes  of  system.  this  The  primary  and  thesis,  computer  system  is  comprised  For  the  i s a computer  of  processors,  p o s s i b l y other devices.  c o n s i s t s of b l o c k s o f  The  independent code from a  program.  It  for  the  execution  o f a l l of t h e t a s k s ; t h a t i s , t h e minimum amount  of  any  is  resources.  the s e t of r e s o u r c e s  s e c o n d a r y s t o r a g e , and  task system then  of  resource  assumed t h e r e s o u r c e s  is  t h e maximum, o v e r  amount r e q u i r e d by any schedule  exists.  schedule  given  scheduling The  general  scheduling  resources  task  system,  a  set  behavior.  system.  resources  best and  a  The  structure  may  be  with primary  e i t h e r case,  of  i n terms  the  general  i s the o p e r a t i o n a l precedence c o n s t r a i n t s Further  structure  is  imposed  by  of t h e t a s k  s t o r a g e d e v i c e s as a s e t o f r e s o u r c e s ,  s e c o n d a r y s t o r a g e may  subdivided storage  into  being  primary  the  faster  be c o m p r i s e d o f d i s k and  and  the  system. the  set  secondary  of t h e two. tape  The  d r i v e s . In  t h e r e a r e d i f f e r e n c e s w h i c h impose c o n s t r a i n t s on  of t h e  resource  of  storage  space.  b e t w e e n t h e members of a s e t of r e s o u r c e s of the g e n e r a l The  of  valid  the  be c o n s i d e r e d  which are used f o r the e x e c u t i o n  of r e s o u r c e s  t h e use  s i n g l e t a s k . I t i s assumed t h a t a  s c h e d u l i n g p r o b l e m may  and  consider  storage  a l l t a s k s , of t h e minimum  s c o p e of t h e p r o b l e m i s t o f i n d  problem  of the t a s k  we  a  sufficient  strategy.  of s t r u c t u r e  If  The  are  total  scheduling behavior  add  These  relations  to the s t r u c t u r e  problem. of  a  s y s t e m i s c h a r a c t e r i s e d by  a  3  s t a t e space. possible  The  transitions  actions  which  may  Suppose t h a t a p a r t i c u l a r of  the  system.  As  between occur  behavior  the  the  in  a  states  particular  i s i m p o s e d on  system p r o g r e s s e s  are the  the  general  scheduling  executed  schedule  and  the  strategy  determines  f o l l o w e d . Hence, t h e s c h e d u l i n g the g e n e r a l The Petri  objective  of  and  present  i n the resources.  to  this  be e v a l u a t e d  of  states.  The  sequence of s t a t e s i s  strategy i s the  thesis  behavior  of  i s t h e development of a  a means o f  studying  nets have t h e a b i l i t y  structure  the behavior  sequence  arising  Petri  nets  from  general  t o model  from the precedence r e l a t i o n  system  describe  the  are to  problem.  problems. P e t r i  structure arising  the tasks which  which  net formulation t o provide  scheduling the  scheduling  of  tasks which a r e c u r r e n t l y executing. A  in this description i s a  scheduling  terms  p r o b l e m , t h e s t a t e s a r e d e f i n e d by t h e  t a s k s w h i c h have c o m p l e t e d e x e c u t i o n , be  actions  through the state  space, a c e r t a i n sequence of s t a t e s i s f o l l o w e d . I n the  state.  both  of the task  the r e l a t i o n s h i p s  a l s o have t h e a b i l i t y  to  o f t h e s y s t e m . The s c h e d u l i n g s t r a t e g i e s  a r e m o d e l e d by m o d i f i c a t i o n s t o t h e P e t r i n e t  analysis. I n an e a r l y p a p e r by S h a p i r o are  applied  to  The  net  [84],  Petri  nets  a s e q u e n c i n g p r o b l e m . The m a c h i n e c o d e f o r a  FORTRAN D O - l o o p e x e c u t i n g Petri  and S a i n t  on a CDC 6600 i s o p t i m i s e d  using  a  model o f t h e DO l o o p a n d t h e h a r d w a r e c o n s t r a i n t s .  m o d e l i n g w h i c h was p r e s e n t e d  i s a t a much l o w e r  level  than  4  is  intended  The  by  the P e t r i  net  f o r m u l a t i o n t o be p r e s e n t e d  method of o p t i m i z a t i o n i s e x e c u t i o n  solution  which  is  at  or  of  the  near a t h e o r e t i c a l  net  here.  until  a  optimal  one  is  context  uses a  found. A s e c o n d use restricted [92,  of P e t r i  c l a s s of P e t r i  9 3 ] . To  resolution.  determine the best  this  presented  the  is  here.  not  1.2  O v e r v i e w of  the  C h a p t e r 2 i s an  nets  nets,  are  Chapter  optimization  conflicts  i s generated  then  evaluated  aim  is  of  through  the  to In  exhaustive  formulation  Petri a t an  presented  to  in detail  be  after  in  nets.  The  basic  informal l e v e l .  The  two  the  sections,  the b e h a v i o r a l a n a y l s i s . Three c l a s s e s  marked g r a p h s , t i m e d introduced  relevant  for  formulation.  is  of  which  net  is  i n t r o d u c t i o n to  a n a l y s i s and  nets, are  model  Thesis  structural  Petri  net  p r o p e r t i e s are d i s c u s s s e d  a n a l y s i s of P e t r i  Petri  cannot  Both approaches are discussed  i n t r o d u c t i o n of t h e  and  Each  the  the  ideas  which  manner i n w h i c h t o r e s o l v e t h e c o n f l i c t .  approaches  searches;  nets  in a scheduling  resolve a c o n f l i c t , a Petri  each p o s s i b l e  both  nets  with  Petri  emphasis  nets  on  t o t h e d e v e l o p m e n t of t h e  the  and  coloured  properties  formulation  in  3.  Chapter formulation  3 d e a l s w i t h the  definition  of  scheduling  the  general  of  the  Petri  p r o b l e m . The  net  general  5  scheduling  model  presented.  The  separated of  the  upon  which  definition  into  two l o g i c a l  Petri  net  model  Secondly, the modeling s t r a t e g y by t h e P e t r i formulation nets  is  of  the of  formulation  the  Petri  the  the  construction  formulation  i s discussed.  behavior  in detail  is  the  of  the  net a n a l y s i s i s presented.  compared  based  net formulation i s  sections. First, of  is  scheduling  The P e t r i  to previous  uses of  net Petri  for scheduling. Chapter 4 presents  problem  to  the a n a l y s i s of a s p e c i f i c  d e m o n s t r a t e t h e u s e of t h e P e t r i  The p r o b l e m w h i c h i s a n a l y z e d processors  of d i f f e r e n t  the h e u r i s t i c s Chapter conclusions.  net f o r m u l a t i o n .  i s t h e use o f l i s t  speeds. R e s u l t s of the  and a d i s c u s s i o n o f t h e r e s u l t s 5  is  a  scheduling  for  further  on  comparison  of  i s presented.  summary o f t h e s i g n i f i c a n t  Suggestions  scheduling  research  results  and  are  also  and t h e  formal  included. Appendix A c o n t a i n s notation level  for  in this  the  terms  thesis.  the formal d e f i n i t i o n s which  are discussed  a t an  informal  6  CHAPTER 2 PETRI NETS  A Petri systems.  net i s a formal  Petri  nets  model f o r t h e  i s an i m p o r t a n t  system. In these s i t u a t i o n s , the P e t r i  graphical increase  2.1 B a s i c A and  nets  r e p r e s e n t a t i o n . The P e t r i  provide  a  natural  net i s e a s i l y  simple  extended  t o model d i f f e r e n t c o n c u r r e n t  to  systems.  Concepts and Ideas  Petri  n e t i s a p a i r , <P,T>, where P i s a s e t o f p l a c e s  T i s a s e t of t r a n s i t i o n s  conceptualizing  a  Petri  bipartite  shows  of a s i m p l e  the  graph  appears i n Figure  [53], A  net  representation, a  is  in  directed  convenient  graph.  nodes,  circles  and  Figure  n e t whose f o r m a l  2 . 1 ( b ) . The f o r m a l  of  2.1(a)  representation  representation  rectangles,  means  terms of i t s g r a p h i c a l  i n A p p e n d i x A. I n t h e g r a p h i c a l r e p r e s e n t a t i o n , of  aspect of the  f o r the system which i s r e f l e c t e d i n a  its ability  of  a r e u s e f u l f o r t h e modeling of systems i n  which the concurrency of a c t i o n s  representation  representation  i s defined  t h e two  represent  types  places  and  are  the  transitions, respectively. The  structural  relationships  between  properties the  places  of  the  net  and t h e t r a n s i t i o n s of t h e  n e t . The r e l a t i o n s h i p s a r e t h e d i r e c t e d e d g e s i n t h e g r a p h i c a l representation  of t h e n e t . A p l a c e  which i s  connected  by  an  P4  P6  P3  P5  (a) G r a p h i c a l  Representation  P={P1 P2,P3 P4,P5,P6} r  r  T={T1,T2,T3,T4} TI : P1 -> P2 T2:  P2+P4  T3:  P3+P5 -> P4+P6  T4:  P6 * P5  (b) F o r m a l  Figure  P1+P-3  Representation  2.1: A s i m p l e  P e t r i net  8  edge f r o m i t s e l f  to a t r a n s i t i o n , i s s a i d  to that t r a n s i t i o n . A place a  transition  transition. of  to i t s e l f  Similarily,  i n p u t s and  an  output  places  Consider program.  the  shown  of  the  The  1  place  P2  and  P4  a  P5  are  the  flowchart  represents  then,  the  flowchart  the marker t r a v e r s e s program are  graphical representation 2.2.  marker  as  or  net  flowchart  held  of.  as  the  markers i n  i n the p l a c e s  of  is a dot ,  as  1  is a triple,  <P,T,m>,  i s a d i s t r i b u t i o n of t o k e n s i n  in  the  the  a different  flowchart  s t a t e of t h e  dynamic  by  the  execution  of a t o k e n  firing  in  state  analogy,  the  computer program.  properties  t h e movement o f t o k e n s  the  the  Each marking r e p r e s e n t s  i n d i c a t e s the  behavioral  the  e x e c u t e d . The  A marked P e t r i net  just  computer  s e c t i o n s of t h e p r o g r a m . I f  c a l l e d tokens which are  of a n e t .  is  input  of  are  through  Places  that terms  structure  c h a r a c t e r i z e d by move  2.1(a),  in  of  P e t r i net;  flowchart  described  flowchart  in Figure  places  be  from  of  the  where m i s a m a r k i n g . A m a r k i n g the  output place  In F i g u r e  between the d i f f e r e n t  n e t . The  may  edge  T2.  s e c t i o n s of t h e  a P e t r i net  an  place  of  program,  different  t o be  transitions  a m a r k e r i s u s e d t o t r a c e on the  input  the analogy  The  relationship  i s said  of t r a n s i t i o n T4.  to t r a n s i t i o n  an  w h i c h i s c o n n e c t e d by an  outputs to places.  place  t o be  of the  of t h e  the net.  net  are  Tokens  transitions.  A  If a place holds several tokens i t i s convenient to i n d i c a t e t h e number o f t o k e n s by t h e number r a t h e r than a number of dots.  9  F i g u r e 2.2: A m a r k e d P e t r i  net  10  t r a n s i t i o n may under  i f i t i s enabled i n  t h e assumed f i r i n g  transition of  fire  its  rules.  the  current  In the s i m p l e s t  i s e n a b l e d when t h e r e i s a t l e a s t  input  places.  which are assigned to assigned  to  places  d e t e r m i n i n g whether  are  and  taken  a transition  I n F i g u r e 2.2,  one  fires  The  firing  i n s t a n t a n e o u s l y . The 2.3  and  2.4  t h e n T3,  The systems  transition  the f i r i n g  on t h e m a r k e d n e t o f  may  be  of  its  assumed shown  in  output  to occur Figures  of t r a n s i t i o n s , Figure  of a s e q u e n c e  expressed  the t r a n s i t i o n s  system which o c c u r as a r e s u l t  of  2.2.  T4 The  transitions  behavior  of  i n t e r m s of c o n d i t i o n s  and  the  which  be  present  r e p r e s e n t the events i n the  of the c o n d i t i o n s p r e s e n t .  conditions  are  o c c u r r e n c e o f an e v e n t and w h i c h c o n d i t i o n s occurrence  the marking  p l a c e s r e p r e s e n t c o n d i t i o n s w h i c h may  indicate  when  m a r k i n g of the n e t .  t h e s y s t e m and  edges  is  P e t r i n e t m o d e l s t h e s t r u c t u r e and  e v e n t s . The in  a  of a net i s t h e f i r i n g  which  are  by r e m o v i n g a t o k e n f r o m e a c h o f i t s  which i l l u s t r a t e s  initial  weights  which  i s e n a b l e d under  movementof tokens i s  respectively,  execution f r o m an  of  rules,  consideration  i n p u t p l a c e s and d e p o s i t i n g a t o k e n i n t o e a c h places.  a  token i n each  capacities  into  rule,  i s enabled.  t r a n s i t i o n T4  shown. A t r a n s i t i o n  firing  I n more c o m p l e x f i r i n g t h e - edges  marking  necessary result  o f an e v e n t . C o n s i d e r t h e f o l l o w i n g  e v e n t s f o r t h e n e t shown i n F i g u r e  2.1.  The  for  the  from  the  conditions  and  11  F i g u r e 2.4: T3  fired  12  P 1 : consumer  r e a d y t o consume a  unit  P2: consumer r e a d y t o t a k e a u n i t P3: b u f f e r  empty  P4: b u f f e r  full  P5: p r o d u c e r r e a d y t o p r o d u c e  a  from  unit  P6: p r o d u c e r r e a d y t o d e p o s i t a u n i t  T 1 : consumer consumes a  into  buffer  unit  T2: consumer t a k e s a u n i t  from  T3: p r o d u c e r d e p o s i t s a u n i t T4: p r o d u c e r p r o d u c e s a  buffer  buffer  into  buffer  unit  The P e t r i  n e t now m o d e l s t h e i n t e r a c t i o n o f a p r o d u c e r  consumer  through  conditions  a  bounded b u f f e r .  i n the system which are c u r r e n t l y  The e x a m p l e i l l u s t r a t e s the  The m a r k i n g  ability  of  Petri  two  important  and  indicate  ideas  underlying  n e t s t o model systems. F i r s t ,  the net  t r a n s i t i o n s T2 and T4 a r e e n a b l e d u n d e r t h e m a r k i n g . I n the producer-consumer  from t h e b u f f e r These a c t i o n s T2  and  T4  arises  since  change  of  or the  may fire  t r a n s i t i o n are  can  occur concurrently, together.  the f i r i n g state.  s y s t e m , t h e consumer c a n t a k e a  producer  produce  another  2.4, terms unit unit.  which i s modeled i f both  The a b i l i t y  t o model c o n c u r r e n c y  of a t r a n s i t i o n c a u s e s  Only p l a c e s which are input  affected.  the  valid.  c o r r e c t l y models the c o n c u r r e n c y i n the system. In F i g u r e  of  a  only  a  local  or output t o a  13  The s e c o n d imposes  the c o r r e c t  example, In  important idea  i s that  transitions  a  unit  and  since  deposit  correctly  model  system, i t  the  fire.  producer  must  into the buffer before the  f r o m t h e b u f f e r . The t r a n s i t i o n s  are  t h e y a r e c o n n e c t e d by a s e r i e s o f edges  upon  which the tokens t r a v e l . model  net  T4 a n d T3 a r e f i r e d b e f o r e T2 may  consumer can t a k e a u n i t sequenced  Petri  sequencing of events i n the system. In t h e  terms of t h e producer-consumer  produce  the  both  Petri  n e t s t h u s have t h e  ability  to  t h e c o n c u r r e n c y between e v e n t s and t h e  s e q u e n c i n g c o n s t r a i n t s of e v e n t s of t h e system. Consider  the  producer-consumer  addition example  of  a  second  consumer  to  the  shown i n F i g u r e 2.2. The P e t r i n e t  must m o d e l t h e c o n t e n t i o n b e t w e e n t h e c o n s u m e r s when b o t h ready  to  take a u n i t  f r o m t h e b u f f e r . The P e t r i the  additional  net model i s  shown i n F i g u r e  2.5  conditions  e v e n t s of t h e s e c o n d c o n s u m e r . T r a n s i t i o n s  and  where  are  places  are the  and T6 s h a r e a common i n p u t p l a c e , P4, a n d a r e s a i d t o conflict.  Under  b o t h may f i r e . contention structural  the  marking  Hence  for  the  property  in  shown, e i t h e r T2 o r T6 b u t n o t  the  Petri  unit  in  which  be  T2  net the  exists  correctly  buffer. as  a  models  Conflict result  of  the is a the  r e l a t i o n s h i p between r e l a t e d e v e n t s . The b e h a v i o r o f a s y s t e m  i s c h a r a c t e r i z e d by t h e movement  of  tokens i n the P e t r i  the  b e h a v i o r o f t h e s y s t e m c a n be i n f e r r e d  p r o p e r t i e s of t h e P e t r i  net model of t h e system. P r o p e r t i e s of  n e t . Three  such  from t h e b e h a v i o r a l  properties  of  Petri  14  Figure  2.5:  2 consumer - s i n g l e  producer  system  15  n e t s a r e l i v e n e s s , p e r s i s t e n c e and The of  l i v e n e s s p r o p e r t y i s important f o r the d e t e r m i n a t i o n  t h e p r o p e r t i e s of a s y s t e m . A t r a n s i t i o n  exists the  a  marking  transition  marking,  if  stronger  there  all  that  e,  i s that a t r a n s i t i o n  r e a c h a b l e from a l l  i n which the t r a n s i t i o n  is live,  t h e n one  can  other  in m.  The  reach a state  is live i f  markings  The  use  of  the  p r o p e r t i e s of p a r a l l e l  I f the P e t r i  infer  net model  (assuming a c o r r e c t  i n w h i c h no a c t i o n s may  of  determining  liveness  [36,  38,  behavioral property closely  persistence.  A  marked  net  d o e s n o t d i s a b l e any o t h e r  2.5,  firing  of one  subject  related  o f T2 o r T6,  88,  determining 48}  and  for  [ 1 8 , 3 1 , 37,  i s also well  i s persistent  transition the  44,  p r o p e r t i e s of c o n c u r r e n t systems  50, 5 1 , 70, 7 1 , 72, 76, 83, 9 1 , 98, 99] The  for  the  occur.  n e t s has been t h e  property  a  model),  11, 43, 52, 53, 55, 68, 69, 76,  programs  of  i s enabled. A net i s l i v e i f  l i v e n e s s p r o p e r t y of P e t r i  much r e s e a r c h [ 3 , 5, 6,  A  2  t h e s y s t e m has no a c t i o n s w h i c h n e v e r o c c u r and t h a t  system cannot  94].  i n which  e x i s t s a sequence of t r a n s i t i o n s ,  of i t s t r a n s i t i o n s a r e l i v e .  system  there  a  s t a t e m e n t of l i v e n e s s  net  marking  t h r o u g h a sequence of s t a t e s r e s u l t i n g  there e x i s t s a marking the  if  i s r e a c h a b l e from  2  m,,  is live  r e a c h a b l e from the i n i t i a l  i s enabled. A marking, m ,  w h i c h t a k e s m,  of  boundedness.  to  studied.  conflict  i f the f i r i n g  transition.  In  under the m a r k i n g  removes a t o k e n f r o m t h e p l a c e , P4, t h u s d i s a b l i n g  41,  the  is of a  Figure shown, other  16  transition. exist may  Hence, the net  i n the net, then, have  a  conflict  t h e t r a n s i t i o n s T1 common  input  does not  A  d i s a b l e T2.  persistent  consider  the  represent interest, place  Petri  final  boundedness.  firing  of  For  The  tokens  one.  if  Petri  [2,  relevant  Petri 66].  ensures  to  be  resources  for  and  a  is  net,  one  may  places  to  the  F o r most r e a l resources  token  discussed  systems of  is  finite.  c o u n t of t h a t p l a c e i t s places are  A  never  bounded.  i t s p l a c e s a r e bounded by a v a l u e  i n t r o d u c t i o n to  to  the  model  Petri  nets  introduced  of r e s e a r c h c o v e r i n g a  theoretical  i n the B i b l i o g r a p h y 78],  of  of not  also safe.  a p p l i c a t i o n s and  papers  the  nets are a r i c h area  listed  enabling  seen t h a t t h e examples d i s c u s s e d are  T h i s completes the properties  its  shown  of h a r d w a r e [ 8 ,  i n t e r p r e t a t i o n s of  i s s a f e i f a l l of  o n l y bounded but  nets  f o r the r e s o u r c e s .  be  under  a  circuit.  i s bounded i f a l l o f  easily  under the m a r k i n g  design  Petri  t h e amount o f s t o r a g e  I t can  share  persistence property  i n the  to represent  k—bounded  s i n c e they  T2  net  Figure,2.6,  model of a h a r d w a r e c i r c u i t  of  some  storage  is  net  net  property  e x c e e d s k. A n e t  is  o f T1  race hazards e x i s t  The  of  in conflict  firing  d i s a b l e T1.  conflicts  i s p e r s i s t e n t . However, a  e x h i b i t p e r s i s t e n c e . In are  The  p e r s i s t e n t . I f no  i s u s e f u l i n t h e m o d e l i n g and  t h a t no  A  T2  p l a c e . The  m a r k i n g does not nets  the net and  and  i s not  also  in  the  the  i n Chapter wide  topics. A selection  and  and  of  two  3.  range papers survey  17  F i g u r e 2.6: A p e r s i s t e n t P e t r i  net  18  2.2  A n a l y s i s of P e t r i The  a n a l y s i s of  s t r u c t u r a l and analysis  the  Petri  behavioral  i n t o two  modeling, The  Nets  analysis  phases i s  synthesis  of  [ 7 4 ] . The  based  upon  t h e m o d e l and  net  and  the  behavioral  the  restrict  behavioral  the  net.  The  i n t o two  phases:  separation  the  two  operation  s t r u c t u r a l a n a l y s i s d e t e r m i n e s the  p r o p e r t i e s of  and  nets i s separated  static  of  of  the  stages  of  the  properties  a n a l y s i s determines the  structural  analysis  a n a l y s i s to P e t r i  model.  is  of  dynamic used  nets which are  to live  bounded.  2.2.1  Structural Analysis S t r u c t u r a l a n a l y s i s i s b a s e d upon t h e  structures  i n the  characteristic structure effect  of  on  a f f e c t the  matrix  the  net.  the  transition  net  is The  token  j . The  an  behavior nX m  elements of  count  notion  of  s t r u c t u r e s are  of  matrix r,  place  r  that c e r t a i n  the  net.  representing ij '  i  identified  by by  a r e  the the  the  The the net  firing  of  solutions  to r«g<0, r»g>0, f•r<0, and where f and The  g are  f»r>0,  vectors  solutions  to  and r«g^0  "•"  i s a matix  and  multiplication.  t o r»g<0 i d e n t i f y  sets  of  19  t r a n s i t i o n s which  create  or  destroy  tokens.  Consider  the  e x a m p l e shown i n F i g u r e 2.7. g, i s t h e t r a n s p o s e o f a p o s i t i v e integer or  s o l u t i o n t o r«g>0 . Each element  equal  elements integer are  to  zero.  solutions  accumulate solution  T2 and T3 a r e i d e n t i f i e d  o f g,. The  repeatedly  structures  fired,  removed  an  i n p l a c e P4. g to  from  identified  t o r«g>0 a r e c a l l e d  r»g<0.  the  2  by t h e n o n - z e r o  by  the  positive  g e n e r a t o r s . As T2 a n d T3  arbitrary  number  i s t h e t r a n s p o s e of  of a  tokens can non-trivial  T1 and T2 f o r m an a b s o r b e r . I f T1 a n d T2  are repeatedly f i r e d ,  cannot  of g, i s g r e a t e r t h a n  1  an a r b i t r a r y  place  P4.  number  of  tokens  can  I f a generator e x i s t s ,  be b o u n d e d . I f an a b s o r b e r e x i s t s  in  a  net  be  the net  which  is  bounded, t h e n , t h e n e t i s not l i v e [ 8 8 ] , The  solutions  p l a c e s which a f f e c t is a positive  to  f«r<0  and  t h e movement  integer  which a r e i d e n t i f i e d  solution  t o f«r^0  identify  s e t s of  of tokens through the n e t . f ,  t o f»r<0. The p l a c e s P3 a n d  by t h e n o n - z e r o  elements  P4  of f, are c a l l e d  a d e a d l o c k . I f t r a n s i t i o n T3 o r T2 i s f i r e d a t o k e n r e m a i n s i n P4 P3  or  P 3 , r e s p e c t i v e l y . H o w e v e r , i f T1 o r T4 i s f i r e d ,  l o s e s a token which  other  transition.  f  2  i t cannot  r e g a i n by t h e f i r i n g  i s a solution  t o f«r>0 w h i c h  of  to t h e r e s t of the n e t . In g e n e r a l a t r a p c o n s i s t s of  1  the  tokens  i n the t r a p remain  The r e l a t i o n s ^ and > a r e component-wise  any  identifies  P5 a s a t r a p . Once a t o k e n i s p l a c e d i n P5 i t c a n n o t  places;  then,  be r e t u r n several  i n the t r a p unable t o  comparisons.  (a) A P e t r i net  (b) C h a r a c t e r i s t i c  9i=(0,  1 , V,  matrix, T  0)  g =(1,1,0,0) 2  f , = (0,  0, 1 , 1 , 0)  f = ( 0 , 0, 0, 0, 1) 2  (c) S o l u t i o n s  t o r»g, f»r  F i g u r e 2.7: S t r u c t u r a l  analysis  21  circulate net,  i n the rest  then,  the  net  then, the net i s l i v e The count e.  i s not l i v e .  sequence,  a,  r«g=0,  marking  | r i  i n a net,  r e s u l t on t h e  token  transition  is  fired  k^  ).  then, the net e f f e c t  of a f i r i n g  x i s 0. I f t h e n e t e f f e c t  returns  to  itself,  may be e x e c u t e d  that  infinitely  to  be s t r o n g l y  solution  positive  0  to  ,  c,  then,  marking  a  on a  sequence,  many t i m e s on t h e s t a t e  x.  <s,  I f the  t r a n s i t i o n , then, the state  x is  non-terminating. A P e t r i net i s strongly  i f t h e r e i s such a s t a t e  integer,  A net which  is  sequence,  i s , x=<r^>x. The f i r i n g  sequence c o n t a i n s each  non-terminating the  a  where =  said  exists  in  of a sequence of t r a n s i t i o n s ,  each  g (k),k2,...,ki,...,k  firing  exists  i f i t i s n o t bounded [ 8 8 ] .  a p l a c e by t h e f i r i n g  In the f i r i n g  If  I f a trap  dot product, r * g , i s the o v e r a l l  of  times,  of t h e n e t . I f a deadlock  f«r=0  and  each  i n the net  [53]. If  of the elements  of f i s a  then, the net i s both a deadlock  i s a single  trap  and a s i n g l e  deadlock  and a is  trap.  bounded  [88]. A  special  c a s e e x i s t s when t h e n e t i s b o t h s t r o n g l y  t e r m i n a t i n g a n d b o u n d e d . The n e t i s s a i d  to  The  f o r a n e t t o be w e l l -  n e c e s s a r y and s u f f i c i e n t c o n d i t i o n s  be  non-  well-behaved.  b e h a v e d a r e g i v e n by Theorem 1 [ 5 3 ] A GPN i s w e l l - b e h a v e d i f a n d o n l y i f r«g=0 a n d f » r = 0 have p o s i t i v e i n t e g e r s o l u t i o n s f o r t h e v a r i a b l e s f and g. r i s t h e c h a r a c t e r i s t i c m a t r i x .  22  A  well-behaved  net  precludes  t r a n s i e n t b e h a v i o r . The the  Behavioral The  well-behavedness  marking.  The  analysis  possible  of a P e t r i  states  net i s a s y s t e m a t i c  reachable  tree  is called  b e h a v i o r a l p r o p e r t i e s of l i v e n e s s ,  from  reachability  tree  l a b e l e d w i t h a marking  and  The  The  the r e a c h a b i l i t y b o u n d e d n e s s and  label  the  edges  are  which  are  persistence  tree. nodes a r e  labeled  with  marking.  of the t r e e , g e n e r a t e a l l of  the  reachable  from  the  marking  m a r k i n g , c r e a t e a new  node and  i t w i t h t h a t m a r k i n g . Draw an edge f r o m t h e l e a f  fired  to  marking enabled, already  create  the  with  marking  i s a dead m a r k i n g , t h a t then  mark  it  as  a  the  transition  labeling  t h e new  i s , .there a r e dead  node. R e p e a t  t o each  which  was  node. I f t h e  no  transitions  marking. I f the marking  l a b e l s a n o t h e r node i n t h e t r e e , t h e n , mark  a s an e x i s t i n g  a  root  directly  t h e edge  The  t r e e begins w i t h the  t h e l e a f . F o r e a c h new  node and l a b e l  the  tree.  i s a d i r e c t e d g r a p h . The  of t h e r e a c h a b i l i t y  n o d e . F o r e a c h unmarked l e a f  labeling  initial  r o o t node i s l a b e l e d w i t h t h e i n i t i a l  generation  markings  the  r e a c h a b l e from  d e c i d e d by e x a m i n a t i o n o f t h e r e a c h a b i l i t y  transition.  restrict  s y s t e m a t i c s e a r c h i s p e r f o r m e d by t h e g e n e r a t i o n  m a r k i n g . The  The  to  bounded.  a t r e e r e p r e s e n t i n g a l l of the m a r k i n g s  initial  new  i s used  with  Analysis  behavioral  s e a r c h of t h e  are  m o d e l i n g of systems  a n a l y s i s t o n e t s w h i c h a r e l i v e and  2.2.2  of  the  the above p r o c e s s u n t i l  the  node  a l l of t h e  23  l e a v e s h a v e been marked and no new It finite  can  easily  be  seen  tree, since a f i n i t e  nodes c a n be g e n e r a t e d .  t h a t a bounded n e t g e n e r a t e s a  number  of  states  However, i f a p l a c e i s n o t bounded t h e r e e x i s t markings  for  are  possible.  infinitely  t h e n e t . A s y m b o l , o, i s i n t r o d u c e d t o  places with a r b i t r a r i l y  many t o k e n s .  The  behavior  many  indicate u  of  is  d e f i n e d t o be u+a=o u~a = u  a<u, where a i s a n a t u r a l number, o may coefficient and  to  3, A p p e n d i x  tree,  if  x>y,  a  A ) . For a  marking,  initial  transition is  created  marking  f o r w h i c h x^>y^  of  n e t and  the  net  enabled i n the i n i t i a l  P1+P4  P1+P2+P3>P1+P3  in  the  comparison, X i > y  shows a P e t r i  marking  by  x,  reachability  where y i s any m a r k i n g on a p a t h f r o m t h e  u r e p l a c e s the c o e f f i c i e n t s  The  the  firing  yielding and  the  P2>0P2,  its is  i s true. reachability  P1+P3. T3  m a r k i n g . The  hence,  firing  of  T1  creates  i s the  fires  P1+P2+P3. the  tree.  marking  o f T3. T r a n s i t i o n T2 marking  root  1<i<n, t h e n ,  i f  only P1+P4  on  Note  coefficient  becomes o. T r a n s i t i o n s T1 and T3 a r e e n a b l e d u n d e r The  infinity  p l a c e i n the m a r k i n g , x (see D e f i n i t i o n s 1  node and > i s a c o m p o n e n t - w i s e  F i g u r e 2.8  be t h o u g h o f as an  the that  of  P2  P1+oP2+P3.  t h e m a r k i n g P1+oP2, s i n c e  u-1=o.  S i n c e t h e r e a r e no t r a n s i t i o n s w h i c h a r e e n a b l e d u n d e r  P1+uP2,  the  in  node i s m a r k e d a s a d e a d m a r k i n g . The  firing  o f T3  the  (a)  a P e t r i net  (P1+oP2+P3)*  where * i n d i c a t e s a dead s t a t e (b) Figure  an e x i s t i n g  state  Reachability  2.8: B e h a v i o r a l  a n d **  Tree analysis  indicates  25  m a r k i n g P1+uP2+P3 c r e a t e s t h e m a r k i n g P1+oP2+P4. T r a n s i t i o n T2 is  fired  to  c r e a t e t h e m a r k i n g P1+uP2+P3. S i n c e  l a b e l s a node, t h e l e a f generation either  existing  node.  The  of the t r e e i s c o m p l e t e s i n c e a l l of the l e a v e s  p r o p e r t i e s of the net a r e d e c i d e d  reachability  m a r k e d a s a dead  markings  tree.  The  s t a t e . Thus,  by  inspection  t r e e o f F i g u r e 2 . 8 ( b ) has a the net i s not l i v e .  u for a coefficient,  t h e n e t i s n o t bounded. The  Since  p e r s i s t e n c e s i n c e the net i s not Figure of F i g u r e  2.9  2.6.  the  is  not  t r e e f o r the P e t r i  net  t r e e c o n t a i n s no l e a v e s w h i c h a r e m a r k e d a s  dead m a r k i n g s , hence, place  use  live.  shows t h e r e a c h a b i l i t y  The  net  of leaf  c o n t a i n s nodes w h i c h a r e l a b e l e d w i t h m a r k i n g s w h i c h  each  are  generated.  The  tree  an  d e a d m a r k i n g s o r e x i s t i n g m a r k i n g s and no new  c a n be  the  i s marked as  the marking  the net i s l i v e .  i n each of the markings  The  coefficients  for  i s 1, t h e r e f o r e t h e n e t i s  s a f e . The  n e t i s a l s o p e r s i s t e n t , s i n c e , e a c h node has a t most  a single  sucessor.  2.3  C l a s s e s of P e t r i The  upon  Petri  three  Nets  net model p r e s e n t e d  c l a s s e s of P e t r i  n e t s and c o l o u r e d P e t r i Petri permits  nets  with  a  in  Chapter  3.3  is  n e t s : marked g r a p h s , t i m e d  n e t s . Marked  restricted  graphs  structure.  are The  g e n e r a l c o n d i t i o n s f o r t h e l i v e n e s s and  a  based Petri  class  of  restriction the  safeness  26  •  r  (P1+P2) |  T1  (P3+P4) |  T3  (P3+P1)  j j  T2-  (P2+P4) T3  (P1+P2)* where * i n d i c a t e s an e x i s t i n g  Figure  2.9: R e a c h a b i l i t y  tree  state  f o r net of F i g u r e  2.6  27  of  nets  belonging  n o t i o n of t i m e  to  the  class.  The t i m e d n e t s m o d e l t h e  i n the n e t . Coloured nets a l l o w the modeling  r e s o u r c e a t t r i b u t e s and d y n a m i c h i e r a r c h i e s . The nets  and c o l o u r e d P e t r i  described  i n Chapter  timed  Petri  nets are e x t e n s i o n s to the P e t r i  2.1. The e x t e n s i o n s i n c r e a s e  nets  ability  of  Petri  n e t s t o m o d e l s y s t e m s i n a n a t u r a l a n d compact manner.  2.3.1  Marked Graphs The  class  of  Petri  c r e a t e d by r e s t r i c t i n g the net i s r e s t r i c t e d and  t o be o u t p u t  F i g u r e 2.1  However,  nets  the  known  92,  class  a  to a single t r a n s i t i o n .  single  transition  The e x a m p l e shown i n  S i n c e no c o n f l i c t s a r e  allowed,  s y s t e m s c a n be m o d e l e d w i t h a marked  restrictions  do  allow a simplification  of P e t r i  nets  are a p a r t i c u l a r i l y  graph. of the well-  [ 1 7 , 44, 39, 52, 53, 67, 69, 70,  93, 100] and many r e s u l t s a r e  Petri  1  t o be an i n p u t t o  a n a l y s i s of t h e n e t s . Marked graphs studied  a s marked g r a p h s , i s  t h e s t r u c t u r e o f t h e n e t . E a c h p l a c e of  i s a marked g r a p h .  only deterministic  known  for  this  class  of  nets. Due  to  marked g r a p h ,  the  restricted  nature  of t h e s t r u c t u r e of the  a d i r e c t e d g r a p h , G=<V,E>, where V i s a  set  of  v e r t i c e s and E i s a s e t of e d g e s , may  be u s e d  representation  The s e t s V a n d E a r e t h e  of  a  marked  graph.  as t h e g r a p h i c a l  t r a n s i t i o n s a n d p l a c e s , r e s p e c t i v e l y , o f t h e marked g r a p h .  1  of  A marked g r a p h  The  i s n o t t o be c o n f u s e d w i t h a marked P e t r i n e t .  28  tokens i n t h i s edges is  representation are  o f t h e g r a p h . The  producer-consumer  placed  edge  as  the  The  can  transitions  following  Theorem 2  be  specified  theorems  in Figure  fire. G.  The  The  tokens  liveness  and  2.2  2.10. edge  follow  the  safeness  i n terms of the d i r e c t e d p a t h s .  define these  properties.  [17]  A m a r k i n g i s l i v e i f and o n l y i f t h e t o k e n c o u n t every d i r e c t e d c i r c u i t i s p o s i t i v e . Theorem 3  the  i s e x e c u t e d , t h e t o k e n s move f r o m  d i r e c t e d paths i n the graph, properties  on  model of F i g u r e  shown i n i t s d i r e c t e d g r a p h r e p r e s e n t a t i o n As a m a r k e d g r a p h  to  rectangles  of  [17]  A l i v e m a r k i n g i s s a f e i f and o n l y i f e v e r y edge i s i n a d i r e c t e d c i r c u i t w i t h a t o k e n c o u n t o f 1. In the producer-consumer  e x a m p l e shown  liveness  are  directed  and  safeness  circuits,  T4-P5-T3-P6-T4. of  By  Timed P e t r i In a r e a l  During  this  Figure  easily.  T2-P1-T1-P2-T2,  2.10,  the  There are t h r e e  T2-P3-T3-P4-T2  i n s p e c t i o n , each c i r c u i t  1. H e n c e , t h e m a r k e d g r a p h  2.3.2  verified  in  i s l i v e and  and  has a t o k e n c o u n t  safe.  Nets  system, a c t i o n s o c c u r over a d u r a t i o n of time n e i t h e r  time.  the i n p u t c o n d i t i o n s nor the output  c o n d i t i o n s a r e v a l i d . As d e s c r i b e d a b o v e , been assumed t o o c c u r i n s t a n t a n e o u s l y . The  the t r a n s i t i o n s n o t i o n of  time  have is  29  30  introduced  in  transition places  the  and  the  time  where t r a n s i t i o n  delay  between  by r e m o v i n g t o k e n s  the  transition places  from t h e  completes [ 6 3 , 64,  i l l u t r a t e s how a t i m e d  u n a b l e t o be u s e d t o e n a b l e  transitions  firing  82,  real  87],  by  81,  transition  92, fires  number. is a  Tokens  for a delay  time  i n a p l a c e . The m o d e l i n g o f t h e t i m e  t h i s manner r e q u i r e s a c o m p l e x mechanism  the  input  method o f m o d e l i n g t h e n o t i o n o f t i m e  i n t h e p l a c e s o f t h e n e t [ 1 0 , 7 1 , 73,  i s deposited  the time  T1 h a s a d e l a y o f T,, a p o s i t i v e  An a l t e r n a t i v e  it  a  i n the output  1 0 2 ] . F i g u r e 2.11  delay  of  initiates firing  d e p o s i t i n g tokens 93,  form  are after  delay i n  f o r the execution  of  a timed net. Using  the  ideas  of  methods of m o d e l i n g t i m e transition  T1  of  stepwise  refinements  [ 9 4 ] , t h e two  c a n be shown t o e q u i v a l e n t .  Figure  2.12(a)  with  time  Consider  delay,  r,.  Transition  T1 c a n be s u b s t i t u t e d by two t r a n s i t i o n s ,  T1",  a p l a c e P T 1 , a s shown i n F i g u r e 2 . 1 2 ( b ) . I n t h e n e t  and  of F i g u r e token  is  2 . 1 2 ( b ) , T1' a n d T 1 " o c c u r held  i n p l a c e PT1  now m o d e l e d a s a d e l a y delay  may  be  instantaneously  f o r a time  replaced  enough  time  in  real that  and  r , . The t i m e  by a t r a n s i t i o n  the  delay i s a  w i t h a d e l a y and two  2.13.  A second concept of importance f o r timed In  and  i n a place. S i m i l a r i l y , a place with  p l a c e s a s shown i n F i g u r e  synchrony.  T1'  Petri  s y s t e m s , s e v e r a l a c t i o n s may they  may  be  considered  nets  is  begin  close  to  begin  31  A  B  T1  0  (a) T r a n s i t i o n  Place  T1  A 1  1  r—  0  —  t  t Place  B  1 0 i - J —  T  t + T,  (b) Token c o u n t  Figure  2.11:  of  Firing  p l a c e s A and  of  transition  B  TI  A  T1  B  (a)  O  T1 '  A  PT1  T1 "  (b)  Figure  2.12:  A timed  transition  -O  T1 (a)  T1  A'  '  TA  A"  .(b)..  Figure  2.13:  A timed  transition  33  simultaneously.  If  transition,  in order to c o r r e c t l y  of  then  each  action  is  modeled simulate  t h e a c t i o n s , t h e t r a n s i t i o n s must b e g i n  t i m e . The reduces  n o t i o n of s y n c h r o n o u s the  s t a t e s , one in  which  i n which k  of  separate  the  firing  behavior  a t t h e same  transitions  k t r a n s i t i o n s are enabled  transitions  transition  is fired  in  the  transitions I (f)  of  have  transitions  allowed to f i r e  have  been  may  be  and  fired.  a t a t i m e , t h e r e a r e k!  sequences, there are the  firing  a  also  s i z e o f t h e s t a t e s p a c e of t h e n e t . C o n s i d e r  the  which  as  For  synchronously,  second  If a  single orders  the  intermediate states in been f i r e d .  the  different  fired.  two  firing  which  some  I f the t r a n s i t i o n s  then, a l l of  the  are  intermediate  s t a t e s a r e e l i m i n a t e d . H e n c e , a more compact r e p r e s e n t a t i o n of the s t a t e The  space i s p o s s i b l e . introduction  of  the  notion  of t i m e t o P e t r i  c o m p l i c a t e s t h e d e s c r i p t i o n of t h e s t a t e of a n e t . A m,  of a n e t  net.  At  i s no any  longer s u f f i c i e n t  time,  i n f o r m a t i o n must be at  which  the  descriptor  time  transition  completes  the  transition  to  function,  r.  is  describe firing  t o d e s c r i b e the s t a t e of a may  completing firing  taken  be  is  the net [102].  become e n a b l e d  have not c o m p l e t e d  marking,  firing  and  i n c l u d e i n t h e s t a t e d e s c r i p t i o n . The  convenient  t r a n s i t i o n s may  transitions  and  nets  an  issue  this time  here.  i s the i n s t a n t a f t e r At  begin  its firing.  this firing The  a r e d e s c r i b e d by  time,  A a  other  as a r e s u l t  of  transitions  which  the remaining  time  34  r = {(T ,R )} c TXH i  where in  i s a real positive  the f i r i n g  pair,  the  analysis  behavioral  timed  net.  The  in  the  A  described  in  Chapter  instantaneous labeled  of a t i m e d n e t i s a  of  behavioral  called  the  graph  of  space of  instantaneous descriptors  manner  descriptors,  which  firing.  GRID, r e p r e s e n t s t h e s t a t e  2.2.2.  with a selector,  indicates  tree  graph  same  remaining  of t i m e d P e t r i n e t s d i f f e r s o n l y i n  analysis.  generated  x  The s t a t e  of t h e n o t i o n o f t i m e i s a  instantaneous descriptors,  s- ,  i s the time  ( m , r ) , when a t r a n s i t i o n h a s j u s t c o m p l e t e d  extension,  the  number w h i c h  o f t r a n s i t i o n T±.  Since the modeling  the  +  i  as The  the  reachability  nodes  d^=(m^,r^),  and  where a s e l e c t o r ,  transitions  were  of  the the  s c T * . The fired  is  tree,  GRID  are  edges  are  selector,  t o c r e a t e the  state, d j . S i n c e t o k e n s become a v a i l a b l e the  completion  of t h e f i r i n g  to. enable  of a t r a n s i t i o n , a s t a t e  dead i f t r a n s i t i o n s have y e t t o c o m p l e t e dead firing  if  there  are  no  transitions  firing.  A  t r a n s i t i o n s w h i c h have n o t  a n d t h e r e a r e no t r a n s i t i o n s  enabled.  at  i s not  state  is  completed  35  2.3.3  Coloured P e t r i In a P e t r i  represent  Nets  net  model  resources  in  a t t r i b u t e s w h i c h may  of  a  the  system,  system.  n o t be e a s i l y  the  The  tokens  often  r e s o u r c e s may  have  represented in a Petri  net.  Many a u t h o r s h a v e a d d r e s s e d  this  problem  attributes  [21,  32, 38, 71, 73, 83, 98,  to  the  tokens  by  1 0 1 ] , C o l o u r e d t o k e n s a r e a c o n v e n i e n t method tokens with a t t r i b u t e s infinite has an  number  of  Petri  the  [79].  n e t . The  The  net  with  equivalent  involves a duplication colour  101]. Except  of c o l o u r s , a P e t r i  equivalent  construction  [38, 83,  of  of  the 99,  visualizing  i n the case of  an  net w i t h c o l o u r e d tokens uncoloured  tokens.  The  net w i t h o u t c o l o u r e d tokens  transitions  construction  assigning  and  results  places  for  each  i n a l a r g e and  complex  use o f c o l o u r e d t o k e n s p r o v i d e s a n a t u r a l and  compact  representation. B e y o n d t h e s i m p l e use o f a t t r i b u t e s , partial  order  on  the i m p o s i t i o n of  the c o l o u r s a l l o w s the modeling of  h i e r a r c h i e s . C o n s i d e r t h e e x a m p l e shown i n F i g u r e The  producers,  Pi,  and  P i  c o r r e s p o n d i n g b u f f e r , B-J-. The units  from  buffers,  interact with their capacity PT T has Consumer  one.  B,  2  2  lowest p r i o r i t y  a  C,  units and  The  consumers of  b y producer a l l  by p r o d u c e r P priority  the  consume  2  through a channel  on t h e c h a n n e l o v e r  on t h e c h a n n e l .  [38].  into C  t a k i n g a u n i t produced  u n i t produced  priorty  2.14  r e s p e c t i v e l y . The  corresponding buffer  Consumer C,  taking  , deposit  consumers,  and B ,  the h i g h e s t p r i o r i t y C  2  a  is  2 2  a  others. has  the  dynamic  36  F i g u r e 2.14:  A producer-consumer  system  37  priority  since  u n i t s present The system order The  on  i n the  coloured of  on  the  of  the  net  model  the  output  e d g e s of t h e  under  2.15. of  c o m p a r a b l e and  partial  Figure  2.15.  o u t p u t p l a c e . The  The  colour  tokens  shown. T o k e n s n o t  c a n n o t be  the  labels  t h e minimum  transition.  order  The  t r a n s i t i o n s are  t r a n s i t i o n s are  the p a r t i a l  not  the  producer-consumer  bottom  i n the  used to enable the  by a p a t h a r e  the  e d g e s of t h e  input  compared  of  i s shown a t t h e  token deposited  be  c o n s u m e r s d e p e n d s on  i s shown i n F i g u r e  the  w h i c h may  of t h e  buffers.  2.14  colours on  priority  Petri  Figure  labels  colour  the  are  connected  u s e d f o r an  edge  so  labeled. The  priority  c o l o u r of  the  of a t r a n s i t i o n  tokens  which  transition  at that point  P7 c o n t a i n s  a t o k e n of c o l o u r  colour priority higher  C .  Both  2 2  T5  o r T6  T6  execution and  1 2  are  t h a n t h e minimum e n a b l i n g  may  fire  partial  order.  colour C  l 1 f  transition.  P8  since C , 2  One  then,  and  1 2  can T5  has  and  dynamic p r i o r i t y  hierarchy  P8  to  of  the net.  e n a b l e d but  colour  C  see  Petri  are  1 2  that  a  T5  of  of T6,  specified.  u s e d t o model r e e n t r e n c y  the  Suppose  token  has T5,  a  C ,  is  I f P7  has  1 2  C . 2 2  i f P7  has  C 1, 2  firing  correctly The  coloured  a  of  higher  either  i n c o m p a r a b l e under  over the net  minimum  enable  contains  colour  the  a t o k e n of c o l o u r  priority  coloured  a l s o be  has  easily  The  may  C  available  s i n c e t h e minimum e n a b l i n g  a t o k e n of c o l o u r C T5  are  i n the  and  i s d e t e r m i n e d by  token  o f any models Petri  "in computer s o f t w a r e  the of  other the nets [38,  (Pi  1)  (Pia)  (Pai)  Figure  2.15:  A coloured  Petri  net  39  101  3.  A the are  further  abstraction  introduction similar  of t h e c o l o u r e d P e t r i net model i s  o f t r a n s i t i o n schemes [ 3 2 ,  98].  Transitions  i f t h e y a r e c o n n e c t e d t o t h e same p l a c e s i n t h e  same manner e x c e p t f o r t h e l a b e l s  on t h e c o n n e c t i n g e d g e s .  example  i s shown i n F i g u r e 2.16. The  two  of  similar  transitions  transition  transitions  may be t h o u g h t  shown  in  to  the  two  instances  of  F i g u r e 2.17. A t r a n s i t i o n scheme may  thought of as a mapping of elements of  be  o f P* o n t o o t h e r  An  the be  elements  P*. T h u s , t r a n s i t i o n schemes a l l o w a c o l o u r e d n e t t o r e t a i n natural  r e p r e s e n t a t i o n of a  system.  F i g u r e 2.16:  Similar  transitions  p  Q  R  •  •  e  •  ®  •  F i g u r e 2.17:  A transition  scheme  41  CHAPTER 3 THE PETRI NET FORMULATION A  scheduling  resources of  problem i s comprised of a task  f o r i t s execution  tasks. A Petri  of t h e t a s k  system and t h e s t r u c t u r e  of t h e s c h e d u l i n g differs to  scheduling  26,  27,  the  the s t r u c t u r e  resources.  n e t s a r e used t o model t h e b e h a v i o r  from p r e v i o u s  Petri-net-based  Scheduling  general  Model  scheduling  model  f r o m a more c o n v e n t i o n a l  presented  treatment  here  as  j u s t another  r e s o u r c e . The r e a s o n  the P e t r i  resource  o f t h e model  physical  resource  [16,  f o r the treatment  of  resources  be  executed.  In  set  of p r o c e s s o r s .  to  the  processors  as  i s demonstrated during the c o n s t r u c t i o n of  scheduling  resource  are  and n o t as a s p e c i a l  n e t m o d e l . The s c h e d u l i n g p r o b l e m s  the g e n e r a l The  differs  2 8 ] . The f o r m a l i z a t i o n f o r t h e model i s p r e s e n t e d i n  considered  another  here  approaches  A p p e n d i x A. The m a i n d i f f e r e n c e i s t h a t t h e p r o c e s s o r s be  The  problems.  3.1 The G e n e r a l  slightly  of  scheduling  s t r a t e g y . The a p p r o a c h w h i c h i s d e f i n e d  significantly  The  and a s t r a t e g y f o r t h e  net i s used here t o f o r m u l a t e  t o o l s of a n a l y s i s of P e t r i  system, the  of  are  drawn  from  model. the  general  s c h e d u l i n g model a r e a n y  w h i c h a t a s k may r e q u i r e i n o r d e r general, the resources A d d i t i o n a l resources  for i t to  i n c l u d e a t l e a s t one  may r e p r e s e n t  primary  42  or  secondary  libraries. units  of d i f f e r e n t  the  functionality,  several  t o be a s i n g l e  type It  task  cardinality  system  of t h e  executed  specify  subroutine  convenient  of  general  The  data  I f T^<Tj, t h e n ,  execution.  terms  The  g r a p h w i t h no  an  rXr  s e t , ^7,  between  matrix,  i s assumed  the  o r d e r , <,  on  any  graph  tasks.  The  the  tasks.  before  t a s k Tj by  a  directed  of e d g e s w h i c h  is  o p e r a t i o n s on  to  constraints  i s ' represented  g i v e n as a l i s t  i n g e n e r a l . Note t h a t i f the  is  model i s  t r a n s i t i v e e d g e s . The  g r a p h i s assumed t o be  of  unit  where r i s t h e  precedence  order  the  task.  must c o m p l e t e e x e c u t i o n partial  of  consider  r  operational  be  units  scheduling  2  dependencies  t a s k T^  directed acyclic  is 0(r)  to  ={T, , T , . . . , T } ,  s e t . E a c h t a s k of t h e  once.  the  acyclic  each c o n t a i n  with  be a q u i r e d by a  the  speed.  l i b r a r i e s may  resource  precedence c o n s t r a i n t s are a p a r t i a l  begins  units, speed or  t o be a v a i l a b l e i n d i s c r e t e u n i t s , where a  d e f i n e d on a s e t of t a s k s ,  be  subroutine  identical  l i b r a r i e s may  of  is  s m a l l e s t amount w h i c h can The  or  u n i t s of d i f f e r e n t  subroutine  functionality.  resources  contain  s e t s of s u b r o u t i n e s . The  considered varing  may  devices  of u n i t s of v a r y i n g f u n c t i o n a l i t y a n d / o r  example,  different  input/ouput  A s e t of r e s o u r c e s  a combination For  storage,  specified  in  the m a t r i x  are  0(r ). 2  Each task of  time.  times.  T^->0  An  i n the nXr  set,  matrix,  i s the e x e c u t i o n  , i s executed  in a finite  {T^J}, i s the m a t r i x time  of t a s k  j on  of  amount  execution  processor  i .  43  The  equality  i s i n t r o d u c e d s i n c e two  t h e c o n s t r u c t i o n of t h e P e t r i u n a b l e t o be Each t a s k  consists  system i s  shown  of t e n t a s k s , T1  represents  a t a s k . The  the e x e c u t i o n  graph i n d i c a t e that data d i r e c t i o n of the The  for The  each  require  resource  specified  It  whose  of  The  task  E a c h node i n t h e  set graph  the  task  d i r e c t e d edges of  to  execute.  =[R (Tj), 1  the the  The  2  s  of  resources. resource  of t a s k T j . I t i s assumed t h a t  any  assumed  resources  resource  R (Tj),..., R (Tj)]  t h e amount  task  may  c o n f i g u r a t i o n . The  is  resource  separate  resources  f o r t h e d u r a t i o n of  any  The  i s t r a n s f e r r e d between t a s k s and  s p e c i f i e s the  r e q u i r e s more r e s o u r c e s release  T10.  3.1.  of t h e t a s k . The  i n the d i s c r e t e u n i t s i n  available. resource  Figure  through  f o r the e x e c u t i o n  maximum r e q u i r e m e n t initial  in  infinite.  processor.  j , where s i s t h e number of s e t s of  component R ^ ( T j )  required  is  on a t l e a s t one  s p e c i f i e d by (f^  are task  T—  is  transfer.  tasks  requirements  j , then,  l a b e l s of t h e nodes i n d i c a t e  time  used i n  f o r m u l a t i o n . I f a t a s k T^  on a p r o c e s s o r  i s assumed t o e x e c u t e  A task  and  executed  net  dummy t a s k s a r e  satisfied  resource which  by  the  requirements  the  the  are  resources  are  t h a t a t a s k r e q u i r e s an amount o f i t s e x e c u t i o n . The  d u r i n g the until  requirements  be  i  it are  execution  task  nor  neither  does the  completes execution. such  may  be  task Tasks  modeled  as  tasks. c l a s s of s c h e d u l i n g  s t r a t e g i e s t o be c o n s i d e r e d  here  44  T9/2  T10/1  Task/execution  Figure  3.1:  Task  system  time  \%J,  <,{r )) i  45  is  restricted  to  strategies  Nonpreemptive s c h e d u l i n g being  executed  begins  execution,  performance t i m e , w, task  interruption,  i t runs to completion used  which i s the time . The  to execute  optimal execution  3.2  The  as a r a t i o ,  Petri  The  Net  Petri  as a t i m e d - c o l o u r e d  two  of  phases.  the  between  resources.  The  scheduling  p r o b l e m . The  resources. to is  The  marking.  The  time  the  execution  i s d e n o t e d by w*. a  given  problem  the The is  First, Petri  tasks  phase  the  the s c h e d u l i n g  the  s c h e d u l i n g model i s  n e t . The  Petri  problem,  and  net  models  the  data  the p r o p e r t i e s of  models  behavior  scheduling  scheduling problem i s  scheduling  the  second  by  stopping.  a l l of t h e t a s k s of  the  of the  behavior  of  the the  scheduling problem i s  s t r a t e g y and  the  initial  set  of  s t r a t e g y i s m o d e l e d by m o d i f i c a t i o n s  t h e b e h a v i o r a l a n a l y s i s of t h e P e t r i generated  without  based approach t o the  formulated  d e t e r m i n e d by  task  w/w*.  into  relationships  i s , once a  Formulation  net  structure  tasks  that  s t r a t e g y on  separated  the  nonpreemptive.  here i s to minimise  performance of a s c h e d u l i n g expressed  are  s t r a t e g i e s a r e c h a r a c t e r i z e d by  without  criteria  set  which  execution  of  n e t . Hence, a the  net  f o r an  schedule initial  46  3.2.1  The C o n s t r u c t i o n  The P e t r i the  use  of  derived  net  model  transition  from t h e  coloured  of  tokens  time, of  the  the  the  for  execution  net  algorithm  required  shown  of  the  task  the  task  the  task  in Figure  of  task  graph.  graph  system.  in  precedence  is  given the  terms  net  the  The data  of  graph d e f i n e s  firing  particular  provides a  set  natural  resources  used  construction  of  the  r e s o u r c e s . The  i n terms of  manipulations  the  node,  of  portion  Petri  the  graph.  a  The i n i t i a l  precedence net  precedence  single  STOP-START  Recall,  a  a marked g r a p h .  to  the  constraints  node  is  first  precedence  edge c o m p l e t e s  marked  a d i r e c t e d graph.  the  with  relation  exit  of  constraints.  model b e g i n s  r e p r e s e n t i n g the  of  of  assigned  The g e n e r a l p r e c e d e n c e  addition  augmented p r e c e d e n c e defined  the  to a s i n g l e - e n t r y  The  system.  both the  execution  s y s t e m and t h e  3.2.  thought  The c o n s t r u c t i o n o f  converted  the  task  an a l g o r i t h m f o r  r e p r e s e n t a t i o n of  the  resources,  is  system.  the  acyclic  task  s y s t e m and f o r t h e  may  directed  structure  Each  time  be  the  with  r e p r e s e n t e d by a t r a n s i t i o n scheme.  the  1 is  net  extended  task  construction graphical  for  net  the  model g i v e n is  c o n t r a i n t s of  t r a n s i t i o n scheme  of  Model  The  The c o l o u r e d - t i m e d P e t r i  Algorithm Petri  is  execution  representation for  times.  a r e u s e d t o model t h e  of  resources.  Net  a coloured Petri  precedence  Each task  instantiation  is  Petri  firing  and p h y s i c a l r e s o u r c e s , system.  the  Hence,  graph the  The nodes  may  the be  augmented and  edges  47  1.  2.  To t h e p r e c e d e n c e g r a p h , "START" and "STOP".  add  two  nodes  labelled  Add a d i r e c t e d edge f r o m t h e START node t o e a c h . node w h i c h has no i n c o m i n g e d g e s e x c e p t t h e STOP node.  3.  Add a d i r e c t e d edge from e a c h node w h i c h has o u t g o i n g e d g e s t o t h e STOP. node.  no  4.  Add a directed edge from t h e STOP node t o START node. L a b e l t h e edge "READY" a n d mark with a s i n g l e uncoloured token.  the it  5.  L a b e l each of  the edges w i t h  6.  L a b e l each of  t h e nodes w i t h a t r a n s i t i o n  7.  Repeat  Steps  8.  Define  a s e t of c o l o u r s ,  9.  Add a place resource.  10.  Add d i r e c t e d e d g e s t o and f r o m each node(task) w h i c h r e q u i r e s t h a t r e s o u r c e and l a b e l t h e e d g e s with Cf.  8-11  f o r each  and  label  11. Mark the place with r e p r e s e n t i n g the i n i t i a l colours,  a place  name. name.  resource.  Ci=(X^,<i). i t with  the  name o f  the  the number of tokens resource c o n d i t i o n s .  12.  D e f i n e a s e t of data tokens.  13.  Define i n the  14.  Define a set of colours for the net, C = V C i ^ C o ^ C d , where C i s the uncoloured token.  a transition graph.  Co( = (X^, <<*),  scheme f o r e a c h  0  Figure  3.2  Algorithm 1  for  the  node(task)  48  are  labeled  acyclic is  for  the  formal  representation.  graph of the precedence  shown  i n Figure  3.1  c o n s t r a i n t s of a  [ 1 6 ] . The p r e c e d e n c e  f r o m t h e t o p t o t h e b o t t o m . The marked Steps  1-6,  is  shown i n F i g u r e  The  directed  task  system  i s assumed  t o be  resulting  from  graph  3.3. The marked g r a p h  retains  t h e n a t u r a l r e p r e s e n t a t i o n o f t h e p r e c e d e n c e c o n s t r a i n t of t h e task  system. The  remainder  resources  of  necessary  the  f o r the execution  is convenient to consider o p e r a t i n g on t h e f o r m a l The r e s o u r c e s marked  construction  deals  with  of the task system. I t  t h i s p o r t i o n of the c o n s t r u c t i o n  are represented  by a p l a c e  i n the P e t r i  w i t h t o k e n s from a c o l o u r s e t . A p l a c e  is  c o n n e c t e d t o and f r o m e a c h t r a n s i t i o n ( t a s k ) w h i c h  is  i s g e n e r a t e d by S t e p s  based  until  the  t i m e and d o e s  execution  l a b e l e d with the colour set Petri  1. The  in  and p r o c e s s o r  is  not  completed.  defined  manner  for  the  release  more  the  The e d g e s a r e resource.  The  resources  situations.  The m o d e l i n g o f t h e p r o c e s s o r s  processors  requires  this  net model a l l o w s the m o d e l i n g of a v a r i e t y of  slightly  place  on t h e a s s u m p t i o n t h a t a t a s k u s e s t h e r e s o u r c e f o r  the d u r a t i o n of i t s e x e c u t i o n resource  1-6 o f A l g o r i t h m  The m o d e l i n g o f t h e r e s o u r c e s  net  i s added t o the  which  resources.  as  r e p r e s e n t a t i o n of the n e t .  net  that  the  flexible  modeling  as  a  of  functionally  [ 5 7 ] . Groups of f u n c t i o n a l l y  resource  dedicated  allows  a  dedicated processors  49  F i g u r e 3 . 3 : The  marked graph a f t e r  Step 6  50  may and  be  modeled  by d i f f e r e n t  p a r t i a l order  i n the net. A c o l o u r  i s d e f i n e d f o r each group a l l o w i n g  m o d e l i n g of v a r i a t i o n A  places  within  t h e g r o u p of  the  c o l o u r set i s d e f i n e d f o r each resource  resource. A p a r t i a l order  reflecting  the r e l a t i o n s h i p s  resources. resources the  The  special  or p r o c e s s o r s ,  resources  are not  case  of  the  p l a c e added i n  t o be  i s d e f i n e d on  between  for  processors.  S t e p 9. A c o l o u r i d e f i n e d f o r e a c h a t t r i b u t e for  set  the  considered  thecolour  attributes  of  i d e n t i c a l resources,  i s m o d e l e d by u n c o l o u r e d  set the  either  tokens.  If  i n t e r c h a n g a b l e , a n u l l p a r t i a l order  is  specified. A t r a n s i t i o n scheme i s d e f i n e d f o r e a c h of  the  net a f t e r  The  t r a n s i t i o n scheme i s t h e  of  the  behavior  transition output for  a l l of t h e r e s o u r c e  a s e t of  conditions.  The  manner t h a t  none  step in  the  input tokens  This corresponds  the e x e c u t i o n  p l a c e s have been a d d e d .  of t h e t r a n s i t i o n ( t a s k ) .  scheme map  tokens.  final  of  the  schemes colours  in  specification  The  i n s t a n c e s of  on  to  to d i f f e r e n t  of t h e t a s k r e s u l t i n g transition  transition(task)  a  set  a of  input conditions different  are  defined  defined  in  output  i n such a  Step  8  are  3.1.  The  redundant. A task  simple  i s t a s k T4  transition  scheme  i s shown i n T a b l e  f r o m t h e e x a m p l e shown i n F i g u r e  s y s t e m i s assumed t o r e q u i r e no a d d i t i o n a l execution  except  t h e p r o c e s s o r s . The  3.1.  resources  processors  The for  a r e of  task the  speeds  C3  co  e  ci  a  C2  (g>  (b)  Figure  P5  P6  3.4:  Colour  sets  P8  Processor  P10  P1 1  O  CO  • •  • • •  • • • • • • • T a b l e 3.1:  C1 C2  T r a n s i t i o n scheme,  T4  2 3 4  52  : b : b = 1 : 2 / 3 : 1 / 2 . The 2  data tokens  3  t o p t o b o t t o m o r d e r may between the  are  i n s t a n t i a t i o n s of t h e t r a n s i t i o n  and  the t r a n s i t i o n  t h e e x a m p l e of  a  speeds.  A  and  3.4(b).  The  the  CO  processors,  partial  of  and  C2  represent  respectively. is  order  to  be  It  of  used  partial  of  different  dedicated.  different  shading  f a s t e s t and  assumed  before a slower  that  o r d e r . The  the  slowest  the  faster  processor,  and  complex  and C3  some  represent  C1  and  CO  s p e e d s . C1  are  of  which  are  processors  general  i s assumed t o  g e n e r a l p u r p o s e p r o c e s s o r s can C3  i n s o f t w a r e , and  reflects  the  final  architecture  the  perform  purpose faster  set  functionally with  special an  array  processors than  CO.  The  t h e f u n c t i o n s of C2 s p e e d . The  partial  between the p r o c e s s o r s b o t h  of  and  order i n the  speed.  example  [45,  be  hence a t a s l o w e r  differences  f u n c t i o n a l i t y and The  the  processors  h a r d w a r e , f o r e x a m p l e , a f l o a t i n g - p o i n t p r o c e s s o r and  different  so  colour  c o l o u r s e t models a group of  speeds  C2  processor.  of  i s d i r e c t e d downwards.  F i g u r e 3 . 4 ( a ) shows a s l i g h t l y more and  First  o r d e r a r e shown i n F i g u r e  the  is  partial  resources.  processors  partial  hierarchy  of c o l o u r s e t s ,  c o l o u r s a r e d e p i c t e d by t h e d i f f e r e n t  tokens.  processor  set  set  The  scheme.  scheme i n m o d e l i n g  consider  colour  uncoloured.  be u s e d t o d e f i n e a p r i o r i t y  T h r e e e x a m p l e s i l l u s t r a t e t h e use orders  a l l  46,  is 97].  a  dynamically The  reconfigurable  a r c h i t e c t u r e t o be  modeled,  CE-  Figure  3.5:  A dynamically  reconfigurable  CE.  architecture  54  shown i n  Figure  3.5,  consists  of  three  16-bit  computing  e l e m e n t s , C E j . Each C E j c o n s i s t s of a p r o c e s s i n g e l e m e n t , a  memory  e l e m e n t , ME£,  computing MS£.  input/output  e l e m e n t s a r e c o n n e c t e d by two  The  connecting  processors  created  reconfiguration The or  and an  elements by  the  i s controlled  element, GEf.  connecting  control  the  computing  processors.  connection,  then,  If  elements,  size  of  by t h e c o n t r o l e l e m e n t ,  a  connecting  The  the  elements.  a r c h i t e c t u r e c a n be r e c o n f i g u r e d i n t o  48-bit  PE^,  The  V.  16-bit, 32-bit  element  allows  t h e two c o m p u t i n g e l e m e n t s a c t as a  single  32-bit processor.  I f the c o n n e c t i n g  allow  a  connection,  t h e two c o m p u t i n g e l e m e n t s a r e c o n s i d e r e d  to  be  then,  two s e p a r a t e  architecture bit  p r o c e s s o r s . The  element does not  a  connecting  elements a l l o w  t o be r e c o n f i g u r e d i n t o c o m b i n a t i o n s of elements.  The  only  restriction  is  16-  the  two  o u t e r m o s t c o m p u t i n g e l e m e n t s c a n n o t be c o n n e c t e d t o f o r m a  32-  bit  computing  the  the  processor. Consider  The  processor  in  Table  between model  r e q u i r e m e n t s and new  3.2.  The  task execution  task execution  times  1 and 5. The m a r k e d g r a p h p o r t i o n remains  processors tokens, computing partial  t h e p r e c e d e n c e c o n s t r a i n t s shown i n F i g u r e  C2  elements, order  of  the  i s added t o t h e marked g r a p h . Three and  C3, CE  1 f  are  used  CE  and  2  on t h e c o l o u r s i s n u l l  to CE , 3  appear  a r e random i n t e g e r s Petri  t h e u n c h a n g e d as shown i n F i g u r e 3.3. A  place  C1,  times  3.1.  represent  net single  coloured the  respectively.  three The  s i n c e the r e l a t i o n s h i p s  Task  No. of b i t s  T  i  T1  16  3  T2  32  3  16  5 •  T4  48  3  T5  32  4  T6  32  5  T7  32  3  T8  16  1  T9  32  2  T10  16  1  T3  •  Table 3.2: Task p r o c e s s o r requirements and e x e c u t i o n times  56  between  the computing  transition  task  the  specification  T3.  The  execution  requirement a c t i n g as  element,  CE , 2  better  to  as a  T3 be  schemes,  task  T3  requires a  16-bit  task  be  task  and  be  a  T4  In  t o be  48-bit  task  the  the  consider  modeling  uncoloured  tokens.  net  Appendix  (see  place  the and  the  The  indicate  modeled  16-bit processors. an  a  32-bit  The  would  weights  T4  which tasks  respectively. to  the  architecture,  elements  by  three  a generalised  Petri  on  the edges  of computing  fashion  the  elements  scheme a p p r o a c h  be  for  of  schemes f o r  of c o r r e c t word w i d t h . in this  processor,  execute task  computing  t h e number  scheme f o r  computing  reconfigurable  net  computing  comprised  3.5,  transition  The  transition  to  and  end  A  the p o s s i b i l i t y of  transition  3.4  three  1).  processor T7  The  computing  the p r i o r i t y i s assumed  3  order  Petri  remaining  a processor  dynamically the  computing  The  or CE -CE .  in  processor.  I f the middle  which allows  2  consider  computing  two  i n which  i n Tables to  as  requiring  processor.  a r e shown  of  T3  in  three  the  configured.  connected  modeling  create  A  of the  to configure  i s e x e c u t e d on  contrast  processor  be  e l e m e n t s , CET-CEJ  a l l  T3,  configured  i n T a b l e 3.3  T7,  any  16-bit processor.  top to bottom.  requires  tasks  transition  16-bit processor,  processor  computing  T7  a  only  i s shown  example  must  the  s a t i s f i e d by  i s assignd  could  32-bit  modeled  of  c o n f i g u r a t i o n would  element  task  of  is  elements  elements  i s more c l e a r l y  schemes.  For  This  a  elements  is  from  the  elements  to  A p a r t i a l net shown  in  of  Figure  Input  Data  Processor  Output  P3  C1  P8+P9  P3  C3  P8+P9  P3  C2  P8+P9  Table  Input  3.3: T r a n s i t i o n  Data  scheme  Processor  f o r t a s k T3  Output  P11+P12  C1+C2  P15  PI1+P12  C2+C3  P15  Table  Input  3.4: T r a n s i t i o n  Data  P5+P6+P7  Table  scheme  Processor " C1+C2+C3  3.5: T r a n s i t i o n  scheme  Data  Data  f o r task  T7  Output  Data  P10+P11  f o r task  T4  F i g u r e 3.6: T a s k s T3 a n d T7  59  3.6. H o w e v e r , special  t h i s a p p r o a c h does not a l l o w t h e m o d e l i n g of t h e  interconnections  between t h e p r o c e s s o r s ,  that  i s , the  end c o m p u t i n g e l e m e n t s , CE, a n d C E ,  c a n n o t be u s e d t o f o r m  32-bit  tokens  3  processor.  The  given  processor  t o an end c o m p u t i n g e l e m e n t , CE, o r step  assigning  Petri  problem  net  model  i s assumed  t o be e x e c u t a b l e  Theorem  a  CE . 3  net model  on f i n i t e  resources.  s t r a t e g y d e p e n d s on t h e s t a t e  The space  is  finite.  net model c o n s t r u c t e d  Theorem  by A l g o r i t h m  4  1 is  bounded. 4  PROOF: F i r s t  i t i s shown t h a t  g r a p h . Then  of t h e r e s o u r c e property  considers  places  1-3 c o n v e r t s  single-entry the  steps  1-6 y i e l d s a l i v e  net the  and  safe  i t i s t o be d e m o n s t r a t e d t h a t t h e a d d i t i o n does not a f f e c t the s t r u c t u r a l  and t h e n e t r e m a i n s  Steps a  A  d e s c r i p t o r s , GRID. The  Algorithm 1 c o n s t r u c t s a l i v e and bounded P e t r i from the a c y c l i c d i r e c t e d graph r e p r e n t a t i o n of p r e c e d e n c e c o n s t r a i n t s of a t a s k s y s t e m .  marked  16-bit  and bounded n e t , s i n c e t h e  and bounded t i m e d n e t  a s s e r t s that the P e t r i and  requiring  n e t h a s ben c o n s t r u c t e d .  t h e n e t , the graph of i n s t a n t a n e o u s  GRID f o r a l i v e  live  Petri  is a live  modeling of the s c h e d u l i n g of  task  model t h e  i n the c o n s t r u c t i o n of the P e t r i  i s the a s s e r t i o n that a v a l i d valid  a  cannot  priority  The f i n a l  to  uncoloured  a  bounded.  an a r b i t r a r y p r e c e d e n c e  node, graphical  liveness  single-exit  node  representation  relation  relation. of  the  If  into one  precedence  60  relation,  an a c y c l i c  graph, then, there e x i s t s a d i r e c t e d  path  f r o m t h e START node t o any node i n t h e g r a p h . I f a node h a d no p r e d e c e s s o r s , t h e n , i t would  be c o n n e c t e d t o t h e START node by  s t e p 2. I f a node h a d p r e d e c e s s o r s , t h e n , one c o u l d t r a c e along  a  directed  path  t o a node w i t h no p r e d e c e s s o r s w h i c h  would  be c o n n e c t e d t o t h e START node by  each  node  is  back  step  2.  Similarily,  on a d i r e c t e d p a t h t o t h e STOP node. T h e r e f o r e  e a c h node a n d e a c h edge i s on a p a t h f r o m t h e  START  node  to  t h e STOP n o d e . S t e p 4 a d d s an edge f r o m t h e STOP node t o t h e START node. The  directed  cicuits least  paths  of  the precedence  g r a p h become d i r e c t e d  i n w h i c h a l l t h e n o d e s a n d a l l o f t h e e d g e s l i e on one  such c i r c u i t .  A l l of t h e d i r e c t e d c i r c u i t s  t h e STOP-START edge s i n c e t h e o r i g i n a l acyclic.  contain  g r a p h was assumed t o be  Now c o n s i d e r t h e g r a p h t o be a m a r k e d g r a p h . When t h e  STOP-START edge i s m a r k e d w i t h a READY t o k e n , circuit  at  has  a  token  every  directed  c o u n t o f 1. H e n c e , t h e n e t i s l i v e a n d  s a f e by Theorems 2 a n d 3. The r e m a i n d e r liveness  of  the  of t h e p r o o f i s based  START  definition  node  net  to  enables  the  of t h e problem," a l l  transitions the  must  the  net. Consider the i n i t i a l  w i t h t h e READY p l a c e marked w i t h s i n g l e the  upon  fire  original  once. state.  s t a t e of the net  t o k e n . The  execution  structural  of  the  firing  of  tasks.  By  t a s k s execute once, hence, a l l Firing  t h e STOP node r e t u r n s t h e  Hence,  r e p e t i t i v e a n d r*g=0 h a s a p o s i t i v e  the  integer  net  is  solution  strongly , where-r  61  is  the c h a r a c t e r i s t i c  a positive  integer  m a t r i x . S i n c e t h e n e t i s s a f e , f»r=0 h a s  solution.  Now c o n s i d e r t h e c h a r a c t e r i s t i c the If  addition  of t h e r e s o u r c e p l a c e s , r and r * , r e s p e c t i v e l y .  r i s an n x m m a t r i x , t h e n ,  identical  m a t r i c e s b e f o r e and a f t e r  to  the  first  the  first  n  rows  of  r' are  n rows o f r . The rows i n r ' f o r t h e  r e s o u r c e p l a c e s a r e rows of z e r o e s . S i n c e t h e edges a r e to  and  from  each  task  w h i c h r e q u i r e s t h e r e s o u r c e and t h e  t a s k s do n o t consume t h e r e s o u r c e s , t h e n , a^j =b^^. a ^ number o f t o k e n s of  transition  from  i by t h e f i r i n g  only  reflect  therefore  the  r»g=0  and  Therefore  first  only  net  result  and  to  count  of a p l a c e ,  f o r the resource places. the  t o the  are  the  equation  r'»g'=0.  Since r'»g=0.  to r'.  equation,  same  are abitrary positive  be a p o s i t i v e  entries r^j  f'»r'=0.  Since  z e r o rows a r e a d d e d t o r t o g e t r ' , t h e n t h e  n elements of f 1  on t h e t o k e n  integer solution  the s o l u t i o n s  only  j . Since the  deposited i n  rows were a d d e d t o r t o g e t r ' , t h e n  g i s a positive  elements of f to  of t r a n s i t i o n  the s o l u t i o n  Consider f»r=0  t h e number o f t o k e n s  =0 f o r t h e e n t r i e s  Consider  i s the  p l a c e i which i s r e q u i r e d f o r the f i r i n g  j . b^-j i s  place  drawn  integer  as  f.  The  remaining  integers f o r the solution  solution.  f ' = ( f - l , f 2 , • • • j f » w 1 r ° 2 i • • • ' °s ^ c  where  a-  x  are arbitrary  of r e s o u r c e p l a c e s added.  positive  i n t e g e r s a n d s i s t h e number  62  Since  f•r'=0  and  r'«g'=0,  therefore hence,  the  the  net  is  places  live,  are  for  set.  any  Since  for for  least  the  net the  the  net  is  the  scheduling initial the  of  system.  READY places. the  task place  of  that  live  the  system.  is  well-behaved  is  and  of  and t h e  The P e t r i  the  in  Petri  net  must from  the  be the  maximum  minimum s e t  initial  may  state  of  fire. is  live  Q.E.D.  the net  Petri is  live  marking  marking  token  resource  place  is  the  conditions  initial one  be marked  t r a n s i t i o n scheme  The i n i t i a l  least  of  e n a b l i n g tokens  presence each  portion  The  resource  e n a b l i n g tokens  resource  A live  of  must  created.  each of  graph  places  c o n s t r u c t i o n of  marking.  at  marked  and b o u n d e d .  model.  The e x e c u t i o n task  state  The  initial  and  places  resource  well-behaved,  completes  the  the  minimum s e t  ensures is  of  hence,  task.  represents  of  a live  This  a live  the  The minimum s e t  tokens  therefore  only  that  single  enabling  state  self-loops,  marked by a t  resource  live.  initial  such a f a s h i o n  colour  w i t h the  structurally  Since the  net  is  for  net  and bounded  for the  a token  i n each of simulates  model  the the  the  net  execution in  the  resource execution  63  3.2.2  M o d e l i n g the B e h a v i o r of a S c h e d u l i n g S t r a t e g y Consider a s c h e d u l i n g problem,  resources is  for  i t s e x e c u t i o n . The  a  task  s t a t e space  a l l of the c o m b i n a t i o n s of completed,  and  unexecuted  and  f o r the  partially  the  problem  completed  t r a n s i t i o n s between t h e s t a t e s  are  the  t a s k s w h i c h began e x e c u t i o n t o l e a d t o t h e n e x t s t a t e .  One  may  c o n s i d e r the s t a t e space  the  nodes  and  t a s k s . The  system  edges  are  r e s p e c t i v e l y . The tasks  t o be a d i r e c t e d g r a p h where  the  s t a t e s and  the s t a t e  p a t h s between t h e i n i t i a l  h a v e been e x e c u t e d and a f i n a l  have been e x e c u t e d r e p r e s e n t p o s s i b l e  state  transitions,  state  i n which  no  i n which a l l t a s k s  schedules for  the  task  system. Since  the  schedules  are  paths i n the s t a t e space,  optimal schedule i s a path with the along  its  length.  To  find  p a t h s between the i n i t i a l  shortest  space  to to  reduce  s t a t e and a f i n a l  achieve  scheduling  the  state  heuristic  may  through the s t a t e space p o r t i o n of t h e s t a t e If Petri space  the  general  be a p p l i e d t o t h e  or  near  be  optimal  state  schedules.  A  thought of as s e l e c t i n g a p a t h  based  on  information  from  only  a  space.  formulation  of  the s c h e d u l i n g model i s a t i m e d  n e t , t h e n , the s t a t e space of t h e p r o b l e m of the P e t r i  in  amount o f t h e s e a r c h i n g o f t h e  optimal  time  the o p t i m a l s c h e d u l e a l l of the  must be s e a r c h e d . A s c h e d u l i n g h e u r i s t i c may problem  execution  the  net. A v a l i d  s c h e d u l e may  is  the  state  be t h o u g h t o f  as  64  a p a t h t h r o u g h t h e s t a t e space of t h e space  of a t i m e d P e t r i  Petri  net.  The  n e t i s s e a r c h e d by t h e c o n s t r u c t i o n o f  the  g r a p h o f i n s t a n t a n e o u s d e s c r i p t o r s , GRID. A v a l i d  may  be f o u n d by f i n d i n g a p a t h f r o m  d ,  to  0  a descriptor  state  i n which a l l  the  initial  schedule  descriptor,  t r a n s i t i o n s h a v e been  fired  once. An a l g o r i t h m  f o r the c o n s t r u c t i o n  bounded t i m e d P e t r i constructs  the  n e t i s shown i n F i g u r e 3.7.  nets  i n the o r i g i n a l  [102],  The  complete graph r e p r e s e n t i n g a l l  r e a c h a b l e from the i n i t i a l necessary  o f a GRID o f a l i v e  where  d e s c r i p t o r . The application•of  the  Algorithm  of t h e  complete  states  graph  t i m e d n e t s were u s e d f o r p r e l i m i n a r y  the c o n t e x t of the s c h e d u l i n g model would y i e l d  s c h e d u l e . However, s i n c e  n e t s and t h e g e n e r a l s c h e d u l i n g p r o b l e m a r e  [16,  27,  the  amount o f  optimal  of  searching  Step  4  transitions problem  of  and  yet  algorithm the  state  achieve may  optimal  of  or  near  be m o d i f i e d t o s e a r c h a  space  of  the  net.  The  approach.  b e h a v i o r of t h e s c h e d u l i n g h e u r i s t i c of  NP-complete  t o t h e a l g o r i t h m a r e u s e d t o model t h e b e h a v i o r  the h e u r i s t i c The  The  amount  modifications  optimal  h e u r i s t i c methods a r e an a p p r o a c h t o r e d u c i n g -  results.  restricted  the  graph  i t i s known t h a t b o t h t h e a n a l y s i s o f  Petri  55],  is  the a n a l y s i s of timed  p e r f o r m a n c e e v a l u a t i o n . The c o n s t r u c t i o n o f t h e c o m p l e t e in  and  the  algorithm.  to f i r e finding  The  problem  of  on t h e c u r r e n t d e s c r i p t o r which  tasks  to  is  modeled  finding is  exactly  by  which the  e x e c u t e on t h e c u r r e n t  65  1.  L a b e l t h e r o o t node d = ( m , r ) , where m initial marking and r ={} i s the remaining time. 0  0  0  i s the initial  0  0  2.  di:=d ,  3.  Repeat  where d ^ i s t h e c u r r e n t node.  0  Steps  4-9 u n t i l  there  are  no  unmarked  • leafs...4.  Find  5.  Repeat  6.  Generate  7.  C r e a t e a new node and l a b e l i t d £ ) . J o i n t h e node w i t h an edge and l a b e l i t s - j . I f d ^ , i s an e x i s t i n g n o d e , t h e n mark i t w i t h a *.  8. 9.  Figure  the s e l e c t o r s , Steps  6-8  a new  {s-}, e n a b l e d  on m^  of d^  f o r each S J .  descriptor,  d  . v  +  S e t t h e c u r r e n t node,  t o any unmarked  leaf.  3.7: An a l g o r i t h m f o r t h e g e n e r a t i o n o f t h e GRID o f a l i v e a n d bounded n e t  66  state. This  i s easily  transitions  in  the  seen s i n c e Petri  the  tasks  are  modeled  net f o r m u l a t i o n of the s c h e d u l i n g  p r o b l e m . The number o f s e l e c t o r s w h i c h i s g e n e r a t e d controls  t h e amount o f t h e g r a p h s e a r c h e d ,  s e l e c t o r s c o n t r o l the paths behavior  searched.  of a s c h e d u l i n g h e u r i s t i c  of a s t a t i c o r a d y n a m i c s c h e d u l i n g Consider scheduling heuristic  modeling  heuristic, schedules  prioritzed execute  the  list,  list the  L,  as  of  modeling  is  behavior  unexecuted  behavior  the  list  implementing  the  search  scheduling  the  the  is  simple  scheduling from  a  becomes f r e e t o list  scheduling  of t h e l i s t ,  i n t h e two i d e n t i c a l p r o c e s s o r  of  a  task  soon a s a p r o c e s s o r of  of  The l i s t  i s d e p e n d e n t upon t h e g e n e r a t i o n  optimal  of  heuristic.  C o f f m a n a n d Graham A l g o r i t h m A f o r t h e g e n e r a t i o n L,  4  and t h e p a r t i c u l a r  The  scheduling.  first  by S t e p  may be t h o u g h t o f i n t e r m s  the  a new t a s k . The p e r f o r m a n c e  heuristic  as  L. The  of t h e l i s t ,  case  modeled  [ 1 6 ] . ' The  simply  f o r s e l e c t o r s as a scan  by  of the l i s t ,  L. The l i s t the  s t a t e space other  Another limited  search  schedules.  of  than  lookahead  of the s t a t e space  then, paths not ending  task  set,  no  searching  of  the path s e l e c t e d .  heuristics,  involves a  [ 4 ] . I f the paths  represent  in a final  S e v e r a l p a t h s may be s e a r c h e d  be d o m i n a t e d by o t h e r the  involves  the states along  c l a s s of h e u r i s t i c s ,  schedules,  to  scheduling heuristic  until  p a r t i a l schedules.  . P o s s i b l e schedules  state are p a r t i a l they  Consider  a r e found a  subset  are permutations  of  67  t h e s u b s e t of t a s k s .  If a permutation  has a s m a l l e r c o m p l e t i o n  time, then, i t dominates the other permutations idea of  of  s e q u e n c e d o m i n a n c e may  the graph  3.3  which  e x t e n s i o n of P e t r i founded  the  net  Petri  performance 33,  t o c o n t r o l t h e amount  system  The  use  e v a l u a t i o n of system  which  86, may  of t i m e d P e t r i  general  n e t s t o i n c l u d e t h e n o t i o n of  on t h e d e s i r e  model.  70, 8 1 , 82,  use  systems  for useful  also  been  [84,  92,  93],  precluding An  for  used  be m o d e l e d by w e l l - b e h a v e d nets  is  in  for  the  performance  beyond  the  scope  the o p t i m i z a t i o n  The  notion  decision  addressed  machines  with  example  executed  of  nets.  The  evaluation  of  of the p r e s e n t Petri  nets  constrains  the  i n the untimed  nets f o r the  parallel  6600.  the  operation  paper  have  case.  programs  capabilitites.  is. a  net,  Saint [84].  in a high level algorithmic in  work.  optimization  i s t h a t of g e n e r a t i n g e f f i c i e n t  detailed  on a CDC  21,  of s e q u e n c i n g d e c i s i o n s  time  of P e t r i  Petri  i s p r e s e n t e d by S h a p i r o and  algorithms are expressed The  [10,  1 0 2 ] . However much of t h e work i s l i m i t e d  e x a m p l e of t h e use  problem  from  nets f o r the  i s w e l l documented  some of t h e s e q u e n c e s p o s s i b l e  sequencing  time  information  of timed P e t r i  W i t h i n t h e s c o p e of t h e p r e s e n t w o r k , t i m e d  The  The  i s constructed.  is directly  of  80].  R e l a t e d Work The  to  be u s e d  [4,  The  language.  FORTRAN D O - l o o p  6 8  The  approach t o the sequencing problem  decompilation  of  the  algorithm.  removal of the i n c i d e n t a l the  high  level  algorithm  with  decompilation  the  i s the  sequencing c o n s t r a i n t s introduced  language.  i s modeled  The  begins  The  the  c o n t r a i n t s a r e added t o t h e P e t r i  n e t m o d e l . The  optimization  is  of  executing  a  simulation  c o n d i t i o n s have theoretical  and  been  optimal  scope  Saint  tried  or  of  of  machine  than the  The  code.  scope  In  and  of  near  the  the  Shapiro problem  n e t model o f  machine  strategy  of S e c t i o n  and S a i n t  contrast,  i s a heuristic  FORTRAN  considered  s i n g l e time.  DO-loops  The t a s k s  functional  a n d S a i n t model i s a t a l o w e r  i s the  part  of  optimization the  i n the present  the  o b j e c t i v e of the  optimal  repetition  i n the general  of  strategies,  s t r a t e g y o r an imply  level  3.2.1. The o b j e c t i v e  work i s t h e m o d e l i n g o f s c h e d u l i n g  operations. is  solution  w o r k . The P e t r i  operations  net formulation  o f t h e work o f S h a p i r o  the  a  initial  t h e p r o b l e m w h i c h i s a d d r e s s e d by  the Shapiro  than the P e t r i  present  when  initial  a n d S a i n t m o d e l s t h e FORTRAN D O - l o o p a n d t h e h a r d w a r e  Thus,  machine  that i s ,  i s achieved.  i s more r e s t r i c t e d  at the l e v e l units.  algorithm,  i s s t o p p e d when a l l s e t s o f  w h i c h i s a d d r e s s e d by t h e p r e s e n t Shapiro  the  t h e n e t . The n e t i s e x e c u t e d f o r e a c h s e t o f  c o n d i t i o n s . The s i m u l a t i o n  The  Petri  of  the hardware  by  a  version  n e t . Next  performed  as  decompiled  by  of  scheduling  whether  strategy.  the  machine  problem,  which  work a r e assumed t o be e x e c u t e d a  The p r o b l e m a d d r e s s e d by S h a p i r o  and S a i n t  is a  69  form  of  the  g e n e r a l s c h e d u l i n g problem, and s o , t h e p r e s e n t  work i s a p p l i c a b l e . A more r e c e n t a p p r o a c h  t o t h e problem of the o p t i m i z a t i o n  of t h e s e q u e n c i n g o f e v e n t s u s i n g presented  by  net model used computation, The  Tani  a  Petri  net  approach  e t . a l . [ 9 2 , 9 3 ] . The b a s i s f o r t h e P e t r i  i n [ 9 2 , 93] i s a t h e o r e t i c a l model o f hence,  the  parallel  name c a p a c i t a t e d c o m p u t a t i o n  graph.  problems addressed f o r c a p a c i t a t e d computation graphs  the  existence  earliest  of  and l a t e s t  admissable  schedules,  schedules, the  t h e maximum c o m p u t a t i o n r a t e  are  are  algorithms f o r the  termination  property  and  f o r periodic schedules.  A c o m p u t a t i o n g r a p h , CG, i s a m a r k e d g r a p h loops  is  allowed. A self-loop  i n which  self-  i s an edge w h i c h i s i n p u t a n d  o u t p u t t o a s i n g l e node. A c a p a c i t a t e d c o m p u t a t i o n g r a p h , CCG, i s a c o m p u t a t i o n graph w i t h t h e edges number  of  tokens  which  r u l e s must be a l t e r e d output  may  limited  the  total  be h e l d on an e d g e . The  firing  s i n c e a node c a n n o t  fire  firing  the  token  on  The  the  edge a f t e r  of i t s  capacitated  the  delay  the i n i t i a t i o n  o f a node. E a c h node i s f i r e d a maximum  where X-£ i s a p o s i t i v e A  i f any  e d g e s h o l d s t h e maximum number o f t o k e n s . E a c h edge i n  a CCG, i s a s s i g n e d a t i m e . The t i m e r e p r e s e n t s placing  in  of  X^  in  of the times,  integer.  computation graph  i s shown i n F i g u r e 3.8.  l a b e l s on t h e e d g e s ,  ( c , d ° , r ), i n d i c a t e t h e c a p c i t y o f  the edge, c , . t h e i n i t a l  m a r k i n g o f t h e . e d g e , d ° , and t h e t i m e  e  e  e  70  Figure  A capacitated  k=l  k=2  s,(k)  3  s (k)  computation  graph  k=3  k=4  k ~" 5  8  13  18  23  ......  0  5  10  15  20  ...  s (k)  0  2  5  10  15  ...  Sfl(k)  2  7  12  17  22  2  3  Table  3.8:  3.6:  An  admissable  s c h e d u l e f o r CCG  of F i g u r e  3.8  71  delay in  of t h e e d g e , r .  t e r m s of t h e  of t h e  firing  earliest the  s^(k)  of  with  possible  combination  resolution  shows  of  contention  n e t . The  conflict  resolution the  3.10  3.2.  initiation  +U  an An  admissable  algorithm for  3.9.  of  duplication the time  the  the  resolution  smallest i n the  1-6  definition  have  resolved  i n the  [93].  m o d e l e d as  i s modeled u s i n g a and  edges,  the  places.  r e s o l u t i o n of a c o n f l i c t initial  i s converted best  markings.  t o a CCG  schedule,  time,  by  Each  model f o r  the  schedule  s p e c i f i e s the  conflict  CCG.  capacitated  in Section  computation  1. E a c h t a s k e x e c u t e s  of t h e p r o b l e m , h e n c e , X^=1,  number of t a s k s . The  a  arbitrarily.  n e t model w h i c h i s p r e s e n t e d the  the  graph  t h e marked g r a p h r e p r e s e n t a t i o n c o n s t r u c t e d  of A l g o r i t h m  on e a c h edge may  first  places  two  s t r u c t u r e of t h e  i s a s p e c i a l c a s e of  model. Consider  The  completion  P a r t of the P e t r i  is  of  delay  conflict  i s found.  is  of the c o n f l i c t  i l l u s t r a t e s the  which a schedule  Step  3.6  of F i g u r e  t h e d u p l i c a t i o n o f t h e p l a c e s and  3.2  of t h e k  expressed  c o n t e n t i o n between o p e r a t i o n s  resource  m a r k i n g and  Figure  with  time  i s shown i n F i g u r e  t o model r e s o u r c e  generalized Petri  initial  s^(k)  is  c a p a c i t a t e d c o m p u t a t i o n g r a p h model d o e s n o t  system  Each  f o r t h e CCG  i . Table  f o r t h e CCG  f i n d i n g of the  ability  schedule  which i s the  node  schedule  The  A  The  &  a s i n g l e time  1<i<r, where r i s  marked g r a p h i s s a f e , h e n c e , t h e  be a r b i t r a r i l y a s s i g n e d  any  by  non-zero  by the  capacity value.  72  Sj(1):=0 1^j<m  1.  Initialize  2.  Repeat S t e p 3 u n t i l f o r a l l nodes.  3.  (1):=max  no more c h a n g e s a r e p o s s i b l e  /.j<1>;  SiOJ+r-ij f o r a l l input a r e unmarked  edges  Si(l)-Tjj f o r a l l output \ w h i c h a r e marked t o c a p a c i t y 4.  Repeat  5.  s  edges  S t e p 5 f o r 2<k^maxX-i  (k):=max  / SJ (k-1 )+TJJ  Si(k-d )+T j 0  i  Si (k-Cji+dji edges  Figure  which  3.9: An a l g o r i t h m  f o r a l l input )-TJ  to construct o f a CCG  edges  i j  f o r a l l output]  /  theearliest  schedule  73  74  This  is  the  a p p r o a c h e s . The of c o n f l i c t s simple  the  similarity  resolutions  and  awkward  number o f CCG's  for  exists  each  is  possible the  conflict.  In  to a processor.  be  needed  The  methodology a l s o does not adapt e a s i l y  of  varying  initial  resolution, must be  the c o n v e r s i o n  repeated  of  of t i m e s . Due nets  as  a  adequately model.  a CCG  for  the  model r e s o u r c e  The  use  contention  r e s o u r c e s . The  and  present  models would  and  initial  and  schedule. evaluation of  generating resources.  the  class  limited  restricts  provides the a b i l i t y  Saint.  an a r b i t r a r y  restricted  model,  The  number  of  Petri  ability  t h e use  of  the  n e t s as a b a s i s f o r the  ability  to  to  the  model  t o model h i e r a r c h i e s i n  work d e f i n e s a f o r m u l a t i o n w h i c h i s  more f l e x i b l e model i f r e s o u r c e factor.  CCG  to f i r e  contention  work  task  whole p r o c e s s  Shapiro  of t h e c o l o u r e d P e t r i  present  the  e t . a l . i s more a p p l i c a b l e  by  are allowed  t o t h e c h o i c e of a basis  model i n t h e resource  to a  of  during  f o r the  f o r e a c h s e t of  the problem which i s addressed  number  o r even a good  c o n d i t i o n s . The  s c o p e of t h e work of T a n i  transitions  the  resource  schedule  identical  o f t h e number of  A l a r g e number of CCG  t o f i n d the best  the  e x i s t s each time a  assigned  to  even  a  general,  is  The  for  when  product  of a t a s k system, a c o n f l i c t  schedules  two  m e t h o d o l o g y d e s c r i b e d above f o r t h e r e s o l u t i o n  conflicts  conflict  between the  o f a t a s k s y s t e m e x e c u t i n g on a s e t of  p r o c e s s o r s . The  execution  of  becomes u n m a n a g a b l e  case  resource  limit  contention  is  an  important  75  CHAPTER 4 THE The  ANALYSIS OF A SCHEDULING PROBLEM  scheduling  execution  problem  to  be  addressed  here  o f a t a s k s y s t e m on a s e t of p r o c e s s o r s  s p e e d s . The  s c h e d u l i n g s t r a t e g y t o be c o n s i d e r e d  scheduling.  The  performance  criteria  for  p r o b l e m i s the m i n i m i z a t i o n of t h e e x e c u t i o n  of  i s the  different  here i s  the  list  scheduling  time f o r the task  system. List studied  scheduling [1,  14,  i n a m u l t i p r o c e s s o r environment  15,  16,  i s known t o y i e l d good p e r f o r m a n c e  identical  processors  of C o f f m a n  Much  of  processors the  levels  three h e u r i s t i c s  are  the  research  of d i f f e r e n t  performance  the  processors slowest  ordered  Algorithm  A  compared  bound  using  randomly  graphs. i n t h e use o f l i s t  speeds  i s i n the area  of the l i s t  suggests  poor  i n which the d i f f e r e n c e  o f upper  bounds  of  Liu  and  performance  for  sets  between  s p e e d i s l a r g e . A much t i g h t e r  the case of a n u l l precedence  scheduling for  s c h e d u l i n g . A summary o f t h e  b o u n d s i s shown i n T a b l e 4.1. From t h e work [56],  first,  p r e c e d e n c e g r a p h s f r o m t h e l i t e r a t u r e and f r o m  generated precedence  on  highest  of  and Graham, and a p r o p o s e d h e u r i s t i c , maximum c h a i n  l e n g t h maximum t i m e . The sample  f o r the case  [ 1 ] . T h r e e methods o f g e n e r a t i n g  of t a s k s a r e compared,  well-  24, 26, 27, 28, 30, 57, 5 6 ] . L i s t  scheduling  lists  is  the  fastest  bound i s p r e s e n t e d  r e l a t i o n , that  is,  Liu of and for  independent  76  Partial  Order  Bound  arbitrary  w/w*  1 + bj_ - b_L  bn  3 2  *  arbitrary  Reference  .  1 2n  1 + 2s/n  B  Liu  and L i u [56]  n  G o n z a l e s e t . a l . [28]  Jaffe  [40]  Notes 1. n i s t h e number o f p r o c e s s o r s . 2. bi i s t h e s p e e d o f p r o c e s s o r i . 3. B „ i s p r o c e s s i n g power of n p r o c e s s o r s .  Table  4.1: Bounds f o r l i s t s c h e d u l i n g of d i f f e r e n t s p e e d s  on  processors  77  tasks.  The bound o f J a f f e  i s a bound f o r t h e e x e c u t i o n o f a n y  t a s k s y s t e m on a m a c h i n e o f n p r o c e s s o r s u s i n g t h e i processors  f o r e x e c u t i n g t h e task system  [ 4 0 ] . The i f a s t e s t  p r o c e s s o r s a r e f o u n d by t h e m i n i m i z a t i o n o f bounds s u g g e s t p o o r p e r f o r m a n c e  fastest  B /B^+b,/b^. A  f o ra general  The  list.  4.1 The S c h e d u l i n g M o d e l The  scheduling  model p r e s e n t e d are  model f o r t h e p r o b l e m  i s a subset  i n S e c t i o n 3.1. The r e s o u r c e s  restricted  to  a  single  f o r the  set  of  P = { P , , P , . . . , P A ) . The t a s k s y s t e m i s c o m p l e t e l y 2  in  Section  3.1. The  performance c r i t e r i a  The s e t o f p r o c e s s o r s , P, - i s a different of  s e t of  s p e e d s . The s p e e d o f a p r o c e s s o r  execution  speed  of  as  described  the remaining  processors  l ^ b i > 0 . The s e t o f p r o c e s s o r s  i s the  system. processors  of  i , b^, i s t h e speed  r e l a t i v e t o t h e speed of t h e f a s t e s t  P, i s assumed t o be t h e f a s t e s t p r o c e s s o r  problem  processors,  t o be u s e d  m i n i m i z a t i o n of t h e e x e c u t i o n time of t h e task  of t h e  processor.  of speed  ^ = 1.  The  i s r e s t r i c t e d t o t h e range  i s assumed t o be o r d e r e d  ,  such  that, b,>b >...^b*. 2  A  measure  of a s e t of processors  i s t h e p r o c e s s i n g p o w e r , B.  The p r o c e s s i n g power o f t h e i f a s t e s t sum  of  t h e speeds o f t h e f i r s t  power o f P i s B„.  p r o c e s s o r s , B' , x  i s the  i p r o c e s s o r s . The p r o c e s s i n g  78  The  s e t of p r o c e s s o r s  C =(X ,<p). P  Each  p  processors set  P  ordered,  convenience, of  bi=1.  slower  c, In  c^,  modeled  by  in  set  speed. Since  the  the i t is  list  available fastest  the processors  colour set, a larger  scheduling  processor.  processors  assumptions  coloured  token  transition.  is  slowest  bottom. processor time The general task  from  set,  represents  p  subscript  that  a  the For  speed  indicates  of  each  the  The  least  place represents of  firing  the  a  times  execution  time  differ  the  tasks  to  place has  is  least  used  the  Under  p  general  enabling  to  fire  c, a t t h e b o t t o m and s p e e d s and  c  k  c^  a at is  form of the p a r t i a l o r d e r  partial enabling the  fastest  fastest  order  is  coloured  from  top  to  token  from  the  available  at  processor  transistion.  execution  to  the  the p a r t i a l o r d e r , < .  input  p r o c e s s o r s . The  Thus,  to  c o l o u r e d P e t r i n e t s , the  p a r t i a l order  i on p r o c e s s o r  assumed r^/bj  X  w h i c h have  tasks  assignment  i s m o d e l e d by for  The  assigns  The  shown i n F i g u r e 4.1.  the  colour  assumed  t h e t o p , where k i s t h e number o f d i f f e r e n t the  a  c o l o u r set models the o r d e r i n g .  represents the  is  processor.  The  the  colour,  of a c e r t a i n  is  P,  of t h e t a s k s a r e f o r the  t a s k . The  j i s g i v e n by only  -r^/bj.  {T^},  1<i<r.  execution The  is a  time  of a  processors  are  i n t h e i r s p e e d of e x e c u t i o n ,  hence,  i s v a l i d for a l l processors. List  s c h e d u l i n g a s s i g n s the e x e c u t i o n  of  a  task  to  a  79  Cp=(X ,< ) p  X  p  = {c 1 , c 2 , • • • i ^ } c  p  V ,  k  t  I  6  F i g u r e 4.1:  c .  c,  Colour set f o r p r o c e s s o r s of d i f f e r e n t  speeds  80  processor  by  scanning  L, a r e assumed t o be closer  to  the  to execute  to  As  they  The  assignment  to y i e l d  i n order  of d e c r e a s i n g  priority.  the  are assigned  different the  list  the e x e c u t i o n a  faster  processor,  of l i s t  are  relies  scheduling  on  the  available.  no  processors  execute.  List  the ordered  i s t h a t no  t a s k s ready to execute. scheduling  This problem i s  a  last slow  time  in  list  processor.  plus  then, a b e t t e r the  faster  case,  for  executed I f the  An  processor  optimal  i n order  processors  and  slow  execution  schedule  i s a cause  suppose the next  tasks  on  the  from  available.  to of on is  extends  of w a i t i n g  time  would r e s u l t becomes  the  task  processor  t a s k beyond the time the  processors  This  general.  compounded  t a s k t o be  of t h e  processor  the task u n t i l  a  becomes  f o u n d on  c o n t a i n t a s k s which are are delayed  i s the to  are  processor  there  but  than  i s scanned from head  t a s k s ready to  speeds. For a simple  assigned  processor  task  results.  may  better.  until  simple  of n o n - o p t i m a l i t y of l i s t  "fit"  list  fastest  t h e r e a r e no  i f there are  schedule  a  ready t o execute  t o the  is relatively  good  idle  t a s k , the  continues  or u n t i l  When  list,  A  i s of h i g h e r p r i o r i t y  list.  a new  A characteristic are  list  tasks which are  list,  scheduling  t a s k s i n the  of  available  available  of t a s k s . The  h e a d of t h e  task near the t a i l  tail.  a list  for  faster  delaying  81  4.2  Algorithms The  for List  effectiveness  the p r i o r i t i z e d task(s)  to  list  be  list  considered  here.  The  known t o p e r f o r m  well  CG  produce optimal and  of p r o c e s s o r s  The  tasks  for  sucessor shown  t h e c h a i n . The chain  starting  E x a m p l e 1 i s 34. is  the  lists  generated  The  l e n g t h of the  of  the  of t h e e x e c u t i o n  task  T.  is a  chain  times  The  for  the  sequence  i s the  of t h e  height  starting  of  immediate  length  tasks  in  longest  of t a s k T10  in  ( £ 7 , < , { } ) , The  s u b s e q u e n t c h a i n of a  task  longest chain s t a r t i n g  w i t h an  with  1  Tet7.  T  The  case  effects  necessary  h e i g h t , h, o f a t a s k s y s t e m , longest chain  A  processors  of a t a s k T i s t h e l e n g t h o f t h e  The  T.  by A l g o r i t h m  i t i n the c h a i n . In Example  h, o f E x a m p l e 1 i s 62.  task  [1],  Coffman  C=(T5,T6,T9,T14) i s a c h a i n . The  the  is  speeds.  are  height, i s the  problem  heuristic  identical  [40]. A chain  task  the  i s proposed f o r the  the p r o c e s s o r  definitions  4.2,  with  the  HLF,  next  for  speeds which c o n s i d e r s the  task preceeding  height  the  i d e n t i c a l processors  f o r t h e c a s e of  and  each  i s t h e sum  find  algorithms  first,  times. A h e u r i s t i c  times  Figure  of a c h a i n  levels  of t h e h e u r i s t i c s ,  to the  in  The  of d i f f e r e n t  which  to  t o be c o m p a r e d i s A l g o r i t h m A of  following  discussion  i s d e p e n d e n t upon  t o be compared f o r  highest  schedules  of t h e e x e c u t i o n  scanned  Three h e u r i s t i c  L, a r e  [14].  unit execution  scheduling  i n t h e c a s e of  second h e u r i s t i c Graham,  list  executed.  of t h e  and  of  L, w h i c h i s  generation  The  Ordering  immediate sucessor  s u b s e q u e n t c h a i n of t a s k T5  i n Example 1 i s  of (T7,  82  task/execution  F i g u r e 4.2:  time  Example 1  83  T9,  T13,  T16,  T18,  T21).  t a s k system, i s the  sum  The list  highest  simply  starting  w i t h t a s k T.  in  first  order  defined  by  the  Since  cardinality  F i g u r e 4.3  a highest  levels  list  to  each  according  Figure  4.4.  s u c e s s o r s of t a s k  T.  T  longest  is  chain  of t h e  tasks  same l e v e l a r e o r d e r e d  i n the  list  s y s t e m has  . The  to  that  assigns  from  an  integer,  tasks are ordered i n a  be in  result  one  tasks.  c(T). Algorithm  defined Note  the  more t h a n  w h i c h may  Graham  T of  to decreasing is  the  shows t h e  o r d e r i n g on  task  ,S(T)  a  the t a s k s i n a  l e v e l of a t a s k  t h e r e a r e many l i s t s  first  for  levels  A l g o r i t h m A of C o f f m a n and 1<o(T)<r,  orders  of  i n general a task  task at each l e v e l ,  time  t i m e s of t h e t a s k s i n  heuristic  of l e v e l s . The  E x a m p l e 1. T a s k s a t t h e  arbitrarily.  execution  132.  levels  in decreasing  the t o t a l  of t h e e x e c u t i o n  is f o r E x a m p l e 1 i s  %J'.  „,  A  the  is  shown  s e t of  Algorithm  A  in  immediate arbitrary  d e c i s i o n s must be made o n l y when S ( T ) = S ( T ' ) . T h u s , A l g o r i t h m in  general  does  not  a s s i g n m e n t f o r Example The  proposed  execution highest highest  time,  levels levels  chain should to a f a s t e r  generate  a  unique  1 i s shown i n F i g u r e  heuristic,  maximum  and  first  longest  be of h i g h e r processor  priority,  a  An  length  f r o m two  processing  heuristic,  L.  a(T)  4.5.  chain  MCLMT, c o m b i n e s n o t i o n s  first  list  A  maximum  heuristics,  time.  From  t a s k w h i c h has  such t h a t ,  i t is  than a task w i t h a s h o r t e r c h a i n  a  the  longer  assigned length.  .  task/level  Figure 4.3:  Example  1  levels  84  85  1.  An a r b i t r a y t a s k T with S(T )=* o ( T ) i s d e f i n e d t o be I . 0  0  is  chosen  and  0  2.  Suppose f o r some k ^ r , t h e i n t e g e r s 1,2,... ,k have been a s s i g n e d . F o r e a c h t a s k T f o r w h i c h a has been defined on a l l e l e m e n t s o f S ( T ) , l e t N(T) d e n o t e t h e d e c r e a s i n g s e q u e n c e o f integers formed by o r d e r i n g the s e t {a(T'):T'eS(T)}. At least one of these tasks T* must satisfy N ( T * ) < N ( T ) f o r a l l s u c h t a s k s T. C h o o s e one s u c h T* a n d d e f i n e c ( T * ) t o be k.  3.  Repeat the assignment i n Step 2 u n t i l a l l t a s k s o f £7 have been a s s i g n e d some i n t e g e r .  where  N=(n, , n , . . . ,n )<N' = ( n , n , . . . ,n <), 2  t  1  2  t  t,t £0,  if  ( i ) f o r some i ^ O , n^ =n^ , f o r a l l j , 1 <,j<i-1  or  " i i ( i i ) t<t' and n ^ n ^ , <  n  Figure  l<j<t.  4.4: Coffman-Graham A l g o r i t h m A  r  and  task/c(T)  Figure  4.5:  Example  1, CG  Algorithm  A  87  For  example,  height  then,  tasks  h/b, i s t h e l o w e r  on t h e c h a i n d e f i n i n g t h e is  longest  processing  bound of t h e o p t i m a l  is  i f t h e bound i s t o  execution  decreasing  time  execution  easily  achieved  time  shown  be  heuristic,  achieved.  schedule  the  on t h e  From  the  the tasks are ordered  f o r the case of equal  that  shortest  chain  execution  For  the  time  is  some p o i n t i n  Suppose  two p r o c e s s o r s ,  of  the  the  p r o p o s e d h e u r i s t i c , MCLMT,  execution  processor  Processors  j , b{>bj . Two  a r e t o be a s s i g n e d  for the tasks are To  derive  of  the  task  system.  i and j , a r e a v a i l a b l e t o e x e c u t e  t a s k s . The s p e e d s o f t h e p r o c e s s o r s , respectively.  time  available.  derivation  consider  by  lengths.  by a s s i g n i n g t h e t a s k w i t h t h e l o n g e s t e x e c u t i o n  to the f a s t e s t processor  and  sufficient  A l l t h e t a s k s o f t h e l o n g e s t c h a i n must be e x e c u t e d  fastest processor  It  the  of t h e task system. I f t h e r e  power, w*.  consider  i  is  i and j , a r e b ^  assumed  to  be  new  and  bj,  faster  than  t a s k s , T^. a n d ^ , a r e r e a d y t o  execute  t o t h e p r o c e s s o r s . The e x e c u t i o n  times  and T^, r e s p e c t i v e l y . the f i r s t  s o r t i n g c o n d i t i o n of the h e u r i s t i c ,  d e f i n e a q u a n t i t y , A. L e t t h e c h a i n l e n g t h o f t h e t a s k s T^ a n d T^  be 1 y a n d l - j _ ,  execute  r e s p e c t i v e l y . S u p p o s e t a s k T^ i s a s s i g n e d  on p r o c e s s o r  processor  j . Let  when i t i s a s s i g n e d  To c o n s i d e r  i and task 6^  i s assigned  to  execute  to on  be t h e l e n g t h o f t h e c h a i n o f t a s k  to the processor i .  only the e f f e c t  of the c u r r e n t assignment,  assume  88  the  remainder  processor.  Consider  of  Similarily  the  chain  is  for task  T^,  d i f f e r e n c e , A,  A  If  the  "V-\* k T  the assumption t h a t T  then,  / b  executed  on  between the c h a i n  i-  { 1  r;i  + T  i s assigned  i  / b  i  the  fastest  lengths.  )  ( , )  to processor  i is valid,  A>0. -  ^  (l  | <  -T +T /b )-(l -T +T /b j)>0 K  k  (l -l )>r k  1  Equation  (3)  states that  lengths  of  the  tasks  i  k  1  1  1  -^/^-(^-^/b^)  the  the  must  be  greater times  execution  or  j .  is  higher  ordered  on  processor  such t h a t  equation  (3)  decreasing  chain  The resolves situation  be  chain  criteria  case  with  of.  two  for  in  the  to  extended list  order  lengths  chain  the d i f f e r e n c e  priority,  sorting  equal  chain  processors  by  the  should  be  therefore,  the  list  f o r Example  i s assigned  the  length.  list  of  1  in are  i s assigned  to processor  tasks  Consider  r e a d y t o e x e c u t e two  d e s c r i b e d a b o v e . Assume t a s k t a s k T^  are  S i n c e , the  interpreted  l e n g t h s . The  than  (3)  4.6.  second the  task  may  shown i n F i g u r e  i  .  difference  b e t w e e n t h e amount t h e e x e c u t i o n  (2)  ;  tasks,  to processor  j . From e q u a t i o n  the as  i  and  i  is  (1),  A=T (1-l/b )--r (1-1/b^). u  If  i  t h e a s s u m p t i o n t h a t t a s k T^  valid,  then  A>0.  : i  i s assigned  to processor  task/chain  Figure  4.6:  length  Example 1 c h a i n  length  90  T A >(1-1/bj )/(1 -1/b- ) k  l  But,  | 1~ 1/bj  Hence,  ( i - i / b ^ / d - i / b ^ i  | > i 1-  1  /b  Therefore, and, The  second  decreasing  criteria execution  Note e q u a t i o n list  L  The  to  decreasing  maximum  t i m e , MCLMT,  general,  except  i n certain  may y i e l d  t h e wrong  order  chain  length.  i s the execution chain  time of  length  maximum  a n d t h e maximum c h a i n  heuristic  are  length  identical,  s i t u a t i o n s when e i t h e r  the  in  heuristic  schedule.  two p r o c e s s o r s  ready t o execute  tasks  a n d two  T^ a n d T^, a s a b o v e . S u p p o s e t h e c h a i n l e n g t h o f T ^ i s  g r e a t e r than  Further than  to  subsequent  subsequent  t i m e , MSCMT, h e u r i s t i c  Consider  i n order of  t i m e when t h e c h a i n l e n g t h s a r e e q u a l .  maximum e x e c u t i o n  tasks,  the tasks  a second s o r t i n g c r i t e r i a  tasks.  execution  order  (1) c a n a l s o be i n t e r p r e t e d  according  Similarily, the  i s to  t h e c h a i n l e n g t h o f T^.  suppose t h e subsequent c h a i n l e n g t h of t a s k  t h e subsequent c h a i n  i s less  l e n g t h o f T,.  VVV i T  Using to  t h e MSCMT l i s t ,  a faster processor.  priority may r e s u l t  and  T^ h a s a h i g h e r p r i o r i t y Using  i s assigned  i n a worse  t h e MCLMT l i s t ,  and i s a s s i g n e d  T^ h a s  t o a faster processor.  schedule  than  a  higher  Either  the reversed  list  schedule  91  depending  on  the  differences  i n the processor  of n o n - o p t i m a l i t y  differences  for either  The h e u r i s t i c  reduces  problems a r e c o n s i d e r e d . t o be u n i t first.  times,  Each  then  task  can  order  heuristic  simpler  are  the  source  i f  times  restricted  are r e s t r i c t e d  reduces t o highest  o n l y add a s i n g l e u n i t identical  to  the  levels  to the length, level.  I f the  t o a n u l l p a r t i a l order, then, the  a longest processing  n u l l p a r t i a l o r d e r means t h e t a s k s a r e case  and  i s a possible  forms  I f the execution  is  to  lengths  heuristic. to  i s restricted  reduces  the  speeds. T h i s  the h e u r i s t i c  therefore, the length partial  in  time h e u r i s t i c . A  independent.  In  this  t h e s u b e q u e n t c h a i n l e n g t h s o f a l l t a s k s i s 0. The t a s k s then, ordered  decreasing The heuristics lists  u s i n g t h e second c r i t e r i a  execution lists  f o r Example 1 r e s u l t i n g are  shown  a r e s o r t e d f r o m t h e random l i s t  processors  f o r the execution  P={P!,P ,P ,P„} 2  a  list  of  times.  a n d a random l i s t  of t h e s c h e d u l e s  into  3  The s p e e d s o f t h e p r o c e s s o r s  from each of t h e t h r e e in  Figure  4.7.  shown. The G a n t t  o f E x a m p l e 1 on  a  The  charts s e t of  a r e shown on F i g u r e s 4.8 a n d 4.9. a r e b, = 1 a n d b = b = b = 2 / 3 . 2  3  4  (T1 T2 T3 T4 T5 T7 T10 T6 T9 T8 T14 T12 T13 T16 T15 T18 T19 T11 T21 T17 T20) (a) MCLMT  '  (T1 T2 T3 T4 T5 T7 TG T9 T8 T10 T14 T12 T13 T16 T15 T18 T.19 T17 T11 T20 T21) (b) HLF  (T2 T1 T3 T4 T5 T6 T7 T9 T10 T8 T13 T12 T14 T16 T15 T18 T19 T1.7. T20 T i l T21) ( c ) CG  (T6 T13 T12 T18 T3 T5 T21 T2 T1 T16 T20 T14 T10 T11 T4 T17 T7 T8 T9 T19 T15) "  F i g u r e 4.7:  (d) RANDOM  Ordered l i s t s o f t a s k s f o r Example 1  T10  Til  T3  T21  "  T13  T2  T6 T8  T1  T4  T5  T7  T9  T19  T12  T15  T14  T16 T18  I  0  1  1  1  1  1  5  10  15  20  25  — I  30  1  1  '  35  40  45  (a)  T10  i  i  50  55  i  i  i  i  i  65  70  75  80  85  T20  T3  T12  T2  T6 T8 T4  »  60  HLF  T11  T1  K  T20  T5  T7  T9  T19  T13  T15  T14  T16  T17 T21 T18  I  1 — 1  I  0  5  15  10  .  I  '  i  i  i  i  I  20  25  30  35  40  45  50  I  55  (b) MCLMT F i g u r e 4.8: Schedules f o r Example 1  i  i  i  i  i  i  60  65  70  75  80  85  T10  T21  T3  T7  TI  T1 1  T2  T4  T5  T12  T8  T9  T19  T14  T15  T13  T16  T6 i  0  5  10  15  i  i  20  25  I I 30 35  1 40  1 45  50  [jr.,  Tie' T20 • 1 1  1  1  55  70  75  60  65  80.  85  (a) Coffman-Graham  T10  T20  T1  T12  T3  T4  T2  T11  T7  T5  T9  T8  T19  T14  T15  T13  T16  T17  I T2 1  T6  10  15  20  25  30  35  T18 40  45  50  55  (b) Random F i g u r e 4.9: Schedules f o r Example 1  60  65  70  75  80  85  95  4.3  Experimental The  for  Outline  GRID a n a l y s i s a l g o r i t h m and  additional  t h e c o m p a r i s o n of t h e h e u r i s t i c s a r e  The  symbolic  retention (see  computational  of  Appendix  A  also  p a r t of the  Petri  and  n  Figure  allow  the  2.1(b)). use  elements  a l s o be  also for  of the v e c t o r  transition.  Since  of the v e c t o r are three  The  the  transitions  o f s e l f - l o o p s , an e s s e n t i a l  output  length  i s defined  places.  The  t o n, many of  the  described  in  85  null partial  orders  order,  orders.  are  shown i n F i g u r e s  task  50  t a s k s , 65  are  order,  B.1  and  t a s k s and. 75  used  the B.2  s e t , %J , r a n g e s i n s i z e  t a s k s . Four randomly g e n e r a t e d p a r t i a l  tasks,  elements  are as n o t e d i n T a b l e  a least constrained p a r t i a l  s i z e of the  to  partial  a most c o n s t r a i n e d  The  to  and  a r e c o m p a r e d f o r 15  of t h e p a r t i a l  orders  non-zero  C h a p t e r 4.2,  comparison,  partial  the  zero.  orders  and  for  i s connected  T h r e e s p e c i a l c a s e s of t h e p a r t i a l  order  n,  i n d i c a t e which places are connected  heuristics  a  the  grammar-style  in general, a transition  randomly generated l i s t , sources  allow  d e f i n e d as v e c t o r s of  a s m a l l number of p l a c e s , r e l a t i v e  The  LISP of the  i s t h e number o f p l a c e s . A v e c t o r  i n p u t p l a c e s and  The  of  net f o r m a l i z a t i o n .  T r a n s i t i o n s can where  capabilities  programs  implemented i n LISP.  the grammar-style d e f i n i t i o n  definitions  the  the  t a s k s , are  4.3. the  partial  latter  two  of A p p e n d i x  B.  from  orders  in  a  10 t a s k s  of s i z e s ,  to 40  i n c l u d e d for. the  96  comparison. Each task time  chosen  execution  i n the p a r t i a l from  time  i s assumed  taken  from other  times  execution  for  distribution execution  be a p o s i t i v e  sources,  execution  execution  b e t w e e n a minimum  time.  The  execution  i n t e g e r . F o r t h e examples  the comparisons  times  an  made  f o r the  i n a d d i t i o n t o t h e random  execution  time  are  not  are  defined  to  be  unit  c o l o u r s e t , X , which i s used f o r t h e comparisons i s p  shown i n  avoids  i s assigned  times.  The  rational  to  execution  i f the  uniform  a n d a maximum  time  defined  a  orders  Table  4.2.  The  assumption  numbers a n d t h e e x e c u t i o n  that  times  the  speeds  are positive  are  integers  t h e problems a s s o c i a t e d w i t h f i n i t e machine a r i t h m a t i c  r e a l numbers. T h i s  assmption  i s made  without  loss  of  generality. A and  t a s k s y s t e m i s d e f i n e d by a t a s k s e t , a p a r t i a l  the execution  times are  f o r the  assigned  tasks.  different  The  tasks  of the  partial  orders  creating  s e v e r a l t a s k s y s t e m s b a s e d on a s i n g l e p a r t i a l  For  each task system, the schedule  on  several  Petri  net  several  different  sets  formalization,  initial  the  initial  times,  i s found f o r i t s processors.  Petri  net  thus  order.  execution  In terms, of the  i s executed  with  m a r k i n g s , mO, o f t h e f o r m , m0=(READY c ,  Each  of  execution  order,  marking  C £ ... c j ) .  i sa list  of tokens  w i t h a s i n g l e READY  Colour '  Processor Speed  c,  Table  4.2:  c  2  c  3  1 2/3 1/2  c.  1/3  c  5  1/5  c  6  Colour set  1/6  for  experiments  98  t o k e n a n d two o r more p r o c e s s o r t o k e n s .  The  necessary  net modeling  f o r the portion of the P e t r i  dependencies  (see Step 4  of  the colour  Algorithm  READY  1 ) . c,  elements  of  s e t , X . At l e a s t  initial  marking  fastest  p r o c e s s o r h a s i t s s p e e d n o r m a l i z e d t o 1.  p  i s the token c,, since  token  is  the data  and  c^ are  one t o k e n i n t h e  i t i s assumed t h a t  the  4.4 R e s u l t s a n d D i s c u s s i o n A summary o f t h e r e s u l t s number  of  different  sets  s y s t e m s b a s e d on t h e p a r t i a l the  list  from  one  the h e u r i s t i c other  of processors t e s t e d  2  i s t h e number o f  times  the  list  list. time,  MCLMT,  list  t o g e n e r a t e a s c h e d u l e whose l e n g t h i s s h o r t e r  heuristics MCLMT l i s t  of  times  g e n e r a t e s a s c h e d u l e a s good a s a t l e a s t  l e n g t h of t h e schedules  is  f o r the task  o r d e r , n, i s t h e number o f  The maximum c h a i n l e n g t h maximum found  i s the  0  the h e u r i s t i c generates the schedule with the  shortest execution time. n from  i s shown i n T a b l e 4.3. n  i n 98  which  a r e generated  o f 160 c a s e s  f o r the f i f t e e n  i s a l s o found t o generate a schedule  by  is  than t h e  the  other  e x a m p l e s . The whose  length  no l o n g e r t h a n one o r more o f t h e h e u r i s t i c s c o m p a r e d i n 39 160  cases  tested.  Overall,  best schedule of t h e four l i s t s cases  t h e MCLMT l i s t  generated the  c o m p a r e d 86 p e r c e n t  of the  tested. Note Example 1 a c c o u n t s  f o r o v e r 20 p e r c e n t o f t h e c a s e s  MSCMT Example 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  Total  Notes 1. 2. 3. 4.  r 21 22 19 85 16 . 10 12 16 15 19 30 40 50 65 75  no  ni  34 1 1 21 . 10 6 13 20 6 6 7 6 6 5 6 3  23 10 9 6 5 4 13 2 5 2 3 5 5 6 1  160  98  HLF ni 9 1 3 2 0 6 6 2 1 4 3 0 0 0 1  39  0 0 4 1 1 0 0 0 0 1 0 1 0 0 1  9  CG ni  ni  7 1 0 1 0 1 2 2 1 4 3 0 0 0 1  RANDOM nJ  2 0 4 1 0 3 1 2 0 0 0 0 0 0 0  23  14  2 0 3 1 0 4 6 2 1 1 2 0 0 0 1  23  ". :  r I s the number of t a s k s . no Is the number of cases. n i 1s the number o f best schedules. ni Is the number o f schedules a t l e a s t as good as one o t h e r .  Table 4 . 3 : Sumary o f R e s u l t s  ni 0 0 1 0 0 0 0 0 0 0 0 0 0 0 o  1  tl! 2 0 0 0 0 6 1 0 1 1 0 0 o 0 o  11  Notes Example 2 l e s s 1 [ 1 4 ] p. 88 [24] [57]  [15] [1]  p.  6  <:most c o n s t r a i n e d <:least c o n s t r a i n e d [ 1 4 ] p. 92 [59]  Randomly Randomly Randomly Randomly  generated generated generated generated  100  tested.  Since,  independent through  Example  1  i s Example  the s h o r t e s t at  s c h e d u l e i n 75 o f 127 c a s e s least  as  good  as  per cent of t h e cases  fewer in  results  a  single  f o r examples  and  to  generate  i n 30 o f 127  t h e b e s t s c h e d u l e i n 83  i f Example 1 i s ommitted.  are heavily  weighted  by t a s k s y s t e m  with  t h e number o f t a s k s r a n g e s  f r o m 20 t o  85, e x c l u d i n g  E x a m p l e 1. F o r t h e s e E x a m p l e s , i t i s f o u n d t h a t t h e MCLMT generated  the  shortest  schedule  i n 35  of  s c h e d u l e a t l e a s t a s good a s one o t h e r l i s t cases. For the larger generate  task systems,  47 c a s e s a n d a  i n another  t h e MCLMT  list  8 o f 47  i s found  t h e b e s t s c h e d u l e i n 91 p e r c e n t o f t h e c a s e s  to  which  tested. The  l e n g t h s of the schedules generated  heuristics an  a  t h a n 20 t a s k s . E x a m p l e s 2, 4, a n d 11-15 a r e t h e e x a m p l e s  which  were  2  i s found t o generate  one o t h e r l i s t  c a s e s . The MCLMT i s f o u n d t o g e n e r a t e  The  less  task, consider only the results  15. I n t h i s c a s e , t h e MCLMT l i s t  schedule  2  schedule.  a b s o l u t e preformance t h e bound  The  ratio  i s an  of the h e u r i s t i c s .  of the  i s easily  lemma.  indication  of the  J a f f e ' s bound i s  used  c a l c u l a t e d . The r a t i o s w/w*' a r e  shown i n T a b l e 4.4. The l o w e r b o u n d , w*', following  each  i s c o m p a r e d t o J a f f e ' s l o w e r bound on t h e l e n g t h o f  optimal  since  by  i s defined  by t h e  101  Example 1 2 3 4 5 6 7 8 9 10 1 1 12 13 14 15  r  MCLMT  HLF  21 22 19 85 16 10 12 .16 15  1.17 1.10 1 .26 1.14 1 .05 1.21 1.19 1.53 1.13 1.11 1 .08 1 .41 1.00 1 .04 1 .05  1 .35 1.18 1 .50 1 .20 1.15 1 .45 1.71 1 .53 1 .22 1.1 1 1.11 1 .57 1 .04 1.13 1.06  19  30 40 50 65 75  where w*'  CG  RANDOM  1.35 1 .27 1 .30 1.19 1 .25 1.29 1 .26 1 .65 1 .20 1.28 1.15 1 .54 1 .02 1.14 1 .08  i s the lower bound on the l e n g t h Of the optimal schedule Table 4.4: Average  w/w*'  1 .38 1:38 1 .42 1 .37 1 .29 1 .35 2.00 1 .76 1.19 1.41 1 .21 1.61 1.15 1.15 1 .22  102  Lemma 1 [ 4 0 ] Let (%/,<, v) be a t a s k s y s t e m t o be s c h e d u l e d on a set o f p r o c e s s o r s o f d i f f e r e n t s p e e d s . L e t w* be t h e f i n i s h i n g t i m e o f an o p t i m a l s c h e d u l e . T h e n , w*>max(M/B ,h/bT). a  The r a t i o s g i v e n tested value  i n Table  from  The  be  the  f o r e a c h e x a m p l e . The a c t u a l v a l u e o f w/w*'  ratio  cases  ranges i n  1.00 t o 2.31. I n g e n e r a l , t h e v a l u e s a r e  be i n t h e r a n g e f r o m  list  4.4 a r e a s i m p l e mean o f  found  1.00 t o 1.50.  w/w*'  i s an i n d i c a t o r o f p e r f o r m a n c e f o r t h e  o r d e r i n g h e u r i s t i c s c o m p a r e d . A l a r g e v a l u e o f w/w*' caused  by two r e a s o n s .  used f o r l i s t case  scheduling  i s t o be d i s c u s s e d  bound  may  may  Under c e r t a i n c o n d i t i o n s , any l i s t  results later  in  poor  performance.  i n the s p e c i f i c  1. The s e c o n d c a u s e o f a l a r g e v a l u e lower  to  underestimate  of  the  t e s t on E x a m p l e  w/w*'  length  This  is of  that  an  the  optimal  schedule. J a f f e ' s bound i s a v e r y operational very  precedence  l o o s e bound f o r c e r t a i n  constraints.  I f the p a r t i a l  h i g h l y c o n s t r a i n e d , s u c h a s E x a m p l e 8,  many  c h a i n s which a r e of approximately  c h a i n d e f i n i n g t h e h e i g h t , h. C o n s i d e r such c h a i n s d i f f e r Assume  the  processor  types  then,  of  order i s  there  are  t h e same l e n g t h a s t h e t h e c a s e where  several  f r o m t h e l o n g e s t c h a i n by o n l y a few t a s k s .  s e t of  processors  includes  a n d t h e bound f o r t h e o p t i m a l  t h e t a s k s on .the l o n g e s t c h a i n a r e  only a single  fast  i s d e f i n e d by h/b^. I f  executed  on  the  fastest  103  processors, tasks  with  processor the  then  the remaining  the  longest  chain  processors  chain.  may  in t h i s case. Table  be l o n g e r  than  is  schedules  situation  an e x a m p l e o f a t e s t  are  times  on a  to  portions  and  the  a comparison f o r J a f f e ' s lower  Example  1.  The  of  construction  an  length  bound f o r t h e  of  schedule  Fernandez  an  schedule.  schedule  the case of i d e n t i c a l p r o c e s s o r s .  i s i n c l u d e d as  the  four  lists.  shortens until  Gantt  t o an e x h a u s t i v e  chart  In  of the best  length  enables  to  method the  the lower  general,  is  the  the of  method bound i n  following  search. w i t h the i n s p e c t i o n  schedule  The t a s k a s s i g n m e n t s a r e swapped  the  schedule  The  is similar  The c o n s t r u c t i o n o f an o p t i m a l b e g i n s of  optimal  o f t h e p r e c e d e n c e c o n s t r a i n t s of  and B u s s e l l [ 2 5 ] f o r f i n d i n g  p r o c e d u r e amounts  of  bound.  optimal  o f an o p t i m a l  later.  lengths  1 and t h e s m a l l s i z e o f t h e s e t o f t a s k s  construction  of  structure  chain  run f o r a . p a r t i c u l a r  I n g e n e r a l , t h e p r o b l e m o f f i n d i n g an o p t i m a l The  of  f o r t h e s e t of  J a f f e ' s lower  The l e n g t h of an o p t i m a l  intractable.  slower  i s discussed  f o r Example  compared  l e n g t h o f t h e o p t i m a l , w*', w*.  schedule  share  the l e n g t h of the l o n g e s t  An e x a m p l e o f t h i s  4.5  of t h e s h a r e d  T h u s , an o p t i m a l  assignment of e x e c u t i o n  schedule,  must be e x e c u t e d  so d e l a y i n g t h e e x e c u t i o n  longest  the  t a s k s on t h e c h a i n s w h i c h  of the schedule.  resulting the  swapping  The s w a p p i n g  continues  no f u r t h e r i m p r o v e m a n t c a n be made.  if  from the  Processors  Cl C l Ci Cl Cl C l C i CI Cl Cz Cl C l Cl Ca Ci Ci  Ci C2 Cl  Cz  C1  Ci C]  E x e c u t i o n Time w MCLMT 70 62 88 67 67 90 78 78  HLF  CG  72 64 88 67 69 92 94 80  72 64 95 82 77 92 78 92  Table 4 . 5 : R e s u l t s f o r Example 1  RANDOM 72 62 93 82 82 92 94 104  .  w* '  w*  66 62 80 62 62 88 66 62  68 62 82 67 67 90 78 78  105  As an e x a m p l e , i t i s shown t h a t t h e l e n g t h of an schedule  f o r the  is  From t h e G a n t t c h a r t shown i n F i g u r e 4 . 7 ( b ) ,  68.  system can T12  to  tasks T11  The  and  T15  T11  executed  i n each of the  T9).  the  The  chain  f o r each  partition,  longest chain is  and  they  complete  the  on  the  for equal slow  each  i s executed  delay  on  before  cannot  of l e n g t h 38 u n i t s  execution  t o be times  be  of  execution  two  of  any of  the for  if  and they  the  lengths  i s ( T 1 , T4,  two  of the  slower  t h e t a s k s on the  tasks  t a s k s on  T5, in  A l l other processors  the  longest  not  on  the longest  executed  there are  executed and  the  the  chain.  i n less time,  sufficient  c o n c u r r e n t l y . The  the  processors tasks are  of t h e t a s k s a r e a s s i g n e d  p r o c e s s o r s . N o t e t h a t no b e n e f i t can  the e x e c u t i o n  T1 1,  i s optimal.  second p a r t i t i o n task  to  overlap.  fastest processor.  the the  In the  task  i s no  of  longest chain  l o n g e s t c h a i n do n o t  schedule  the  partition.  execution  partition  2  except  but  there  i s t h e sum  Therefore  the  partitions  then,  chain complete e x e c u t i o n .  Since  c )  2  i s of l e n g t h 38 u n i t s . E a c h t a s k  exectuted  tasks, i n the p a r t i t i o n  T1  third partitions  as e a r l y as p o s s i b l e ,  first  c ,  2  t o t h e p r e c e d e n c e c o n s t r a i n t s . T10  s e c o n d and  schedule  (c,, c ,  T h e r e i s no o v e r l a p b e t w e e n  l e n g t h of the o p t i m a l schedule  In the  d e f i n e d by  into three p a r t i t i o n s .  t o T21.  due  o v e r l a p the  the o p t i m a l  T7,  and  of t h e t a s k s  T10  may  are  be p a r t i t i o n e d  T14  execution  s e t of p r o c e s s o r s  optimal  the  three  t a s k s on  result  tasks the  to  of the  from d e l a y i n g  since  the  fast processor  the would  1 06  result 6  i n an e x e c u t i o n  time  of 8 u n i t s .  Hence, t h e o p t i m a l  is  units. In  the  third  partition,  consider  C1=(T16,T18,T21) a n d C 2 = ( T 1 6 , T 1 9 ) . C h a i n units  and  chain  C2  i s of l e n g t h  c h a i n s may be e x e c u t e d  fully  T16  i s executed  both  c h a i n s . I f T19 i s e x e c u t e d  the  actual  slower  processor,  time  on a s l o w e r  execution execution  the actual  executed  of t a s k s T15,  serially  of  Assume  s i n c e i t i s common t o processor,  execution  T17  the  on a s l o w e r and  T20  the p a r t i t i o n  on a s l o w  l e n g t h of t h e o p t i m a l  schedule  on t h e  f o r c h a i n C1  execution  time  processor.  Note t h e  does  since  processor  time  then, and f o r  I f t a s k s T18 a n d T21 a r e e x e c u t e d  then,  20  e i t h e r T19  f o r c h a i n C2 i s 23 u n i t s  i f T19 i s e x e c u t e d  time  length  processor.  on a s l o w e r  i s 28 a n d f o r c h a i n C2 i s 20. H e n c e , minimized  chains  18. S i n c e o n l y one o f t h e  the fast prcessor  execution  c h a i n C1 i s 22 u n i t s .  C1 i s o f  on t h e f a s t p r o c e s s o r ,  o r T18 a n d T21 must be e x e c u t e d on  the  not the  affect  tasks  i n 21 u n i t s  is  the  may be  o f t i m e . The  f o rthe t h i r d p a r t i t i o n  i s 22  un i t s . The  length  of  lengths of the optimal  the  optimal  schedules  schedule  i s t h e sum o f t h e  f o r each p a r t i t i o n .  w*=38+6+22=67 The l e n g t h o f an o p t i m a l  schedule  1 on t h e s e t o f p r o c e s s o r s units.  f o rthe execution  d e f i n e d by ( c  1  f  c , c, 2  2  of Example c ) 2  i s 68  107  A  comparison  between J a f f e ' s  of an o p t i m a l s c h e d u l e  indicates  is  to  relatively  However, n o t e The  close  the  significant yields  amount,  a poor  that,  schedule  of  exceeds  the  In  illustrated  single  fast  i n Figure  processor  a l s o met i n t h e l a s t  processor  arbitrary  two  of  altering  /T„;„ <bT/b ^ the t h i r d  test,  value  significantly  t h e bound  optimal,  as  that a  behavior  is  verified  f o r test  procedure runs  outlined i n  to  examine  the  t h e s e p a r a m e t e r s a r e shown i n A p p e n d i x B.  In the f i r s t slower  an  a  1 are highly constrained  This  parameters a r e changed t o a l t e r  large  of  parameters i n the experimental  and  case,  by  s p e e d s a n d t h e maximum e x e c u t i o n t i m e s a r e  effect  times  bound  relations.  4.3. Sample r e s u l t s  bi/b^.  bound  schedule.  4.2. The s e c o n d c o n d i t i o n ,  cases.  Chapter  The  the  i s included i n the s e t of processors, i s  using the other precedence The  the  this  length  d e s c r i b e d a b o v e . The t a s k s o f E x a m p l e as  i n general,  two s e t s o f p r o c e s s o r s t e s t e d .  w*'/w*=1.26.  estimate  bound a n d t h e l e n g t h  l e n g t h o f an o p t i m a l  that for the last  l e n g t h o f an o p t i m a l  lower  test,  /r^, =b, /b n  speeds  are  i sachieved T^^/T^U  for affect  .  the ratios,  used.  n  W  / T  and l o n g e r  In  by u s i n g v e r y  >b,/b „ i s a c h i e v e d I n each t e s t ,  T  the  W  I  H  and  execution  second  test,  slow p r o c e s s o r s . I n by t h e  use  of  a  t h e parameters d i d not  t h e dominance o f t h e proposed  heuristic,  MCLMT. The to  final  test  on E x a m p l e 1 i l l u s t r a t e s t h e r e s t r i c t i o n  u n i t e x e c u t i o n t i m e s . N o t e t h a t t h e HLF a n d t h e MCLMT  lists  108  generate  t h e same s c h e d u l e . T h i s b e h a v i o r i s v e r i f i e d  o t h e r p r e c e d e n c e r e l a t i o n s . The processors which The of  schedules  Coffman  scheduling strategy  yields  a n d Graham A l g o r i t h m A l i s t  t h e same l e n g t h a s t h e HLF l i s t  final  observation  list,  described  t e s t e d , t h e MSCMT l i s t of  poor  performance.  generates a schedule  a n d t h e MCLMT  list.  This  order.  i n the results  b e t w e e n t h e s c h e d u l e s g e n e r a t e d by MSCMT  of  i s due to~ t h e u n i t e x e c u t i o n t i m e s a n d t h e r e l a t i v e l y  simple s t r u c t u r e of t h e p a r t i a l A  f o r the sets  i n c l u d i n g c, a r e f u r t h e r examples of s i t u a t i o n s i n  the l i s t  behavior  with the  is a  comparison  list  and t h e  t h e MCLMT  i n Chapter  4.2.  a n d t h e MCLMT l i s t  O v e r t h e 160 c a s e s  generated  schedules  t h e same l e n g t h i n 121 o f t h e c a s e s . I n 20 o f t h e c a s e s t h e  MCLMT  list  generated a better  t h e MSCMT l i s t  s c h e d u l e a n d i n 19 o f t h e c a s e s  generated a better  schedule. This  t h e n o t i o n t h a t t h e two h e u r i s t i c s a r e a l m o s t  agrees  identical.  with  109  CHAPTER 5 CONCLUSIONS AND SUGGESTIONS FOR FURTHER RESEARCH  5.1 Summary a n d A  Petri  Conclusions  net  formulation  f o r the  problem i s developed i n t h i s  thesis.  is  of  b a s e d upon t h r e e c l a s s e s  timed to  Petri  the  general  nets and c o l o u r e d  formulation begins scheduling  scheduling  of  the P e t r i  definition  the  main  Petri  configuration  nets  a task  to  formulation  resource arises  improve  and  the  has  here,  cannot  then the  their  ability  Schedules are e a s i l y  executing  the P e t r i  The  net formulation  The  the algorithm f o r the  n e t f o r m u l a t i o n may be on  the  formal  problem. Petri  net formulation are in  the a b i l i t y  processor  which  s y s t e m on d i f f e r e n t  Petri  of  net model.  i s g e n e r a t e d by  i n g e n e r a l . As p r e s e n t e d  formulation presented  situation.  the s t r u c t u r e of the  transformation  scheduling  advantages  net  of  extended  approach  n e t . A schedule  of the g e n e r a l  of P e t r i  variety  n e t s . The g e n e r a l  by e x p r e s s i n g  of a  net formulation graphs,  n e t . The P e t r i  thought of as t h e r e s u l t  scheduling  marked  s t r a t e g y i s m o d e l e d by m o d i f y i n g  execution  these  nets,  problem i n terms of a P e t r i  the a n a l y s i s of the P e t r i  The  The P e t r i  Petri  Petri  general  this  thesis,  t o model a wide  configurations. be  modeled  Petri  nets  to  model  If  under are a  a the  easily  particular  generated f o r t h e e x e c u t i o n of  sets of i n i t i a l  n e t model w i t h d i f f e r e n t  resources initial  i s a compact a n d n a t u r a l  by  simply  markings.  description  1 10  of  the general  scheduling  The l o g i c a l and  the  problem.  separation  modeling  of  of the modeling of  the behavior  the  structure  i n the scheduling  problem  a l l o w s c h a n g e s t o made i n e i t h e r t h e s t r u c t u r e o r t h e  behavior  of t h e problem w i t h o u t analysed  in  processors to  Chapter  independently.  Consider  4, n a m e l y , l i s t  scheduling  of d i f f e r e n t  be f u n c t i o n a l l y  set  of  dedicated  scheduling  coloured  and t o  processors to  strategy  is  of d i f f e r e n t  model t h e s c h e d u l i n g  same.  The  logical  be  of  Suppose  s t r a t e g y and t h e P e t r i  two  i s defined to  subject to c o n f l i c t  Petri  disadvantages  net f o r m u l a t i o n takes  transitions,  the  modified  net remains the  also  i n the  f o r m u l a t i o n . The  advantage of the assumption that a  fire  earliest  natural representation is  different  flexibility  to their  as  soon  r e s o l u t i o n . Since  n e t f o r m u l a t i o n . The  transition  a  s e p a r a t i o n of the modeling of the behavior  of t h e f o r m u l a t i o n .  transition  i s m o d e l e d by  s p e e d s . The GRID a n a l y s i s i s  use  Petri  speeds  d e s i r e d t o be m o d e l e d f o r t h e s e t o f  of t h e s t r u c t u r e of systems p r o v i d e s  are  a r e now  different  instead,  and  There  f o r a s e t of  tokens but the a n a l y s i s modeling the l i s t  remains unchanged.  scheduling  problem  speeds. Suppose t h e p r o c e s s o r s  w i t h i n a f u n c t i o n a l g r o u p . The s e t o f p r o c e s s o r s a  the  as  i t  is  enabled,  t h e t a s k s a r e modeled as  schedules formulation  a r e g e n e r a t e d under t h e does  not  include  a  f o r the modeling of a r b i t r a r y d e l a y s . A assumed  u n i n t e r r u p t e d once i t b e g i n s  to  fire  firing.  completely This  notion  a n d t o be prevents  111  consideration  of  preemptive  t h e s e d i s a d v a n t a g e s may implementation the  of  be o v e r c o m e by  the  use o f t h e  scheduling  i n Chapter  Petri  problem  Note  t h a t both of  modifications  the  tasks.  net  formulation  i s demonstrated  heuristic The  in l i s t  i s proposed  of  the  are  in  scheduling  and  which  are  list.  In  generated a better as  additional  5.2  generated  by  are  the  execution  compared  to  the h i g h e s t l e v e l s  the first  a  randomly  comparisons, the proposed  heuristic  s c h e d u l e i n 98 o f 160 c a s e s as  in  at  least  one  other  tested schedule  and  a  i n an  160 c a s e s .  Suggestions for Further Research The m a j o r  use  good  39 o f  of  schedules which  h e u r i s t i c , A l g o r i t h m A o f C o f f m a n and Graham, and  schedule  list  decreasing  l e n g t h s . The  g e n e r a t e d by t h e p r o p o s e d h e u r i s t i c  generated  f o r the  different  f o r o r d e r i n g the  length,  t h e c a s e of e q u a l c h a i n  schedules  general  p r o p o s e d h e u r i s t i c , MCLMT, o r d e r s t h e l i s t  order of d e c r e a s i n g c h a i n time  the  4.  e x e c u t i o n o f a t a s k s y s t e m on a s e t o f p r o c e s s o r s of s p e e d s . A new  to  b e h a v i o r a l a n a l y s i s which i s used f o r  s t u d y of the problem The  strategies.  of  suggestion for further  the P e t r i  presented  in this  problem.  The  r e s e a r c h i s the  n e t f o r m u l a t i o n . The thesis  is  a  use o f t h e  relatively  simple  scheduling problem d i s c u s s e d l i s t  a simple resource structure c o n s i s t i n g p r o c e s s o r s of d i f f e r e n t  speeds.  of  a  further  formulation scheduling  scheduling for single  set  of  112  The  formulation  s t r a t e g i e s other noted  in  than  difference  the the  problem  assigned result  be  list  used  to  evaluate  scheduling.  List  t h e c o m p a r i s o n of t h e h e u r i s t i c s ,  poor performance i n  The  may  the  case  where  s p e e d of t h e  with  list  t o a slow  scheduling  processor  i f the e x e c u t i o n  when  is a  of t h e t a s k  scheduling, i s known t o  there  f a s t e s t and  scheduling  exists  that  t a s k may  would  until a  faster  i s delayed  i s a v a i l a b l e . This s i t u a t i o n  suggests  strategy  may  situation. A  strategy  better in this  The  formulation  i n Chapter  may  be  e f f e c t s of more s t r u c t u r e d processors specified shown  which no  was  the  between  the  and  elements  a r c h i t e c t u r e , may  the t r a n s i t i o n such  as  tokens.  of  through  The  of  the  set  of  processors.  of  modeling  a  the t r a n s i t i o n  is  an  relationship  reconfigurable  t h e use  imposed  4  reconfigurable  special the  It  of a s e t  schemes. O t h e r r e l a t i o n s  those  be m o d e l e d u s i n g  resources,  net  f o r the comparisons i n Chapter  i s modeled n a t u r a l l y  resources,  coloured data  resources.  r e s o u r c e s . The  computing  tokens  f o r the  of  formulation i s capable  s t r u c t u r e i n the  architecture  sets  used  arbitrary  sets  look-ahead  used f o r the examination  example of the d y n a m i c a l l y  a r c h i t e c t u r e t h a t the  the  look-ahead  3.  i n t e r c o n n e c t i o n s between the  through  coloured  a  i s w i t h i n the m o d e l i n g c a p a b i l i t i e s of the P e t r i  f o r m u l a t i o n as p r e s e n t e d  be  schedule  processor  perform  large  processor.  a  better  yield  a  slowest  as  by  combination schemes and  a  of in  network  of  colour  the  set  of  1 1 3  The from  final  the  theory.  The  arbitrary  suggestion  scheduling Petri  net  for  further  takes  ideas  problem to suggest changes i n P e t r i formulation  d e l a y s , or the p a r t i a l  i s unable firing  has  a time d u r a t i o n a s s o c i a t e d w i t h  net  theory  these  research  model  either  of a t r a n s i t i o n  i t . Extension  t o a l l o w c o n s i d e r a t i o n of P e t r i  modeling c h a r a c t e r i s t i c s  to  of t h e  nets which  is desirable.  net  which Petri  possess  11 4  Bibliography  1.  Adam, T.L., Chandy, K.M., D i c k s o n , J.R., "A Comparision of L i s t S c h e d u l e s f o r P a r a l l e l P r o c e s s i n g S y s t e m s , " Comm. ACM, V o l . 1 7 ( 1 2 ) , Dec. 1974, p. 685-590.  2.  Agerwala, T., "Some A p p l i c a t i o n s o f P e t r i N e t s , " P r o c . N a t i o n a l E l e c t r o n i c s C o n f . , V o l . 32, 1978, p. 149-157.  3.  A g e r w a l a , T., C h u e d — A m p h a i , Y—C., " S y n t h e s i s Rule f o r Concurrent Systems," P r o c . 15th D e s i g n Automation Conf., J u n e 1978, p. 3 0 5 - 3 1 1 .  4.  A p p e l b e , W.F., I t o , M.R., "Scheduling H e u r i s t i c s in a Multiprogramming Environment," IEEE Trans. Computers, V o l . C - 2 7 ( 7 ) , J u l y 1978, p. 628-637.  5.  A r a k i , T., K a s a m i , T., "Some D e c i s i o n P r o b l e m s R e l a t e d t o the R e a c h a b i l i t y Problem f o r P e t r i N e t s , " Theor. Comput. S c i . , V o l . 3, 1977, p. 8 5 - 1 0 4 .  6.  Araki, T., K a s a m i , T., " D e c i d a b l e P r o b l e m s on t h e S t r o n g C o n n e c t i v i t y of Petri Net Reachability Sets," Theor. Comput. S c i . , V o l . 4, 1977, p. 99-119.  7.  Ayache, J.M., Azema, P., D i a z , M., " O b s e r v e r : A c o n c e p t f o r O n — l i n e D e t e c t i o n of Control Errors i n Concurrent Systems," Proc. 9th Int'l. Symp. Fault-Tolerant C o m p u t i n g , 1979, p. 79-86.  8.  Azema, P., V a l e t t e , R., D i a z , M., " P e t r i N e t s as a Common Tool f o r Design V e r i f i c a t i o n and Hardware Simulation," P r o c . 1 3 t h D e s i g n A u t o m a t i o n C o n f . , 1976,. p. 109—116.  9.  Baer, J—L., E l l i s , C.S., " M o d e l , D e s i g n , and E v a l u a t i o n of a C o m p i l e r f o r a P a r a l l e l Processing Environment," IEEE Trans. Software E n g i n e e r i n g , V o l . S E - 3 ( 6 ) , Nov. 1977, p. 394-405.  10.  B e r l i n , F.B., " T i m e - e x t e n d e d P e t r i Nets," U n i v e r s i t y o f T e x a s a t A u s t i n , 1979.  11.  Berthelot, G., R o u c a i r o l , G., " R e d u c t i o n o f P e t r i N e t s , " M a t h e m a t i c a l F o u n d a t i o n s o f Computer S c i e n c e , 1976, p. 202-209.  12.  B e s t , E., S c h m i d , H.A., " S y s t e m s o f Open P a t h e s i n P e t r i Nets," M a t h e m a t i c a l F o u n d a t i o n s o f Computer S c i e n c e , 1975, p. 186-193.  M.A.  Thesis,  115  13.  Brauer, W., Springer-Verlag,  ed., Net T h e o r y and (New Y o r k , 1 9 8 0 ) .  Applications,  14.  C o f f m a n , E.G., J r . , Graham, R.L., " O p t i m a l S c h e d u l i n g f o r Two—Processor Systems," Acta Informatica, V o l . 1(1), 1972, p. 203-213.  15.  C o f f m a n , E.G., J r . , Denning, P.J., Operating Theory, P r e n t i s s - H a l l , (Toronto, 1973).  16.  C o f f m a n , E.G., J r . , e d . , Computer and J o b Shop S c h e d u l i n g Theory, John W i l e y ( T o r o n t o , 1976).  17.  Commoner, F., H o l t , A.W., E v e n , S., P n u e l i , A., "Marked D i r e c t e d G r a p h s , " J . Comput. S y s t . S c i . , V o l . 5 ( 5 ) , 1971, p. 511-523.  18.  C o n t r o n i s , J.Y., L a u e r , P.E., " V e r i f i c a t i o n o f C o n c u r r e n t Systems of P r o c e s s e s , " Proc. Int'l. C o m p u t i n g Symp., 1977, p. 197-207.  19.  Courvoisier, M., Valette, R., "Description and R e a l i z a t i o n of P a r a l l e l C o n t r o l S y s t e m s , " P r o c . 1 5 t h I E E E F a l l COMPCON, 1977, p. 167-172.  20.  Courvoisier, M., Seek, J . P . , "Hardware I m p l e m e n t a t i o n o f G e n e r a l i z e d P e t r i Nets," E l e c t r o n i c L e t t e r s , V o l . 15(24), 22 Nov. 1 9 7 9 , p.770-772.  21.  Cox, L.A., J r . , " P r e d i c t i n g C o n c u r r e n t Computer System Performance Using Petri Net Models," Proc. 1978 ACM A n n u a l C o n f . , 1978, p. 9 0 1 - 9 1 3 .  22.  Crespi-Reghizzi, S., Mandroili, D., "Some Algebreic Properties of P e t r i Nets," A l t a Frequenza, V o l . 45(2), F e b . 1976, p. 130-137.  23.  Devy, M., Diaz, M., "Multilevel Specification and Validation of the C o n t r o l i n Communication Systems," P r o c . I n t ' l . C o n f . D i s t r i b u t e d Computer S y s t e m s , 1979, p. 43-50.  24.  E c k e r , K., " A n a l y s i s o f a S i m p l e S t r a t e g y Constrained Task Scheduling," Proc. P a r a l l l e l P r o c e s s i n g , 1978, p. 181-183.  25.  F e r n a n d e z , E.B., B u s s e l l , B., "Bounds on t h e Number o f Processors and Time for Multiprocessor Optimal S c h e d u l e s , " IEEE T r a n s . Computers, V o l . C - 2 2 ( 8 ) , Aug. 1973, p. 7 4 5 - 7 5 1 .  Systems  f o r Resource Int'l. Conf.  1 16  26.  Garey, M.R., Graham, R.L., "Bounds f o r M u l t i p r o c e s s o r S c h e d u l i n g w i t h R e s o u r c e C o n s t r a i n t s , " SIAM J . C o m p u t i n g , V o l . 4 ( 4 ) , 1975, p. 187-200.  27.  Garey, M.R., Johnson, D.S., "Complexity Results for Multiprocessor S c h e d u l i n g Under Resource C o n s t r a i n t s . " SIAM J . C o m p u t i n g , V o l . 4 ( 2 ) , 1975, p. 3 9 7 - 4 1 1 .  28.  Gonzales, M.J., Scheduling," ACM 173-204.  29.  G o n z a l e s , T., I b e r r a , O.H., S a h n i , S., "Bounds for LPT Schedules on U n i f o r m P r o c e s s o r s , " SIAM J . Comput., V o l . 6 ( 1 ) , 1977, p. 155-166.  30.  G o y a l , D.K., " S c h e d u l i n g E q u a l E x e c u t i o n Time T a s k s Under Unit Resource R e s t r i c t i o n , " Proc. I n t ' l . Conf. Parallel P r o c e s s i n g , 1 9 7 8 , p. 188-192.  31.  Grabowski, J . , "The Unsolvabi1ity o f Some Language P r o b l e m s , " I n f . P r o c e s s i n g L e t t . V o l . Aug. 1979, p. 60-63.  32.  Grenrich, H.J., Lautenbach, K., "The Analysis of Distributed Systems by Predicate/Transition Nets," Semantics of Concurrent Computation, Springer—Verlag, (New Y o r k , 1 9 7 9 ) , p. 123-146.  33.  Han, Y.H., " P e r f o r m a n c e E v a l u a t i o n of a Digital System Using a Petri N e t - L i k e Approach," Proc. National E l e c t r o n i c s C o n f . , V o l . 32, 1978, p. 168-172.  34.  H e i m e r d i n g e r , W.L., Han, Y.H., "A Graph Theoretic Approach t o F a u l t T o l e r e n t Computing," F i n a l R e p o r t , A i r Force Office of Scientific Research, Contract No. F 4 4 6 2 0 - 7 5 - C - 0 0 5 3 , S e p t . 1977.  35.  H e i m e r d i n g e r , W.L., "A P e t r i n e t A p p r o a c h t o S y s t e m L e v e l Fault Tolerence Analysis," Proc. National E l e c t r o n i c s C o n f . , V o l . 32, p. 161-165.  36.  H e r z o g , O., "Automatic Deadlock Analysis of Parallel P r o g r a m s , " P r o c . I n t . C o m p u t i n g Sypm., 1977, p. 209-216.  37.  Herzog, 0., " S t a t i c A n a l y s i s o f C o n c u r r e n t P r o c e s s e s f o r Dynamic Properties Using P e t r i Nets," S e m a n t i c s of Concurrent Computation, Springer-Verlag, (New York, 1 9 7 9 ) , p. 66-90.  Jr., Computing  "Deterministic Processor S u r v e y s , V o l . 9 ( 3 ) , 1977, p.  P e t r i Net 9(2), 17  117  38.  Irani, K.B., Z e r v o s , C.R., Priority Hierarchies and Synchronization Structures," P a r a l l e l P r o c e s s i n g , 1979, p .  "Modelling of Conflicts, Reentrancy i n Concurrent Proc. 1979 Int'l. Conf. 196-204.  39.  Izbicki, H., "Marked Graphs With R u l e s , " P r o c . Symp. Recent Advances 1974, p . 307-310.  40.  Jaffe, J.M., " E f f i c i e n t S c h e d u l i n g w i t h o u t t h e F u l l Use of P r o c e s s o r R e s o u r c e s , " T h e o r . Comput. S c i . V o l . 1 2 ( 1 ) , 1980, p.1-17.  41.  Janicki, R., "A Characterization of Concurrency-like Relations," Semantics of Concurrent C o n f u t a t i o n , S p r i n g e r - V e r l a g , (New Y o r k , 1979), p. 109-122.  42.  J a n t z e n , M., "On t h e H i e r a r c h y o f P e t r i N e t L a n g u a g e s , " RAIRO I n f . T h e o r . / T h e o r . Inf., Vol. 13(1), 1979, p. 19-30.  43.  Jones, N.D., Landweber, L.H., L i e n , Y.E., " C o m p l e x i t y o f Some P r o b l e m s i n P e t r i N e t s , " T h e o r . Comput. Sci., Vol. 4, 1977, p . 277-299. ••,  44.  K a r p , R.M., M i l l e r , R.E., " P a r a l l e l P r o g r a m S c h e m a t a , " Comput. S y s t . S c i . , V o l . 3, 1969, p . 147-195.  45.  Kartashev, S . I . , K a r t a s h e v , S.P., "Dynamic A r c h i t e c t u r e : P r o b l e m s and S o l u t i o n s , " Computer, V o l . 1 1 ( 7 ) , J u l y 1978, p.26-40.  46.  K a r t a s h e v , S . I . , K a r t a s h e v , S.P., "A M u l t i c o m p u t e r S y s t e m w i t h Dynamic A r c h i t e c t u r e , " I E E E T r a n s . C o m p u t e r s , Vol. C - 2 8 ( 1 0 ) , O c t . 1979, p. 704-721.  47.  K a s a m i , T., M i l l e r , R.E., "Homomrphisms Between M o d e l s o f Parallel Computation," IBM Research Report, RC-7796, 1979.  48.  Kwong, Y.S., "On Absence of Livelocks in Parallel Programs," Semantics of C o n c u r r e n t Computation, S p r i n g e r - V e r l a g , (New Y o r k , 1 9 7 9 ) , p . 172-1.90.  49.  L a u e r , P.E., Campbell, R.H. , "A Description of Path Expressions by Petri Nets," Proc. 2nd ACM Symp. P r i n c i p l e s o f Programming L a n g u a g e s , 1975,. p . 95—105.  50.  L a u e r , P.E., C a m p b e l l , R.H., "Formal S e m a n t i c s of a C l a s s of H i g h Level Primatives for Coordinating Concurrent P r o c e s s e s , " A c t a I n f o r m a t i c a , V o l . 5, 1975, p . 297-332.  Generalized i n Graph  Firing Theory,  J.  1 18  51.  L a u t e n b a c h , K., S c h m i d , H.A., "Use o f P e t r i N e t s f o r Proving Correctness of Concurrent Process Systems," I n f o m a t i o n P r o c e s s i n g '74, 1974, p. 181-191.  52.  Lien, Y.E., "A N o t e on T r a n s i t i o n S y s t e m s , " S c i e n c e s , V o l . 10, p.347-362.  53.  L i e n , Y.E., " T e r m i n a t i o n P r o p e r t i e s o f G e n e r a l i z e d Petri N e t s , " SIAM J . Comput., V o l . 5 ( 2 ) , J u n e 1976, p. 2 5 1 - 2 6 5 .  54.  Lipton, R . J . , " R e d u c t i o n : A Method o f P r o v i n g P r o p e r t i e s o f P a r a l l e l P r o g r a m s , " CACM., V o l . 1 8 ( 1 2 ) , D e c . 1975, p. 717-721.  55.  Lipton, R . J . , "The Reachability Problem E x p o n e n t i a l Space," Y a l e U n i v e r s i t y , Dept. of S c i e n c e , R e s e a r c h R e p o r t No. 6 2 , J a n . 1976.  56.  L i u , J.W.S., L i u , C.L., "Bounds on S c h e d u l i n g A l g o r i t h m s for Heterogeneous Computing Systems," Information P r o c e s s i n g 74, North—Holland, (Amsterdam, 1974), p7 349-353.  57.  L i u , J.W.S., L i u , C.L., "Performance Analysis of Multiprocessor Systems C o n t a i n i n g F u n c t i o n a l l y D e d i c a t e d Processors," Acta Informatica, V o l . 10(1), 1978, p. 95-104.  58.  M a n a c h e r , G.K., " P r o d u c t i o n a n d S t a b l i z a t i o n o f R e a l - T i m e Task S c h e d u l e s , " J . ACM, V o l . 1 4 ( 3 ) , July 1967, p. 439-465.  59.  Mandroili, D., "A N o t e on Petri Net Languages," Information and C o n t r o l , V o l . 34(2), June 1977, p. 169-171.  60.  M a r t i n , D.E., E s t r i n , G., "Experiments and Systems," IEEE T r a n s . E l e c t r o n i c E C - 1 6 ( 1 ) , F e b . 1967, p. 59-69.  61.  M e i l i n g , E., "On t h e M o d e l l i n g Power of P e t r i D e p t . o f Computer S c i e n c e , C o r n e l l , TR79-403.  62.  Merlin, P.M., "A Methodology f o r t h e Design and Implementation of Communication P r o t o c o l s , " IEEE T r a n s . C o m m u n i c a t i o n s , V o l . C O M - 2 4 ( 6 ) , J u n e 1976, p. 6 1 4 - 6 2 1 .  63.  Merlin, P.M., Farber, D.J., "Recoverability of Communication Protocols-Implications of a Theoretical S t u d y , " IEEE T r a n s . C o m m u n i c a t i o n s , V o l . COM-24(9), S e p t . 1976, p. 1036-1043.  Information  Requires Computer  on C o m p u t a t i o n s Computers, V o l . Nets,"  1 19  64.  Miller, R.E., K a s a m i , T., " C o m p a r i n g M o d e l s o f P a r a l l e l Computation by Homomorphisms," Proc. COMPSAC, 1979, p.794-799.  65.  Memmi, G., "Notion de D u a l i t y e t de S y m e t r i e Dans l e s R e s e a u x de P e t r i , " Semantics of Concurrent Computation, S p r i n g e r - V e r l a g , (New Y o r k , 1 9 7 9 ) , p. 9 1 - 1 0 8 .  66.  M i s u n a s , D., " P e t r i N e t s a n d Speed I n d e p e n d e n t D e s i g n , " CACM, V o l . 1 6 ( 8 ) , A u g . 1973, p . 474-480.  67.  M u r a t a , T., " S t a t e E q u a t i o n , C o n t r o l a b i l i t y and Maximal Marking of P e t r i N e t s , " IEEE T r a n s . A u t o m a t i c C o n t r o l , V o l . A C - 2 2 ( 2 ) , J u n e 1977, p. 412-416.  68.  M u r a t a , T., " C i r c u i t T h e o r e t i c A n a l y s i s a n d S y n t h e s i s o f Marked Graphs," IEEE T r a n s . C i r c u i t s and Systems, V o l . CAS-24, J u l y 1977, p. 400-405.  69.  M u r a t a , T., K o h , J . Y . , " R e d u c t i o n a n d E x p a n s i o n o f L i v e and S a f e Marked Graphs," Proc. 1979 ISCAS, 1979, p. 841-844.  70.  M u r a t a , T., " S y n t h e s i s o f M a r k e d G r a p h C o m p u t a t i o n M o d e l s f o r P r e s c r i b e d R e s o u r c e s a n d P e r f o r m a n c e , " P r o c . COMPSAC, 1979, p. 807-812.  71.  Noe, J.D., N u t t , G . J . , "Macro E - N e t s f o r Representation of Parallel Systems," IEEE T r a n s . Computers, V o l . C - 2 2 ( 8 ) , A u g . 1973, p . 7 1 8 - 7 2 7 .  72.  Noe, J.D., C r o w l e y , C P . , A n d e r s o n , T.L., " D e s i g n I n t e r a c t i v e G r a p h i c a l N e t E d i t o r , " P r o c . CIPS-ACM R e g i o n a l Symp., 1974, p. 386-402.  73.  Noe, J.D., " H i e r a r c h i c a l M o d e l l i n g W i t h P r o N e t s , " P r o c . N a t i o n a l E l e c t r o n i c s C o n f . , V o l . 3 2 , 1978, p. 155-160.  74.  Pacas-Skewes, E., "A D e s i g n M e t h o d o l o g y for Digital Systems Using P e t r i N e t s , " Ph.D. T h e s i s , U n i v e r s i t y o f T e x a s , A u s t i n , 1979.  75.  P a t i l , S.S., " A s y n c h r o n o u s TM-62, May 1975.  76.  Patil, S.S., " C o o r d i n a t i o n o f A s y n c h r o n o u s E v e n t s , " MIT P r o j e c t MAC, TR-62, J u n e 1970.  77.  P e t e r s o n , J . L . , " C o m p u t a t i o n Sequence S e t s , " S y s t . S c i . , V o l . 1 3 ( 1 ) , 1976, p. 1-24.  Logic  Array,"  o f an Pacific  Project  J.  MAC,  Comput.  1 20  78.  Peterson, J.L., "Petri Nets," 9 ( 3 ) , S e p t . 1977, p. 223-252.  Computing S u r v e y s , V o l .  79.  P e t e r s o n , J . L . , "A N o t e on C o l o r e d P e t r i Nets," I n f . P r o c e s s . L e t t . , V o l . 1 1 ( 1 ) , 29 A u g . 1980, p. 40-44.  80.  Ramamoorthy, C.V., F o x , T.F., L i , H.F., "Scheduling P a r a l l e l P r o c e s s a b l e Tasks f o r a U n i p r o c e s s o r , " IEEE T r a n s . C o m p u t e r s , V o l . C - 2 5 ( 5 ) , May 1976, p . 4 8 5 - 4 9 5 .  81.  Ramamoorthy, C.V., Ho, G.S., " P e r f o r m a n c e E v a l u a t i o n o f Asynchronous C o n c u r r e n t Systems U s i n g P e t r i Nets," IEEE T r a n s . S o f t w a r e E n g i n e e r i n g , V o l . S E - 6 ( 5 ) , S e p t . 1980, p. 440-449.  82.  Ramachandani, C , "Analysis of Asynchronous Concurrent S y s t e m s By P e t r i N e t s , " MIT P r o j e c t MAC, TR-120, F e b . 1 974.  83.  S c h i f f e r s , M. , Wedde, H., " A n a l y s i n g P r o g r a m S o l u t i o n s o f Coordination Problems by CP—Nets," Mathemat i c a l F o u n d a t i o n s o f Computer S c i e n c e , S p r i n g e r — V e r l a g , (New Y o r k , 1 9 7 8 ) , p. 4 6 2 - 4 7 3 .  84.  S h a p i r o , R.M., S a i n t , H., "A New A p p r o a c h t o O p t i m i z a t i o n of Sequencing D e c i s i o n s , " Automaatic Programming, V o l . 6 ( 5 ) , 1970, p. 2 5 7 - 2 8 8 .  85.  S h a p i r o , S.D., "A S t o c h a s t i c P e t r i Net w i t h Applications to Modelling Occupancy Times f o r Concurrent Task S y s t e m s , " N e t w o r k , V o l . 9, 1979, p. 375-379.  86.  Sifakas, J . , "Use o f P e t r i Nets for Performance Evaluation," P r o c . 3 r d I n t ' l . Symp. M e a s u r i n g , M o d e l l i n g and E v a l u a t i n g Computer S y s t e m s , 1977, p. 7 5 — 9 3 .  87.  S i f a k a s , J . , " R e a l i z a t i o n of F a u l t T o l e r e n t S y s t e m s by C o d i n g P e t r i N e t s , " P r o c . 8 t h I n t ' l . Symp. F a u l t T o l e r e n t C o m p u t i n g , 1978, p. 2 0 5 .  88..  Sifakas, J . , "Structural Properties of P e t r i M a t h e m a t i c a l F o u n d a t i o n s o f Computer S c i e n c e , S p r i n g e r - V e r l a g , (New Y o r k , 1 9 7 8 ) , p. 4 7 4 - 4 8 3 .  89.  S i l v a , M., D a v i d , R., "Programmed S y n t h e s i s o f A u t o m a t i c L o g i c D e s c r i b e d by P e t r i N e t s : A M e t h o d o f I m p l e m e n t a t i o n on a M i c r o c o m p u t e r , " RAIRO A u t o m / S y s t . A n a l , e C o n t r o l , V o l . 1 3 ( 4 ) , p. 369-393  Nets,"  121  90.  S t a r k , P.H., "Free Petri Net Languages," Mathematical F o u n d a t i o n s o f Computer S c i e n c e , Springer-Verlag, (New Y o r k , 1 9 7 8 ) , p. 506-515.  91.  Szlanko, J . , " P e t r i Nets f o r P r o v i n g Some C o r r e c t n e s s Properties of Parallel Programs," Proc. IFAC/IFIP W o r k s h o p on R e a l Time P r o g r a m m i n g , 1977, p. 7 5 — 8 3 .  92.  T a n i , K., M u r a t a , T., " S c h e d u l i n g P a r a l l e l Computations with Storage Constraints," Proc. 12th A s i l o m a r Conf. C i r c u i t s , S y s t e m s and C o m p u t e r s , 1978, p. 7 3 6 - 7 4 3 .  93.  T a n i , K., Onaga, K., K a k u s h o , 0., " M o d e l i n g and Analysis of R e s o u r c e — C o n s t r a i n e d N e t w o r k P r o b l e m s by P e t r i N e t s , " P r o c . I n t ' l . Conf. C y b e r n e t i c s and Society, 1978, p. 884-888.  94.  Valette, R., "Analysis of Petri Nets by R e f i n e m e n t s , " J . Comput. S y s t . S c i . , V o l . 18, 35-46.  95.  V a l k , R., "On Computational Power of Extended P e t r i Nets," M a t h e m a t i c a l F o u n d a t i o n s o f Computer S c i e n c e , S p r i n g e r - V e r l a g , (New Y o r k , 1 9 7 8 ) , p. 5 2 6 - 5 3 5 .  96.  Van Leuwen, J . , "A P a r t i a l S o l u t i o n t o t h e R e a c h a b i l i t y Problem f o r Vector A d d i t i o n Systems," Proc. 6th Symp. T h e o r y o f C o m p u t i n g , 1974, p. 303-304.  97.  Vick, CR., K a r t a s h e v , S . I . , K a r t a s h e v , S.P., "Adaptable A r c h i t e c t u r e s f o r Supersystems," Computer, V o l . 13(11), Nov. 1980, p. 17-35.  98.  Voss, K., " U s i n g P r e d i c a t e / T r a n s i t i o n N e t s t o Model and Analyse Distrbuted Database Systems," Proc. COMPSAC, 1979, p. 801-806.  99.  Winter, R., "An E v a l u a t i o n Net M o d e l f o r t h e P e r f o r m a n c e E v a l u a t i o n o f a Computer N e t w o r k , " P r o c . 3 r d I n t ' l . Symp. M e a s u r i n g , M o d e l l i n g and E v a l u a t i n g Computer Systems, 1979, p. 95-113.  100.  Yoeli, M. , G i n s b e r g , A., " P e t r i Net L a n g u a g e s and T h e i r Applications," University of Waterloo, Faculty of M a t h e m a t i c s , R e s e a r c h R e p o r t CS-78-45, Nov. 1978.  101.  Zervos, C.R., Irani, K.B., "Colored P e t r i Nets: Their P r o p e r t i e s and A p p l i c a t i o n s , " RADC-TR-77-246, Aug. 1977.  Stepwise 1979, p.  1 22  Zuberek, W.M., "Timed Petri Nets and Preliminary Performance Evaluation," Proc. 7 t h Symp. Computer A r c h i t e c t u r e , 1980, p. 88-96.  123  Appendix A D e f i n i t i o n s  Petri  and N o t a t i o n  Net N o t a t i o n  n i s t h e number o f p l a c e s . m i s t h e number o f t r a n s i t i o n s .  Scheduling  Notation  n i s t h e number o f p r o c e s s o r s . r  i s t h e number o f t a s k s .  s i s t h e number o f  Definition If  resources.  1 [53]  P={A,,A ,...,A ] 2  recursively, (i)  i s a s e t s y m b o l s , t h e n P* i s  A  as  defined  follows.  A, t h e empty s t a t e ,  i s i n P*.  ( i i ) A i i s i n P*, 1<i<n. (iii)  I f x a n d y a r e i n P*, so i s x+y.  where + i s a c o m m u t a t i v e , a s s o c i a t i v e A  general  form  x= I x A ^ ,  where  i  binary x^  operator.  i s t h e number o f  o c c u r r e n c e s o f A^ i n x.  Definition  2 [53]  A generalized Petri  n e t , GPN.  GPN=<P,T> P={AT,A ,...,A } i s a s e t of p l a c e s . 2  A  T={ t , , 1 , . • • , t*\}  P*  2  t  i  :  \ ^ i a  A  ">  ? ii b  A  P* i s a s e t o f t r a n s i t i o n s i  1 24  Definition  3 [53]  A marked P e t r i n e t , MPN. MPN=<P,T,m> m i s an e l e m e n t o f P*  Definition  4 [53]  The c h a r a c t e r i s t i c (r  Definition  i 3  )=  a  x i  -b  matrix,  r.  i 3  5 [80]  A t i m e d P e t r i n e t , TPN. TPN=<GPN,o> 0:  T^  (T|,T^  onto a p o s i t i v e  Definition  )  a  function  mapping  a  transition  r e a l number, T.  6 [102]  An i n s t a n t a n e o u s d e s c r i p t o r , d . di=(m ri) i r  m^_€ P* i s t h e m a r k i n g . T X  Definition  R  i s the remaining  time.  7 [38]  A c o l o u r e d P e t r i n e t , CPN. CPN=<GPN,C,F> C=(X,<): a s e t o f c o l o u r s X a n d a p a r t i a l o r d e r , <. F: A  X  a  function  mapping  e a c h edge c A o n t o a  c o l o u r , where A i s t h e s e t o f e d g e s .  125  Definition  8  A state  y  exists  a  results  i n the s t a t e  Definition  of  transition,  y i s reachable  t r a n s i t i o n s , «=a,e states,  x^,  Def i n i t i o n  in  2  from a s t a t e •.•«\,  fired  x through a  i f there  exists a  sequence sequence  that,  = tf  x  tf  X,  a directed  graph  i s a sequence  t h e e d g e s a r e c o n n e c t e d head  to  of edges  such  tail.  11  A directed first  when  10  path  that  there  i i => i ^ - |  X=  Definition  enabled i n x which  if  x=t=3> y .  1<i<k, s u c h x  A  x,  t,  x,  9  A state of  i s d i r e c t l y r e a c h a b l e from a s t a t e  and  circuit last  i s a p a t h w i t h one  node.  common  node,  the  1 26  Definition  12 [ 1 6 ]  A task  ( %/, < , { } ,  system  { (R  })  £7=(T,,T ,...,T ): a s e t of tasks 2  r  <: an i r r e f l e x i v e p a r t i a l o r d e r on T^-:  execution  time of t a s k  i on p r o c e s s o r j .  (P, =[R, ( T j ) ,R ( T j ) , . . . , R ( T j ) ] : r e s o u r c e 2  requirement  j.  of t a s k  Definition  s  13 [ 4 0 ]  The t o t a l e x e c u t i o n  t i m e , v, o f a t a s k  system,  i Definition A  14 [ 4 0 ]  chain  starting  with  task,  (T j , . . . , Tj , T^ , . . . , T-j) , s u c h  Tj,  is  that,  T^  a s e t of t a s k s , is  an  immediate  s u c e s s o r of T j , Tj<T^, f o r a l l t a s k s i n t h e c h a i n .  Definition The  15 [ 4 0 ] height  of  longest chain  Definition  a  task  i n the task  s y s t e m , h, i s t h e l e n g t h o f t h e system.  16  The l e v e l o f a  task,  longest chain s t a r t i n g  T^,  is  the  with task,  T^.  cardinality  of  the  Definition The  17  total  [40] p r o c e s s i n g power of  i processors,  Appendix B  Processors  E x e c u t i o n Time w MCLMT 298  i  C « c» C S C 5 Ca Ci C i C)  i  C  I  198  C l  C  I  C i C l C i C i C C  C  I  380 304 300 432  190  HLF  CG  334 388 328 284  380 388  472 208 190  RANDOM  328 328 384  408 388 304 328  226 248  200 190  190  432  208  190  Table B . I : Example 1 w i t h longer e x e c u t i o n times and slower  Processors  C  1  Cl  C l  Cl  Ci Ca C l C e C 6 C i C s C s C  l  C  i  C l  W* '  260 208 289  190  processors  E x e c u t i o n Time w MCLMT 68 98 104 142 90 130  HLF ; 68  152 178 178  170 152  CG 70 1 10 102 176 138 180  Table B . 2 : Example 1 executed on slower  RANDOM 70 120 138 172 148 162  processors  w* ' 68 89 91 80 76 78  E x e c u t i o n Time w r11 rY> o cI~Ic s s o cr/™\s i~i t~  C I  Cl  ci  Ci Cl  Cl C i C i C I C i  C i C I C I C I C I C I  Cl Cl Cl C i  HLF  CG  RANDOM  w* '  120 135 1 19  126 145 130 168  126 139 133 144 156  104 123 104 136 104  160  128 146 131 154 158  C l  138 129  160 148  158 149  156 154  104 104  186  188 244 184  188 248  Cl  238 184  190 243 236  213 168  244  246  210  210  290 286  210  210  251  C!  CJ CJ C l C 3 C l Ci  MCLMT  C] C l Cl CJ  140 138 C i  222  Table B.3: Example 1 w i t h longer e x e c u t i o n  248 282 258  times  177  236 177 168  Processors  Cl Ci C l c< C l Cl Cl c• C3 C i Cs Ce CI C3 C3  E x e c u t i o n Time w MCLMT 12 24 15 24 24 13  HLF 12 24 15 24 24 13  CG 12 24 15 24 24 13  RANDOM 12 24 15 24 24 14  Table Et.4: Example 1 w i t h u n i t e x e c u t i o n times  w*' 1 1 18 14 13 15 1 1  

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-0065615/manifest

Comment

Related Items