Optimization of interacting controllers using K-wise tests

Abstract

Digital systems are represented as a network of interacting components, and often their control units are as well modeled as a network of finite-state machines (FSMs). It is possible that when an FSM ( M<inf>2</inf> ) is driven by another FSM ( M<inf>1</inf> ) as opposed to being driven from outside, some of its states and transitions may never be visited. Such cases may occur when M<inf>2</inf> is for example designed as a library component and hence is designed to work in a greater context - not only with M<inf>v</inf> Hence, M<inf>2</inf> may be logic-minimized - called hierarchical optimization (HO), or the composite machine, M<inf>1</inf> → M<inf>2</inf> may be minimized - called global optimization (GO). We do HO as it is faster though sometimes less globally optimal than GO. Compared to the best previous HO method, we are significantly faster. We extract the composite machine M<inf>1</inf> → M<inf>2</inf> only once. We do combinational simulation as opposed to sequential. Instead of randomly picking from permissible test sequences, we filter out the ones that are k-wise complete. We inject faults and simulate in a topological order and remove multiple redundancies. As a result of our run-time efficiencies, we are also able to handle bigger FSMs than previous literature. ©2007 IEEE. © 2008 Elsevier B.V., All rights reserved.