No. 7 (2020)

The paper deals with prospects for the design of high-performance reconfigurable computing devices
based on modern Xilinx UltraScale+ FPGAs. The aim of the research is the computational density
up to 128 LSI FPGAs in one 3U 19’ product. Besides, it is necessary to provide the required powersupply and cooling of the system’s computing elements during execution of computationally expensive
tasks. To provide the product’s required parameters in the given design package, we made the topology
of our printed circuit boards and the design technology of their parts more complex. To cool the components
of our computer system, we use the immersion technology. The distinction of the designed computer
systems is wide capabilities of data exchange inside the block and among the blocks. It is crucial for
tightly-coupled tasks, where the number of data transfers among functional devices is much higher than
the number of such devices. As the main links between FPGAs, we use differential lines with multigigabit
transceivers (MGT). The optical channels based system of data exchange among the blocks is
provides the throughput over 2 Tbit/sec. We designed and produced a prototype of a computational
module based on UltraScale+ FPGAs, and a prototype of a reconfigurable computational block. The
computational block contains a general-purpose processor and all needed input-output interfaces. It is a
stand-alone device. We used the new-generation computational module for implementation of several
algorithms of various scientific and technical problems, and proved its wide applicability. We designed
a modified immersion cooling subsystem, which dissipates total heat up to 20 kW. To achieve such level
of heat dissipation, we implemented technical solutions concerning all components of the cooling system:
the cooling agent, heat sinks, the pump, the heat-exchange unit. It is possible to unite several blocks
into computer complexes with the performance up to tens of petaflops. Such complexes require a suitable
engineering infrastructure.

The article is show the reduction of time spent on generating combinations of elements of
the set. The elements of the set are formed from samples (left parts) of the production rules. The
main task is to build time-efficient schemes (algorithms) for parallel generation of combinations of
array elements. With regard to production systems, such schemes are necessary for the activation
of a subset of products applicable to character data in the current step. The basis is taken and
developed the well-known algorithm of the parallel bubble. The switching circuit "parallel bubble"
consists of two alternating variants of switching elements in pairs. These commutations are based
on local union into pairs of array elements with adjacent indices. Such a local combination of
elements into pairs leads to "small" displacements of elements along the length of the array and
the regular nature of the generation of pairs. In each pair, the operation of comparison-exchange
of operands is performed. For production systems, the comparison operation is reduced to the
search for sample intersections and the formation of a list of conflicting words. The reduction in
the generation time of combinations is based on the construction of switching options with distributed
combining of elements in pairs with a step equal to 4. The developed switching scheme contains
on odd switching steps with a local combination of elements in pairs. In even-numbered
steps, a switching accelerator is performed with a distributed combination of elements in pairs.
The simulation of the work of the developed switching scheme was carried out on typical tasks of
sorting and complete enumeration of pairs of elements. The reduction of time costs compared with
the scheme "parallel bubble" by 15-18%. A linear dependence of the sorting time with a slope
angle less than 1 was determined. This allows the use of a switching circuit for large-scale production
systems. Local and distributed communications in the switching scheme preserve the
property of regularity. This feature determines the hardware implementation of the circuit in the
form of a parallel switch with natural scaling. This scheme can be used in a specialized production
device for decomposing a production system into independent subsets of products.

