Discrete-event knowledge (DEK) consists in a variety of automaton-based data structures which are generated by knowledge-based and engineering systems, including intelligent diagnosis systems. Model-based diagnosis me...
详细信息
Discrete-event knowledge (DEK) consists in a variety of automaton-based data structures which are generated by knowledge-based and engineering systems, including intelligent diagnosis systems. Model-based diagnosis methods for discrete-event systems (DESs) are typically supported by large automata that allow for the efficient generation of the candidate diagnoses when the DES is being operated. However, the generation of the DEK may involve a determinization step, where a nondeterministic finite automaton (NFA) is transformed into an equivalent deterministic finite automaton (DFA) by means of the classical Subset Construction algorithm. When this determinization is performed online and the NFA is large, the diagnosis engine may slow down to such an extent that the entire diagnosis task is jeopardized. This is why a novel determinization algorithm is proposed, called Quick Subset Construction, which, instead of generating from scratch the equivalent DFA, removes the nondeterminism by operating directly on the NFA. This way, the larger the NFA and the smaller the portion of nondeterminism involved, the faster Quick Subset Construction will be over Subset Construction. Massive experimentation on large automata has confirmed this result empirically.
This paper presents two new versions of the Critical Channel Traversing (CCT) algorithm. CCT is a conservative parallel discrete event simulation algorithm that has been shown to achieve very high performance when use...
详细信息
ISBN:
(纸本)9780769516080
This paper presents two new versions of the Critical Channel Traversing (CCT) algorithm. CCT is a conservative parallel discrete event simulation algorithm that has been shown to achieve very high performance when used in a wide area computer network simulator. The first of the new algorithms called simple sender side CCT is similar to the original, but busy waiting is eliminated. Results presented show that simple sender side CCT avoids performance problems that can be caused by busy *** second new algorithm called receive side CCT employs a different strategy for updating channel clocks and determining which objects should be scheduled on critical channels. Performance results show that this version provides better scaling with respect to the connectivity of the model, at the expense of some added complexity.
暂无评论