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.
The article discusses new algorithm to increase the efficiency of the operation of multiplying a matrix Kronecker product (KP) by a vector. It is based on the use of the KP properties. This operation is widely used in solving problems of processing signals, images, cryptography, etc., where the formation of large matrices with specified properties is performed using small size matrices. In this case, matrices with the following properties are used: orthogonal (unitary), invertible, involutive. Multiplying an n × n square matrix by a vector has a computational complexity of O(n2). Therefore, with an increase in the number of elementary matrix factors, the size of the resulting KP matrix and the complexity of multiplying it by a vector grow exponentially. This circumstance significantly increases the time for solving applied problems. The aim of the proposed work is to construct an algorithm that accelerates the processes of forming the KP and multiplyingthe vector by it. It is proposed to combine the process of multiplication with the process of forming the KP. Thus, the KP matrix is not actually calculated explicitly. Instead, the KP factor matrices are iteratively multiplied by the vector components in O(nlog2n) time with linear memory complexity. The computational scheme with the hypercube topology for the possible hardware implementation of the proposed algorithm is presented. It can be easily pipelined. Section 1 presents the definitions and properties of the KP used in the synthesis of the proposed algorithm. Section 2 presents an example with n = 8 illustrating the proposed algorithm, on the basis of which, in Section 3, a hardware-oriented structure of its implementation for arbitrary n is proposed.
