Introduction

In recent years, there has been a significant increase in interest in the development of information technologies related to the receipt, processing, transmission and storage of Earth remote sensing data. Moreover, the work is carried out both in the hardware and software segments: on the one hand, the equipment of the spacecraft themselves is constantly being improved, the existing ground infrastructure is developing, the network of ground control stations and the range of their functional capabilities and tasks are being modernized and expanded, and on the other hand, they are being developed and highly efficient methods of computer processing of Earth remote sensing data are being improved, including high-resolution space images and the latest hyperspectral data, new software systems for their processing are being created, etc.

Earth remote sensing data are used in solving a wide range of problems of ensuring state security, environmental monitoring and environmental protection, prevention and analysis of natural disasters and various emergencies, urban infrastructure development and many other pressing problems.

Most of the modern methods for processing remote sensing data of the earth's surface are aimed at solving the problems of preprocessing and analyzing the received space images, identifying and recognizing thematic objects on them in order to create digital models of the Earth's surface, as well as solving the problems of monitoring the selected objects. Along with classical methods, hybrid methods of remote sensing data analysis are being developed using technologies for high-performance processing of large volumes of video data and artificial neural networks [1].

The creation of the latest global Geoinformation Monitoring Systems of a new generation, along with the development of the mathematical apparatus, requires the accumulation of a data bank of space images of the Earth's surface, including dual-purpose space data obtained from various sources: spacecraft, ground and surface stations, flying laboratories, etc. also the creation of a network of groundbased information processing centers. The relevance of such monitoring systems is determined by the possibility of creating on their basis highly efficient IT technologies for performing various interdisciplinary research [1].

Currently, high-performance technologies are widely used to process Earth remote sensing data on computing clusters with GPUs [2,3].

The study [4] presents the results of the practical use of hardware and software systems based on a distributed grid-infrastructure of supercomputer resources for solving resource-intensive applied problems of remote sensing of the Earth.

Note that the growth of complex problems, the solution of which is associated with the use of modern IT technologies, leads to the need to use parallel computing. Parallel computing is interdisciplinary in nature. They affect, in particular, such areas as numerical methods, structures and algorithms for data processing, hardware and software, systems analysis. This allows you to apply the knowledge gained in the study of parallel computing in various areas of scientific and practical activities.

Characteristic properties of space hyperspectral images in the context of compression perspectives

At present, remote sensing devices, placed on airplanes and spacecraft, are quite effective in solving various problems of monitoring the earth's surface [5]. Most of these systems render a scene image using a multichannel shooting mode. A promising type of such a regime is hyperspectral imaging, which covers the optical and near infrared ranges of electromagnetic radiation, has high spectral and good spatial resolutions and simultaneously forms from several hundred to one and a half thousand raster hyperspectral images that are practically combined with each other. The peculiarities of hyperspectral imaging determine a high degree of redundancy of the resulting raster images, since the images in two adjacent spectral channels usually have a correlation coefficient close to one, because for neighboring spectral channels, the difference in wavelengths is minimal [5-11, 15, 16].

Brief characteristics and problems of efficiency of existing methods of compression of space raster hyperspectral images

All existing methods of image compression in general are divided into two groups, providing lossless and lossy compression.

Lossless compression methods provide not very high compression ratio of raster hyperspectral images of Earth remote sensing (~ 3 -4), but their use does not introduce any distortions into decoded images [8], which is their indisputable advantage. However, since the obtained values of the compression ratio do not always meet the requirements of practice, the problem of developing and applying methods of compression of raster hyperspectral images with losses [9 -12], which form higher values of the compression ratio at the output compared to the methods of the first group, is urgent.