One of the main factors that significantly complicate the understanding, translation and
analysis of texts obtained by automatic speech recognition or optical recognition of text images
are the distortions contained in them in the form of erroneous characters, words and phrases.
The most typical errors of recognition systems are: – replacement of a word with a similar sounding
or graphic spelling; – replacing several words with one; – replacement of one word with several;
– skipping words; – insertion or deletion of short words (including prepositions and conjunctions).
As a result of recognition, a text is obtained that has distortions and consists mainly of dictionary
words, including in places of distortion. With a large amount of distortion, the texts become
almost unreadable. Automatic processing of such texts is very difficult, although this task is
relevant both for Russian and for other common languages. Correction software that works well at
low distortions in the text, in the case of texts with a high level of distortion, regardless of their
origin, show unsatisfactory results. This makes it necessary to develop independent approaches to
correcting distorted texts. A new multi-pass method for correction of distorted texts based on sequential
error identification and correction of distorted texts is proposed. Non-dictionary word
forms and word forms which occurrence probability in the text in accordance with the selected
probabilistic model is less than a preset threshold are considered to be distorted. After setting of
the distortion sign for individual words, this sign is spread to their combinations, i.e. distorted text
fragments are extracted. A list of possible word variants which includes only those word forms
from the dictionary that are located at a certain Levenshtein distance from the word under study is
built for them. The corrected text from word variants is obtained by searching for the most probable
chain of word forms. The correction method consists of several passes, at each pass only those
fragments of the text are corrected that remained distorted after the previous pass of correction.
The method allows to increase significantly the quality (accuracy) of the correction. In the carried
out experiments the quality of correction in terms of the F1-measure for moderately distorted texts
has been increased by 9 %, and for highly distorted texts – by 7.7 %.

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.

We consider the algorithmic complexity of calculating the exact probability distributions of
statistical values and their exact approximations by solving the first multiplicity equation. As exact
approximations of probability distributions of statistical values, we consider their Δ−exact distributions
that differ from the exact distributions by no more than a predetermined, arbitrarily small
valueΔ. It is shown that the basis of the method for calculating the exact probability distributions
of statistical values is the enumeration of elements of the search area for solutions to a linear
equation of multiplicity of types, composed of vectors of multiplicity of types, each element of
which is the number of occurrences of elements of a certain type (any sign of the alphabet) in the
sample under consideration. At the same time, it is shown that the method of limiting the search
area for solutions is used to calculate exact approximations of the probability distribution of statistical
values. An expression is given that defines the algorithmic complexity of calculating exact
distributions by solving the first multiplicity equation. The given expression is finite and allows for
each value of the alphabet power to determine the maximum sample size for which, using a limited
computational resource, exact distributions can be calculated by solving the first multiplicity
equation. The range of parameters represented by the sample size and alphabet power for which
exact distributions can be calculated with a limited computing resource is defined. To estimate the
algorithmic complexity of calculating exact approximations of distributions, we present an expression
for the first time obtained for the number of solutions to the equation of the first multiplicity
with a restriction on the coordinate values of the solution vectors. An expression is given that defines
the algorithmic complexity of calculating exact approximations by solving the first multiplicity
equation with a restriction on the coordinate values of the solution vectors. As a parameter for
limiting the coordinates of solution vectors, the maximum frequency statistic value is used, the
probability of exceeding it is less than a pre-set, arbitrarily small valueΔ, which allows calculating
exact approximations of distributions that differ from their exact distributions by no more than the
selected value Δ. The given expression is finite and allows for each value of the alphabet to determine
the maximum sample size for which, when using a limited computational resource, exact
approximations can be calculated by solving the equation of the first multiplicity under the restrictions
set using the valueΔ. The results of calculations of the maximum sample volumes for
which exact approximations can be calculated are presented. It is shown that the algorithmiccomplexity of calculating exact distributions exceeds the complexity of calculating their exact approximations
by many orders of magnitude. It is shown that the use of the first multiplicity method
for calculating exact approximations allows for the same values of the alphabet power to increase
the sample volume by two or more times compared to the calculation of exact distributions.

