RU199929U1 - DEVICE FOR PROCESSING STREAMS OF SPACE-TIME DATA IN REAL TIME MODE - Google Patents

Abstract

The utility model relates to information processing facilities. The technical result is to increase the efficiency of processing spatio-temporal data streams by reducing the time for pre-filtering messages and increasing the throughput of the device. The device for processing spatio-temporal data streams in real time contains a router responsible for sequential processing of incoming messages, and at least two parameterizable programmable computing units, each of which is configured to implement an operator selected from the comparison of coordinates in cells of regular flag grids and mappings of coordinates and cut lines with flags. 1 ill.

Description

The utility model refers to information processing facilities, namely, to a device for processing streams of spatio-temporal data in real time, and can be used as part of a cyber-physical system for monitoring production processes based on distributed networks of intelligent geosensors.

When processing streams of spatio-temporal data coming from networks of geosensors, there is a need to determine the value of spatial predicates of the form: "is there an intersection between the areas g and p", where g is the area of uncertainty of the position of the geosensor at the time of measurement, and p is a certain area defined task of the subject area.

The traditional approach to performing tasks of this kind involves a combination of two stages - the stage of pre-filtering using a particular spatial index and the stage of calculating the spatial predicate using the Egenhofer and Gerring nine-dimensional model or the extended nine-intersection model (DE-9IM, Dimensionally Extended 9 Intersection Model ), developed by Clementini et al.

Currently, there is a need to create more efficient tools for processing spatio-temporal data streams in real time, providing processing of a large number of spatially coordinated messages with controlled delay. That is, the system must have high throughput in order to process N incoming messages per second, while the system's response to each message must be formed in no more than S seconds (latency).

The authors of the utility model have found a way to solve the above problem by creating a solution that provides hardware implementation of a part of the processing process that presupposes a preliminary interpretation of coordinates from a message. Thus, a refined (final) interpretation of coordinates in some cases may not be needed at all, and in others it may require a much smaller amount of data. Together, this allows both to increase the throughput and reduce the latency of the system for processing space-time data.

The technical result of the claimed utility model is to increase the efficiency of processing spatio-temporal data streams by reducing the time for pre-filtering messages and increasing the throughput of the device.

The specified technical result is achieved in that the claimed device for processing streams of space-time data in real time contains a router responsible for sequential processing of incoming messages and at least two parameterizable programmable computing units, each of which is configured to implement the operator selected of the following: mapping coordinates in grid cells to flags, and mapping coordinates and cut-off lines to flags.

FIG. 1 is a block diagram showing the general principle of operation of the device in accordance with one of the possible variants of its implementation.

The claimed device for processing streams of spatio-temporal data in real time operates at the level of messages, each of which contains a certain payload, which includes coordinates and a set of logical features - flags.

A flag is understood as a logical sign: either it exists or it is not. Initially, the set of flags is empty.

The physical implementation of the device assumes the presence of a hardware implementation of elementary basic procedures - operators in the form of specialized microcircuits or FPGAs (programmable logic integrated circuits). An example is the representatives of the UltraScale and UltraScale + families manufactured by Intel and Xlinix. The operator is responsible for the procedure that receives the message data as input and modifies its set of flags depending on the processing result. The specific composition of operators may vary depending on the task and operating conditions.

In accordance with the task set by the authors, the claimed device is focused on processing spatial data with high performance, therefore, operators should be able to process each message in a limited time, ideally constant.

Examples of spatial analysis problems solved by operators include the following.

1. Determination of the belonging of coordinates to cells of a regular grid: each cell assumes the addition of a certain set of flags.

2. Determination of the relative position of coordinates and a set of cutting lines: each combination of mutual positions involves the addition of a certain set of flags.

Operators need data to operate. For example, for operator 1 (see block 1 in Fig. 1) these are the parameters of regular grids and sets of flags for each cell, and for operator 2 - sets of cutting lines and sets of flags for each of their combinations.

The operator's programmable memory is used to store the necessary data. It is available to the operator in read mode and can be divided among several instances of the same operator.

The hardware implementation of the operator requires a certain set of peripheral equipment for operation, which supports its operation and provides reception and transmission of processed data, together with which it forms an information processing unit. The set of equipment itself is determined by the specification of the FPGA or microcontroller. Several blocks can provide the implementation of the same operator, which, due to the parallel operation of the blocks, allows one operator to execute on several messages simultaneously.