Lossy compression methods use an approach based on the expansion of the initial signals in terms of a particular system of basis functions with a given approximation accuracy ε. In this case, the optimal coding of raster hyperspectral images will be provided only by such a system of basis functions, which, for a given root-mean-square error δ, provides the minimum, or close to it, the number of basis functions

) ( , ..., ), ( 2 ), ( 1 t m t t   

. Then the process f(t) (t 1 ≤ t ≤ t 2 ) can be approximately represented in the form

   m k t k k C t f 1 ) ( ) ( ~ of basis functions ) ( , ..., ), ( 2 ), ( 1 t m t t   

. The coefficients C1, C2, …, Cm are considered as a code of the curve f(t). The approximation error in this case is:

    m k t k k C t f t 1 ) ( ) ( ) (   .

Obviously, different types of encoded hyperspectral data will require different optimal systems of basis functions.

To be able to apply the methods of this group, the original raster hyperspectral data must be converted into a set of vectors obtained as a result of sequential line-by-line scanning of the original rasters.

Certain difficulties in using these methods are associated with the fact that the choice of an informative system of basis functions is mainly determined either from the experience and intuition of the researcher, or from the external similarity of the initial signal with the form of basis functions. This can lead to the fact that the optimal, or close to it, the system of basis functions may not be found, especially in the of a complex form of the initial signal, which is certainly characteristic of the studied raster images.

The solution to the problem can be found as a result of the use of objective methods for choosing a system of bases, in which they do not rely on human knowledge, but proceed only from the properties of a set of initial continuous data. One of such optimal basis systems is the system of eigenvectors of the covariance matrix calculated for a given set of initial data, and the corresponding eigenvalues characterize the accuracy of the approximation. However, this method is quite cumbersome in terms of computations, in addition, the system of basis functions obtained in this way allows, with a given accuracy, to encode not every function of the original set of signals, but only on average over the set. In this case, the main part of the data will be encoded with a given approximation accuracy, however, the encoding of extreme data can occur with a significant error. Obviously, when coding hyperspectral raster images, this is an undesirable property of the resulting basis system.

The problem of compression of raster hyperspectral images of the earth's surface remains a rather urgent problem of image processing and information transfer. Despite the abundance of the proposed compression methods and software compression systems created on their basis, the problem of increasing the resource efficiency of the proposed methods remains quite acute.

In [12], the authors proposed a sequential quasi-optimal algorithm for eliminating the information redundancy of raster hyperspectral images of remote sensing of the Earth with controlled losses based on the construction of a system of local homogeneous "well-adapted" basis functions [17,18]. Practical use of the algorithm revealed its sufficient efficiency in terms of the obtained compression ratio of raster hyperspectral images, however, the temporal efficiency of its operation can hardly be called satisfactory.

Statement of the problem

Develop a parallel algorithm for the formation of a system of local homogeneous "well-adapted" basis functions for compression with controlled losses, and analyze its efficiency in comparison with the sequential version when encoding a sample of 360 grayscale 16-bit raster hyperspectral images of the Earth's surface (spectral channel data).

Problems of design and creation of parallel methods and algorithms for compression of raster hyperspectral images

The main task of increasing the efficiency of high-performance tools used for processing streams of hyperspectral rasters of the earth's surface is the parallelization of computations. To solve this problem, two approaches are distinguished [19], which consist in:

1. dividing each set of raster images of spectral channels into separate fragments -streams 1, 2, ..., N elements -pixels, each of which is processed separately in a parallel mode, while the division goes along the width and / or height of the image, and also due to portioned loading of snapshot data into RAM; 2. formation of data streams 1, 2, ..., N, each of which is a combination of groups of raster images of different spectral channels. Each of these generated streams is processed separately in parallel. The total number of channels is divided evenly by the number of processing cores of the processor(s). Parallel computing systems are physical computer systems, as well as software systems that implement in one way or another parallel data processing on many computing nodes, which is most suitable for the problem being developed, taking into account the fact that most modern computer systems are multiprocessor. The idea of parallelizing computations is based on the fact that most problems can be divided into a set of smaller problems that can be solved simultaneously.

The main idea of the distribution of the computational process is the transition from parallelism at the instruction level to parallelism at the data and task level. The development of methods and algorithms that implement parallel computing mechanisms for solving complex scientific and technical problems is often a significant problem.

When developing software, we will rely on a cascade with feedback model, as one of the basic ones when creating parallel methods [21]. This model allows, based on the operational analysis of the effectiveness of the developed computational schemes, at any stage of development, to return to the previous steps. Efficiency is assessed by analyzing parameters such as speedup, efficiency, scalability generated by parallel computing.

When implementing a parallel version of the algorithm for forming a system of local homogeneous "well adapted" basis functions, we take into account that the computational scheme for solving the problem is known. This determines the composition and order of subsequent actions to determine effective ways of organizing parallel computing. Let us highlight the three most essential steps [19][20][21]:

 sequential analysis of the possibility of independent implementation of individual blocks and components of the code being developed with further segmentation into a set of subtasks. Successful code segmentation will inevitably speed up your program;  determination of a set of information interactions between individual subtasks in the process of solving the original problem, ensuring the minimization of such interactions;  selection of the necessary computing system and implementation of the distribution of the formed set of subtasks among the processors. At the same time, we take into account that the computational load on the processors must be balanced. The analysis shows that most often a return is carried out in order to correct from the last step to the first step of the given scheme. This is due to the fact that after determining the available number of processors, it is the composition of the formed set of tasks that must be adjusted. At the same time, in the presence of a small number of processors, subtasks can be enlarged, or, conversely, detailed. Some developers distinguish these actions as an independent stage of parallel computing design and are defined as scaling of the developed algorithm [21].

As a result, we can distinguish 4 fundamental stages of the process of developing parallel algorithms: 1. decomposition of the task into subtasks that are implemented independently; 2. determination of information interactions for the formed set of subtasks; 3. scaling of subtasks, determining the number of processors; 4. definition of system architecture, assignment of subtasks to processors, scheduling.

Steps 1-4 can be repeated as needed, for example, to improve the efficiency of the algorithm. If the desired indicators are not achieved, then the mathematical model of the problem should be changed.

The above scheme is general, in this regard, in each specific case, the sequence of steps may vary. Decomposition stage. The original task is analyzed and segmentation is carried out into a set of basic subtasks. At the same time, the minimum requirements are imposed to ensure the same amount of computational load in the allocated subtasks and to ensure the minimum information exchange between the processors.

The stage of analyzing information dependencies between subtasks. There are 4 types of dependencies between executed subtasks: local or global, structural or arbitrary, static or dynamic, synchronous or asynchronous. Local data transfer schemes are used for neighboring processors, in contrast to global schemes, in which all processors take part. According to the methods of interaction, structural, corresponding to typical communication topologies, and arbitrary are distinguished. Static constraints are defined at design time, and dynamic constraints are defined during calculations). If the next operation is performed after the previous one has been completed by all processors, then a synchronous method of interaction is selected, and if the processes cannot wait for the complete completion of data transfer actions, then we are dealing with an asynchronous method of interaction. At the same time, subtasks have a high degree of informational interdependence.