The article considers the number of solutions to the equation of the first multiplicity of types,
composed of vectors of multiplicity of types, each element of which is the number of occurrences of
elements of a certain type (any sign of the alphabet) in the sample under consideration. The equation
of the first multiplicity of types relates the number of occurrences of elements of all types in
the sample under consideration and the volume of this sample. The main attention is paid to the
conclusion and proof of the correctness of the expression that determines the number of nonnegative
integer solutions of the equation of the first multiplicity of types under conditions of restrictions
on the frequency of occurrence of alphabet characters. The solution of the equation ofthe first multiplicity of types is the basis for calculating exact approximations of the probabilities
of statistical values by the first multiplicity method, where the exact approximations are Δexact
distributions that differ from the exact distributions by no more than a predetermined, arbitrarily
small value Δ. The value that expresses the number of solutions to the equation of the first multiplicity
of types is one of the values that determine the algorithmic complexity of the method of the
first multiplicity, without knowing the value of which it is impossible to determine the parameters
of samples for which, under restrictions on the computational resource, exact approximations of
distributions can be calculated. Also, the value expressing the number of solutions to the equation
of the first multiplicity of types is used in the method of the first multiplicity to limit the search area
for solutions to the equation. The number of solutions to the equation of the first multiplicity is
considered under conditions of restriction on the maximum value of the elements of the multiplicity
vector, and the case is considered when one or more elements of the alphabet may be missing in
the sample. First obtained the expression that defines the number of nonnegative integer solutions
to equations of the first multiplicity of types in terms of restrictions on the values of the frequencies
of occurrence of signs and the possibility of absence of one or more characters of the alphabet in
the sample reviewed. Analytical expressions are obtained that allow calculating the number of
integer nonnegative solutions of the equation of the first multiplicity of types for any values of the
alphabet power, the sample size, and the limit on the maximum frequency of occurrence of alphabet
characters. The form of the obtained expression allows you to use it when studying the algorithmic
complexity of calculating exact approximations of probability distributions of statistical
values with a pre-specified accuracy Δ.

Many digital signal processing tasks can be represented in the form of information
graphs. Reconfigurable computing systems based on FPGAs can have a structure that directly
corresponds to the information graph of the problem being solved. The construction of the task
graph and the subsequent creation of the computational structure can take a significant amount
of time when performed manually. In this regard, it becomes necessary to create algorithms for
transforming information graphs that can be performed automatically. The article proposes
algorithms for transforming homogeneous graphs containing associative operations and mixed
graphs containing two types of operations, one of which is distributive with respect to the other.
Transformations of graphs of the first type (consisting of operations of the same type) are reduced
to the transition from a sequential form of a graph to a pyramidal form to speed up the
execution of all graph operations. If the available amount of equipment is not enough to impl ement
all operations of the graph, a transformation is applied that splits the original graph into
isomorphic subgraphs. The size of the subgraph depends on the available computing resources.
In this case, the computational structure will correspond to such a subgraph. Transformations
of graphs of the second type (consisting of operations of two types, some of which are distributive
with respect to others) are reduced to dividing the graph into subgraphs containing operations
of the same type, connected in a special way. After that, these subgraphs can be converted
into a pyramid shape to speed up the execution of all graph operations. In this case, the number
of vertices with distributive operations can increase significantly, and therefore it may be necessary
to reduce their number. It follows that when transforming graphs of the second type, it is
necessary to choose a specific form to which the graph will be reduced, based on the ratio of its
size and the available computing resource. Thus, the proposed algorithms for transforming
information graphs of various types can be effectively used in the development of computational
structures based on FPGAs

In the paper we review software tools for translation of sequential C-programs into scalable
parallel-pipeline programs written in the COLAMO language, used for programming of reconfigurable
computer systems. In contrast to existing tools of high-level synthesis, the translation result
is not an IP-core of a task fragment, but a complex task solution for multichip reconfigurable
computer systems with automatic synchronization of data and control signals. We analysed the
main translation steps of a sequential C-program such as transformation into an information
graph, analysis of data dependencies and selection of functional subgraphs, transformation into a
scalable resource-independent parallel-pipeline form, and scaling a COLAMO-program for a
specified multichip reconfigurable computer system. A program is scaled with the help of performance
reduction methods, applied to a completely parallel form of a task (an information graph),
adapted to the architecture of a reconfigurable computer system. We developed several rules,significantly reducing the number of transformation steps of task scaling, and providing a continuous flow of data processing in the functional subgraphs of the task. The developed software tools
for translation of C-programs into FPGA configuration files significantly decrease the synthesis
time of a task computing structure for multichip RCSs and the total task solution time.

