Research On Logic Reversible Synthesis Algorithm Of Cosmic-scale Data Set

Nowadays the off-line logic indefinite chips reverse decrypting technology, as one of key technologies detecting the security of chips design,has been one of the most attractive research subjects. With the scale-up of various chips, the scale of data collected in the process of the off-line reverse decrypting has taken on the exponential level increase, but the traditional logic synthesis algorithm can't meet the requirement of cosmic-scale data sets, either in the respect of processing ability or in the respect of the capability and efficiency of cosmic data processing.Based on analyzing traditional logic synthesis algorithm deeply, the thesis emphasizes studying logic reversible synthesis algorithm under the condition of the cosmic-scale data set, combining features of data-collecting when doing the off-line reverse decrypting. The major research content and development are as follows:1. The thesis analyzes the processing pattern and course towards the off-line logic reversible synthesis. Traditional serial processing pattern adopts the method of dealing with data sets in blocks orderly,which makes every processing dependent excessively on the former intermediate result. However, the collateral processing pattern adopts another method that is independent processing, which improves the execution efficiency of reversible logic synthesis. The thesis, combining the different process patterns, analyzed the relative algorithms applicable, which prepared the ground for the design of succeeding off-line logic synthesis subsystem.2. The thesis puts forward to support iterative search algorithm of minimum coverage. Uunder the condition that there are quite a bit output variables, it is more likely for partial outputs sharing the same product terms other than all sharing the same one. Therefore, the thesis puts forward to change the one-time computing process into iterative searching mode of the optimum result, adopting the method to find the sharing of product terms between output variables step by step and on each step working out the opposite minimum coverage in order to approach the optimum result by the method of iterative optimize. The proposed method can handle complex problem in reasonable time while the result is near by the optimum. Meanwhile the thesis adopts extremal search algorithm based on the intersection iterative, which reduce the time complexity of extremal search.3. The thesis puts forward to neighborhood search algorithm. Traditional algorithm didn't consider the relativity between each state. So if the amount of data state is large and both former and later completion states are quite discrete, it's easiest to take the space-blasting problem to the intermediate result when processing. Therefore, the thesis adopts the neighborhood method searching for largely approximating state subset among completion state sets, and computing the data through building index table of neighboring states so that guaranteeing the relativity between formerly and later data computing, and avoiding the problem of the rapid inflation of intermediate result sets. At the same time, by improving consensus algorithm, the method implements simplification towards data in states, compressing the scale of data sets, and improving computing efficiency of algorithm. 4. Based on the above various algorithms, the thesis designs and implements the off-line reversible logic synthesis subsystem combining the practical demand of off-line decrypting system of the logic indefinite chips to reversible logic synthesis. This subsystem is able to provide the function that people themselves can select the optimization pattern and degree based on their own demand. Test indicates that the subsystem can accomplish rapidly and accurately computing reversible logic synthesis of cosmic-scale data set.