Scaling stage. Executed if the number of subtasks differs from the number of processors. Then the transition to the stage of decomposition is carried out. At the same time, the number of subtasks is reduced due to the enlargement of the source data area. First of all, it is necessary to combine areas for which subtasks have a high degree of informational interdependence.

The stage of assigning tasks to processors. At this stage, we take into account the presence of information interactions between the data areas of these tasks and, if they exist, we place such tasks on processors connected by direct data transmission lines.

When developing a parallel algorithm, we take into account that it is characterized by data parallelism and parallelism of tasks, and its efficiency directly depends on the ratio of the time spent on performing computations on fragments of the initial data and the time for transferring data.

In the presence of data parallelism, the task is reduced to dividing the original data array into fragments with their subsequent independent processing on different processors, subject to the requirement for their relatively uniform loading, taking into account their possible different performance.

When there is task parallelism, there is no data parallelism. Then the original task is split into several independent subtasks, and each of them, ideally, is sent to a separate processor. The number of subtasks affects the number of processors. By ensuring that the processors are loaded evenly and the data exchange between them is minimized, significant acceleration can be expected.

Comparing the times spent by different parts of the program, we identify its most resource-intensive parts, which allows us to judge the efficiency of the generated code.

The authors have chosen the CUDA platform as a software and hardware solution that provides a sufficient level of development tools and high efficiency of calculations on the graphics processor. To get a significant increase in performance relative to the central processor, it is important to take into account that the structure of the graphics processor is significantly different from the central processor and the very approach to organizing computing programs is different. So, a graphics processor (in this case, we are talking about CUDA compatible processors) is capable of executing thousands of threads simultaneously. This is possible due to the organization of computational flows in blocks of 32. Each block is included in the block grid. The GPU itself consists of multiprocessors, which contain several grids with blocks of threads. At the same time, next to the GPU, there is a high-bandwidth graphics memory common to all threads. It is important that the exchange of data between RAM and graphics memory is relatively slow, and therefore graphics memory must be used as efficiently as possible for the entire parallel computing process, minimizing data loading and unloading. In addition, the computational cycles themselves must be assembled in such a way that they occupy as many threads as possible per unit of time. As a result, at stage 3 of the process of constructing parallel algorithms stated above, it is necessary to additionally distribute the data in the graphics memory in such a way that it is possible to organize the execution of simple computations many times, while occupying all blocks and all flow grids with computations.

It was shown in [12] that the process of constructing the unit vectors of a system of local homogeneous "well-adapted" basis functions consists of a set of stages described by formulas (1) and (2):

    1 1 1 1 , , 1 1 1 1                          L k k k S S L k k k S S L U U x x x x U U x x x x U k L k L (1) where    N j j x N x 1 1

~, and the point 𝑥 𝑆 𝐿+1 is chosen so that

 1 L           L k k k S S U U x x x x k L 1 , 1 1  (2)        k k j j j U U x x x x , max .

To implement them, a sequential search is required until the    1 L condition is satisfied, where  is the specified approximation accuracy. This fact introduces significant complexity in the application of parallel computing to solve this problem.

It is seen that finding each next basic unit vector of the system of "well-adapted" basic functions is computationally laborious. It is also obvious that it is also impossible to perform all computational operations on the GPU on one set of data at a time by dividing the entire array of computations into many threads. As one of the technological options on the way of constructing a high-performance implementation, it is possible to single out the computations of scalar products in a separate computational procedure, since such computations can be efficiently performed in parallel. In addition, finding the maximum length of a vector can also be organized as a separate computational procedure in such a way that all lengths are stored in a buffer and then the maximum is selected. Thus, as a prototype, a combination of calculations on the central processor and the graphics processor was obtained, where the finding of each subsequent basis vector is organized by a cycle on the central processor, in the body of which the procedures for finding scalar products over the entire data set and finding the maximum length are performed.

Computational experiments show a reduction in computational time (depending on the amount of initial data) by at least an order of magnitude. Obviously, the result obtained is not optimal and intermediate. Research in this area will be continued by the authors in the future.