This paper discusses the structure of the devices and their defining formulas used for local approximation using power-algebraic polynomials when the observed data are known exactly. A multichannel system for processing discrete sequences is considered. On the basis of the considered system the research of acceleration of calculations in the system from specialized computational modules is carried out. The carried out researches have shown, that the developed model of multichannel data processing system allows to reduce essentially time for data processing.
Organization of calculations or processing of data on the observed samples of the process carried out with the help of the representation of algebraic polynomials refers to the class of methods of analytical representation and signal processing. This paper discusses the structure of the devices and their defining formulas used for local approximation with the help of power algebraic polynomials, when the observed data are known exactly. 2. Multi-channel system for processing discrete sequences The representation of the functions of the observed data can be referred to the issues of interpolation with the help of polynomials on linearly independent systems of functions and are considered later as the issues of coordination of local interpolation functions on smoothness in the nodes of their conjugation [2, pp. 146-194].
The approximation of the processes on the observed samples can be carried out with the help of algebraic polynomials, for example, the point method of least squares or methods of local interpolation, which belong to the class of methods of analytical representation of signals. Here we consider algebraic models and methods of the need to solve local satisfaction with the conditions of smooth coupling, approximation by discrete data.
Thus, at first it is assumed that all sample values of the process and its derivatives in the interpolation and coupling nodes are known.
Let's denote an interpolation polynomial through Pi (t) , which provides the approximation of the process y(t) at the interval [ti , ti+1 ) , ti < ti+1 , i = 0, 1, , by some number of known values of this process y(tij ) = yij , j = 0, 1, , n , and, possibly, its derivatives y (r) (tij ) = yi(jr) , r = 0, 1, , m j and yi(j0) ≡ yij .
The moments ti of the pairing of polynomials Pi−1 (t) and Pi (t) will be referred to points or nodes in the pairing, and the moments tij , at which sample values yij and y (r ) are taken, will be referred to ij interpolation nodes. The intervals [ti−1, ti ] and [ti , ti+1 ] , called interpolation intervals, are obviously areas of definition for polynomials Pi−1 (t) and Pi (t) . Interval boundaries, within which interpolation nodes tij are located, are denoted as moments ti and ti+1 , so interval [ti , ti+1 ] is the area where the observed data used in interpolation formula construction or mapping Pi (t) : [ti , ti+1 ] → [ti , ti+1 ] are defined.
Interpolation polynomial Pi (t) by the system of algebraic functions t k , k = 0, 1, , N , i.e. polynomial Pi (t) = ai0 + ai1t + ai2t 2 + aiN t N , can be written in the form
n mj Pi (t) = ∑ ∑ Lrij (t) yi(jr) ,
j=0 r=0 d l dt l Lrij (t)
t =tik = δ jk δlr , l, r ∈ Μ j .
It can be shown that the problem of constructing polynomials (
It should be taken into account that the system of functions t k refers to the class of generalized Chebyshev systems, which by definition should have a non-zero determinant
1 0 0 1 0 U ∗ 0 t0 1 t1 2 t2
N
= tN t0 ⋅ 1 ⋅ ⋅ 0 ⋅ tn ⋅ ⋅ ⋅ 0 ⋅
≠ 0 . (
In this case, we can conclude that there is an interpolation polynomial at any location of
interpolation nodes and, in particular, the existence of fundamental polynomials Lrij (t) , and hence the
possibility of approximation of observed data using the (
The essential point of this conclusion is that in each node of interpolation there should be known
the values of both the process and all its derivatives up to a given maximum order. However, if the
physical features of the problem as the initial data in the construction of the interpolation polynomial
are sample values of the process and its derivatives, measured at different moments of time, and
interpolation polynomial instead of (
n
Pi (t) = ∑ ∑ Lrij (t) yi(jr) , (
j=0 r∈Μ j
where Μ j is a subset of multiple integers (0, 1, , m j ) . The fundamental polynomials satisfy the
conditions
(
This can be shown in a simple example of building a second-degree polynomial
P(t) = a0 + a1t + a2t 2 a using the values specified in the interpolation nodes P(t0 ) = y0 , P(t1) = y1 ,
P(t2 ) = y2 . The coefficients of this polynomial, taking into account the given conditions, should
satisfy the system of linear algebraic equations
1 t0 t02 a0 y0
0 1 2t1 a1 = y1 . (
The determinant of this system is (t2 − t0 )(t2 + t0 − 2t1 ) . In case of equidistant nodes, when t2 + t0 = 2t1 , it is equal to zero. At the same time, the solution of the system and, accordingly, the solution of the interpolation problem does not exist, except for the unlikely case of a multi-digit solution, when the ranks of the main and extended matrices coincide.
Such a situation, although not necessarily, may arise in general. Therefore, if there is a need to use
formulas of the type (
Using formula (
∞ n m j ∞ yˆ (t) = ∑ Pi (t)Ii (t) = ∑ ∑ ∑ Ii (t)Lrij (t) yi(jr) .
i=0 j=0 r =0 i=0
Sampling values yij and yi(jr ) , which clearly define interpolation and fundamental polynomials (1; 4), can be divided into two classes: the actual measured values, the values of process y(t) and its derivatives y (r) (t) in the interpolation nodes tij , and the values that represent their estimation from indirect data. This estimation can be obtained, for example, by calculating the values of polynomial Pi−1 (t) representing the process at the previous step of interpolation, and the values of its derivatives Pi(−r1) (t) in the required interpolation nodes. On the interpolation schemes, such values will be marked with an asterisk in the future so that they can be distinguished from the measured values.
To ensure the required smoothness of the interpolation formula (
When considering the case where the layout of the interpolation nodes and the length of the segments [ti , ti+1 ) do not depend on the number i of the interpolation step, i.e.
ti+1 − ti = Θ
and tij = t j + iΘ ,
and if you enter the discrete time t =τ + kΘ , the interpolation formula (
k =0 k =0 j=0 r=0 where Lrj (τ ) ≡ Lr0 j (τ ) – the fundamental polynomials defined in interval [t0 , t1 ) , L0j (τ ) ≡ Lj (τ ) and the time window I (t − kΘ) ≡ Ik (t) . Further on, for the sake of certainty, it is also believed that t0 ≡ t0q = 0 .
The interpolation of processes in the multidimensional space represented by a discrete function is
done in a similar way, if the formula (
From the above studies and according to [8], it is clear that the use of dot MNAs is fully justified,
since this method allows us to obtain the lowest number of coefficients compared to other
interpolation methods, such as spline functions, interpolation polynomial Lagrange, etc., with the same
value of error.
3. Study of acceleration of calculations in the system of specialized computational modules
The expression (
l l yˆ (t) = ∑ Flr y(t)Φ0 =∑ Flr ykl , l =1 l =1
(
y(t)
y(
F1 F2 . . .
Fl F`1 F`2 . . .
F`l + + +
ŷ(t)
As can be seen from Figure 1 and in accordance with (
yk(lr) = y(r) (tk + Θ) , k = 0, 1, 2, … , N-1, (
j is sequence offset, j∈{0, 1, 2, …, N-1}.
An evenly distributed sequence can be represented depending on offset j in the form of k = 0, 1, 2, … , N-1.
(13) y(r)[d (k + j)T ], j > k.
In practical terms, the expressions (12) and (13) describe situations, where the nodes of the interface respectively coincide with the reference points of process y(t) and its derivatives.
It should also be noted that the l-th channel of the model of multichannel data processing system with the function of the data generator Fl is a set of filters Flir (S ) in the form of n Fl = ∑ Fli (S ) , i=1 which form the structural scheme presented in Figure 2. with the transfer function in the form of l n 1 Flir (S ) = ∑ ∑ (arjil − crjile−SΘ ) ,
l =1 i=1 Sli where с is series coefficients. (14) yk
r F l1
r F l2
After transformation of expression (14) relative to Si with regard to the limitations of the equality type
r = 0, d = 1, j = 0, c = 0, (15) the solution of determining the acceleration of computational operations depending on the number of specialized calculators and on the volume coefficient of parallel calculations a is carried out by the formula l Sl = . (16)
l(1 − a) + a
We can see from expression (16) that the increase of calculation efficiency depends on the algorithm of the task, when restricting the type a < 1, which allows us to estimate the efficiency of parallelization of the algorithm and the conclusion about the necessary number of specialized calculators [1, 5].
Dependence of the growth of computational operations' acceleration on different number of specialized calculators on the size coefficient of parallelized calculations a is shown in Figure 3.
Figure 3 shows that the increase of computation speed for the computer system from l specialized calculators can be obtained at the value of parameter a according to the condition 0.25 ≤ a ≤ 0.75 .
The results of the research of the dependence of the acceleration of calculations on the number of specialized calculators l are shown in Figure 4.
Figure 4 shows that with the coefficient a = 0.75 in the algorithm, the increase in the number of parallelized cores of specialized calculators up to the value of l ≥ 16 leads to a significant increase in performance, in particular, the use of a single quad-core GPU as a specialized calculator increases the performance by more than 2 times.
The developed model of multichannel data processing system was used for research and development of the algorithm of advanced audio stream mixing in telecommunication systems [10]. Application of the developed algorithm in a heterogeneous computer system reduces the time for data processing to 0.2226x10-3 sec. instead of 1.351x10-3 sec. – the time of data processing by the base algorithm.
Studies have shown that the increase in calculation efficiency depends on the algorithm of the task when limiting the a < 1 type. It allows you to estimate the efficiency of algorithm parallelization and make a conclusion about the necessary number of specialized calculators. Thus, the increase of calculation acceleration for a computer system from l specialized calculators can be obtained with the value of parameter a in accordance with the condition 0,25 ≤ a ≤ 0.75. At the same time, the increase of the number of parallelized cores of specialized calculators up to the value of l = 16 at the value of the coefficient a = 0.75 in the algorithm leads to a significant increase in performance, but with a further increase up to l > 256 it does not bring any significant results, which is consistent with the main provisions of Amdal and Graham's researches.