Home

Technical Report CMU/SEI - School of Computer Science

1. QueueDefinition QueueDefinition GlobalPortName vv gt Transformation gt GlobalPortName QueueSize IntegerValue Examples queue ql pl gt gt p2 Two ports connected through a new unbounded queue The two ports must have the same typ reconnect ql pl gt gt p2 Two ports connected through a previously declared queu The two ports must have the same typ queue q2 100 pl gt xyz gt p2 Two ports connected through a bounded size 100 queue Data are transformed in the queue by a process xyz queue q3 pl gt gt NULL A queue with a grounded destination port Meaning A queue definition establishes a logical link between two ports that communicate by passing data from the first port source to the second port destination A queue is not permanently attached to the ports specified in the queue s declaration and can be recon nected i e attached to other ports via the reconnect statement in the structure clause of a reconfiguration statement Section 8 5 The optional queue bound in a queue declaration specifies the maximum number of elements that will be stored in the queue at any one time If a queue is reconnected the original declared queue bound is retained If a queue is full when a enqueue operation is attempted the process trying to store the data waits until the queue has space for the new item If
2. Abstract Durra is a language designed to support the development of large grained parallel programming applications These applications are often computation intensive or have real time requirements that require efficient concurrent execution of multiple tasks devoted to specific pieces of the appli cation During execution time the application tasks run on possibly separate processors and communicate with each other by sending messages of differ ent types across various communication links The application developer is responsible for prescribing a way to manage all of these resources We call this prescription a task level application description It describes the tasks to be executed the possible assignments of processes to processors the data paths between the processors and the intermediate queues required to store the data as they move from source to destination processes Durra is a task level description language a notation in which to write these application descriptions This document is a revised version of the original reference manual 2 It de scribes the syntax and semantics of the language and incorporates all the lan guage changes introduced as a result of our experiences writing task and ap plication descriptions in Durra A companion document Durra A Task Level Description Language User s Manual 7 describes how to use the compiler runtime environment and support tools 1 Introduction Durra also called
3. The interface portion of a task description or a task selection provides information about the ports of the processes instantiated from the task A port declaration specifies the direction of the data movement and the type of data moving through the port 5 2 Rules for Matching Selections with Descriptions If a task selection provides a port declaration clause the port declarations must be iden tical i e names directions and types of the ports must be identical CMU SEI 89 TR 34 15 16 CMU SEI 89 TR 34 6 Behavioral Information Syntax BehaviorPart BEHAVIOR REQUIRES vv predicate ES ENSURES AVEF predicate Van TIMING TimingExpression predicate Larch Predicate Meaning The behavior part of a task description specifies functional and timing information about the task The functional information consists of a pre condition requires on what is required to be true of the data coming from the input ports and a post condition ensures on what is guaranteed to be true of the data going to the output ports The timing information part consists of a timing expression timing describing the behavior of the task in terms of the operations it performs on its input and output ports The formal meaning of the behavioral information is essentially based on first order logic In what follows we give only an informal introduction
4. Indian millet and Guinea corn is a type of grain sorghum with slender stalks widely grown in warm dry regions Durra sounds like durable which isn t a bad connotation Carnegie Institute personnel indicated that corn is by far the largest in size of all grains We re spectfully declined their suggestion for a name denoting largest grain Many computation intensive real time applications require efficient concurrent execution of multiple tasks independent programs devoted to specific pieces of the application Typical tasks include sensor data collection obstacle recognition and global path plan ning in robotics and vehicular control applications Since the speed and throughput re quired of each task may vary these applications can best exploit a computing environ ment consisting of multiple special and general purpose processors that are logically though not necessarily physically loosely connected We call this environment a heterogeneous machine CMU SEI 89 TR 34 1 During execution time processes which are instances of tasks run on possibly sepa rate processors and communicate with each other by sending messages of different types Since the patterns of communication can vary over time and the speed of the individual processors can vary over a wide range additional hardware resources in the form of switching networks and data buffers are required in the heterogeneous machine The application develo
5. or strings as the case may be and compatibility is based on value equality If the attribute is predefined in the language compatibility is attribute dependent See Ap pendix B b for details about the predefined attributes 7 1 Rules for Matching Selections with Descriptions If a task selection includes an attribute expression a predicate a matching task de scription must provide values that satisfy the predicate i e the expression yields true when evaluated in the context of the values declared for the attribute If a task descrip tion provides a list of values for an attribute a matching task selection is satisfied if any of these values satisfies the expression For example if a task description includes an attribute size with values 1 3 5 then a task selection with an attribute expression of the form size gt 4 is satisfied by the task description because the value 5 makes the attribute expression true If a task selection includes an attribute expression a predicate that uses an attribute not present in a task description or if a task description provides attributes not used in the attribute expression of a task selection these attributes are ignored for the purposes of matching a library task 24 CMU SEI 89 TR 34 8 Structural Information Syntax StructurePart STRUCTURE StructureClause_List ace StructureClaus PROCESS ProcessDeclarat
6. TM E1 i lt 1M E2 i A TM E2 i lt 1M E1 i when W gt E1 Mp E1 Y i W M E1 1 before a1 gt E1 Mp E1 V i TM E1 i lt a1 after a1 gt E1 Mp E1 Y i M E1 i 2 a1 during a1 a2 gt E1 Myp El a vi al lt M E1 i lt a2 during a1 r2 gt El My El avilals TM o E1 i sal r2 Alri r2 Vi TA i r1 lt OA i lt TA i r2 A r1 Vi A i lt TA i r1 Alrt viL TA i r1 lt JA i A true a My Mapping from Timing Expressions to Booleans Timing Expression M Timing Expression E M E loop E1 M E1 E1 En Mj E1 M En El En oat Mas My EN guard gt El me snai guards when before during after A t1 t2 A b My Mapping From Timing Expressions to Operations Table A 2 Assigning Meaning to Timing Specifications task taskname behavior requires Req ensures Ens timing E end taskname we give meaning to the predicates of the functional specification as related to time i e CMU SEI 89 TR 34 37 at what times are these predicates to hold via a function M Table A 3 which maps from behavioral specifications to Boolean values M Predicate x Timing Expression Boolean Pred Expr M Predicate Timing Expression Req E M Req E V i Req TM E i A Mp EDI Ens E M Ens E Vi Ens 1M E 1 A M E Consistent Ens E Table A 3 Assigning Meaning to
7. a function returning an integer a real a string or a time value can appear instead of an integer a real a string or a time value respec tively B b Predefined Attributes The following attributes are predefined in the language mode implementation processor source xwindow xdisplay and debug B b 1 Mode Attribute 42 CMU SEI 89 TR 34 Syntax ModeAttr MODE Identifier Examples mode Round_Robin Meaning The values of the mode attribute are identifiers denoting the operation performed by one of the predefined tasks broadcast merge and deal Possible values are de scribed in Section B c The identifiers used as values for the mode attribute are just a convenient shorthand to select what are expected to be frequently used tasks B b 2 Implementation Attribute Syntax ImplementationAttr IMPLEMENTATION StringValue Examples implementation demo Meaning The value of the implementation attribute is the name of the file containing the actual object code The format of a file name may vary with the host operating system B b 3 Processor Attribute Syntax ProcessorAttr PROCESSOR Identifier Examples processor processor processor ibm1401 sun sunl Meaning The configuration of the heterogen
8. to give meaning to the combination of our functional and timing specifications We use four of their notational conventions Syntax Meaning TA The start of an operation action in RTL s terminology JA The end of an operation E i The time of the i occurrence of event E where events in our con text are the start of an operation or the end of an operation is an occurrence function that captures the notion of real time P t1 t2 The interval of time during which the predicate P holds P holds be fore or at t1 from t1 to t2 and at or after t2 If t1 and t2 are iden tical then P holds at an interval around t1 For brevity we will use P t when t1 t2 i e P holds around time t A a Assigning Meaning to Timing Specifications In this section we describe the meaning of our timing specifications in terms of RTL logic In the following discussion we assume E E1 and E2 are arbitrary timing expres sions A A1 and A2 are operations t1 and t2 are times absolute or relative al and a2 are absolute times ri and r2 are relative times and W is a predicate of a when guard To simplify the exposition we introduce a simple rewrite rule Any timing expression of the form repeat n gt E can be rewritten as a sequence of n occurrences of the un guarded expression E E EE E Thus the only guards we need to consider are before after during and when Table A 1 gives the axioms that describe the st
9. 42 43 ImplementationAttr 43 In 6 15 IndeterminateTime 18 Integer 5 IntegerLiteral 7 IntegerValue 7 9 18 19 26 InterfacePart 11 13 15 InternalPortName 30 Is 6 9 Loop 6 19 20 Merge 6 48 46 47 Minus_time 6 41 Mode 6 42 43 46 ModeAttr 43 Not 6 8 Null 6 26 27 28 29 Of 6 9 Or 6 8 Out 6 15 ParallelEvent 19 Plus_time 6 41 42 Port 4 6 11 15 PortBinding 25 30 PortDeclaration 15 PortName 6 15 30 Predicate 17 Primary 8 Process 4 6 25 ProcessDeclaration 25 ProcessName 6 25 Processor 4 6 42 43 44 ProcessorAttr 43 ProcessQueueName 6 30 ProcessQueueTermination 30 Ptime 6 18 20 21 Queue 4 6 25 QueueDeclaration 25 26 QueueDefinition 26 QueueName 6 26 QueueOperation 18 QueueReconnection 25 26 QueueSize 26 50 Real 5 RealLiteral 7 RealValue 7 18 Reconfiguration 6 25 30 ReconfigurationExit 30 ReconfigurationLabel 30 Reconnect 6 25 Record 6 9 RecordTransform 27 Relation 8 Remove 6 30 Repeat 6 19 20 Requires 6 17 ScalarTransform 27 Seconds 18 SequentialEvent 19 Signal 6 41 42 Size 6 9 Source 6 42 44 SourceAttr 44 String 5 StringLiteral 7 StringValue 7 43 44 45 Structure 6 13 25 StructureClause 25 30 StructurePart 11 25 Switch 4 Task 4 6 11 13 TaskDescription 8 11 TaskName 6 11 13 TaskSelection 13 25 Term 8 Then 6 30 TimeBase 18 TimeLiteral 7 18 TimeValue 7 18 19 TimeWindow 18 19 Timing 6 17 TimingExpression 17 19 T
10. A real num ber can terminate with a period without a fractional part CMU SEI 89 TR 34 1 4 Keywords and Predefined Identifiers Keywords and predefined identifiers are highlighted in normal text by writing them in bold face or inside quotation marks respectively The following words are keywords in the language after and array atime attribute attributes before behavior bind binds dtime during end ensures exit if in is loop not of or out port ports process processes ptime queue queues reconfiguration record reconnect reconnects remove repeat requires size structure task then timing to type union when Several keywords exist in both singular and plural form and have the same meaning in either form process processes port ports queue queues bind binds and attribute attribute The following words are predefined identifiers in the language broadcast current_atime current_dtime current_ptime current_size deal debug delay dequeue enqueue implementation merge minus_time mode signal source null plus_time processor xdisplay xwindow 1 5 Local and Global Names In a task description the writer declares the names of task components such as ports atributes queues etc These names are local and unique within a task Outside a task its compone
11. Combined Specifications The predicate Consistent Ens E used in the definition of M checks to see if the ensures Ens predicate is meaningful with respect to the timing expression E Consistent is defined by using two auxiliary predicates Uses and Depends We define Uses Uses element x input queue x output queue x Predicate gt Boolean such that for all input queues qip output queues doup elements in the output queues x Uses x Gin dout ENS true if qin appearsin x a Ens gt isIn Qout X false otherwise UsesSet x Qout Ens Gin Uses x Qin dout ENS for all x such that isIn Ayur X where a appearsin b is a syntactic relation that checks if the text a occurs in the text b Intuitively Uses checks to see if the computation of x the element enqueued on Qyut can be proven from the Ens to use any of the elements from qip We define Depends Depends element x input queue x output queue x Timing Expression gt Boolean such that for all input queues qip output queues q elements in the output queues x and for all 1 lt i lt length q where q yy is first rest go p Dependsi i q Qin Gout E true if E E1 qo E2 or E E1 Qour E2 or E E1 9 11 E2 and Qin appearsIn E1 and qu appearsin El i 1 times false otherwise DependsSet x qu E qin Depends x Gin dout E for all x such that isIn Qout X Intuitively Depends says that output elements can depend on only elements t
12. Licensing Agent NO WARRANTY THIS CARNEGIE MELLON UNIVERSITY AND SOFTWARE ENGINEERING INSTITUTE MATERIAL IS FURNISHED ON AN AS IS BASIS CARNEGIE MELLON UNIVERSITY MAKES NO WARRAN TIES OF ANY KIND EITHER EXPRESSED OR IMPLIED AS TO ANY MATTER INCLUDING BUT NOT LIMITED TO WARRANTY OF FITNESS FOR PURPOSE OR MERCHANTABILITY EXCLUSIVITY OR RESULTS OBTAINED FROM USE OF THE MATERIAL CARNEGIE MELLON UNIVERSITY DOES NOT MAKE ANY WARRANTY OF ANY KIND WITH RESPECT TO FREEDOM FROM PATENT TRADEMARK OR COPYRIGHT INFRINGEMENT This work was created in the performance of Federal Government Contract Number F19628 95 C 0003 with Carnegie Mellon University for the operation of the Software Engineering Institute a federally funded research and development center The Government of the United States has a royalty free government purpose license to use duplicate or disclose the work in whole or in part and in any manner and to have or permit others to do so for government purposes pursuant to the copyright license under the clause at 52 227 7013 This document is available through SAIC ASSET 1350 Earl L Core Road PO Box 3305 Morgantown West Virginia 26505 Phone 304 284 9000 FAX 304 284 9001 World Wide Web http www as set com sei html e mail webmaster O www asset com Copies of this document are available through the National Technical Information Service NTIS For informa tion on ordering please contact NTIS directly Nat
13. Matching Selections with Descriptions Structural Information 8 1 Process Declarations 8 2 Queue Declarations 8 3 Data Transformations 8 4 Port Bindings 8 5 Reconfigurations References CMU SEI 89 TR 34 O 0 JJOO Bh ON Appendix A Formal Meaning of Timing Expressions A a Assigning Meaning to Timing Specifications A b Assigning Meaning to the Combined Specifications A c Examples Appendix B Predefined Language Facilities B a Predefined Functions B b Predefined Attributes B b 1 Mode Attribute B b 2 Implementation Attribute B b 3 Processor Attribute B b 4 Source Attribute B b 5 Window Attribute B b 6 Display Attribute B b 7 Debug Attribute B c Predefined Tasks B c 1 Broadcast Task B c 2 Merge Task B c 3 Deal Task B c 4 Examples Index CMU SEI 89 TR 34 List of Figures Figure 1 Figure 2 Figure 3 Figure 4 Figure 5 Figure 6 Figure 7 Mapping of Logical and Physical Components A Template for Task Descriptions A Template for Task Selections Use of Global Attribute Names Nested and Alternative Reconfiguration Statements Merge Task Divide Task CMU SEI 89 TR 34 11 13 24 32 39 40 CMU SEI 89 TR 34 List of Tables Table A 1 Axioms About Operation Start and End Times Table A 2 Assigning Meaning to Timing Specifications Table A 3 Assigning Meaning to Combined Specifications CMU SEI 89 TR 34 36 37 38 Durra A Task Level Description Language Reference Manual
14. R 34 47 48 CMU SEI 89 TR 34 Index 17 7 8 9 19 23 27 41 7 8 9 19 23 27 41 18 l 8 15 25 26 27 30 15 17 23 25 30 lt 8 After 6 19 20 And 6 8 Array 6 9 ArrayDimension 9 ArrayTransform 27 Atime 6 18 20 21 Attribute 6 23 AttributeDescPart 11 23 AttributeSelPart 13 23 AttrName 6 23 AttrValue 23 BasicEvent 19 Before 6 19 20 Behavior 6 17 CMU SEI 89 TR 34 BehaviorPart 11 13 17 Bind 6 25 Broadcast 6 43 46 47 Buffer 3 Buffers 4 Comment 5 CompilationUnit 8 Configuration file 43 45 Conjunction 8 Consistent 38 39 40 Current_atime 6 41 Current_dtime 6 41 Current_ptime 6 41 Current_size 6 41 42 Deal 6 43 46 47 Debug 6 42 45 DebugAttr 45 Delay 6 18 19 20 21 Depends 38 DependsSet 38 39 40 Dequeue 6 18 19 Disjunction 8 DisplayAttr 45 Dtime 6 18 20 During 6 19 21 Durra compiler 3 7 8 23 41 47 Durra excutive 3 Durra executive 23 31 41 42 44 45 Durra library 3 ElementSize 9 End 6 11 13 30 Enqueue 6 18 19 26 Ensures 6 17 Event 18 19 Executive 4 Exit 6 30 31 Expression 8 19 23 30 ExternalPortName 30 Field 9 FieldName 6 9 27 FieldTransform 27 FunctionCall 7 41 FunctionName 7 41 FunctionParameters 7 41 GlobalAttrName 6 7 GlobalPortName 6 18 26 30 GlobalProcessName 6 27 49 GlobalQueueName 6 Guard 19 Identifier 5 6 7 30 43 45 If 6 30 Implementation 4 6
15. Technical Report CMU SEI 89 TR 034 ESD TR 89 045 Durra A Task Level Description Language Reference Manual Version 2 Mario R Barbacci Jeannette M Wing September 1989 Technical Report CMU SEI 89 TR 034 ESD TR 89 045 September 1989 Durra A Task Level Description Language Reference Manual Version 2 Mario R Barbacci Jeannette M Wing Software for Heterogeneous Machines Project Unlimited distribution subject to the copyright Software Engineering Institute Carnegie Mellon University Pittsburgh Pennsylvania 15213 This report was prepared for the SEI Joint Program Office HQ ESC AXS 5 Eglin Street Hanscom AFB MA 01731 2116 The ideas and findings in this report should not be construed as an official DoD position It is published in the interest of scientific and technical information exchange FOR THE COMMANDER signature on file Thomas R Miller Lt Col USAF SEI Joint Program Office This work is sponsored by the U S Department of Defense Copyright 1989 by Carnegie Mellon University Permission to reproduce this document and to prepare derivative works from this document for internal use is granted provided the copyright and No Warranty statements are included with all reproductions and derivative works Requests for permission to reproduce this document or to prepare derivative works of this document for external and commercial use should be addressed to the SEI
16. a cross bar switch intelligent buffers on the switch sockets and a executive that can communicate with all processors buffers and I O devices Actual experience with the implementation of the language and runtime environment and building demonstration applications 4 5 6 8 13 9 have resulted in a number of changes to the language and these changes are reflected in the revised version of this language reference manual 1 1 Scenario The following is a scenario from the user s viewpoint of how the task level language is used to help develop an application to run on some target heterogeneous machine We see three distinct phases in the process a the creation of a library of tasks b the creation of an application description and c the execution of the application Library creation activities These happen early in the life of an application when the primitive tasks are defined 1 The developer breaks the application into specific tasks Typical tasks are sensor processing feature recognition map database management and route planning Other tasks might be of a more general nature such as sorting array operations etc 2 CMU SEI 89 TR 34 2 The developer writes task implementations i e programs For a given task there may be possibly many implementations differing in program ming language e g C Lisp Ada processor type e g Motorola 68020 DEC VAX performance characteristics or other attributes The wri
17. a from their input queues and store data in their output queues following a task specific pattern provided by a timing expression A timing expression describes the behavior of the task in terms of the operations it performs on its input and output ports this is the behavior of the task seen from the outside 6 2 1 Time Literals Syntax TimeLiteral Seconds TimeBase IndeterminateTime Seconds IntegerValu RealValue TimeBase DTIME Time since start of day ATIME Time since start of application PTIME Time since start of process IndeterminateTime Examples 3615 5 atime An application relative time 1 hour and 15 5 seconds after the start of the application LLO Two and a quarter seconds relative to some previous event ia An indeterminate point in time Meaning Time values are used to specify points in time These can be either 1 absolute in which case they must be followed by the name of a time base the start of the day the application or the process or 2 relative to some prior event in a timing expression in which case a time base is not allowed All time values are measured in seconds An absolute time value using DTIME cannot exceed 86400 the number of seconds in a day 6 2 2 Event Expressions and Time Windows Syntax Event GlobalPortName QueueOperation DELAY TimeWindow Ti
18. abel fol lows the exit keyword the immediately enclosing label is assumed The condition following the when keyword acts as an assertion attached to the current structure of the application It can be used to terminate reconfigurations derived from it as shown in Figure 5 If condition_2 is ever satisfied the structure of the application changes back to the form it had when reconfiguration L_1 took place regardless of what reconfigurations e g L_2a L_2b L_3 might have taken place later In addition to these implicit terminations the inner reconfiguration statements can also have termina tion statements of their own CMU SEI 89 TR 34 31 reconfiguration L_1 if condition_1 then remove F process 7 queue reconfiguration Ti 2a f then end if 1 2295 ts pe then reconfiguration Ti 32 If sa then end if end if exit when condition_2 Terminates L_2a L_2b L_3 etc end if Figure 5 Nested and Alternative Reconfiguration Statements The exit statement condition if present might never be satisfied in which case only a parent configuration s exit statement can terminate the current reconfiguration 32 CMU SEI 89 TR 34 References 1 2 3 4 gt 6 7 8 9 E A Arnould F J Bitz E C Cooper H T Kung R D Samson and P A Steenkiste The Design of Nectar A Network Backplane for Heterogeneous Multicomputers In Proceedings of t
19. art and end times of operations and composition of operations We assign a meaning to timing expressions by introducing a function My Table A 2 a which maps timing expressions to Boolean values My Timing Expression Boolean In the definition of M we use an auxiliary function M Table A 2 b which maps timing expressions to operations Mio Timing Expression Operation My is needed because start time and end time are meaningful only for queue opera tions As an example of how to interpret the formalism intuitively consider the entries for the during guard in Table A 2 a This guard specifies a time window during which the oper ation is allowed to start The first time value of the window is the earliest start time CMU SEI 89 TR 34 35 1 For any queue operation A and for some implementation defined time window T1 T2 the following axiom expresses the default duration of the operation V i T1 lt A i EA lt T2 2 For any queue operation A t1 t2 with a duration defined by the time window t1 t2 the following axiom expresses the duration of the operation vilti lt JA OA lt t2 3 For any sequence of queue operations A A1 An the following axiom relates the start and end times of the composition to the start and end times of the individual opera tions v i TA i TA1 i A A i JAn i 4 For any parallel queue operations A A1 An the foll
20. broadcast ports port declarations end broadcast B c 2 Merge Task The task merge has one output port and as many input ports as needed The type of the output port is the union of all the input types Input data items are merged and sent to the output port task merge ports port declarations attributes mode identifier end merge A merge discipline must be provided as a value to the mode attribute in a merge task selection as described in Section B b 1 Possible values include fifo ordered by time of arrival to the merge process and round_robin one datum from each consecu tive input port and repeating Because of transmission delays the order of arrival of the data might differ from the order in which the data were sent out A FIFO merge process uses time of arrival not time of creation to order the data B c 3 Deal Task The task deal has one input port and as many output ports as needed The type of the input port is the union of all the output types Input data items are sent to one output port task deal ports port declarations attributes mode identifier end deal A deal discipline must be provided as a value to the mode attribute in a deal task selection as described in Section B b 1 Possible values include fifo output to the first port with a waiting consumer with a random choice if there is more than one waiting consumer round_robin output
21. cifies the properties of a terminal emulator un der the X Window screen management system The values of the attributes are used by the Durra executive to start a terminal emulator under which the task implementation will execute These attributes are useful when the task implementation is an interactive pro gram Otherwise the input and output streams of all the task implementations running on a given processor might be scrambled together B b 6 Display Attribute 44 CMU SEI 89 TR 34 Syntax DisplayAttr XDISPLAY Identifier Examples xdisplay SUN_1 Meaning The configuration of the heterogeneous machine specifies the different values for the xdisplay attribute including names of classes of processors as well as names of indi vidual processors as illustrated above This information is maintained in a configuration file accessed by the runtime environment See the Durra User s Manual 7 for additional details The value of the xdisplay attribute specifies the name of a display for a terminal emulator under the X Window screen management system The value of the attribute is used by the Durra executive to start a terminal emulator under which the task implemen tation will execute This attribute is useful when for instance one would like all inter active tasks to display their output at a given console regardless of which processor the task is running on The default is the d
22. d M is the meaning function mapping a predicate and timing expression into a Boolean 3 A task description matches a task selection if the predicate associated with the be havioral information of the task description implies that of the task selection If no timing expression appears the predicate simplifies to R gt E and that of a task description must imply that of the task selection CMU SEI 89 TR 34 21 22 CMU SEI 89 TR 34 7 Attributes Syntax AttributeDescPart ATTRIBUTE Attribute _ List micolon 7 Attribute AttrName AttrValue AttrName 7 Y AttrValue_List omma as and AttributeSelPart ATTRIBUTE Expression Examples Attributes in a task declaration attributes author 3mw color red white blue implementation cowcatcher queue_size 25 Attributes in task selections attributes processor Sun attributes author jmw or author mrb attributes color red Or color blue and not author Mr_Ed Meaning Attributes specify miscellaneous properties of a task They are a means of indicating pragmas or hints to the Durra compiler and the Durra executive In a task description the developer of the task lists the possible values of a property in a task specification the user of a task writes an expression listing the desired name values of the task s property All attr
23. d is followed by a time window during which the sequence is allowed to start The first value is the earliest start time allowed and must be an absolute time value the second value is the latest start times allowed and can be an absolute time value or a time value relative to the former If the time base of the latest start time is PTIME or ATIME and the deadline has elapsed the task is ter minated This guard describes what is required to be true of the state of the system e g time values and queues sizes before the sequence is allowed to start It is a pre condition for starting the sequence 6 2 4 Restrictions on Time Values and Time Windows Although the syntax allows both absolute and relative time values to appear in either of the two boundaries in a time window not all of the possible combinations make sense 1 In the time window attached to delay operation the time values must be relative i e no time basis allowed and are interpreted relative to the start of the operation 2 In the time window of a during guard the first time value Tin must be absolute The second time value Tmax can be absolute or relative In the latter case the time value is relative to T min 6 3 Rules for Matching Selections with Descriptions The meaning of the behavioral information is a predicate M R T gt M E T where R is the requires predicate E is the ensures predicate T is the timing expression an
24. e timing expression says that the computation of the quotient need depend on only what is in a and not what is in b This inconsistency can be formally proven since UsesSet first q q Ens a b DependsSet first q g E a More specifically to show UsesSet first q q Ens a b we first note that Uses quotieni first a first b a q Ens true Uses quotieniffirst a first b b q Ens true since a and b both appear in the first argument assume quotient is a trait operator for real numbers Using equational reasoning on the Ens we can show first q quotient first a first b By substitution we get Uses first q a q Ens A Uses first q b q Ens yielding UsesSet first q q Ens a b 40 CMU SEI 89 TR 34 Appendix B Predefined Language Facilities In this appendix we define the functions attributes and tasks that are built in into the language and are implemented by the Durra compiler or the Durra executive B a Predefined Functions The following functions are predefined in the language current_dtime current_atime current _ptime minus_time plus time current_size and signal Some functions compute the time elapsed from the beginning of the day the start of the application or the start of a process Other functions perform computations with time values Finally there is one function that returns the number of elements stored
25. eous machine specifies the different values for the processor attribute including names of classes of processors as well as names of indi vidual processors as illustrated above This information is maintained in a configuration file accessed by the runtime environment See the Durra User s Manual 7 for additional details CMU SEI 89 TR 34 43 The value of the processor attribute can vary in specificity by using a processor class name or an individual processor name For example SUN means any SUN processor SUN1 means a specific SUN processor If the user specifies the name of a class of processors as the value of the processor attribute any member of the class can be used to execute the task B b 4 Source Attribute Syntax SourceAttr SOURCE StringValue Examples source this is a string Meaning The value of the source attribute specifies an initial parameter to be passed to the task implementation when it is started by the Durra executive The actual means of passing this parameter is implementation dependent e g command line environment variable predetermined file location The parameter can be used by the task implementation for any purpose or can be ignored B b 5 Window Attribute Syntax WindowAttr XWINDOW StringValue Examples xwindow geometry 80x24 200 200 Meaning The value of the xwindow attribute spe
26. ependent optimization 8 4 Port Bindings Syntax PortBinding ExternalPortName InternalPortName ExternalPortName PortName InternalPortName GlobalPortName Example binds inl p_deal inl outl p_merge outl Meaning A port binding maps a port defined by an inner task to a port defined by an outer task 8 5 Reconfigurations Syntax Reconfiguration 1 ReconfigurationLabel IF Expression THEN ProcessQueueTermination StructureClause_List space ReconfigurationExit END hanan i ReconfigurationLabel Identifier ProcessQueueTermination REMOVE ProcessQueueName_List omma in ReconfigurationExit EXIT ReconfigurationLabel WHEN Expression 30 CMU SEI 89 TR 34 Examples reconfiguration L_1 if condition_to_enter_this_configuration then remove process_and_queue_names process declare new processes queue declare new queues reconects reconnect old queues exit L_1 when condition_to_exit_this_configuration end if Meaning A reconfiguration statement is a directive to the Durra executive It is used to specify changes in the current structure i e the process queue graph of the application and the conditions under which these changes take effect Typically a number of existing proc esses and queues are substituted by new proce
27. er a task that merges data coming from two input into one output queue as shown in Figure 6 task merge ports inl in2 in item outl out item behavior ensures outl insert insert outl first inl first in2 timing loop in2 outl inl outl end merge Figure 6 Merge Task The ensures clause specifies that the output queue s items be ordered such that the item from in1 is before that from in2 but the timing expression specifies that if the item from in1 is output on the queue outi it must be the second not first item in the queue here we assume that the output queue is initially empty This inconsistency can be formally proven CMU SEI 89 TR 34 39 UsesSet first out1 out1 Ens in1 DependsSet first out1 out1 E in2 Since the UsesSet is not a subset of the DependsSet for first out1 Consistent Ens E is false The example in Figure 7 illustrates why subsetting and not equality is used in the defini tion of Consistent It also shows the use of the Ensures predicate and the need for equational reasoning about elements in a queue see the second conjunct in the Uses predicate task divide ports a b in real q r out real behavior ensures first ost first a first r timing loop a q b r end merge post first b Figure 7 Divide Task The ensures clause in the Divide task specifies that the quotient of b divided by a is in q and the remainder in r however th
28. ess or equal 1 8 Compilation Units There are two kinds of compilation units i e separately compilable units type declara tions and task descriptions CompilationUnit TypeDeclaration TaskDescription Each compilation unit must be submitted to the Durra compiler as a single text file If no errors are detected the unit is entered into the library 8 CMU SEI 89 TR 34 2 Type Declarations Syntax TypeDeclaration TYPE TypeName IS TypeStructure TYPE TypeName IS UnionStructure TypeStructure SIZE ElementSize NARRAY OF TypeName VYARRAY ArrayDimension OF TypeName RECORD 77 ELeld List sa wa ears ArrayDimension a EA IntegerValue_LiSt ace FEAT DE Positive integers ElementSize IntegerValue Positive number of bits IntegerValue TO IntegerValue Non negative size rang Field FieldName TypeName UnionStructure UNION wate TypeName List oma Examples type packet is size 128 to 1024 Packets are of variable length type tails is array 5 10 of packet Tails are 5 by 10 arrays of packets type mix is union heads tails Mix data could be heads or tails type rec is record header integer size integer data packet Recs have two integers and one packet in that order Meaning Type declarations are compilation units tha
29. hat were previously or concurrently input We now define Consistent 38 CMU SEI 89 TR 34 Consistent Predicate x Timing Expression Boolean as follows Consistent Ens E V X V Qout lISIN Aout X gt UsesSet x qoup Ens c DependsSet x dout E Intuitively we check that each element x in each output queue depends on only ele ments that have been dequeued from input queues strictly before or concurrently with the enqueueing of x A c Examples In the absence of a timing expression we can perform standard first order reasoning on a functional specification For example if the multiply task s ensures predicate had the additional conjunct first out1 posi first in1 then by equational reasoning substitution of equals by equals we see that the ensures predicate is satisfiable only if first in1 first in2 first in1 In the absence of a functional specification we can use the axioms and rules of RTL plus our extensions listed in Section A a to determine inconsistent timing expressions For example if the expression is ini out1 in2 we can apply axiom 5 of Section A a to show that for each task cycle the end of the last input operation in2 cannot follow the end of the last output operation out1 thus invalidating the timing expression More interestingly however is to show how a combined specification can be proven inconsistent where in fact each separately is consistent and meaningful For example consid
30. he Third International Conference on Architectural Support for Programming Languages and Operating Systems ACM April 1989 M R Barbacci and J M Wing Durra A Task Level Description Language Technical Report CMU SEI 86 TR 3 DTIC ADA178975 Software Engineering Institute Carnegie Mellon University December 1986 M R Barbacci and J M Wing Specifying Functional and Timing Behavior for Real time Applications Lecture Notes in Computer Science Volume 259 Part 2 Proceedings of the Conference on Parallel Architectures and Languages Europe PARLE Springer Verlag 1987 pages 124 140 M R Barbacci C B Weinstock and J M Wing Programming at the Processor Memory Switch Level In Proceedings of the 10th International Conference on Software Engineering Singapore April 1988 M R Barbacci MasterTask The Durra Task Emulator Technical Report CMU SEI 88 TR 20 DTIC ADA199429 Software Engineering Institute Carnegie Mellon University July 1988 M R Barbacci D L Doubleday and C B Weinstock The Durra Runtime Environment Technical Report CMU SEI 88 TR 18 DTIC ADA199480 Software Engineering Institute Carnegie Mellon University July 1988 M R Barbacci D L Doubleday and C B Weinstock Durra A Task Level Description Language User s Manual Technical Report CMU SEI 89 TR 33 Software Engineering Institute Carnegie Mellon University September 1989 M R Barbacci D L Doubleday C B Weinstoc
31. ibute values used in matching task selections with task descriptions must be constants computable before execution time i e tasks and their implemen tations are static properties of an application Example attributes include author version number programming language file name and processor type There may be as many attributes as desired The name of an attribute can appear in any context in which its value can appear For instance if the user defines an attribute queue_size with an integer value as in the examples above then queue_size Can appear anywhere an integer value is expected This permits the user to define for example the size of message queues and use the name to specify families of tasks i e tasks that share the same value for some attri bute as shown in Figure 4 The syntax and semantics of the attribute values are attribute dependent If the attribute is not predefined in the language the values are treated as uninterpreted numbers time CMU SEI 89 TR 34 23 processes Master_Process task Master_Task A task selection attributes Key_Name some value Other attributes maybe end Master_Task pl task foo attributes Key_Name Master Process Key_Name Same attribute value as in Master Process end foo p2 task bar attributes Key_Name Master_Process Key_Name Same attribute value as in Master_Process end bar Figure 4 Use of Global Attribute Names values
32. in a queue These functions together with time and numeric literals constitute the terms used to build expressions in timing guards and reconfiguration conditions Syntax FunctionCall FunctionName FunctionParameters FunctionName CURRENT_DTIME CURRENT_ATIME CURRENT_PTIME MINUS_TIME PLUS_TIME CURRENT_SIZE SIGNAL FunctionParameters er VARE Value_List omma AS The type and number of parameters is function dependent Examples Plus_Time Current_DTime DTIME 9000 2 5 hours later i e 9 000 seconds from the current time Current_Size Master_Process Data_Port the size of a queue feeding a port Meaning The functions with names like current_ time return the number of seconds a real value from the start of the day the start of the application or the start of a process as suggested by their names The function call current_ptime task_or_process_name returns the elapsed time in seconds since the start of the current task i e the task in whose description this func tion is used or the start of a process instantiated inside the current task The function call minus_time some_time_value seconds returns the time value ob CMU SEI 89 TR 34 41 tained by subtracting a number of seconds a real or integer value from some time value The function call plus_time some_time_val
33. ion List micolon I QUEUE QueueDeclaration_ List emicolon RECONNECT QueueReconnection_ List micolon 5 BIND PortBinding_List semicolon rr RECONFIGURATION Reconfiguration_List micolon 7 Meaning Process and queue declarations appear under the keyword structure in a task descrip tion These declarations define a graph in which processes are the nodes and queues are the links These graphs depict the internal structure of a compound task The structure part of a task description provides the means for developing hierarchical task descriptions 8 1 Process Declarations Syntax ProcessDeclaration ProcessNam ELISE E TaskSelection Examples pl task finder p2 task finder ports foo in bar out end finder p3 p4 task finder attributes author mrb end finder Meaning An instance of a task is bound to each process s name The name of a task is the minimal part of a task selection Local actual names e g ports foo and bar in the example can be introduced by providing a port declaration provided that the types of ports specified in the task declaration are identical to those provided in the task selec tion Ifthey are left out the formal names used in the task description are used instead 8 2 Queue Declarations Syntax CMU SEI 89 TR 34 25 QueueDeclaration QueueName QueueSize QueueDefinition QueueReconnection QueueName
34. ional Technical Information Service U S Department of Commerce Springfield VA 22161 Phone 703 487 4600 This document is also available through the Defense Technical Information Center DTIC DTIC provides access to and transfer of scientific and technical information for DoD personnel DoD contractors and potential contrac tors and other U S Government agency personnel and their contractors To obtain a copy please contact DTIC directly Defense Technical Information Center Attn BRR 8725 John J Kingman Road Suite 0944 Ft Bel voir VA 22060 6218 Phone 703 767 8274 or toll free in the U S 1 800 225 3842 Use of any trademarks in this report is not intended in any way to infringe on the rights of the trademark holder B Table of Contents 1 a fF W N Introduction 1 1 Scenario 1 2 Terminology 1 3 Notes on Syntax 1 4 Keywords and Predefined Identifiers 1 5 Local and Global Names 1 6 Literal Values 1 7 Expressions 1 8 Compilation Units Type Declarations Task Descriptions Task Selections Interface Information 5 1 Port Declarations 5 2 Rules for Matching Selections with Descriptions Behavioral Information 6 1 Function Part 6 2 Timing Part 6 2 1 Time Literals 6 2 2 Event Expressions and Time Windows 6 2 3 Timing Expressions 6 2 4 Restrictions on Time Values and Time Windows 6 3 Rules for Matching Selections with Descriptions Attributes 7 1 Rules for
35. isplay associated with the processor on which the executive is running B b 7 Debug Attribute Syntax DebugAttr DEBUG StringValue Examples debug a db p usr projects hetsim tasklib current vax Meaning The value of the debug attribute is the command line that would be used to execute a task under control of the appropriate source level debugger The format of the com mand line depends on the language debugger and host operating system For example in the Unix implementation if the debug attribute is present the Durra executive starts the debugger by executing the command obtained by concatenating the debug attribute value with the implementation attribute value as in a db p usr projects hetsim tasklib current vax demo Since a separate terminal interface is required for each debugger activated this feature is only available when the environment supports the X Window Manager The effect is that instead of starting the task directly the runtime environment starts an xterm ter minal emulator and runs the specified debugger in it giving it the task name as an argu ment CMU SEI 89 TR 34 45 B c Predefined Tasks The following tasks are predefined in the language broadcast merge and deal B c 1 Broadcast Task The task broadcast has one input port and as many output ports as needed Input data are replicated and sent to all the output ports task
36. k S L Baur D C Bixler M T Heins Command Control Communications and Intelligence Node A Durra Applica tion Example Technical Report CMU SEI 89 TR 9 DTIC ADA206575 Software Engineering Institute Carnegie Mellon University February 1989 M R Barbacci D L Doubleday C B Weinstock and J M Wing Developing Applications for Heterogeneous Machine Networks The Durra Envi ronment Computing Systems 2 1 March 1989 CMU SEI 89 TR 34 33 10 11 12 13 34 J V Guttag J J Horning and J M Wing Larch in Five Easy Pieces Technical Report 5 DEC Systems Research Center July 1985 F Jahanian and A K Mok Safety Analysis of Timing Properties in Real Time Systems Transactions on Software Engineering 12 9 890 904 September 1986 S A Shafer A Stenz C E Thorpe An Architecture for Sensor Fusion in a Mobile Robot In Proceedings of the International Conference on Robotics and Automation pages 2002 2011 IEEE Computer Society Press San Francisco California April 1986 C B Weinstock Performance and Reliability Enhancement of the Durra Runtime Environment Technical Report CMU SEI 89 TR 8 DTIC ADA207445 Software Engineering Institute Carnegie Mellon University February 1989 CMU SEI 89 TR 34 Appendix A Formal Meaning of Timing Expressions We use Jahanian and Mok s Real Time Logic RTL 11 to give meaning to our timing expressions Furthermore we use their logic
37. later sections Figure 2 shows a template for a task description where the port clause constitutes the interface information task task name port REQUIRED port declarations A description of the input output interface of the task behavior OPTIONAL function predicates timing expressions A description of the behavior of the task attribute OPTIONAL attribute value pairs A description of additional properties of the task structure OPTIONAL process declarations queue declarations binding declarations reconfiguration statements A description of the internal structure of the task end task name Figure 2 A Template for Task Descriptions CMU SEI 89 TR 34 11 12 CMU SEI 89 TR 34 4 Task Selections Syntax TaskSelection TASK TaskName InterfacePart BehaviorPart AttributeSelPart END TaskName Meaning Task selections are templates used to identify and retrieve task descriptions from the library A given task e g convolution might have a number of different implementations that differ along dimensions such as algorithm used code version performance or proces sor type In order to select among a number of alternative implementations the user provides a task selection as part of a process declaration as described in Section 8 1 This task selection lists the desirable features of a suitable implementation Syntactically a task selection
38. looks somewhat like a task description without the structure part and all other components except for the task name are optional For example notice that in the syntax of a task declaration the interface part Section 5 requires the declarations of the ports whereas in a task selection the declaration of the ports is optional Figure 3 shows a template for a task selection For brevity if only the task name is given the terminating end task name is optional task task name REQUIRED port OPTIONAL port declarations A signature that must match port directions and types of that of a task description in the library behavior function predicates timing expressions A specification of the desired functional and timing behavior of a task description in the library OPTIONAL attribute attribute expression An expression of named actual attribute values used to match formal attribute values of a task description in the library end task name optional if only the task name is specified OPTIONAL Figure 3 A Template for Task Selections CMU SEI 89 TR 34 13 14 CMU SEI 89 TR 34 5 Interface Information 5 1 Port Declarations Syntax InterfacePart PORT PortDeclaration_List micolon IN gl PortDeclaration PortName_Listoomma AYIN A TypeName PortName_List omma OUT TypeName Examples ports inl in heads outl out2 out tails Meaning
39. meWindow TimeValue TimeValue Queue0peration ENQUEUE VN DEQUEUE f 18 CMU SEI 89 TR 34 Examples inl An operation Dequeue by default on the queue feeding inl inl dequeue The same operation as above delay 10 15 A delay interval lasting between 10 and 15 seconds delay 10 A delay interval taking at most 10 seconds delay 10 A delay interval taking at least 10 seconds Meaning Queue operations performed by the processes constitute the basic events of a timing expression An event represents a queue operation on a queue attached to a specific port taking a variable amount of time to complete A pseudo operation delay is used to represent the time consumed by the process between real queue operations The name of the queue operation is optional If the name is not given a default queue operation is assumed dequeue for input ports enqueue for output ports Intervals of time between queue operations are denoted by a delay operation whose time window describes the minimum and maximum time consumed by the process in between queue operations 6 2 3 Timing Expressions Syntax TimingExpression LOOP SequentialEvent SequentialEvent ParallelEvent_List spaces ParallelEvent i BasicEvent_LiSt4ouble_vertical_bar BasicEvent Even
40. n of operations is repeated indefinitely A timing expression is a sequence of parallel event expressions Each parallel event expression consists of one or more event expressions separated by a double vertical bar to indicate that their executions overlap Since the expressions might take different amounts of time to complete nothing can be said about their completion other than a parallel event expression terminates when the last event terminates A basic event expression is either a queue operation including delay or a timing ex pression enclosed in parentheses The latter form also allows for the specification of a guard an expression specifying the conditions under which a sequence of operations is allowed to start or repeat its execution Guard Description repeat This guard indicates repetitions of a timing expression The number of repetitions is a non negative integer value before This guard is followed by an absolute time value representing the latest start time allowed If the time base is PTIME or ATIME and the deadline has elapsed the task is terminated If the time base is DTIME and the deadline has elapsed the task waits until the end of the day when the time of day resets to 0 after This guard is followed by an absolute time value representing the earliest start time allowed If necessary the sequence is blocked until the deadline 20 CMU SEI 89 TR 34 during when This guar
41. nts are identified by a global name obtained by prefixing the name of a proc ess instance of the task to the name of the component For example p1 out2 could be the name of some output port declared inside process p1 If necessary multiple process names as prefixes can be used For example p1 p2 name is the global name for some component name declared inside the process p2 declared inside the proc ess p1 TypeName Identifier FieldName Identifier TaskName Identifier PortName Identifier GlobalPortName i ProcessName_List erioa 77 PortName NULL AttrName Identifier GlobalAttrName 1 ProcessName_List_erioa I AttrName QueueName Identifier GlobalQueueNam 1 ProcessName_LiSt erioa 07 QueueName ProcessName Identifier GlobalProcessName ProcessName_LiSt eriod ProcessQueueNam GlobalProcessName GlobalQueueName 6 CMU SEI 89 TR 34 1 6 Literal Values Each of the non terminals IntegerValue RealValue StringValue and TimeValue stands for a literals constants of the appropriate kind or b names of attributes Section 7 whose values are literals of the appropriate kind or c calls to predefined functions returning values of the appropriate kind The predefined functions are described in Ap pendix B a IntegerValue IntegerLiteral GlobalAttrName FunctionCall RealValue RealLiteral GlobalAtt
42. o 6 9 Transformation 26 27 TransformName 27 TransformOp 27 Type 6 9 TypeDeclaration 8 9 TypeName 6 9 15 TypeStructure 9 Union 6 9 UnionStructure 9 Uses 38 40 UsesSet 38 39 40 CMU SEI 89 TR 34 Value 7 8 41 When 6 19 21 30 31 WindowAttr 44 Xdisplay 6 42 45 Xterm 45 Xwindow 6 42 44 CMU SEI 89 TR 34 51 52 CMU SEI 89 TR 34
43. ource allocation and scheduling com mands See 6 for details about the runtime environment of Durra 2 The heterogeneous system runs the processes on processors as dictated by the executive program 1 2 Terminology Durra is used for describing process interaction at a logical not physical level and thus it can be used independently of any physical configuration of an actual heterogeneous machine We will use different terms to distinguish between the physical network P of processors memories and switches implementing the heterogeneous machine and the logical network L of processes and data queues implementing the application A The following are terms used in this manual buffer P A computer acting as input or output device interfacing a processor with the switch As an optimization buffers execute predefined tasks and data transformations CMU SEI 89 TR 34 3 implementation A Code written in some programming language for a specific proces port L process L processor P queue L executive P L switch P task L A sor that satisfies the performance functional and other require ments specified in a task description A logical input or output device of a process Input ports remove data from queues output ports deposit data in queues A uniquely identifiable instance of a task running on a processor of the heterogeneous system The same task may be instantiated any number of times
44. owing axiom relates the start and end times of the composition to the start and end times of the individual opera tions v i TA i min TA1 i TAn i JA i max JAI i JAn i 5 Cycles in a repeating task do not overlap The following two axioms express that an input operation cannot finish after the last output operation finishes and that an output operation cannot start before the earliest input operation starts v i max Lout i Lout i Lout i gt max lin i Jin i Jing i Vi min Tout i Tout i Tout i gt min Tin i Tins i Ting i where J and K are the number of output and input queues respectively Table A 1 Axioms About Operation Start and End Times allowed and must be an absolute time value The second time value is the latest start time allowed and can be an absolute time value or a time value relative to the former The meaning of the guarded expression is the conjunction of the meaning of the expres sion proper and a predicate stating the restriction on starting times A b Assigning Meaning to the Combined Specifications Given a task description of the form 36 CMU SEI 89 TR 34 Timing Expression M Timing Expression E Mip E E1 My E1 E1 En My E1 E2 En E1 En A Mp Ei Ej for all i j E1 E2 Mp E1 A Mp E2 A V i WM E1 i lt 7M E2 i E1 E2 My E1 A My E2 A v i
45. per is responsible for prescribing a way to manage all of these resources We call this prescription a task level application description It describes the tasks to be executed the possible assignments of processes to processors the data paths between the processors and the intermediate queues required to store the data as they move from source to destination processes A task level description language is a notation in which to write these application descriptions The problem we are address ing is the design of a task level description language We are using the term description language rather than programming language to em phasize that a task level application description is not translated into object code of some kind of executable machine language Rather it is to be understood as a descrip tion of the structure and behavior of a logical machine that will be synthesized into resource allocation and scheduling directives These directives are to be interpreted by a combination of software firmware and hardware in a heterogeneous machine Although our ultimate goal is to design and implement a task level description language that can be used for different machines and for varying applications this implementation was influenced by both a specific architecture Nectar 1 and by a specific application the autonomous land vehicle ALV and more specifically by the perception compo nents of the ALV 12 We assumed a logical machine with
46. r converting between floating point formats Transformations must be written as separate tasks and instantiated as processes The processes can then be used to build transformation expressions in the queue declara tion Furthermore since the data can be of a structured type there can be transfor mations that apply to a whole datum e g corner turning an array or to the subcom ponents e g rounding and converting to integers the elements of an array of floating point numbers Syntax Transformation Sa TransformOp_List space TransformOp ArrayTransform RecordTransform ScalarTransform ArrayTransform TransformName Transformation RecordTransform TransformName FieldTransform_List FieldTransform FieldName Transformation ScalarTransform TransformName TransformName GlobalProcessName NULL Examples Let s assume we have implemented tasks that perform a few useful transformations such as transposing an array and converting floating point numbers into integers In order to use these tasks we need to instantiate them in the usual manner assume that no other information e g attributes is needed to select the tasks process transpose_process task transpose process fix_process task fix CMU SEI 89 TR 34 27 Assuming that some source port produces arrays of some shape with elements of type float and tha
47. rNa FunctionCall StringValue StringLiteral GlobalAttrName FunctionCall TimeValue TimeLiteral GlobalAttrNa FunctionCall Value IntegerValu RealValue StringValue TimeValue FunctionCall FunctionName FunctionParameters Funct ionName Identifier FunctionParameters Value_List Frl comma The type and number of parameters is function dependent 1 7 Expressions Boolean expressions are used in the language to denote two kinds of conditions or predicates attribute values and reconfiguration conditions Expressions used to specify attribute values in a task selection Sections 7 and 8 1 are evaluated at compile time because their values are used by the Durra compiler to identify tasks from the library Expressions used to specify reconfiguration conditions in a task description Section 8 5 are evaluated at execution time CMU SEI 89 TR 34 7 Expression Disjunction Disjunction Conjunction Disjunction OR Conjunction Conjunction Primary Conjunction AND Primary Primary 2 NOT Term Term 1 Relation VII DESJUNGELOH IJ Relation Value Value Equal Value Value Not equal Value gt Value Greater Value gt Value Greater or equal Value lt Value Less Value lt Value L
48. rbed The null transformation NULL could be used when it is necessary to transform one or more fields of a record but with out applying any transformation to the record as a whole queue ql sport gt NULL head t1 tail t2 gt dport Meaning A sequence of data transformation expressions is convenient short hand for a series of anonymous transformationless queue declarations connecting the transformation proc esses A data transformation is a way to achieve compatibility between the data produced by some source port and the data expected by some destination port The definition of compatibility between types depends on the types 1 Non union types are compatible if they have the same name 2 Union types are compatible if the set of alternative type names in the source type is a subset of the set of alternative type names in the destina tion type 3 A non union source type is compatible with a union destination type if the source type name is a member of the set of alternative type names in the destination type 4 Array types produced by a chain of transformations are compatible with the destination port type if the two array structures are identical they have the same shape size and element type 5 Record types produced by a chain of transformations are compatible with the destination port type if the two record structures are identical they have the same number of fields in the same order and of the
49. rder We can apply rather complicated sequences of transformations as the following ex ample suggests queue ql sport gt t1 t11 t12 t2 t21 t211 t212 gt dport Transformation t 1 produces objects of some array type whose elements will be trans formed by t11 andti2 The result at this point is an array with the same structure as that produced by t 1 but whose elements are of whatever type t12 produces Transfor mations can be nested as shown in the example Transformation t2 produces some array type whose elements scalars or arrays are transformed by t21 which produces some array type whose elements are transformed by the sequence t211 and t212 Record transformations follow a similar pattern except that since not all components i e fields are of the same type we need to specify in addition to whole record trans formations if any specific field transformations 28 CMU SEI 89 TR 34 queue gl sport gt tl head t11 t12 tail t2 gt dport The example illustrates a queue connecting a source port to a destination port The source port generates data of some type suitable as input to a transformation process t1 The output of t1 is some record type with fields head and tail which are trans formed independently of each other The head field is transformed by the sequence t11 and t12 while the tail field is transformed by t2 The records produced by t1 could have additional fields and these are not distu
50. rnative productions Braces indicate optional components of a production 2 Terminal symbols are enclosed in quotation marks but the quota tion marks do not belong to the terminal 3 No distinction is made between upper and lower case letters in terminals and non terminals 4 A non terminal of the form xyz_List comma Stands for a list of one or more xyz s separated by commas i e the character not the string comma CMU SEI 89 TR 34 Processors Buffers Switch Rs Processes O Memory Processor Figure 1 Mapping of Logical and Physical Components Comments start with a double hyphen Any text between the double hyphen and the end of the line is ignored Identifiers are sequences of letters digits and underscores _ An iden tifier must begin with a letter and end with a letter or a digit Consecutive underscores in the middle of an identifier are not allowed Strings are sequences of ASCII printable characters enclosed in double quotation marks A double quotation mark inside a string must be writ ten as two consecutive double quotation marks A string with a double quotation mark inside Integer and real numbers are always decimal i e base 10
51. same type It is not required that the field names be identical A data transformation operation also serves to specify operations that would be inappro priate or inefficient if written as part of one of the application s tasks For example con sider an application that requires scanning an array in different directions e g first by rows then by columns and performing some operation on each element e g comput ing the average of the neighbors Rather than writing several versions of the task one for each traversal pattern one could simply write one version of the task and then in stantiate it as many times as necessary Each process so instantiated could then take its input arrays from queues that perform the appropriate transposition as in q1 p1 gt transpose gt p2 Arrays produced by p1 are transposed while in the queue before they are delivered to p2 CMU SEI 89 TR 34 29 There are a two restrictions on the tasks that could be applied as data transformations First each task must have exactly one input port and one output port Second the port types must match all along the chain of transformations such that data is pipelined through the sequence The same transformation process can be named in several transformation expressions The user should think of them as if each use is a different instantiation Whether or not there exists only one or more than one instantiation of the process is an implementation d
52. sses and queues which are then con nected to the remainder of the original graph The reconfiguration condition is a Boolean expression involving time values queue sizes signal values and other information avail able to the executive at run time More than one reconfiguration statement can be specified in a structure clause The reconfiguration conditions are tested by the executive concurrently If more than one of these conditions becomes true at the same time the executive selects one of the recon figuration statements and changes the structure of the application accordingly This choice of alternative configuration is non deterministic It is useful to think of the possible configurations of an application as the nodes of a tree The root node corresponds to the initial structure of the application description Each alternative reconfiguration statement in the structure part of the application description corresponds to the root of a subtree or alternative structure Each of these in turn can have one or more reconfiguration statements of its own and so on The tree is traversed down when a reconfiguration condition is satisfied and traversed up when an exit condition is satisfied Multiple i e nested reconfiguration levels can be exited at once by writing the label of the outermost reconfiguration statement to be exited The structure of the application changes reverts to the form it had when that reconfiguration took place If no l
53. t Guard gt SequentialEvent Guard REPEAT IntegerValue BEFORE TimeValue Absolute time VVAFTER TimeValue Absolute time DURING TimeWindow Thin 15 Absolute time wHEN Expression A Boolean expression Examples CMU SEI 89 TR 34 19 inl in2 Two parallel input operations starting simultaneously inl delay 10 15 outl Thr sequential operations repeat 5 gt inl delay 10 15 out1 Same as above but as a cycle repeated five times before 64800 DTIME gt A sequence constrained to start before 6 pm 18 hours or 18 3600 seconds after the start of the day after 64800 DTIME gt A sequence constrained to start after 6 pm during 64800 DTIME 7200 gt A sequence constrained to start between 6 pm and 8 pm it is 2 hours counted from the start of the time window when Current_Size inl gt 0 and Current_Size in2 gt 0 gt inl in2 outl A sequence that starts after both input queues have data loop when Current_Size inl gt 0 and Current_Size in2 gt 0 gt inl in2 outl The same sequence as above but repeated indefinitely Meaning A timing expression is a regular expression describing the patterns of execution of operations on the input and output ports of a task The optional keyword loop can be used to indicate that the patter
54. t a destination port consumes transposed versions of the same arrays We could apply the first transformation process as follows queue ql source_port_name gt transpose_process gt destination_port_name The process transpose_process will be applied to each array after it is placed in the queue and before it is delivered to the destination Now assume that the destination port consumes arrays whose shape is that of the trans posed version of the same input array but whose elements are of type fix We could apply both transformation processes as follows queue ql sport gt transpose_process fix_process gt dport The process transpose_process will be applied to each array after it is placed in the queue and then process fix_process will be applied to each element of the trans formed array before the result is delivered to the destination Sometimes it is necessary to apply a transformation to the elements of an array but with out changing the array itself This can be achieved by specifying the null transformation process NULL as the array transformation followed by the desired element transfor mation process queue qi sport gt NULL fix process gt dport If we need to apply more than one transformation to the elements of an array this can be specifed by listing a sequence of transformations queue gl sport gt tl t11 t12 gt dport After applying t1 each element is transformed by applying t11 and t 12 in that o
55. t define the structure of the data produced or consumed by the tasks A type declaration introduces a global name for a data type or a set of previously declared types which can then be used in port declarations There are several kinds of type declarations The simplest data type is a sequence of bits of fixed or variable but bound length More complex types are declared as multi dimensional arrays and records of simpler types An array type declaration that omits the dimensions represents an array of unknown dimensionality A record type decla ration describes the structure of data objects by listing the field names and their types Finally a type declaration can specify the union of a number of previously declared i e named types where data items moving through a process port could be one of any of the member types CMU SEI 89 TR 34 9 10 CMU SEI 89 TR 34 3 Task Descriptions Syntax TaskDescription TASK TaskName InterfacePart BehaviorPart AttributeDescPart StructurePart END TaskName Meaning Task descriptions are compilation units that define the properties of task implementa tions i e user programs Task descriptions are used as building blocks for task level application descriptions A task description is divided into four components 1 interface information 2 be havioral information 3 attributes and 4 structural information All these components will be described in
56. the queue bound is not provided a configuration dependent default queue length is assumed as described in 6 7 The predefined port name NULL can be used to declare or reconnect a queue to an idle source or destination port That is to a port that will not produce or consume any data This feature is useful to plug unused task ports by connecting them to NULL ports When declaring or reconnecting a queue the ports are checked for type compatibility Non union types are compatible if they have the same name Union types are com patible if the source set is a subset of the destination set A non union source type is compatible with a union destination type if the source type name is a member of the destination set 26 CMU SEI 89 TR 34 If the types are not compatible the user must provide a data transformation operation that will convert objects of one type into the other as described below A reconnect statement can not specify a queue size or a transformation These are inherited from the original queue declaration 8 3 Data Transformations Data transformations are operations applied to data coming from a source port in order to make them acceptable to a destination port A data transformation is required if the input and output port types are not compatible Such transformations are needed if for instance the types have the same structure but the data are in the wrong format e g turning a square array on its side o
57. ting of a task implementation is more or less independent of Durra and involves the coding debugging and testing of programs in various languages ex ecuting on various machines 3 The developer writes task descriptions and compiles them using the Durra compiler This is where Durra first enters the picture Durra is used to write specifications of each task implementation s performance and func tionality the types of data it produces or consumes and the ports it uses to communicate with other tasks If a compilation is successful the com piler enters the task description into the Durra library Description creation activities These happen when the user decides to put together an application say an autonomous land vehicle using as building blocks tasks stored in the Durra library 1 The user writes a task level application description Syntactically a task level application description is a single task description and could be stored in the library as a new task This allows writing hierarchical task level application descriptions 2 The user compiles the description During compilation the Durra compiler retrieves from the library task descriptions matching the task selections specified by the user and generates a set of resource allocation and scheduling commands to be interpreted by the Durra excutive These commands constitute a Durra executive program Application execution activities 1 The executive interprets the res
58. to each port in order and repeating and by_type output to the appropriate port depending on the type of the data In the latter case there must be exactly one output port for each possible type accepted by the input port This is the only kind of deal process in which multiple output types are allowed Other kinds of deal processes require compatible output types in all the output ports 46 CMU SEI 89 TR 34 B c 4 Examples Task descriptions for the predefined tasks are not stored in the library The Durra compiler uses the task selection part of the process declaration as the task description In other words predefined tasks are created on demand to satisfy a specific process declaration The following examples illustrate process declarations that are instances of predefined tasks process pb task broadcast ports inl in packet outl out2 out packet end broadcast This process declaration selects a 2 output broadcast task process pm task merge ports inl in2 in packet outl out packet attributes mode round_robin end merge This process declaration selects a 2 input merge task that handles items of type packet in round robin fashion process pd task deal ports inl in packet outl out2 out packet attributes mode round_robin end deal This process declaration selects a 2 output deal task that handles items of type packet in round robin fashion CMU SEI 89 T
59. to obtain multiple processes executing the same code A computer in the heterogeneous system not to be confused with the executive processor or the buffers Each processor in the heter ogeneous system has one or two buffers that act as interfaces be tween the processor and the switch Processors send data to and receive data from buffers as their means of communication with other processors A uniquely identifiable logical link between two processes following a FIFO discipline Queues serve as intermediaries between input and output ports A computer serving as resource allocator and dispatcher in the het erogeneous system It controls the switch all processors and all buffers An interconnection network used to tie together all processors in the heterogeneous system The switch routes data between the buffers attached to the processors An abstraction of a set of implementations each written for a class of processors implementing part of an application Tasks are stored in libraries The processes of the system are implemented by downloading and executing task im plementations i e programs onto processors of the right kind The queues of the sys tem are implemented by allocating space in the corresponding buffers memories This is illustrated in Figure 1 1 3 Notes on Syntax To describe the syntax of Durra we use standard Backus Naur Form BNF with the following conventions 1 Vertical bars separate alte
60. to the individual parts and their combination Appendix A provides the formal details 6 1 Function Part The functional information of a task description describes the behavior of the task in terms of predicates about the data in the queues before and after each execution cycle of the task The Larch Shared Language 10 is used as the assertion language in the predicates of these clauses We use a similar approach as Larch s for the specification of the functional behavior of a task That is we view the task as a procedure whose input and output parameters are defined by the ports of the task If one were to view each cycle of a task as one execu tion of a procedure the requires and ensures are exactly the pre and post conditions on the functionality of that cycle An omitted predicate is taken to be true These are not assertions about the queues connected to the ports For instance an assertion could be made that a datum of some type was sent to an output port It cannot be asserted that the datum is in the associated output queue at the end of the task ex ecution because it could have been removed by then It is up to the implementor of a task to verify that the functionality of the task satisfies the requires and ensures predicates A task description writer and user may assume that the task implementor performed such verification either formally or informally CMU SEI 89 TR 34 17 6 2 Timing Part Processes remove dat
61. ue seconds returns the time value ob tained by adding a number of seconds a real or integer value to TimeValue It should be obvious that current_ptime any_name can never return a value larger than current_atime That is Current_PTime any name lt Current_ATime is always true and the result of Minus_Time Current_ATime ATIME Current_PTime any name is constant and known by the Durra executive at the time any_name starts It is the delay between the start of the application and the start of the process The function call current_size port_ name returns the current number of elements stored in the queue associated with a given port The function call signal process_name integer_value returns true if the last signal raised by a process had a given value and returns false if no signals have been raised so far by the process or if the last signal raised had a different value The signal function can only appear as part of a conditional expression in a reconfiguration state ment Signal values are integer numbers that have no prespecified meaning in the language It is up to the application and task developers to adopt the appropriate conventions See 6 for details about signal raising and other means of communication between the appli cation processes and the executive Calls to these functions can appear anywhere a value of the same kind as the return value can appear That is a call to

Technical Report CMU/SEI - School of Computer Science

Contents

Download Pdf Manuals

Related Search

Related Contents