In the paper, we consider data-equivalent transformations of some kinds of non-linear
computing structures, such as quadratic, fractional and conditional. All computing structures
contain feedbacks. If a pipeline computing structure of a task, implemented on a reconfigurable
computer system, contains feedbacks, the data processing rate slows down, because it is necessary
to wait for feedback results to calculate the next value. The processing rate slows down not
only in the chain with feedback, but in the whole computing structure. As a result, the task solution
time increases. Previous fragments have to delay their data to supply it into a chain with
feedback, and subsequent ones have to remain idle waiting for the feedback result data. At pr esent,
there are no software development tools for reconfigurable computer systems with automatic
optimization of such computing structures. So, the user has to analyze the source code to
find expressions with feedbacks, and to optimize them. As a result, the development time of eff icient
applications considerably increases. We suggest methods decreasing the data processing
time interval (down to unity in the best case) for applied tasks solved on reconfigurable computer systems. Besides, the task solution time also decreases. Owing to the suggested methods,
implemented in the optimizing synthesizer of circuit solutions, transformations are performed
automatically. As a result, the development time for efficient applied tasks with feedbacks decreases
from several days to several minutes.

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.

Fractal algorithms find an increasing number of areas of application - from computer
graphics to modeling complex physical processes, but their software implementation requires
significant computing power. Fractal image compression is characterized by a high degree of data
compression with good quality of the reconstructed image. The aim of this work is to improve the
performance of reconfigurable computing systems (RCS) when implementing fractal compression
and decompression of images. The paper describes the developed methods of fractal compression
and subsequent decompression of images, implemented in a parallel-pipeline method for RCS. Themain idea of parallel implementation of fractal image compression is reduced to parallel execution
of pairwise comparison of domain and rank blocks. For best performance, the maximum
number of pairs must be compared simultaneously. In the practical implementation of fractal image
compression on the DCS, such critical resources as the number of input channels and the
number of FPGA logical cells are taken into account. For the problem of fractal image compression,
data channels are a critical resource; therefore, the parallel organization of computations is
replaced by parallel-pipeline, after the performance reduction of the parallel computational structure
is performed. Each operand goes into the computational structure sequentially (bit by bit) to
save computational resources and reduce equipment downtime. To store the coefficients of the
iterated functions system encoding the image, a data structure has been introduced that specifies
the relation between the numbers of rank and domain blocks and the corresponding parameters.
For the convenience of subsequent decompression, the elements of the array encoding the compressed
image are ordered by the numbers of the rank blocks, which avoids double indirect addressing
in the computational structure. Applying this approach for parallel-pipeline programs
allows scaling computing structure to plurality programmable logic arrays (FPGAs). A practical
implementation performed on a reconfigurable computer Tertius-2 containing eight FPGAs provides
an acceleration of 15000 times compared to a universal multi-core processor and 18–25
times compared to existing solutions for FPGAs. The implementation of image decompression on a
reconfigurable computer shows an acceleration of 380 times in comparison with the similar implementation
for a multi-core general-purpose processor.

This article deals with the question of preventing overflows of the bit grid in highperformance
reconfigurable computing systems based on FPGAs, leading to fatal data processing
errors when obtaining a radar range-velocity portrait of the target. The known methods of solving
this problem are briefly considered. A new method for a priori determination of the number of
scaling points in pipeline-parallel computing structures that form the target's radar range-velocity
portrait is proposed. This technique allows to determine in advance the required number of scaling
points at all stages of integer data processing and to prevent overflows when calculating theFFT (IFFT) in all possible situations. An algorithm of forming of range-velocity portrait from an
initial signal matrix is considered by the example of a continuous-wave radar system with linear
frequency modulation (LFM). Formulas for calculating the maximum value of the amplitude of the
converted signals at all stages of obtaining the range-velocity portrait and the number of iterations
with scaling in the FFT (IFFT) procedures are given. A numerical example of calculating the
number of scaling points for all stages of the algorithm of range-velocity portrait formation is
presented. In the example the required number of iterations with scaling is determined when calculating
the fast convolution and Doppler velocity (taking into account multiplication by the window
function). It allows to prevent signal values from going beyond the bounds of the bit grid. As a
result, it was found that the proposed method for calculating the number of scaling points avoids
an excessive drop in the signal level at the processing output and reduces the ratio of digital processing
errors to the signal level of the range-velocity matrix.