Coordination of processing and, mainly, distribution of messages into blocks is performed by the Router. Its hardware implementation can be built on specialized FPGAs similar to those used to implement operators (Intel, Xlinix, etc.) or a high-performance programmable microcontroller (for example, architecture-based, ARM).

Router operation is determined by the routing program, also stored in memory. The router memory can be implemented as a separate device, or it can be provided as part of an FPGA or a microcontroller that implements the basic functions of the router.

The router processes incoming messages sequentially. Processing consists in comparing the set of flags of each message with the reference ones defined by the routing program, and if a match is found, sending the message for processing to a free block of the type defined by the routing program. If there is no match, the message is sent to the output of the device.

The router operates on the assumption that the result of the work will be placed by the operator in the processing queue.

A processing queue is a set of solutions for storing and prioritizing messages that require processing. The hardware implementation of the processing queue can be constructively isolated and built on the basis of an FPGA or microcontroller, or be integrated into the Router.

The input and output of the claimed device is a set of hardware and software solutions that ensure the integration of the device with general-purpose computing equipment.

Its implementation can be built, for example, on the basis of an Ethernet network, or a local bus for interaction with PCI-Express peripherals.

In this case, the input part provides interaction with the source of messages, and the output part - with the recipient. The source and recipient of messages can be either integrated or isolated.

The receiver of messages is also capable of realizing control communication - transmission of a set of signals that allow changing the data of the programmable memory of operators and routing programs.

The operation of the declared device involves two phases:

1.programming by using the control link to write the desired data to the operator programmable memory and the routing program, and

2. analysis that involves directly processing messages.

The data that must be written into the programmable memory of operators and the routing program form the basis for adapting the device for different territories and tasks - the program.

The construction of the device program involves the solution of an optimization problem, which involves the search for the optimal decomposition of the problem of the subject area into operators, taking into account the presence, number and characteristics of their hardware implementations in the device, and the probabilistic characteristics of the initial data flow.

An example of router and device operation.

The work of a router to process incoming messages is based on successive approximation and can be illustrated as follows.

1. Message M containing the coordinates of the event and an empty set of flags arrives at the Q queue.

2. Router R extracts M from Q and, according to the rule for an empty set of flags, routes M to the block that implements statement A.

3. The block that implements the operator A compares the coordinates from M with a coarse grid and finds that M belongs to a square in the territory (for example, Moscow).

4. The implementation of operator A adds a flag corresponding to "Moscow" to the set of flags of message M and sends it for re-processing.

5. Router R extracts M from Q and, according to the rule for a set of flags ("Moscow"), directs M to the block that implements operator B.

6. The block that implements operator B compares coordinates from M with a more accurate grid corresponding to Moscow and finds that M refers to the square in which the central and western administrative districts are located.

7. The implementation of operator A adds a flag corresponding to "Moscow, Central Administrative District or ZAO" to the set of flags of message M and sends it for reprocessing.

8. Router R extracts M from Q and, according to the rule for the set of flags ("Moscow", "Moscow, Central Administrative District or ZAO"), sends M to the block that implements operator C.

9. The block that implements the operator B compares the coordinates from M with a set of cutting lines and finds that M belongs to the square in which the Presnensky district of the Central Administrative District is located.

10. The implementation of operator A adds flags corresponding to "Moscow, Central Administrative District" and "Moscow, Central Administrative District, Presnensky District" to the flag set of message M and sends it for reprocessing.

11. Router R extracts M from Q and, not finding an appropriate rule, sends a message M to exit processing, with flags: "Moscow", "Moscow, CAO or CJSC", "Moscow, CAO", "Moscow, CAO, Presnensky area".

In this case, the router can provide processing of several messages by different blocks, i.e. provide their parallel processing.

Claims (1)

A device for processing streams of space-time data in real time, containing a router responsible for sequential processing of incoming messages, including the coordinates of the event and a set of logical flags indicating a specific location of the event, and at least two parameterizable programmable computing units, each of which is configured to implement an operator selected from the following: matching coordinates in cells of a regular grid with flags and matching coordinates and cut-off lines with flags, and the router is configured to distribute messages to these blocks, re-routing messages coming from the specified blocks, providing parallel processing of several messages by different blocks.

Images