VHDL Issue Number: 1003 Classification: Language Deficiencies and Modeling Problems Language Version: VHDL-93 Summary: Non-commutative and non-associative resolution functions are a source of non-determinism Related Issues: 0011 Relevant LRM Sections: 2.4 Key Words and Phrases: Resolution functions, non-determinism Current Status: ISAC-Approved ----------------------- Date Submitted: 1989/02/04 Author of Submission: Paul Menchini Author's Affiliation: Menchini & Associates Author's Post Address: 2 Davis Drive P.O. Box 13036 Research Triangle Park, NC 27709-3036 Author's Phone Number: 919.990.9506 Author's Fax Number: 919.990.9507 Author's Net Address: mench@mench.com ----------------------- Date Analyzed: 1994/03/17 Author of Analysis: Chuck Swart Revision Number: $Revision: 1.5 $ Date Last Revised: $Date: 1995/06/20 23:04:03 $ 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 the terms commutativity and associativity intuitively describe the problems, one reviewer has pointed out that they technically do not apply to resolution functions, since resolution functions contain only one argument.The applicable concept is one of order-invariance. In this context, a resolution function is "order-invariant" 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 order-invariant 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 order-invariant, 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-1993 ----------------------------------------------- The sentence in section 2.4 which reads "Such drivers are said to be off." should be rewritten to read something like: "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 order-invariant will result in code which is nondeterministic and nonportable." VASG-ISAC Recommendation for Future Revisions --------------------------------------------- Add the above language to the LRM.