A Rewriting Approach to Replace Asynchronous ROMs with Synchronous Ones for the Circuits with Cycles

Field Programmable Gate Arrays (FPGAs) are a dominant implementation medium for digital circuits which are used to embed a circuit designed by users instantly. FPGAs can be used for implementing parallel and hardware algorithms. Circuit design that minimizes the number of clock cycles is easy if we use asynchronous read operations. However, most of FPGAs support synchronous read operations, but do not support asynchronous read operations. The main contribution of this paper is to provide one of the potent approaches to resolve this problem. We assume that a circuit using asynchronous ROMs is given. In our previous work, we have presented a circuit rewriting algorithm to convert a circuit with asynchronous ROMs into an equivalent circuit with synchronous ones. The resulting circuit with synchronous ROMs can be embedded into FPGAs. However, this circuit rewriting algorithm can handle circuits represented by a directed acyclic graph and does not work for those with cycles. In this paper, we succeeded in relaxing the cycle-free condition of circuits. More specifically, we present an algorithm that automatically converts a circuit with cycles using asynchronous ROMs into an equivalent circuit using synchronous ROMs.