Finding the longest simple path in cyclic combinational circuits

A circuit´s performance is usually measured by the delay of its longest path. A combinational circuit may contain cycles. We shall call these type of circuits “cyclic combinational circuits”. In order to find the delay of a cyclic combinational circuit we need to find the delay of the longest simple path, however traditional longest path algorithms cannot be applied to circuits containing cycles. Finding the longest simple path in a cyclic combinational circuit has been shown to be NP-hard. In this paper we propose an optimal algorithm to solve this problem. The approach we use here is first to replace cycles with matched sub-circuits and then compute the longest simple path of the expanded circuit. The matched sub-circuits are carefully constructed to preserve the path information of the original cyclic combinational circuit. Since the problem is NP-hard, the proposed algorithm has exponential time complexity in the worst case. Nevertheless, the experimental results demonstrate the feasibility of the proposed algorithm