When we solve graph NP-complete tasks on multiprocessor systems, the growth of hardware resource does not lead to the proportional increase of the system performance, and hence, the task solution time is not always reasonable. The aim of our research, given in the paper, is minimization of the solution time of the task of maximal clique enumeration on reconfigurable computer systems (RCS). When we solve tasks on RCSs with the help of the method of parallelizing by layers, the growth of performance also slows down in spite of better scalability in comparison with multiprocessor implementations. In the paper, we suggest a method of parallel-pipeline application development for reconfigurable computer systems. The method is based on parallelizing bylayers for graph NP-complete tasks. We show that the bit representation of sets, which is used for the method of parallelizing by layers, is not efficient for the method of parallelizing by iterations. The new method has another organization of calculations; it processes unordered sets, whose elements are accessed not by addresses (as in arrays), but by values (names of vertices and names of edges of the graph). We show that the new method, based on parallelizing by iterations, provides ramping of the RCS real performance at much larger computational resource in comparison with the method of parallelizing by layers. Its specific performance is lower, because computing substructures are to process more intermediate data due to symbolic representation of sets.
A bioinspired method for solving a set of invariant combinatorial-logical problems on graphs is proposed: the formation of a graph matching, the selection of an internally stable set of vertices, and the selection of a graph clique. A modified paradigm of the ant colony is described, which uses, in contrast to the canonical method, the mechanisms for generating solutions on the search space model in the form of a star graph. The problem of forming an internally stable set of vertices in a graph can be formulated as a partitioning problem. At the initial stage, the same (small) amount of pheromone ξ/m, where m=|E|, is deposited on all edges of the star graph H. The process of finding solutions is iterative. Each iteration l includes three stages. Agents have memory. At each step t, the memory of the agent ak contains the amount of pheromone фj(t) deposited on each edge of the graph H. At the first stage, each agent ak of the population uses a constructive algorithm to find the solution Ur 0k, calculates the estimate of the solution ξk(Ur 0k) and the value of the degree of suitability of the solution obtained by the agent φk (the amount of pheromone corresponding to the estimate). At the second stage, after the complete formation of solutions by all agents at the current iteration, the pheromone ωj accumulated in the j-th cell in the CEPб buffer array is added to each j-th cell of the main array Q2={qj|j=1,2,…,m} of the CEP0 collective evolutionary memory. At the third stage, the general evaporation of the pheromone occurs on the set of edges E of the star graph H. The time complexity of the algorithm, obtained experimentally, coincides with theoretical studies and for the considered test problems is O(n2).
