Class Note for ECE 575 at UA
Popular in Course
Popular in Department
This 10 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Arizona taught by a professor in Fall. Since its upload, it has received 25 views.
Reviews for Class Note for ECE 575 at UA
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
SYSTEM ENTITY STRUCTURE IN DEVS Simulationbased systems design employs a plangenerateevaluate process The plan phase organizes all the models of design alternatives within the chosen system boundary and design objectives The generate phase synthesizes a candidate design model intended to meet the set of design objectives Finally the evaluate phase evaluates behavior andor performance of the generated model through simulation using an appropriate experimental frame derived from the design objectives The overall design cycle repeats the generation and evaluation phases until an acceptable design is found How can we organize a family of models from which a candidate model can be selected generated and evaluated This chapter presents the systems entity structurem odel base SESMB framework for such an organization The idea is as follows Let us first extract the hierarchical composition structures of hierarchical modular models from their implementations Then we save the structures and the implementations separately in organized libraries 0 shows the basic idea in which libraries for model structures and model implementations are called system entity structure base and model base respectively Our goal is to be able to synthesize a simulation model by traversing a model hierarchical structure retrieving component implementations and coupling them together As will be seen later in this chapter a system entity structure represents not a single model structure but a family of model structures from which a candidate structure called a pruned entity structure can be selected Thus the systementity structuremodelbase framework supports the plangenerateevaluate process in systems design ABC AB C Separate Speci cation structure components ENTITY STRUCTURE BASE MODEL BASE ABC AB AB c j B c1 c2 lt xys structure components Synthesis Figure 1 System Entity StructureModel Base Concept Model Base Management By System Entity Structure A model base is an organized library of models that may be either atomic or coupled Models can be saved in the model base for later retrieval Models so retrieved may be reused to create more complex models Thus the model base approach will improve the productivity of the modeling subtask in the overall systems design process Figure 1 shows an approach to model base management that relies on the concept of system entity structure to be explained in the next section The behaviors of primitive components of a real world system are specified by atomic models and saved in the model base Figure l a The structural knowledge of the system is represented as a system entity structure Figure l b by means of an operation called entity structuring The entity structure here serves as a compact representation for organizing all possible hierarchical composition structures of the system This separation of model composition structures from their behaviors may reduce the modeling complexity of real world systems Moreover such separation allows designers to easily construct candidate models with different structures While using the same components To construct a desired simulation model to meet design objectives the pruning operation is used to reduce the SES to a pruned entity structure PES Figure l c This pruned entity structure can be transform ed into a composition tree 0 d and eventually synthesized into a simulation model 0 e by combining it with models in the model base Such models are evaluated via simulation to determine superior solutions to the design objectives EFPEL E l EFoun PELJn b t eprel39dec PELIoutEFin 011 V m PROC adone in gt mv EF PEL PELInFUFFInI read FIFO 0 ready LIFO Out BUFFOIILPROCIin y 19614 PROCdoneBUFFready PROCOM PELOIID solved TRANSD 01 Stop GENR 01 BUFF PROC EF I F solved out Stoph out k buffSPEC m 39 TRANSD GENR rout FIFO LIFO a b EFPEL EFPEL EFOut PELJII gfi gl39dgc PELOutEFin EF PEL PELinFIFOin BF PEL FIFO Out PROch pgldgc PROCd0neFIFOready PROCOIII PELOut FIFO PROC GENR TRANSD FIFO PROC C d EFPEL EF out lt out 4 stop out solved in PEL ink in out out FIFO out 1 PROC ready done 1 c Figure 2 Model Base Management Scheme a model base b system entity structure SES c pruned entity structure PES 1 composition tree e synthesized model System Entity Structure The system entity structure formalism is a structural knowledge representation scheme that systematically organizes a family of possible structures of a system Such a family characterizes decomposition coupling and taxonomic relationships among entities An entity represents a real world object The decomposition of an entity concerns how it may be broken down into subentities As discussed earlier coupling speci cations tell how subentities may be coupled together to reconstitute the entity The taxonomic relationship concerns admissible Varianm ofan entity As shown in Figure 3 an SES is represented as a labeled tree with attached attributes that satis es the following axioms 1 alternating entityaspect or entityspecialization Each node has a mode that is either entityaspect or entityspecialization such that a node and its successors are always opposite modes the mode ofthe root is entity 2 uniformity Any two nodes with the same names have identical attached Variable types and isomorphic subtrees 3 strict hierarchy No label appears more than once down any path of the tree 4 valid brothers No two brothers have the same label 5 attached variables No two Variable types attached to the same item have the same name There are three types ofnodes in the tree An entity node eg A in Figure 3 represents a real world object There are two types of entity namely composite entity and atomic entity A composite entity is de ned in terms of other entities which may be either atomic or composite while an atomic entity can not broken down into subentities Each entity may have attached variables It may also have several aspecm andor specializations An aspect node likeAdec in Figure 3 is connected by a single Vertical line from a composite entity It represents one decomposition of the entity The children of the aspect are entities distinct components of the decomposition Associated with each aspect is a coupling speci cation A specialization node eg Bspec in 0 is connected by a double Vertical line from an entity It de nes the taxonomy of the entity and represents the way in which the entity can be categorized into specialized entities Selection rules may be associated with each specialization and guide the way in which a specialized entity is selected in the pruning process A selection constraint depicted as dotted arrow from an entity to other entities in Figure 3 means that not all entities may be selected independently Once a specialized entity is chosen from a specialization some specialized entities in other specializations associated with the specialization are also selected The dotted arrows from B1 to D1 and G1 in 0 enforces the following selection constraints if entity B1 is selected from specialization Bspec then select entity D1 from specialization D spec and entity G1 from specialization Gspec c n W a rc 3 m 31ch Hrj him 34M 9 out m gm1 u uul u m 21162 um I 4r mu n mm L mu mm ll am 1 mm El 132 D m E r H 1 m M H uus 071m Figure 3 A System Entity Structure System EntityStructureModeIBase SESMB Framework As we explained in a previous section the SESMB framework is a powerful means to support the plan generateevaluate paradigm in systems design Within the framework entity structures organize models in model base Thus modeling activity within the framework consists of three subactivities specification of model composition structure specification of model behavior and synthesis of a simulation model 0 shows a modeling and simulation methodology based on the framework in the process of iterative systems design In the figure the generation phase consists of two subphases pruning and model synthesis The structure specification andor the behavior specification may already exist in the entity structure base andor model base However if the structure specification is not in the entity structure base we need to specify it by building a System Entity Structure which represents a family of possible model structures Likewise if the desired model components are not in the model base we need to develop them and store them in the model base for later use In the pruning phase we select a substructure by pruning the SES with respect to design objectives A simulation model is automatically synthesized from such a pruned entity structure Simulation experiments may require changes of structure andor behavior of the design model The prmiingsynthesisevaluation process is repeated until a desired design is found Once simulation experiments are completed the designer can save structure and behavior specifications in the system entity structure base and the model base respectively for later use D esign model structure in Entity Structure Design model behavi or Specify all models structure Specify all models behavior Completed s no Pruning by design objectives no Design model synthesis v Design evaluation by simui ation Structure change Behavior change Figure 4 Design Methodology Using SESMB Framework Example Design of a transaction processing system Let us exemplify SESMB framework with the design of a transaction processing system As outlined in 0 the transaction manager TM assigns transactions requested by users to transaction processes Each transaction process TP model represents a particular way of processing a transaction Once assigned a transaction it works on it until the transaction is completed or aborted CPU and DISKS are resources that can be used when the transactions are executed CPU actually executes the operations of transactions and DISKS are used is to store databases The concurrency control CC shares the resources among the transaction processes There are three kinds of concurrency control strategies In twophase lacking if a lock request on an object is denied then the requesting transaction is blocked In this strategy a process may become part of a deadlock cycle In the immediaterestart strategy if a lock request is denied then the requesting transaction is aborted and restarted In the optimistic strategy transactions are allowed to execute unhindered and are validated only after they have reached their commit points Notice that the two phase and optimistic strategies have counterparts in the distributed simulation protocols Transactions request Completed transactions TPS Figure 5 TPS Overview System Entity Structure Let s assume that the primitive models of the TPS are already developed and stored in the model base From these models a configuration expert can construct the SES which organizes possible architecturs of the TPS and its performance evaluation module The root entity TREE is the top level entity to evaluate a TPS architecture It is composed of transaction processing system TPS and experimental frame BF TPSis composed of TM for transaction manager 7P for transaction processes CC for concurrency control CPU and DISKS Using the ccspcc the CC can be implemented with the twophase locking Lock the imm ediaterestart Restart or the optimistic Optl zm stic algorithms CPU is actually composed of Buff which stores the operations of transactions and Pmc which actually executes the operations The Bufmay be classified into two specialized types FIFO LIFO under the specialization bu ispcc And the Proc is also classified into high performance processor Hproc and low performance one Lproc The IF can be composed of several transaction processes from one 7P1 to 16 71015 The DISKSmay be configured with either one disk disksr1661 or two disks dI39SkSdccb Each disk also has a buffer There are several attributes such as variables and couplings attached to entities and aspects TPsiEXP El uul l39PS m tpsrg tp39dm rrs out EF my EF TPS urrs m rM llnnsl TM our TV m mar my Hump whoa x v trnnd s UHIHH tm 1 M nu mstD m GENR mp3 11gt of m my cpu cw ms Rfrdec QENR MVEF Wm W541 w a Auk msKs nmcv uul w canal CPU out TP L puch DISKS unl TP disknclj39 l l l GENR TRANSD TM TP cc CPU wwwmuu II Bull out PIUC m genrrspcc lpyspec Ccrspec Cymdm Tommi jaxdy r vac our nul HGENR LGENR TP TN 11216 Luck Rcslan OpLimislic Buff Pro H II T TPS Inn9951186 procrspec DISKS FIFO LIFO Hpmc LPWC DISKS m Bull in dis de disC3420 Bun mu Tiwk m1 Disk Alone Bull mum WM out D SKS our Dacider v w EU DISK dxksOdcc dz39sksIdac Buf Diskl Buffl Diskl Figure 6 SES for TPS and its experimental frame Model Base As shown in Figure 6a the model base is an organized library for component models in modular form Such component models can be either atomic or coupled models specified in the DEVS formalism Since the entity structure of 0 manages the component models in the model base there is a correspondence between entity names and model names A simple correspondence is that names of node entities are identical to names of the corresponding models in the model base In this case names of atomic models in the model base are labels of leaf nodes of type entity in the SES Care must be taken with coupled models if any in the model base since they represent already pruned structures Thus the name of a coupled model also labels a corresponding entity in the SES that has children nodes of aspect type 7 but there is no specialization type on any path from the node down to the leaves Pruning and model synthesis Once the TPSiEXP entity structure has been constructed a designer can explore alternative transaction processing architectures using the pruning operation Many alternatives may be extracted from the SES Among the alternatives the most interesting ones arise from the CC and TP specializations Consider the following design objective Find an optimal number oftransa ction processes and a best concurrency control algorithm Which give both high throughput and Iowresponse time The design objective requires us to construct several kind of simulation models each with different algorithm for concurrency control and with different number of transaction processes The number of transaction processes puts a limit on the number of transactions allowed to be active at any time Table l shows an example of the pruning choices consistent with the design objective It selects the 7P8 for the 7P specialization the Lockfor the CC specialization and so on Entity Selection Input TP tpspec TP8 CC ccspec Lock Proc procspec Hproc Buff buffspec FIFO DI SKS aspect disksdecl GENR genrspec HGENR Table 1 Pruning Specification A configuration expert who constructed the TPS entity structure may also provide some facilities to help users generate good alternatives by constraining the pruning process as mentioned earlier Figure 7 shows an example pruned entity structure A simulation model can be synthesized by retrieVing component models from the model base which correspond to entities in the PES from the model base Figure 8 shows the synthesized model TPSEXP from PBS of Figure 7 TPSEXP I EFout TPSin tpsrexp39dec TPSout EFin EF TPSin TMtrans TMout TP8in l EFin TRANSDsolved TP8transd TPSout TP8tm TMin e dec TRANSDDut HGENRStOp tpsdec TP8cc Lockin TP8cpu CPUin HGENRDut 1330110 TP8disk DISKSin Lockout TP8ccack l CPUout TP8cpuack DISKSbut TP8diskack HGENR TRANSD TM TPS Lock CPU DISKS I CPUin FIFOin I DISKSin FIFOin FIFOout Hprocin I FIFOout Diskin Cp dec Hprocdone FlFOready dlSkSdecj Diskdone FlFOready Hprocout CPUout Diskout DISKSout FIFO Hproc FIFO Disk Figure 7 TPS Pruned Entity Structure TPSEXP EF out stop out solved HGENR TRANSD V out kin in out TPS l trans transd in tm cc in TM LOCk out in ccack out CPU TP8 DISKS A in Ain cpu disk in in out FIFO FIFO out ready ready E in done done in HPTOC out 7 out cpuack V diskack out out DISk Figure 8 Synthesized Simulation Model for TPS Evaluation Performance Evaluation Once a simulation model is synthesized performance evaluation can be carried out via simulation experiments Performance indices to be measured in the experimental frame should be derived from the design objectives Recall that our design objective was to find the optimal number of transaction processes and a best concurrency control algorithm for both high throughput and fast response time Thus our performance indices are throughput and response time These will be measured for different concurrency control strategies as a function of number of concurrent transaction processes The model TRANSD transducer within the experimental frame is already designed to measure such indices The simulation model in 0 is used to evaluate the lock concurrency control strategy with a maximum of eight transaction processes For each alternative concurrency control strategy we provide a pruning specification of the form shown in Table 1 Each such specification generates a corresponding PES which automatically synthesizes an alternative simulation model for performance evaluation The pruningsynthesisevaluation process is repeated until an optimal number of transaction processes and a best concurrency control strategy are found If however the process fails to achieve the desired performance the designer must return to the extend or modify the SESMB For example one can add alternatives under appropriate specialization entities while developing component models for such alternatives and saving them in the model base Thus the plangenerationevaluation process in 0 is repeated until the desired performance is achieved Automatic Pruning of an SES Suppose that instead of having the user prune an SES for a desired model structure we provide an automatic means of iterating through all prunings Provided that the number of prunings is not too large this would provide an automated search capability for finding a best design If the number of design alternatives is too large for an exhaustive search we have to turn to more natural and artificial intelligence to constrain the search space To provide such search capability we need an algorithm that given an SES is capable of computing its total number of prunings and iterating through them oneatatime each time synthesizing the associated hierarchical simulation model from the model base and evaluating it In the following we describe a design of such an algorithm Entity E Edec l l i l E1 E2 E3 Counter N N N3 Number 1 2 3 f alternatives E2Spec Figure 9 Enumerating SES Prunings Recall that an SES is built recursively with alternating specializations and decompositions Likewise the number of alternative prunings can be enumerated and generated recursively An nCounter is used to iterate through the number of alternatives n at each specialization A multicounter which is a serial composition Chapter 5 of nCounters iterates through all alternatives under a decomposition by stepping its component nCounters through these alternatives one at a time The number of alternatives under a decomposition is the product of the alternatives under its entities For example there are nCounters for each of the subtrees under E1 E2 and E3 under Edec in Figure 9 The multicounter under Edec cycles through a total of NlgtltN2gtltN3 alternatives The number of alternatives under a specialization is the sum of those under its entities For example the number under E2spec in Figure 9 is SlSZS3 This recursion stops when leaf entities are encountered The number of alternatives represented by a leaf entity is just 1 itself Finally the number of prunings of the SES is the number of alternatives under the root node Exercise Recall the design the nCounter as a parameterized atomic model Design the multicounter as parameterized coupled model With nCounter components Write the formal algorithm that assigns nCounters and multicounters to nodes in the SES Design an iteration control that steps the root nCounter through its cycle thereby stepping each of the
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'