The purpose of this work is to estimate the time costs for multiplying square binary matrices of size n × n by a device with pipelining the operation of reading data from a specialized multiport memory and compare it with the time costs of the prototype. This work used methods of mathematical logic, set and graph theory, discrete systems and computer devices, and finite state machine design theory. As a result of the study, it was shown that the use of pipelining the operation of reading data from specialized multiport memory reduces the time spent on processing square binary matrices with a size of n ≤ 2048 up to 206.3 times. It can be seen from the data obtained that the loading and unloading time of the source and result data for the proposed device is significantly higher than the matrix multiplication time, which makes frequent loading and unloading of matrices impractical. For example, when performing the operation of transitive closure of a binary relation represented as a binary matrix, the initial matrix is loaded once, followed by a series of squaring, which is effectively implemented by the proposed device. Based on the obtained results, it can be concluded that the proposed device for multiplying square binary matrices with
Е.A. Titenko, I.Е. Chernetskaya, М.А. Titenko, E.V. Melnik, D. А. Trokoz
2024-05-28
Abstract ▼
Relevance. The paper discusses a theoretical approach to organizing parallel computing based on a production model of data flow control. The production paradigm of parallel computing has the necessary conditions for building new architectures and organizing high-performance parallel computing. We consider production (mathematical) systems that control sets of left-hand sides of productions (samples). The goal is to increase the efficiency of parallel inference of solutions by reducing unproductive time spent searching through possible alternatives in the inference graph space. The research is based on the creation of an extended symbolic computation machine for implementing parallel steps. A symbolic computing machine is an abstract system that systematizes production output as a sequence of four computational and search stages. The inference engine defines the general appearance of a homogeneous computing system. The main difference is the decomposition of the base of production rules into separate subsets based on the algebra of production and the structuring of relations between products. Instead of a single “flat” structure, it is proposed to decompose the product base into parts - to introduce a system of independent subsets of products. Parallel inference is implemented for individual subsets without loss of generality, while the search for possible alternatives is reduced. Each subset of productions has a special marker word, the value of which activates only one subset of productions. It is loaded into the operating part of a homogeneous computing system for parallel execution. Results. It is shown that quantitative estimates of the reduction in output time depend on the total number of productions, the number of subsets formed and their size. Simulation has shown that even the simplest decomposition into two subsets (one subset consists of 2 productions) gives a time gain of (1.07-1.52) times, proportional to the total number of productions. Conclusions. The created extended symbolic computing machine is the basis for the subsequent creation of the architecture of a homogeneous computing system with a combination of centralized and local control. This property allows computational units of a homogeneous operating part to work in parallel without excessive access to shared memory.
