STATE-SPACE GENERATION TECHNIQUES IN THE M�BIUS MODELING FRAMEWORK BY JOHN MARK SOWDER B.S., University of Illinois, 1997 THESIS Submitted in partial fulfillment of the requirements for the degree of Master of Science in Electrical Engineering in the Graduate College of the University of Illinois at Urbana-Champaign, 1998 Urbana, Illinois ii ABSTRACT
In modeling, analytical solutions to models of complex systems can often be obtained by creating the state-space of a model and then solving this behavioral representation using numerical techniques. However, in generating such state spaces, two difficulties arise: the prohibitive amount of computer memory needed to store large state spaces, and the large amount of time needed to generate the state-space. In addition, the algorithms used for statespace generation are generally tailored only to a specific modeling formalism. The work presented here addresses these issues using a new toolkit named M�bius. The goal of the M�bius project is to develop an object-oriented, formalism-independent, stochastic modeling framework, and implement the framework in a practical, usable performance/dependability evaluation tool. Use of the M�bius framework permits the state-space generator to be implemented in a formalism-independent way, since the framework defines the properties of state and actions. Exponential, deterministic, and instantaneous action types are supported in the implementation of the state-space generator. To reduce the memory required and the time needed for state generation, efficient data structures and fast output file generation methods were used. The performance of the state-space generator implementation is promising and allows the analysis of large and complex models. By using the M�bius framework, the statespace generator implementation also provides a basis for easy extensions and feature addition. iii To my wife, for her patience, love, and understanding iv ACKNOWLEDGMENTS
During my time at the University of Illinois, I have enjoyed the friendship and guidance of many special individuals. First, I would like to thank my advisor, Dr. William H. Sanders, for his technical guidance, his patience, and all his help with the M�bius project. I would also like to thank Dr. Sanders for letting me be a part of the Performability Engineering Research Group. Without that opportunity, I would not have gone to graduate school. I would also like to thank all my fellow workers in room 229 of CSRL. Thanks to Jay Doyle, Alex Williamson, and Gerard Kavanaugh for all your help, friendship, and technical guidance. Thanks also to Doug Obal and Dan Deavours for their invaluable help in answering my many technical questions. Special thanks to Jenny Applequist for her help in reviewing this thesis. Additional thanks go to the Defense Advanced Research Projects Agency Information Technology Office, for funding under contract DABT63-96-C-0069, and Motorola Space Systems Technology Group, including Renee Langefels and Peter Alejandro, for their long-term funding of the UltraSAN and M�bius projects. I also want to extend a very sincere thank you to my parents for always listening, supporting, and caring. Finally, I want to thank my wife Denise for her continuous encouragement, love, and understanding. v TABLE OF CONTENTS
Page 1. INTRODUCTION............................................................................................................ 1 1.1. Modeling Overview ..................................................................................................... 1 1.2. M�bius Overview......................................................................................................... 2 1.3. Research Objectives..................................................................................................... 3 M�BIUS FRAMEWORK ............................................................................................... 4 2.1. State Variables ............................................................................................................. 4 2.2. Actions ......................................................................................................................... 5 2.3. Models.......................................................................................................................... 6 2.4. Stochastic Process Overview ....................................................................................... 7 STATE GENERATION ALGORITHM.......................................................................... 9 STATE-SPACE GENERATOR IMPLEMENTATION................................................ 14 4.1. Initialization ............................................................................................................... 14 4.2. State and Reward Generation..................................................................................... 15 4.2.1. Model interaction ............................................................................................... 15 4.2.2. Data structures ................................................................................................... 16 4.2.3. Deterministically distributed actions ................................................................. 20 4.3. Output Formatting...................................................................................................... 21 4.4. User Interface ............................................................................................................. 23 RESULTS AND COMPARISONS ............................................................................... 25 5.1. Kanban Model............................................................................................................ 25 5.2. Faulty Processor Model ............................................................................................. 30 CONCLUSION AND FUTURE RESEARCH.............................................................. 35 2. 3. 4. 5. 6. APPENDIX A: STATE-SPACE GENERATOR USER'S MANUAL................................. 37 A.1. M�bius State-Space Generation............................................................................. 37 A.2. Installing the M�bius State-Space Generator Module ........................................... 37 A.3. State-Space Generator Input .................................................................................. 38 A.4. State-Space Generator Output................................................................................ 40 A.5. State-Space Generator Tips and Tricks.................................................................. 42 APPENDIX B: STATE-SPACE GENERATOR OUTPUT FORMATS ............................. 43 B.1. State-Transition Rate Output Formats ................................................................... 43 ASCII Row Format .arm .................................................. 43 Binary Row Format .brm.................................................. 44 ASCII Column Format .acm............................................. 44 Binary Column Format .bcm ............................................ 45 ASCII M�bius Format .amm ............................................. 45 Binary M�bius Format .bmm............................................. 45 B.2. Reward Variable File ............................................................................................. 46 B.3. Deterministic Parameter File ................................................................................. 46 REFERENCES ...................................................................................................................... 48 vi LIST OF TABLES Table Page Table 1: State-Space Generator File Formats ........................................................................ 22 Table 2: Number of States Produced by Kanban Model........................................................ 26 Table 3: Composed Faulty Processor Model Settings and Characteristics............................ 31 Table 4: Performance Results of Composed Faulty Processor Model................................... 32 vii LIST OF FIGURES
Figure Page Figure 1: State-Space Generation, Algorithm 1....................................................................... 9 Figure 2: Next Tangible State Computation, Algorithm 2..................................................... 11 Figure 3: Execution Flow Diagram........................................................................................ 14 Figure 4: Hash Table Data Structure...................................................................................... 17 Figure 5: State-Space Generator Input ................................................................................... 23 Figure 6: State-Space Generator Output ................................................................................ 24 Figure 7: Kanban Model ........................................................................................................ 26 Figure 8: Generation Time Plot for Kanban Model ............................................................... 27 Figure 9: Memory Usage Plot for Kanban Model.................................................................. 27 Figure 10: States per Second for Kanban Model ................................................................... 29 Figure 11: Bytes per State Needed for Kanban Model .......................................................... 29 Figure 12: Faulty Processor Model ........................................................................................ 30 Figure 13: Faulty Processor Job Arrival Model..................................................................... 30 Figure 14: Faulty Processor Composed Model...................................................................... 31 Figure 15: States Generated per Second for Composed Faulty Processor Model ................. 33 Figure 16: Bytes per State Needed for Composed Faulty Processor Model .......................... 33 Figure 17: Adding the State-Space Generator Module .......................................................... 37 Figure 18: State-Space Generator Input Panel ....................................................................... 39 Figure 19: State-Space Generator Output Panel .................................................................... 41 viii 1. INTRODUCTION
1.1. Modeling Overview The use of prototypes is common in industry for the analysis of complex systems. The benefit of building a prototype is that it can effectively mimic the behavior of the system before final production. This allows for the analysis of the performance and dependability of the system before commitment to a final design. However, modern systems are often too complex to prototype in the early development stages. For these systems, computer modeling and analysis are also useful. By using the solutions to a model of a system, a designer can predict performance and diagnose problems and flaws earlier than would be possible if prototyping were the sole evaluation method. Generally speaking, there are three modeling solution methods used to compute information about a system being modeled: closed-form solutions, numerical solutions, and simulation. Closed-form solutions are mathematical descriptions of the measured property written as a function in closed form. While using a closed form is ideal, it is generally impossible to determine one for all but the simplest models. Conversely, when a closed-form solution is not available, a simulation may be used to examine the model. Simulation is a way of numerically exercising the model for the inputs in question to see how they affect the output measures of performance [1]. In other words, a simulation samples the random process and observes the resulting behavior. With enough samples, the measures can be estimated with a certain level of confidence. While simulation can solve any model through this "brute force" approach, it becomes less practical for estimating measures based on events that are rare, because of the large number of samples necessary. An intermediate approach to model analysis is to use a stochastic process to represent the system and solve the process numerically. These processes are often expressed with a high-level modeling formalism such as stochastic activity networks (SAN) [2] and converted into a state-level representation through a method called "state-space generation." State-space generation is an algorithmic way of producing the desired stochastic process of a model given 1 some higher-level, more abstract representation of the model. This behavioral model representation is then solved by one of several numerical techniques depending on characteristics of the behavioral model and on the type of measure the modeler is interested in analyzing. This solution method is called a numerical solution method and is important in model analysis because it produces fast, extremely accurate results for moderately complex systems with rare events, for which simulation is impractical. In addition, with moderately complex systems, numerical results can often be produced with higher accuracy in less time than they could be with simulation. 1.2. M�bius Overview Many modeling tools are currently available that can be used to represent a system in a compact high-level representation, generate a state-space from the high-level representation, and then use numerical solutions or simulation to determine properties of interest. Examples of such tools include UltraSAN [3], HiQPN [4], and DSPNexpress [5], among others. Each of these tools is based on a single high-level modeling language or formalism. The algorithms used for solution and analysis of these modeling languages may be fast, but are often tied closely to the high-level representation that the particular tool uses. Ideally, a modeling tool would have the ability to use many modeling languages to represent systems and use a generic yet complete set of modeling primitives. The SHARPE modeling tool [6] allows multiformalism models, but limits interactions between models to results passed after model solution, and does not permit sharing of states and events between models. Result sharing allows solution methods specific to each formalism to operate on each model, but does not allow general solution methods to operate on a combined, multi-formalism model. The M�bius modeling framework allows more general interaction between models, while at the same time supporting multiple formalisms and a wide variety of solvers. The M�bius approach does not prescribe a particular modeling formalism, but rather a framework to support a diverse set of formalisms. As long as a formalism can be expressed in the framework, it can be supported in M�bius. The M�bius framework consists of a basic set of modeling primitives including "models," "states," and "actions." Each basic component has associated functions defined on it to allow for model execution. Using the framework, 2 each component can be used to define how a model using a specific formalism can act. Thus, the M�bius framework says what the components can do, not how they do it. For example, "firing" an action in a model changes state, but how it changes state depends on the formalism, the model, and how the "firing" was defined. The M�bius framework components have been implemented in a tool referred to as the M�bius tool. The M�bius tool is written in C++ and Java. Java was chosen for its property of rapid interface development due to its assortment of predefined classes and libraries. C++ was chosen for the state-space generator since C++ is compiled and thus produces code that executes fast. 1.3. Research Objectives Four areas of research within the M�bius tool are presented in this thesis: compact and efficient data structures for state generation that produce fast execution and low memory usage; a formalism-generic state generation algorithm, support for deterministically and exponentially distributed and instantaneous actions, and an interface in the M�bius tool that aids in producing the state space of a high-level model. The main objectives of the work are to examine performance results of the new algorithms as well as to provide theory and insight into additional state generation techniques. The rest of the thesis is organized into five chapters. The second chapter presents a more detailed explanation of the M�bius modeling framework, highlighting its interaction with the state-space generator. The basic modeling building blocks are explained there, as are all of the model types within the M�bius tool. The second chapter also includes an overview of stochastic processes for exponential and deterministic distributions. The third chapter describes and explains the formalism-generic state generation algorithm. In Chapter 4, a detailed description of the implementation of the state generation application is presented. Chapter 4 emphasizes the data structures used in the implementation. In Chapters 5 and 6, the results, conclusions, and future work are discussed. In Appendix A, the user's manual for the state-space generator tool is presented. Finally, Appendix B details the output file formats that can be produced by the M�bius state-space generator. 3 2. M�BIUS FRAMEWORK The M�bius framework defines an extensible modeling environment that supports a diverse set of formalisms. A fundamental part of the M�bius modeling framework is the "formalism-generic" interaction between the model and the solution mechanisms. Of specific interest to the state-space generator is the path from "atomic" model to "solvable" model. In this chapter, definitions and explanations of each model type in the M�bius framework are presented. Also, the basic model components "state" and "action" are explained. Finally, in the last section of this chapter, the output of the state-space generator, a stochastic process, will be reviewed to help the reader understand the state generation algorithm described in the next chapter. 2.1. State Variables State variables are entities that have a value and a type associated with each of them and are the basic building blocks of a model. An example of a state variable is a place in a stochastic activity network, where the value is the marking of the place and the type is a natural number. In a model, the set of all state variables and their values represents the "state" of the system. In the M�bius tool, for example, functions used on state variables include statesize(), setstate(), and currentstate(). These methods define the physical size the state occupies in the executable version of the model (memory size), a method to set the state variable to a particular value, and a method to return the value of all the state variables in a model at a given time, respectively. A key feature of this definition of state in the M�bius framework and tool is that it allows for state to be implemented in a potentially complex way. For example, the state of a model could be defined as the collection of all markings in a stochastic activity network combined with the values in a queuing network. The only restriction is that the value and the type of the state variables must be precisely defined. 4 2.2. Actions Actions are the state-changing entities of a model. Within the framework, support is provided both for timed actions, which are actions that complete in a specified amount of time, and for instantaneous actions, which are actions that complete in zero time. The exact implementation of the action specification, including details of the enabling functions, distribution parameters, and state-changing functions, is left to specific formalisms. The M�bius tool simply provides a set of data members and methods that must be defined on the model primitives by the formalism designer in order to describe the execution of models within the formalism. For example, in a stochastic activity network, the enabling function, reactivation methods, and distribution type must be defined in order for a SAN model to execute. An important aspect of actions in the M�bius environment used by the state-space generator is the use of "ranks" and "weights." The rank of an action is defined as the priority of an action within a "group." The weight of an action is the relative importance of an action as compared to other actions in a "group." In state generation, weights are used to probabilistically determine certain exploration paths. For example, in a SAN, weights are the equivalent of cases on activities. Ranks are used by the state-space generator to break ties when two or more instantaneous actions are "enabled" in the same state of the system. An action is said to be enabled if in the current state the action is allowed to fire or execute the state-changing function associated with it through the M�bius framework. Chapter 3 explains in more detail the use of ranks and weights within the state generation algorithm. A useful extension available as a result of the existence of the rank and weight attributes of actions is the creation of action "groups." Groups are sets of actions combined together for selection purposes. Groups are mainly used in the context of simulation of the model, as described in [7]. In simulation, groups behave as actions, but selection of specific actions within the group may occur as a result of model execution. Action composition allows for policies to be developed that define when actions within groups are selected and the processes by which the selection occurs. In the context of the state-space generator, groups are used in the calculation of the total weight of a group when determining the probability of an action firing, as explained in Chapter 3. For example, in stochastic activity networks, 5 activities have cases, which are used to choose probabilistically between possible paths of execution. In M�bius, a SAN activity with cases is represented as a group of activities such that each activity's weight corresponds to the case probability. 2.3. Models Within the M�bius framework, models are made up of actions and state variables. Four types of models are supported in the M�bius framework: "atomic," "composed," "reward," and "connected." Atomic models are the basic building blocks of any larger models that are developed using only one formalism. Combinations of models using single or multiple formalisms are called composed models. Composed models allow creation of new complex system models, using the most appropriate formalism for each component. Not only do composed models facilitate the specification of complex combinations of models, but they also enable exploration of the model structure to obtain a more time- and/or space-efficient solution. Models joined through results are called connected models. Connected models can be used for model interaction through results passed after model solution, as found in SHARPE [6]. Defining "reward variables" on these composed or atomic models allows the various analytic and simulation solution methods to solve for the behavioral characteristics of the model. Reward variables are a method for defining functions on the state of a model. A model containing reward variables and other model(s) is called a reward model. Reward models contain methods for specifying reward variables in terms of the underlying model's state. Reward models may also have additional notions of state. For example, using stochastic activity networks, a reward model may add state to the model for storing impulse reward information. Once reward variables are defined on a model, the model is said to be solvable. Certain parameters within a solvable model may be varied during execution by creation of studies. These studies allow variables within the model to change; each variation is called an experiment. Thus each study may contain multiple experiments that change the model's parameters such that the user can analyze the model under many different conditions. Analytical solution methods and simulations may then be used to analyze the derived solvable 6 model and the experiments defined on it. The state-space generator uses a solvable model to generate a stochastic process, which can be solved numerically, as is explained in detail in the next section. 2.4. Stochastic Process Overview Through the state-space generation, a stochastic process representing the behavior of a solvable model is created. Then, well-established numerical techniques can be used to solve this stochastic process for measures of interest as specified by the reward variables of the model. While many types of stochastic process exist, only a few can be solved numerically. This section will describe two stochastic process types that can be generated by the M�bius state-space generator: Markov processes and Markov regenerative processes. A complete formal definition of the Markov and Markov regenerative processes will not be presented. Instead, a brief overview of the mathematical background will be provided, and details needed for state generation will be examined. Stochastic processes are mathematical models useful for the description of random phenomena as functions of a parameter that usually has the meaning of time (exclusively time for the M�bius tool). More specifically, a stochastic process is a family of random variables {X(t), t T} defined over the same probability space, indexed by the parameter t, and taking values in the set S. The values assumed by the stochastic process are called states, so that the set S is called the state space of the process [8]. One type of stochastic process generated by the M�bius state-space generator represents a Markov process. Markov processes have the following property: P{ X (t ) x | X (t n ) = x n , X (t n -1 ) = x n -1 ,..., X (t 0 ) = x 0 } = P{ X (t ) x | X (t n ) = x n } t > t n > t n -1 > ... > t 0 which is known as the Markov memoryless property. A stochastic process for which this condition holds is known as a Markov process. In words, the condition says that the future evolution of the process from the instant of time tn on is independent of the past history of the process; the future depends only on the current state of the process. Models containing only timed exponentially distributed and instantaneous actions produce Markov processes. 7 Another important class of processes produced by the M�bius state-space generator is that of Markov regenerative processes. A Markov regenerative process has the property that at some time points the process (probabilistically) restarts itself [9]. Informally, there is a sequence of embedded time points at which the Markov memoryless property is satisfied. At these time points, future behavior of the process is independent of the past behavior. Models containing instantaneous actions and timed actions with exponential and deterministic distributions produce Markov regenerative processes. The only limitation imposed on a model is that only one deterministic distribution can be enabled for any state of the model. When numerical techniques are used to solve a model, specific details of the Markov or Markov regenerative process are needed. For the Markov process representation, the statespace generator partially outputs the state transition-rate matrix (sometimes called the infinitesimal generator matrix) Q, defined as
Q = [ qij ]
j i i, j S qii = - qij = -qi where qij is the rate of the process from state i to state j. The state-space generator does not directly produce the qii entries since they are easily obtained by a summation of the qij entries. This form allows the state occupancy probability vector (a vector containing a list of all the probabilities of being in a certain state of the process at a given time) to be solved using a variety of numerical techniques for both steady-state and transient solutions. The output representation produced by the state-space generator for a Markov regenerative process is similar to that produced for a Markov process. This representation is solver-specific and was originally implemented in [10]. To express the regeneration points, a similar state transition-rate output is produced in which the probabilities of each next tangible state are output. Thus the output is a hybrid state-transition rate matrix with rates being replaced by probabilities when a deterministic action is enabled. These probabilities are appended with a minus sign so that the numerical solver can distinguish rates from probabilities. 8 3. STATE GENERATION ALGORITHM
In this chapter, a detailed description of the state generation algorithm used to generate the underlying stochastic process from a model will be explained. A formalism-generic algorithm is presented in terms of the methods defined in the M�bius framework. In the context of this chapter, the term method is used as a way of compactly expressing details of the algorithm, not implementation-specific functions. The state generation algorithm is divided into two parts. The first part is the main state generation algorithm that determines all states of a model in a breadth-first manner. The second part specifies precisely how to determine next states when timed and/or instantaneous actions are enabled in a specific state. 1 At = {t0,t1,...} // At is the set of all timed actions in the model // Az is the set of all instantaneous actions in the model Az = {z0,z1,...} S = {} // S is the set of generated states U = {�0} // U is the set of unexplored states, �0 is the initial state NS = {} // NS is the set of next states 5 While U 6 For some � U NS = {} NS = ComputeNS(� , p=1) using Algorithm 2 // p is a probability ComputeReward(�) 10 ns NS if ns S S = S ns U = U ns End 15 U=U-� End For While end Figure 1: State-Space Generation, Algorithm 1 9 Algorithm 1 (see Figure 1) uses five sets to determine all states in a model: the set of timed actions (At), the set of instantaneous actions (Az), the set of "generated" states (S), the set of "unexplored" states (U), and the set of next states (NS). The sets of timed and instantaneous actions are used in Algorithm 2. The explanation of these two sets is left until the explanation of Algorithm 2. The set of "generated" states contains all unique states that have been produced at any point in time by the state-space generator. Generated states are those "tangible" states that have been found using the ComputeNS method. A tangible state is a state that has no instantaneous actions enabled in it. The unexplored set contains all tangible states that have not been used by Algorithm 2 to determine all tangible next states. The set of next tangible states found by using Algorithm 2 is stored in the NS set. These five sets are used to determine all tangible states for a model. After initialization of the five sets in the algorithm, the main while loop in which unexplored states are generated is entered. First, some state in the unexplored set is picked. Initially, this is the initial state of the model. Then, Algorithm 2 is used to determine all tangible next states of a state � through the method ComputeNS, which takes as input a state and a probability. Initially, the probability value is set to 1 to determine rates from one tangible state to another as explained in Algorithm 2. Algorithm 2 is presented in Figure 2. Before explanation of the policies for execution of Algorithm 2, the Probability method will be presented. The Probability method is used to determine the probability that an action will fire in a certain state of the model. Probability takes an action as input and returns the probability of this action firing in the current state of the model. The probability of each enabled action is determined using the weight method on an action and the equation below. Probabilit y( z ) = z .Weight () 0 .Weight() + 1 .Weight () + 2 .Weight () +..... + z .Weight () The probability is used to determine rate values between tangible states. The StoreQ method is called to store the rates in the state-transition rate matrix representation output by the state-space generator. When the model produces a Markov process (i.e., only exponential timed and instantaneous actions are present) then the rate to a next state can be represented by the multiplication of all probabilities from one tangible state to another by the rate of the 10 action enabled in the previous tangible marking. In the current implementation, two or more t At If t.Enabled() �i+1 = t.Fire(�i) p = p*Probability(�i) If Az and PathLength() < MaxPathLength z : z.Enabled() While z.NumberEnabled() > 0 Case 1: // one enabled �i+1 = z.Fire(�i) Case 2: // more than one enabled z Az : z.Enabled() : z..Rank() = z+1.Rank() SetState(�i) �i+1 = z.Fire(�i) goto line 4, �i =�i+1, p = p*Probability(z) End Else z = HighestRank(z, z+1) �i+1 = z.Fire(�i) End While End Else StoreQ(p) End 1 5 10 15 20 Figure 2: Next Tangible State Computation, Algorithm 2 instantaneous actions enabled by a state change from a deterministic action are not allowed. Algorithm 2 shows how the set of all next states is computed given a state of the model. The algorithm uses the sets At and Az. These sets contain all the timed and instantaneous actions of a model. These actions are split into two sets, since different execution methods are needed for each type. If the current state of the model only contains enabled timed actions, then the next state is determined by calling the Fire method on an action. The Fire method on an action takes a state as input and returns the new state by executing the action's state changing function. The method is executed for every timed action 11 that is enabled given the state � of the model. However, if instantaneous actions are enabled, a more complex state-changing algorithm is employed. While instantaneous actions are enabled, the model continues to change state according to the specific instantaneous action being fired. With respect to the firing of instantaneous actions, there are two possible cases: there is one enabled instantaneous action, or there are two or more enabled instantaneous actions. If two or more instantaneous actions are both enabled in the current state, then an "execution policy" must be used to determine which one is allowed to fire. The M�bius framework defines the execution policy in the context of the state-space generator as the process in which model execution is determined when instantaneous actions are enabled. The M�bius state-space generator uses ranks and weights in this policy. Specific to the algorithm, if more than one instantaneous action is enabled, the first step in the model execution is that the method Rank is called on the action. The Rank method returns the rank of an instantaneous action within the model. The instantaneous action with the highest rank is then fired. However, if two instantaneous actions have equivalent ranks, then Algorithm 2 is recursively applied until the next tangible state is determined. The variable p is modified at each recursive step by multiplication of the new probability found through the Probability method by the old value. This value is then used in determining the overall rate for a Markov process, or probabilities for a Markov regenerative process, from one tangible state to another. When only one instantaneous action is enabled, the Fire method executes and returns the new state. Once the new state is returned from this part of the algorithm, the check for any enabled instantaneous actions, line 4, is repeated. The algorithm then recursively continues while any new instantaneous actions are enabled until all tangible next states are found. The number of recursions, however, is limited to MaxPathLength to allow for practical implementation. After all tangible states are found, Algorithm 2 returns the set of all next states of the model given a current state as input. After returning from Algorithm 2 with the set of next states, Algorithm 1 first calls the method ComputeReward with the current state � as input to determine the reward of state � of the model. The ComputeReward method is defined on a reward model in the M�bius After reward framework, which allows for formalism-independent reward gathering. 12 computation, all next states determined by Algorithm 2 not yet explored are added to the unexplored set. This algorithm continues until the unexplored set is empty and thus all tangible states of the model have been determined. The algorithm returns the set S which contains the set of all tangible states of the model. The implementation of the state-space generator algorithm in the M�bius framework is presented in Chapter 4. 13 4. STATE-SPACE GENERATOR IMPLEMENTATION
In this chapter, we will discuss the implementation of the state-space generation algorithm presented in Chapter 3. The M�bius state-space generator implementation has two main components: a C++ solution engine and a Java interface. As shown in Figure 3, the execution of the C++ state-space generator solution engine is done in three phases: initialization, state and reward generation, and output formatting. We first discuss the initialization stage, which performs the setup required for the model interaction and initializes the data structures. The next section of the chapter discusses the state and reward generation execution stage. In that section, a more detailed description of the data structures used in the implementation as well as discussion of the implementation of deterministic actions is presented. The output-formatting stage is then discussed. That section describes the different representations for the state-transition rate matrix produced by the state-space generator. The chapter concludes by discussing the Java interface used to interact with the C++ solution engine. Initialization State and Reward Generation Output Formatting Figure 3: Execution Flow Diagram 4.1. Initialization In the initialization stage, several steps occur to set up values and parameters needed by the state-space generation routine. The initialization steps in the state-space generator implementation are important since they set up the generic interaction between a model and the state-space generator, and more specifically the interaction with actions in the model. As shown in the first algorithm of Chapter 3, the state-space generator needs two lists 14 corresponding to the two kinds of actions: timed and instantaneous. These lists are formed by using data members defined on actions that flag the type of action being represented. Once the lists are made, the list of timed actions is scanned to determine the distribution types of the actions. Determination of a model's action types allows the state-space generator to ascertain whether all actions are of types supported in the state-space generator. Determination of the action types also makes it possible to use optimized routines for models with certain actions. The initialization stage also allocates an initial block of memory to each data structure. The size of these blocks is fairly large, to avoid the significant overhead that would be caused by many additional allocations during state-space generation. The state-space generator also initializes the output files used to store the state-transition rate matrix and associated reward. In order to minimize the amount of data that must be kept in main memory, these files are written to disk during the state and reward generation stage of state generation. The files are then converted to the desired output format in the output-formatting stage. 4.2. State and Reward Generation After initialization, the next stage of execution is the state and reward generation. Three issues are discussed in this section with respect to the state and reward generation stage: the interaction between models and the state-space generator, the data structures used to store and look up states, and the issues related to supporting deterministically distributed actions. More specifically, the first subsection describes the generic interface of the state-space generator that allows the formalism-independent state generation algorithm to be implemented. The second subsection presents the two data structures used in the generation algorithm: a hash table and a queue. Finally, we discuss how deterministic actions are supported in the state-space generator. 4.2.1. Model interaction The M�bius state-space generator interacts with models in a formalism-independent way. Three methods are used to do this: SetState(), CompareState(), and Fire(). SetState() sets the current state of the model to the input passed to this method. 15 CompareState() takes two states as input and returns true or false depending on whether they are equal. Fire() takes an action as input and returns the new state of the model after this action is fired. The state-space generator obtains implementations of these methods from the reward model. These methods, defined on the reward model, allow the state-space generator to interface indirectly with many types of models, including composed and atomic models. In addition, the state-space generator interacts with the reward model by use of two methods, Reward() and Impulse(), that compute the reward associated with particular states in the model. The two methods are the implementation of ComputeReward as used in Algorithm 1 of Chapter 3. Specifically, the Reward() method returns the reward rate for a specific state. The Impulse() method returns the impulse reward associated with the firing of a certain action in a model. During the state-space generation, the values returned by the Impulse()and Reward() methods are output to a file to avoid the need to hold the set of rewards for all states in memory at once. After the state and reward generation stage has completed, the file contains all reward values for every reward variable for every state in the model. 4.2.2. Data structures A main limitation of state-space generation of large models is the prohibitive amount of time and memory needed. The choice of particular data structures to use in the state generator is thus very important. This section explains the data structures used to store the set of generated and unexplored states. Due to its fast lookup and insertion time, a hash table is used to store the set of generated states due to its fast lookup and insertion time. A queue is used to store the set of all unexplored states, since it provides constant insertion and deletion time. 16 Hash Table
0 1 2 3 4 5 6 7 8 9 . . . . . . . . . . . . . .
Hash_Size State Arrays .... .... . . . . .... .... .... . . . . .... . . . . . .... .... . . . . Figure 4: Hash Table Data Structure Hash Table The data structure used to store the set of generated states must have fast lookup and fast insertion time. Fast lookup time is needed since a lookup must occur for every state generated to determine whether the state is in the set of generated states. Also, each new state generated must be inserted in the generated set to be used in future comparisons. In addition to being fast, the data structure used to store the set of generated states must use as little extra memory as possible, beyond that required to store the states themselves. A hash table was chosen for this data structure because given an efficient hash function, it has fast lookup, fast insertion, and uses memory conservatively. A pictorial representation of the hash table and associated data structures is shown in Figure 4. The figure shows the two components of the data structure: the hash table and the state arrays that contain the states themselves. The hash table holds 32-bit values used to determine where a state can be found in the state array structures. The state arrays are of fixed size and contain the states. Each state array has an associated ID. By using this ID and an index into the array, it is possible to locate particular states. Specifically, the 32-bit values 17 stored in the hash table contain the ID and index information needed. The first 24 bits (bit positions 0-23) of each value represent the index into a state array, and the remaining 8 bits (bit positions 24-31) represent the state array ID. To determine the hash key, which is the index into the hash table to use when either storing newly generated states or searching for a specific state, we use a hash function on the state. To preserve the time efficiency of the hash table data structure, it is important to find a hash function that produces few collisions. Collisions occur when use of the hash function on two states produces two identical outputs, and thus two identical indices into the hash table. It is not straightforward to determine a hash function for the M�bius state-space generator that produces few collisions, since no information about the structure of the state is accessible to the state-space generator and the size of the state being hashed is not known in advance. To build an efficient and useful hash function given these constraints, one must define a function that considers the state as a block of memory, but assigns a known structure to the memory. This is done by breaking each state into a set of 1-byte values. These values are then used as input to the hash function. The hash function also depends on the order of the 1-byte blocks and is adaptable to any state size. In particular, the hash function computes a polynomial function (of degree 32) by use of Horner's rule [11]. The hash function is defined as
HashKey =
StateSize -1 i =0 State[ StateSize - i] � 32 i where StateSize is the number of 1-byte blocks of state and State contains the 1-byte state values. The hash function computes a 32-bit key by summing all values from 0 to StateSize-1. At each step of the summation, the 1-byte state values are multiplied by 32 raised to the power of i to distribute the 1-byte state values over the 32 bits of the hash key. After the key is computed, the index into the hash table is taken to be the modulus of the hash key and the hash table size. The modulus is taken to produce an index within the size of the hash table. It should also be noted that the hash table size is a prime number so that the hash function will distribute well over the entire hash table [11]. In the actual implementation of the state-space generator, the summation is replaced with a bitwise exclusive-or to reduce the time necessary 18 to compute the key. If the state size is not larger than 6 bytes, then the hash function is directly executed, varying i from 0 to the StateSize-1, to obtain the hash key. However, if the state has more than six 1-byte values, then some information may be lost due to the multiplication. Thus, in the M�bius state generator, each state must be brought within the range, which is 6 bytes. For this purpose, the state is broken up into 6-byte partitions, upon each of which the hash function is then executed. The hash key is then formed by taking the exclusive-or of the output of the hash function for every one of these 6byte partitions. Even though a relatively collision-free hash function is implemented in the state-space generator, a collision policy must be used when states hash to the same position in the hash table. To solve this problem, the state-space generator implements a quadratic probing collision resolution strategy using the function f ( j ) = f ( j - 1) + 2 j - 1
where j is the number of collisions. This function specifies a new index to go to when a collision occurs. For insertion, new indices are computed until an empty position is found. For a lookup, all states that are reached must be compared to the next state until either a match occurs (the state is not a new state), or an empty position is reached (the state is a new state, and should be added to the table). If a hash table size that is a prime number is used, the quadratic probing procedure described in the last paragraph is guaranteed to terminate if the table is at least half empty [11]. If a prime number hash-table size is not used, the procedure may loop and never terminate. For this reason, rehashing (described next) is done when the table becomes half full. Quadratic probing also has the desired property of reducing "primary clustering." Primary clustering [11] occurs when keys hash into a cluster of values in the hash table requiring several attempts to resolve the collision, thus reducing overall performance. Another important design decision when using a hash table is the hash table size. Unfortunately, with state generation, there is generally no way to determine a priori the number of states that will be generated before the states are actually produced. Thus, the state-spa