VHDL Issue Number: 0011 Classification: Language Deficiencies and Modeling Problems Language Version: VHDL-87 Summary: Non-commutative and non-associative resolution functions are a source of non-determinism Related Issues: None. Relevant LRM Sections: 2.4 Key Words and Phrases: Resolution functions, non-determinism Current Status: Analyzed 1076-1993 Disposition: Superseded (ISAC Issues Outstanding) Disposition Rationale: N/A Superseded By: 1003 ----------------------- Date Submitted: 1989/02/04 Author of Submission: Paul Menchini Author's Affiliation: CAD Language Systems, Inc. Author's Post Address: P.O. Box 13036 Research Triangle Park, NC 27709-3036 Author's Phone Number: (919) 361-1913 Author's Fax Number: Author's Net Address: mench@clsi.com ----------------------- Date Analyzed: 1990/10/06 Author of Analysis: Chuck Swart Revision Number: $Revision: 1.8 $ Date Last Revised: $Date: 1995/08/03 15:57:45 $ Description of Problem ---------------------- Since the LRM does not specify the order in which driving values are placed into the input vector of a resolution function, tools are free to compose the input vector from the driving values in any convenient order. A non- commutative or non-associative resolution function is, by definition, sensitive to the order of its inputs. Therefore, a non-commutative or non-associative resolution function will, in general, return a different result when invoked by different tools. Indeed, if the tool is not consistent in the order it places signals in the input vector, the resolution function may not behave the same on successive runs of the same tool. Thus, non-commutative and non-associative resolution functions are a source of non-determinism in VHDL. Proposed Resolution ------------------- The properties of commutativity and associativity are difficult to verify automatically. Thus, the LRM should contain either a statement to the effect that such functions are erroneous, or (less desirably) a note stating that such functions are a source of non-determinism and should be avoided. This statement or note should appear in Section 2.4. VASG-ISAC Analysis & Rationale ------------------------------ Although commutativity and associativity are related concepts, the real issue is one of symmetry. In this context, a resolution function is "symmetric" if, given an input array of size n, the function returns the same value for any permutation of the n elements of that array. A resolution function which is not symmetric cannot be guaranteed to return the same result for a given input when invoked by different tools, or even when invoked multiple times with the same values from the same tool. The ISAC feels that it is too much to require that resolution functions be symmetric, particularly since this condition cannot be automatically checked. However, it is appropriate to warn users about this source of nondeterminism. In addition, although there is general agreement that the LRM does not specify the order in which values of sources are placed into the input array of the resolution function, it is felt that a positive statement to this effect is preferable to a negative inference. VASG-ISAC Recommendation for IEEE Std 1076-1987 ----------------------------------------------- The sentence in section 2.4 which reads "Such drivers are said to be off." should be rewritten to read: "The order in which values of sources are placed into the input vector of a resolution function is not defined by the language. Furthermore, the language does not require that the values are placed in the same order on multiple calls to the resolution function when the same sources are driving the signal. Drivers whose values are determined by null transactions are said to be <>." In addition, the following paragraph should be added as a note to section 2.4: "A resolution function is said to be <> if, given any input array of fixed size, the function returns the same value for any permutation of the elements of that array. Since the language does not specify the order in which sources are placed into the input vector of a resolution function, the use of a resolution function which is not symmetric will result in code which is nondeterministic and nonportable." VASG-ISAC Recommendation for Future Revisions --------------------------------------------- Add the above language to the LRM.