The article discusses the issues of digital processing of images of large dimensions in real
time using reconfigurable computer systems (RCS) on the base of programmable logic arrays
(FPGAs). RCS belongs to the class of high-performance multiprocessor computing systems that
have a programmable architecture that allows configuring the structure of a computer system and
optimally adjusting it to the algorithms of the solved task. At the same time, optimization of the
computational structure of the task reduced to the development and implementation of parallel
algorithms corresponding to the specifics of the RCS architecture used. All this allows to effectively
using RCS to solve a wide class of digital signal processing tasks. Offered are methods of increasing
specific and real performance of RCS when solving digital image processing problems
using fast Fourier transform (FFT). Using the example of a procedure for filtering images in the
frequency domain, the main computational steps and methods for optimizing them based on the
properties of the FFT algorithm are discussed. The use of optimization allows to significantly reducing
both the amount of computation and the amount of hardware resources of the FPGA andincrease the performance of RCS for image processing tasks. The FPGA resources freed because
of the optimization of the computational structure can be uses to further parallelize calculations
and accelerate the processing of incoming data. The advantages of presenting data in fixed-point
format when performing calculations on RCS are showed. The use of a fixed point allows not only
to increase the specific and real performance of a computer system compared to a floating point
due to the properties of the format, but also to use arbitrary data bit capacity, which is relevant for
most digital signal processing tasks. The solution to the problem of overflow of the bit grid when
using the fixed-point format using data bit scaling is discussed.

The paper reviewes a problem of optimization and quality improvement of development and
design of multi-channel systems which perform direct volume visualization. Volume visualization
is widely used in modern computer graphics and visualization systems. Volume visualization is
well-know for its requrements - it demands large amounts of data to be processed to produce a
high quality result. The optimization problem is considered as a quality-cost dependence, where
the target is to achieve is the required quality level at minimal cost. The paper proposes a method
for logical synthesis of such systems, which allows to obtain optimal quality-cost ratios depending
on the required parameters. The proposed method allows to achieve a quality level, that is close to
results of a full-search solutions, but it requires a significantly smaller amount of calculations. For
each channel of the system, a set of variables is defined, the optimization of which will ensure the
quality of the resulting images. Based on the optimization parameters, a switching function is constructed
using a Veitch diagram. This approach is implemented programmatically in each channel
of the distributed system in real time, what sets the general scheme of the method. In described
study, experimental research of relatationship between the accuracy of the solution and the
amount of calculations of direct volume visualization in each channel of a distributed system was
performed. A method for optimal image synthesis based equalizing the playback quality in a small
group of channels in a distributed system was developed.

Storing, processing and analyzing of experimental and simulated data are an integral part of
all modern high-energy physics experiments. These tasks are of particular importance in the experiments
of the NICA project at the Joint Institute for Nuclear Research (JINR) due to the high interaction
rate and particle multiplicity of ion collision events, therefore the task of automating the considered processes for the NICA complex has particular relevance. To solve the task, modern physics
experiments use various information systems, which control experiment data flows and simultaneously
service a large number of requests from various systems and collaboration members. The article
describes the design of a new information system based on the Condition Database as well as related
information services to automate storing and processing of data and information on the experiments.
The Condition Database is aimed at storing, searching and using various parameters and operation
modes of experiment systems. The system being implemented on the PostgreSQL DBMS will provide
the information for event data processing and physics analysis and organize a transparent, unified
access and data management throughout the life cycle of the scientific research. The article shows
the scheme and purposes of the Condition Database and its attributes, key aspects of the design are
highlighted. A place of the Condition Database in data processing flow is illustrated. The integration
of the information system with experiment software systems is also presented. The development of the
Condition Database interfaces has been started to use the stored information in event simulation, raw
data processing, reconstruction and physics analysis tasks.