An Exact Optimization Method Using ZDDs for Linear Decomposition of Index Generation Functions

This paper proposes an exact optimization method using zero-suppressed binary decision diagrams (ZDDs) for linear decomposition of index generation functions. The proposed method searches for an exact optimum solution by recursively dividing an index set of an index generation function. Since ZDDs can represent sets compactly and uniquely, they can also represent partitions of an index set compactly and uniquely. Thus, the proposed method can reuse partial solutions (partitions of an index set) efficiently by using ZDDs, and avoid redundant solution search. Experimental results using benchmark index generation functions show the effectiveness of ZDDs.

I. Introduction

Index generation functions [6], [7] are logical models of index searches. Since index searches are widely used as a basic operation in many applications, such as detection of computer viruses and packet classification, fast hardware for index generation functions has been required. In addition to processing speed, an ability for quick updating of index generation functions is also important particularly in these network applications, because virus patterns and rules for classification are frequently updated. Thus, there is merit to a memory-based hardware design.