Design And Implementation Of Kernel P System On CUDA

Membrane computing is a new branch of natural computing. The main idea is to abstract computing models from the structure and functions of the living cells as well as the cooperation of cells, which includes discussions on calculation models and calculation techniques. Currently, different variants of P systems have been introduced and studied for their computational power. The existence of different variants with specific features, provides flexibility and some freedom in modelling various problems, but represents a drawback for formally verifying the correctness of these models. To solve this problem, kernel P systems were introduced in2013. The main purpose is to provide a formal framework which includes many well-known features of existing P systems and some new elements at the same time. Since the proposed of kernel P system is relatively late, and the study of realization of kernel P system is also relatively few. Thus, the implementation of kP systems in CUDA for solving various problems, including NP-hard problems is important. For these reasons, the topic of this article is kernel P system design and implementation based on CUDA. The aim is solving a class of NP-hard problems based on kernel P sytems and its implementation, which can provide some technical support for the future applications.The main results and research of this paper can be summarized as follows:1、 Studied the structure and evolution of the kernel P systems and utilized the trading time for space method to design the alphabet, multisets, rules, membrane structure etc for solving NP-hard problem.2、 Because of the long time-consuming according to the traditional serial way, in this paper, We utilize the CUDA parallel environment and define the CUDA blocks as compartments and the CUDA threads as units which execute the rules to take full advantage of high-performance graphics processor units. And experimental results achieve good performance.3、 Proposed the detail of solving two classes of NP-hard problem, which is called the subset sum problems and the satisfibility problem, by kernel P system. Compared to the active membrane P system, kernel P system can decrease the requirements of alphabet, rules, system simulation cycle etc. The experiments about the solutions of the subset sum and satisfiability problems show that the framework and method are feasible. And the results also indicate that Using CUDA is at most26times faster than CPU.