Optimization of Input-Constrained Systems

摘要

The computational demands of algorithms are rapidly growing. The naive implementation uses extended double-precision floating-point numbers and has therefore extreme difficulties in maintaining real-time performance. For fixed-point numbers, the value representation pushes in two directions (value range and step size) to set the application-dependent word size. In the general case, checking all combinations of all different values on all system inputs will easily become computationally infeasible. Checking corner cases only helps to reduce the combinatorial explosion, as still checking for accuracy and precision to limit word size remains a considerable effort. A range of evolutionary techniques have been tried where the sheer size of the problem withstands an extensive search. When the value range can be limited, the problem becomes tractable and a constructive approach becomes feasible. We propose an approach that is reminiscent of the Quine-Mc.Cluskey logic minimization procedure. Next to the conjunctive search as popular in Boolean minimization, we investigate the disjunctive approach that starts from a presumed minimal word size. To eliminate the occurrence of anomalies, this still has to be checked for larger word sizes. The procedure has initially been implemented using Java and Matlab. We have applied the above procedure to feed-forward and to cellular neural networks (CNN) as typical examples of input-constrained systems. In the case of hole-filling by means of a CNN, we find that the 1461 different coefficient sets can be reduced to 360, each giving robust behaviour on 7-bits internal words.