Method for parallel processing of ordered data streams

FIELD: information technology.

SUBSTANCE: method involves obtaining input data streams; transmitting part of the input data streams for processing to processor units, each part of the input data streams being provided with attributes - an input stream identifier and an identifier of the position of that part in the input stream; processing parts of the input data streams; providing the sequence order of the parts of the input data streams which corresponds to the order of the parts of the input data streams, carried out by searching for a processor unit where part of the determined input data stream is processed, said part being in a certain first stream before the part already processed in the processor unit under consideration, wherein if a few of such processor units are found after search, the processor unit selected is that which processes part of the determined input data stream located closest to the processed part of the determined input stream; the processed part of the determined input data stream is transmitted from the considered processor unit to the selected processor unit, also in the presence of processed parts of the input data stream received from other processor units; if no such processor units are found after search, the processed parts of the input data stream are transmitted to the corresponding output data stream, where the sequence order of the parts corresponds to the sequence order of parts in the corresponding input stream, taking into account processed parts of the input data stream received from other processor units.

EFFECT: high efficiency of processing input streams by eliminating waiting for the end of processing the next part of the input stream in cases when previous parts have already been processed.

10 dwg, 1 tbl

 

The technical field to which the invention relates.

The present invention relates to computing and, in particular, to methods for parallel processing of multiple digital data streams, each of which represents a sequence of discrete data sets of a certain type, for example, IP packets, etc.

The level of technology

When processing digital data is often the task parallel processing of multiple digital data streams, which in General have different speed, with automatic multi-channel device that provides the necessary processing each input stream and transmit it in a processed form to the appropriate output stream, and the characteristic speed of data processing in each processing channel may be substantially less than the rate of the input stream, and the required processing rate of each input stream without delay is achieved by having multiple channels of processing.

Important conditions for successful operation of such devices is ensuring strict adherence to the sequence of the processed data in each output stream corresponding sequence in the input stream, as well as high performance.

The character data may be different, for example it may be a transformation in adnych packet Protocol ATM weekend in IP packets, conversion of the input encrypted/unencrypted IP packet, respectively decrypted/encrypted IP packets, etc.

So, there is a method of transferring data between one or more first network ports, receiving one or more first data streams, and one or more second network ports, transmitting one or more second data streams [1].

The method includes the following steps:

- sending data from one or more first data streams to multiple processing channels;

- processing of data in parallel by two or more processing channels;

- receiving data processed by the processing channels and

- sending the processed data to one or more second streams into one or more second ports

moreover, at least one thread from the first and second data streams are transmitted in frames (frames, and each frame in this one thread processed one (the only) channel processing, but at least two frames in the same stream processed by two different processing channels.

The data obtained in each of the first data stream is transmitted in the corresponding second data stream in the same order in which these data were in the first data stream.

After receiving the first stream of each frame before sending processing in the channel of the processing gets additional attributes (data), which include, at least,

- the number of the frame in the first stream and

- the channel ID, which is sent to the given frame.

To ensure the correct order of the processed frames in the corresponding second thread is available stack memory, formed on the principle of "first - come, first-out (first in - first out, FIFO), which identifies the channel to the channels of processing, in which frames are sent from the first stream.

So when, after receiving the channel processing the processed frame is sent to the second thread, it is done in the order of the identifiers of the channels in the FIFO stack.

It should be noted that in the known method uses the original terminology, according to which, in particular, the term "frame" means a discrete set of digital data in a specific format corresponding to any of the adopted Protocol (ATM, IP and others).

For the implementation of the known method is used, the system including:

the first unit to send data from one or more first data streams to multiple channels of processing, in which at least one thread from the first and second streams, the data is transmitted in frames, and the first unit is configured to send each frame only one of the channels of processing, as well as the settlement of the AMB, at least two different frame in two different channel processing;

- multiple processing channels, each of which contains a separate processor;

- second unit for receiving data processed by the processing channels, and send the processed data to one or more second streams into one or more second ports;

- control procedures to ensure that the second unit identifiers of channels for each channel processing, which is sent to the frame of the first block

the second block is made with the ability to get the IDs of the channels from the control unit order in the same order in which the frames are at least one first stream,

thus, when the second unit receives a channel identifier, the second unit sends the frame from the corresponding channel processing in the second thread, so that the frames are sent to at least one second flow channel processing in the order specified by the identifiers of the channels.

In the known method provides processing staff both permanent and variable size. In the General case, even when processing frames of constant size at a predetermined algorithm, the processing time of individual frames may differ due to various factors (different speed of operation of separate channels,different time memory access etc). Thus, it could be a situation when the current frame of the first stream has already been processed in any processing channel but cannot be transferred to the output of the system, since the previous frame, for which he should not yet processed and transferred to the output in the second stream. In this situation, the system waits for processing and transmission to the first output of the previous frame, then the current, to ensure the correct order of the frames.

Even more significantly, such a delay may occur in processing frames of variable size. Such delays reduce the system performance that is the disadvantage of this method.

There is also known a method of providing network system for parallel processing of data streams [2], and the system contains

the first unit, providing

- receive input data streams from external network connections;

the separation of input data streams;

- supply of each part of each input data stream attributes;

- sending parts of each input data stream to the processor units for processing;

- a set of processor units, each of which is composed of a processor and a memory buffer for storing the processed parts of the input data stream and provides

- processing for a given algorithm parts in adnych data streams;

- sending the processed parts of the input data stream to the corresponding output data streams;

- storage of the processed parts of the input data stream in the buffer memory until the fulfillment of conditions make these parts into a corresponding output data stream;

the second unit, providing

- reception of the processed parts of the input data stream;

- creation and modification of output queues containing (output token processing), and the number of output queues corresponds to the number of output data streams;

- transfer of processed parts of the input data streams in the form of corresponding output streams data in an external network;

the first block is associated with a set of processor units and the second block, and CPU blocks are also associated with the second block.

According to the method in one of the proposed options for implementation:

receive input data streams from the network connections in the first block;

- set the desired correspondence between input and output data streams;

- form in the second block output queue of threads, the number of which corresponds to the number of output data streams;

- form in each processor unit output queue of the processor units, the number of which corresponds to the number of output data streams;

- send part of the input data stream for processing in the processor blocks, and each part of each input data stream is supplied attributes, which included

- the ID of the processor that sent this part of the input stream;

- the ID of the input stream;

- put the ID of the processor that sent the next part of the input data stream for processing in the output queue of the thread of the second block, which corresponds to the specified output stream and contains (output token processing);

- process input data streams processor blocks to obtain the corresponding parts of the output data streams;

- write down the ID of the processor unit that has ended processing portion of a particular input data stream, the output queue for this CPU block that corresponds to the given output stream;

- provide {order} parts of the output data streams from (processor units), which corresponds to the order of the parts of the input data stream, and to provide {the correct order}

- compare the ID of the processor unit that has ended processing of the first thread with the correct next ID processor block is as in (output token processing) and if the identifiers do not match, then

- save the processed portion of the first stream in the buffer memory of the given processor unit;

- write down the ID of the processor unit in the output queue of the given processor unit;

- handle the next part of the input data stream in this processor unit;

- if the identifiers match, then

- send part of the output data streams of the processor units in the second block for generating output data streams, in which the order of the parts corresponds to the order of parts in the respective input streams and

- after sending another processed portion of the first flux change in each processor unit the processor ID of the block in the output queue for that processor unit for the corresponding output stream (output token processing) of the corresponding output stream. In the known method provides for processing of parts of the input data stream (packets) both permanent and variable size.

Here the processing of parts of the input data stream at a predetermined algorithm, the processing time of individual pieces may vary due to various factors (different speed of operation of individual processor units, times the second time, memory access etc). Thus, it could be a situation when some part of the input stream has already been processed in any processor unit, but may not be immediately transferred to the output of the system, because the previous part of the input stream has not yet been processed.

To ensure the order of parts in the output data stream, exactly coinciding with the order of the parts of the corresponding input data stream, using a specially formed the first element of which (output token processing) is the ID of the processor unit, which should come into the output stream of the next processed part of the input data stream.

The identifier can be used integers, memory addresses, array indexes, etc.

After sending the input data streams for processing in the processor blocks placed the ID of the processor that sent the next part of the input data stream for processing in the output queue of the thread of the second block, which corresponds to the specified output stream and contains (output token processing), and

- before writing the identifier processing unit block access to the output queue, ensuring, thus, the exclusive write access from the processor unit (and not the record from any other processor unit);

- perform account identifier by performing atomic operations, and then

- remove the lock.

After processing in any processor block part of the input data stream is conducted to check the compliance of the ID processing unit and the correct ID from the output of the token processing.

If these identifiers match, then the processed part of the input data stream is transmitted to the output system in the second block, and an output token processing is modified by deleting from its queue for this room processor block.

If these numbers do not match, then the processed portion of the first stream is stored in the buffer memory of the given processor unit and memorize the ID of the given processor unit in the output queue of the given processor unit, organized in the format of stack memory FIFO.

After that, the processing unit stops and continuously checks the rooms processor unit and the correct number of output token processing until these numbers will match.

According to a preferred variant of the method, if the numbers do not match, the processing unit receives from the first block of a new part of the input data stream and processes it. After finishing the job, but the second part of the input data stream is again checking ID from the stack output queue for that processor unit and the correct number of output token processing.

If these numbers match, then the processed part of the input data stream is transmitted from the buffer memory of the given processor unit to the output of the system in the second block, and an output token processing is modified by deleting from its queue for this room processor block.

Modified the stack output queue of the given processor unit by removing the identifier processing unit, transferred to output the processed part of the input data stream.

The known method is taken as a prototype for the proposed technical solutions.

The disadvantage of this method is the low productivity even in a preferred variant of the method, which occurs due to the delay when checking the ID of a specific processor units and the correct number of output token processing until these numbers will match, if a match has not occurred, then the next time check occurs only after processing the new part of the input data stream.

Disclosure of inventions

The technical result is to increase the productivity of processing input streams by eliminating expectations upon completion of the processing of the next part of the input stream in cases where the previous part has already been processed.

This offers the presumed method of parallel processing ordered data flow in the computer system, moreover, the system contains

the first unit, providing

- receive input data streams from external network connections;

the separation of input data streams;

- supply of each part of each input data stream attributes;

transmission parts each input stream data processing units for processing;

- a set of processor units, each of which is composed of a processor and means for storing the processed parts of the input data stream and provides

- processing preset algorithm, parts of the input data stream;

- transfer of processed parts of the input data streams to the corresponding output data streams;

- storage of the processed parts of the input data stream until conditions make these parts into a corresponding output data stream;

- transfer of processed parts of the input data streams to other processor units;

- getting processed parts of the input data streams of the other processor units;

- search for specific items in the attributes of the parts of the input data stream;

the first block is associated with a set of processor units,

the method lies in the fact that

receive input data streams from the network connections in the first block;

- pass part of the input streams for processing in the processor blocks, each part of each input data stream is supplied attributes, which included

- the ID of the input stream;

- the ID of the provisions of this section in the input stream;

- process input data streams processor blocks to obtain the corresponding parts of the output data streams;

- ensure the order of the parts of the output data streams of the processor units, which corresponds to the order of the parts of the input data streams, and to ensure the order

- conduct the search processor unit, which handles a certain part of the input data stream being in a first stream before the part has already been processed in the given processor unit, and

if after searching such processor units found a few,

- choose the processing unit, which handles a certain part of the input data stream, located closest to the treated portion of a particular input stream;

- transmit the processed part of a particular input data stream of the considered processor unit in the selected processing unit, and, if any, previously received from the other processor units processed part of the input data stream;

if after the CIP is ka such processor units is not found,

- transmit the processed part of the input data stream into a corresponding output data stream, in which the order of the parts corresponds to the order of parts in the corresponding input stream according to the previously received from the other processor units of the treated parts of the input data stream.

Thus, in contrast to the known method in the proposed method after the processing portion of a particular input data stream is not delayed, and the processed part of the input data stream is transmitted from the considered processor unit in the selected processing unit. Following the transfer of the processed part of the considered processing unit immediately takes to process the next part of any input data stream and starts to process.

It can be noted also that this next part may belong to a different input data stream that is different from a particular input data stream, to which belonged previously processed and transferred to the part. This option is not available in the prototype, because it uses the identity of the processor units, bound, ultimately, to any single input data stream until the end of its processing, and it also reduces system performance.

Brief description of drawings

1 shows a diagram explaining the principle of organization of the FIFO queue using attributes Next and Last data structures packets_info.

Figure 2 shows the General algorithm for transmitting the processed packet to the system output.

Figure 3 shows the algorithm of finding the "predecessor" among the processed packets.

Figure 4 shows the algorithm transfers the list of packets processed by the software thread to its current "predecessor".

Figure 5 shows the algorithm checks the queue of packets received from "followers", which is a software flow should pass to the output of the system.

Figure 6 shows the algorithm of finding the "predecessor" using field predecessor_value running program flow in the organization sending the processed packet to the output of the system.

Figure 7 shows the life cycle of the facility, access to which is controlled by a reference counting mechanism.

On Fig shows the algorithm of the function GetReference the reference counting mechanism.

Figure 9 shows the algorithm functions RequestToDisableSharedMode the reference counting mechanism.

Figure 10 shows the algorithm functions ReleaseReference the reference counting mechanism.

The implementation of the invention

Consider the example of an implementation of the proposed method in a network router, made in the form of multiprocessor computer systems and designed to convert a variety of I is-breaking data streams, received from the external data network (e.g., network data packets from the Internet), the number of output data streams that are transmitted, for example, in the internal corporate data network.

For definiteness, we can consider the input streams of data representing a sequence of data packets generated by TCP/IP and encrypted using any standard (e.g., DES) with known parameters.

The task of the router is decoding the input data streams and send them to the internal data network users (normal users).

For receiving input data stream router contains

- multiple network interfaces capable of receiving and transmitting data packets on the network;

- multiple processor units, each of which represents a General-purpose processor (e.g., based on x86 or ARM), the processing of received packets,

- memory for storing the received network packets, as well as information necessary for operation of the system.

The architecture of General-purpose processors must support the following types of operations:

- atomic (non-interruptible) the read operation of the memory cell to record the new value (hereinafter about sachets AtomicExchange), for example, the x86 architecture is a command processor "xchg";

- atomic (non-interruptible) the read operation of the memory cell with subsequent recording of reading is increased by the specified number (hereinafter AtomicAdd), for example, the x86 architecture is a command processor "lock xchgadd".

The router operates under the operating system (OS)capable of operating in a multiprocessor configuration (e.g., Linux).

For the implementation of the proposed method for each processing unit is performing the following additional functions that are missing in the prototype:

- transfer of processed parts of the input data streams to other processor units;

- getting processed parts of the input data streams of the other processor units;

- search for specific items in the attributes of the parts of the input data stream;

Transfer the processed parts of the input data stream to the corresponding output data streams is provided by each processor unit. Direct data transfer to the internal network may be implemented using one or more network cards connected to the internal network.

The features required to implement the proposed method, should be provided with application software (CEA), which can be developed specialist the m programming (programmer) on the basis of the provided information about the assignment of functions.

OS components that control the network interfaces the network interface driver is placed received network packets in memory. In addition to each of the adopted package driver creates in memory a special data structure (hereinafter referred to packet_info), which consists of the following fields (attributes):

address of the data packet from a particular input data stream in memory;

- the address of the next data packet from the specified input stream of data in the queue (sequence) packages (next, Next);

- the address of the last data packet in the queue (sequence) of packets (hereinafter, Last);

The attributes of the Last and Next are for Queuing of received packets that are generated by the FIFO scheme. The last data packet in the queue in the Next field recorded 0 (zero).

The organizing principle of a FIFO queue using the specified fields shown in figure 1.

After copying the packet in memory, the driver adds the corresponding structure packet_info in the FIFO queue of received packets. Access to the queue is synchronized using standard operating system functions (synchronization primitive, for example, spinlock in Linux), which provides exclusive access to the sync object (e.g., memory cell). The specified primitive operates as follows: to access the object component of the OS must "capture" (lock) primitive, then can modify the object, and then "let go" of the primitive (unlock).

Packet processing is performed in software processing threads of the OS (for example, kernel threads in Linux), and the number of software threads exceeds the number of processor units in the system and each software thread runs only in one CPU package.

Each program stream has two States:

- "busy" - processing packet, as well as steps to preserve the order of packets;

- "free" - waiting for a new packet for processing, and the stream is not running your CPU block.

The waiting thread is a new package for processing can be implemented using standard synchronization mechanism of the OS, such as waiting on a synchronization primitive semaphore in Linux.

The number of software threads that are in a certain state, is stored in memory in the form of a special data structure (hereinafter referred to threads_info). Access to this structure is also synchronized by a synchronization primitive FIFO queue.

The driver for the network interface after adding packet_info in the queue of received packets based on the data structure threads_info determines whether there is currently a software processing flow in the status "free". If such a program stream eats what, the driver uses a mechanism of synchronization primitive OS for activating the stream.

For processing network packet in the program stream using a special structure (hereinafter - descriptor), which stores all the necessary information to perform the required actions on the network service and send it to the output from the system.

Each program stream has its own fixed set of structures descriptor reserved in RAM. The number of structures in each set software flow equals the number of software threads in the system. This ensures that the program flow will always be free structure descriptor for processing new package.

Structure descriptor can be in three States:

- "busy" - used for batch processing;

- "free" - can be used by the software thread to process a new batch;

transitional state from busy to free - pack processed, but the structure cannot yet be used to handle the new package.

The state management structure descriptor is carried out through a special software reference counting mechanism to the object and additional flags, described below.

Structure descriptor consists of the fields shown in table 1

Table 1
DesignationTypePurpose
statelinkcharacterizes the state of the structure descriptor
idnumberthe ID of the input network stream from which is taken the package described by this structure descriptor
order_idunsigned integerthe sequence number of the packet in the input network flow; it is believed that the package And is located in the input network flow before packet B, if the difference of their sequence numbers, represented as a signed integer, is negative
predecessor_valueaddressthe address of the structure descriptor that describes the service (the"predecessor"), located in the input network flow data before it is processed by the service
predecessor_statelinklink to synchronize access to the field predecessor_value
packets_listaddressthe address of the first element ocher is di, consisting of structures packet_info; this queue is used to transfer packets between software threads in the process of determining the order of their exit system; along with the address packet_info in this field to store two flag Predesessor_Refn Successor_Ref
stopnumbera sign that the descriptor is not in the busy state
freenumbera sign that the descriptor is in a state of "free"

Structure descriptor state is "free"only when the link state went into a state of modification of the object, thus, able to "free" the link state is in a state of modification.

"Busy" patterns descriptor reference state is the state of the shared object.

Receiving the network packet program flow for processing

Program stream after activation by the driver or the end of the batch accesses the queue of received packets, "capturing" a synchronization primitive, and takes the first packet from the queue.

If there are no packets for processing, a software thread releases the synchronization primitive that has a status of "free" and waits for activation at the appropriate synchronization primitive OS.

If the package is there, then after removing it from the queue the software thread generates the ID of the input network data flow to which the packet belongs, using the number of the network interface in the operating system type of the network layer Protocol, and the header information from the network layer (for example, information from the IP header: IP address of source and destination, type of transport layer Protocol). Then the packet is assigned a sequence number, which reflects its location in the input data stream. The thread ID and the sequence number stored program stream in memory in the structure of the descriptor, the address of which is recorded in the variable free_descriptor. Each software thread has its own variable free_descriptor. This variable is always at the time of receipt of the batch to be processed is stored the address of the structure descriptor in the state "free" from a set of descriptor structures program flow.

After filling in the appropriate fields in program stream translates the structure of the descriptor in the busy state (reference state in sharing mode). Then writes the address of the structure descriptor in RAM variable current_descriptor. Each thread is associated a separate variable current_descriptor.

Then the software thread releases the synchronization primitive queue, after which it is believed that he moved in SOS is the right "busy". Software flow proceeds to the processing package (transcript for a given algorithm, there may be additional actions for routing, filtering rules, and so on).

Packet transmission on the output of the system

After processing to determine the correct order of the packet to the output from the system (on the appropriate network interface) program stream searches "predecessor" (predecessor) of the currently being processed in other software packet streams.

"Predecessor" is a packet from the same input network stream data and the processed data from the program stream, but located in the input network stream before him, i.e. with a lower sequence number.

In the structure of the descriptor has a field predecessor_value, in which is placed the address of the structure descriptor used by the software flow producing processing found "predecessor". Access other software threads to the field predecessor_value synchronized by a reference counting mechanism. For this purpose, the descriptor has a field predecessor_state of reference type.

Packet transmission on the output of the system depends on the availability of "predecessor".

If the "predecessor" was not found, it means that all packets from a specific input network stream to the current processed packet it is sent to the system output, consequently processed packet is transmitted on the system output (the driver for the network interface to send).

If the predecessor was found, the program stream adds the package (the package list in the General case, see below) in all packages packets_list in the data structure descriptor "predecessor". In the process of adding software thread checks the signs of the condition in the structure descriptor "predecessor". If signs indicate the busy state, the package has been successfully added to its queue. Now transfer the package next to the output of the system will perform a software thread executing the processing of "predecessor".

If the "predecessor" is in a transitional state (in a state of "busy" it can't be because the software thread that adds package (list of packages), holds a reference to it), then add does not occur. If the "predecessor" were the packets in the queue, the program stream forms of these packages and your package (the package list) a new list of packages.

Then program stream searches "predecessor" in the busy state, using the box predecessor_value in the structure of the descriptor "predecessor". If the search is successful, then found "precursor" is used for the transmission of packets as described above. If the "predecessor" and was not found, the program stream passes the list of packages on the system output (the drivers of the respective network interfaces).

After the transfer of the list of packages on the system output (according to the above algorithm) software flow checks all packets in its structure descriptor (variable current_descriptor). If in the process of checking software thread detects that the queue is empty or in the moment another software thread tries to add packages to send, then this software thread sets the sign of the transition state of its structure descriptor, and proceeds to retrieve the next batch. Otherwise, the program stream receives all packets from the queue and passes them on to the above algorithm.

The scheme of the packets to the output of the system is shown in figure 2.

Search for "predecessor" among the processed packets

Program stream searches "predecessor", looking alternately variables current_descriptor other software threads (hereinafter - descr), and comparing the ID values of the input network stream and serial number of the batch that is processed with the same parameters of its current_descriptor (next - current).

Before performing the comparison program stream receives a reference de-scr.state that blocks the passage of this structure descriptor in the free state (for reuse).

If descr is first found specifier that meet the requirements of "predecessor", a software thread tries to get the link prede-cessor_state. If successful, the address descr saved as "candidate predecessors" (variable pred). The resulting reference descr.predecessor_state ensures that in a state of transition descr from a state of "busy" state to the "free" value descr.predecessor_value to persist until such time as the current keeps this link (descr cannot enter the state of "free"software because the thread has previously received its link descr.state).

If descr is first found structure descriptor that meet the above requirements, a software thread receives a reference descr.predecessor_state and, if successful, descr saved as "candidate predecessors".

If in the previous iteration of the search has already been found "candidate predecessors", then compares the sequence numbers and descr "candidate predecessors" to determine which of them is "closer" to the current.

If closer was descr, a software thread receives a reference descr.predecessor_state and in case of success remembers descr as "candidate predecessors", and links the former presidential candidate predecessors" are exempt.

As a result of successful search last found a candidate predecessors" will be considered a "predecessor", the address will be saved in current_descriptor.predecessor_value and software flow will give him your processed packet to a software thread "predecessor" OTP is it on start-UPS amounted to exit the system after its package.

The search sequence "predecessor" among the processed packet is shown in figure 3.

The packet transmission "predecessor"

For a packet to "predecessor" fields are used corresponding packet_info structure for Queuing packets. For this purpose, the structure of the descriptor has a field packets_list, which stores the address of the first patterns packet_info in the queue (the first element of the queue).

The "predecessor" is checked the field stop structure descriptor. If it is 1 (installed), then this means that this structure descriptor proceeds from the state of "busy" status to "free" and therefore cannot be used as a "precursor", which will transmit the processed packet. In this case, you must perform a new search predecessor by browse the list of predecessors, taking the top of the list field pre-decessor_value current "predecessor".

To send a package (the package list in the General case) "predecessor" software flow records using AtomicExchange flag Successor_ref in the field packets_list "predecessor". The thread then creates a new queue from your package (list of packages) and the queue stored in packets_list "predecessor".

If the software thread discovers that packets_list "predecessor" flag has been set Predecessor_ref, i.e. the "predecessor" in this IOM is NT checks his field packets_list for new packages a software thread considers it to be in a state of transition from "busy" to "free".

If the flag Predecessor_ref has not been installed, a software thread writes the address of the first patterns packets_info formed a queue in packets_list "predecessor"using AtomicExchange. If at this point, the flag Prede-cessor_ref was already installed (analyzed value packets_list that was returned by the function AtomicExchange), a software thread believes that "predecessor" in the transition state.

If the flag has not been set, then this is an indication that the package (package list) successfully passed the "predecessor" and the program flow can proceed to check their fields packets_list to receive new packets for transmission on the output of the system from their "followers".

If software flow could not add package (list of packages) in the queue (the"predecessor" in the transition state), he writes in the box to stop the "predecessor" is 1 and searches for the "predecessor"using field predecessor_value current "predecessor" pred.

Scheme transfer list of packets processed by the software thread to its current "predecessor" is shown in figure 4.

Receiving packets from the "followers" for transmission to the output system

The stream using AtomicAdd function sets a flag Predecessor_ref in current_descriptor.packets_list.

If the value returned by the function AtomicAdd, the quality is TBE address of the beginning of the queue (first element) recorded a value of 0, the queue is empty, and the structure current_descriptor is now in the "transitional" state ("followers" on this signal set by the AtomicAdd function flag Prede-cessor_ref).

If the AtomicAdd function returned a value, in which the flag has been set Successor_ref, at the moment of the "follower" adds packets to the queue current_descriptor. Accordingly, a "follower" find the flag Predeces-sor_ref when to add a new list of packages. Thus, a "follower" will determine that the structure current_descriptor is in a transitional state, and will look for another "predecessor".

If the flag Successor_ref was not set and the queue is not empty, the program stream from the returned values retrieves the address of the first element pack-et_info queue, and then writes (by calling a function AtomicExchange) 0 packet_list descriptor.

If there is a "follower" has started adding their jobs, then the returned value of the function AtomicExchange a flag will be set Successor_ref. In this case, it is also considered that current_descriptor moved in the transition state.

If the flag Successor_ref has not been installed, a software thread performed the validation queue and can transfer the received packet to the output of the system, using the "predecessor" (as described above)or, in the absence of "predecessor", independently of parade the packets to appropriate output network interfaces (using software OS interface to send packets).

If the check batch queue structure current_descriptor moved in the transition state, a software thread puts links predeces-sor_state and state in the status request "exclusive use" (using the function call RequestToDisableSharedMode for each of them), after which the software thread may proceed to select the next packet for processing, using another free structure descriptor from the set.

During the transition links predecessor_state mode modification by releasing all references are checked box predecessor_value: if its value is not zero, then released it (predecessor_value) references predecessor_state and state.

At the transition of the link state in the editing mode by releasing all references, the following actions occur in the structure descriptor:

- the function is executed EnableSharedMode for links predecessor_state;

- record 0 in packets_list;

- writes the value 0 in the field stop;

- writes the value 1 into the free - sign that the structure of the descriptor in the state "free".

After processing package (current_descriptor in a transitional state), the thread executes a search descriptor in the free state by analyzing the field free all descriptors from a set of program flow.

The sequence of checking the queue of packets received from "followers", which program stream must pass to output the system, shown in figure 5.

Search for "predecessor" using the predecessor value

Program stream receives the address of the next "predecessor" (pred.pdecessor_value) his predecessor (pred). If the address is not zero, and the following conditions: the value pred.stop not equal to 1 and the program stream successfully received links pred.predecessor_state and pred.state, this structure descriptor becomes the new "predecessor" for the thread and the search stops.

If the condition is not met, then the next iteration of the search, which performs a similar action to the structure whose address recorded in the field predecessor_value just proven structure descriptor. The number of search iterations (size chain "predecessors") is limited by the number of threads is reduced PA 1 (the current thread).

After searching previous "predecessor" released: unlocked his links predecessor_state and state, respectively.

If you search for "predecessor" is not found, the program stream will forward the packets to appropriate output network interfaces.

The search schema "predecessor" using field predecessor_value running program flow in the organization sending the processed packet to the output of the system shown in Fig.6.

Search patterns descriptor, which is in the state "free"

After the transition current_escriptor in the transition state (program stream has completed all processing and packet transmission, handled in-house or acquired from "followers"), program stream searches free patterns descriptor that will be used for processing of the new package.

The search is performed by checking the fields free from all structures descriptor in the set of program flow. Because the number of structures in the set corresponds to the number of software threads in the system and the current software thread does not block any descriptor structures in other threads, at least one structure descriptor is in the status "free". This statement follows from the above algorithms search "predecessor" and the reference counting mechanism, below.

To implement the proposed method uses a number of auxiliary procedures described below.

The reference counting mechanism on the object

The life cycle of any object in the system (as the object may, for example, be considered a variable in RAM)that uses a reference counting mechanism (hereinafter - the mechanism), begins with initialization (data mechanism, including as part of the object). At this stage access to the object has only its Creator (or owner, which can perform functions and software modules), other software elements of the system (functions, etc the software modules) do not have any information about the existence of the object (object "not published"). After initialization, the owner takes the necessary steps to "publish" object - from this moment on, other software elements of the system may attempt to gain access to its contents.

To allow access to the object owner calls the function Enable-SharedMode, and the object enters the state of sharing. Now the software elements of the system wishing to access the object, must obtain a reference using the function GetReference the mechanism under consideration. In the case of successful receipt of link it is guaranteed that the object will not go into a state of modification until the liberation of the links. Thus, in this state, the so-called guaranteed access to the object read-only (read-only). At the end of the use of the software elements of the system should call the function ReleaseReference mechanism to release the link.

To exit mode, sharing one of the software elements of the system should call the function RequestToDisableSharedMode, as a result of which the object enters the state of waiting the end of the sharing. At this stage, getting new links impossible - i.e. GetReference will fail.

After the release of the last reference, the object will move in condition exclusive access when it released the latest link software is an element of the system can modify the object. To go back to sharing software element of the system must re-call the function EnableSharedMode.

To destroy the object must be eliminated "publication" of the object, resulting in it is guaranteed that none of the software element of the system will now not be able to access the object to get a reference. After this function is called RequestToDisableSharedMode. Subsequently, the software element of the system, which freed the last link, you may delete the object.

The data necessary for the operation of the reference counting mechanism, presented in the form of a structure reference.

Figure 7 shows the life cycle of the facility, access to which is controlled by a reference counting mechanism.

Implementation of reference counting mechanism

The above reference counting mechanism can be implemented using the above functions AtomicExchange and AtomicAdd.

To implement the above mechanism is needed is a data structure consisting of the following fields:

a variable reference, which combines the reference count to the object to obtain a reference (function GetReference) flag Re-quest_To_Release, which, if it is installed, means that you may not obtain new references to the object. The step counter of references (links) is a constant Reference;

variable release_ref, which is counter performed operas the Nations release links used to transition to the regime of exclusive access to the object;

- release_target representing the number of links that must be released to move to the state exclusive access.

The initialization of an object

In reference flag is set Request_To_Release. Thus, the object is put in mode exclusive access and can be "published".

The transition to the state sharing (EnableSharedMode)

Variables release_ref and release_target is assigned the value 0. Atomically sets the reference count to the object is equal to 0, and resets the flag Re-quest_To_Release, allowing the generation of links.

Getting links

To obtain a reference count is incremented reference unit Reference and check its previous value. If the reference has not been set flag Request_To_Release, the link is successfully received and the object is in a state sharing. If the flag was set, then the link is not obtained and the object access is not permitted.

On Fig shows the algorithm of the function GetReference for reference counting mechanism.

A transition to a state modification

In reference flag is set Request_To_Release. If the counter value is 0, then all references have already been released (or not received), and the object status for exclusive access.

If not all references were to release is found by the time flag is set to Re-quest_To_Release, in release_target recorded the previous value of the reference counter that indicates the number of non-exempt reference. Then release ref incremented Reference, and the result of this operation, the previous value release_ref compared with release_target. If the values are equal, then this means that since the installation of the flag Request_To_Release was made to release all references and, accordingly, the object went into a state of exclusive access.

Figure 9 shows the algorithm of the function RequestToDisableSharedMode for reference counting mechanism.

The release links

The reference counter is decremented by one Reference. Then, if the flag has been set Request_To_Release, count is incremented release_ref and compares the previous value (which is returned by function AtomicAdd) release_target. In the case of coincidence of the values of the object's state is exclusive access (was released last reference).

Figure 10 shows the algorithm of the function ReleaseReference for reference counting mechanism.

All procedures and algorithms can be implemented in middleware specialist programming (programmer) on the basis of known functions.

The proposed method allows to avoid delays in the work of the processor units due to eliminating the need to wait for completion of processing of individual packets in other processors the x blocks.

It should be noted that other variants of the proposed method than that described above, and dependent on personal preference when programming individual actions and functions.

Sources of information

1. U.S. patent No. 6434145, Processing of network data by parallel processing channels, the priority of 22.06.1998,, MKI H04L 12/56.

2. Application U.S. No. 09/797197, Methods and systems for the serialization order of information in a network processing environment, publication No. 20020107903, priority from 01.03.2001,, MKI G06F 15/16.

The method of parallel processing ordered data flow in the computer system, and the system contains
the first unit, providing
receiving input data stream (from the external network connections);
the separation of input data streams;
supply each part of each input data stream attributes;
the transfer of parts of each input data stream to the processor blocks to treatment;
the set of processor units, each of which is composed of a processor and means for storing the processed parts of the input data stream and provides
processing according to the specified algorithm parts of the input data streams;
transfer of processed parts of the input data streams to the corresponding output data streams;
storage of the processed parts of the input data stream until conditions make these the t into a corresponding output data stream;
transfer of processed parts of the input data streams to other processor units;
receiving the processed parts of the input data streams of the other processor units;
search for specific items in the attributes of the parts of the input data stream;
the first block is associated with a set of processor units,
the method lies in the fact that
receive input data streams from the network connections in the first block;
transmit the input data streams for processing in the processor blocks, and each part of each input data stream is supplied attributes, which includes the ID of the input stream;
the ID of the provisions of this section in the input stream;
process input data streams processor blocks to obtain the corresponding parts of the output data streams;
provide the order of the parts of the output data streams of the processor units, which corresponds to the order of the parts of the input data stream, and to provide order
conduct the search processor unit, which handles a certain part of the input data stream being in a first stream before the part has already been processed in the given processor unit, and
if after searching such processor units found bore the nly, then choose the processing unit, which handles a certain part of the input data stream, located closest to the treated portion of a particular input stream;
transmit the processed part of a particular input data stream of the considered processor unit in the selected processing unit, and, if any, previously received from the other processor units processed part of the input data stream;
if after searching such processor units is not found, then
transmit the processed part of the input data stream into a corresponding output data stream, in which the order of the parts corresponds to the order of parts in the corresponding input stream according to the previously received from the other processor units of the treated parts of the input data stream.



 

Same patents:

FIELD: information technology.

SUBSTANCE: method involves determining the location of one or more multimedia components, outputs of which are connected to the input of a receiver; scanning multimedia components for sampling availability by checking inputs of multimedia components, if sampling is unavailable; if sampling is unavailable at inputs, checking the media source providing the multimedia components for sampling; if sampling is unavailable at the media source, executing a file ending function or declaring an error status; if sampling is available, transmitting the sampling to the next multimedia component from the multimedia components.

EFFECT: broader functional capabilities.

3 cl, 6 dwg

FIELD: information technology.

SUBSTANCE: method includes the following steps: a first client sends to a relay server and a P2P sever a request to set up a first connection; a second client sends to the relay server and the P2P server a request to set up a second connection; after successful setup of the first relay connection between the first client and the relay sever and the second relay connection between the second client and the relay server, the first and second clients transmit video data through the relay server; after successful setup of the first P2P connection between the first client and the P2P server and the second P2P connection between the second client and the P2P server, the first and second clients temporarily stop transmitting video data through the relay server; the first and second clients transmit video data in P2P mode.

EFFECT: solving such problems as low speed of entering a system, low connection speed and even connection failure, which arise when a client is using a P2P mode, and improving user perception.

15 cl, 4 dwg

FIELD: radio engineering, communication.

SUBSTANCE: method includes steps of: connecting to the device manufacturer through a network communication channel to place an order; downloading an application from a server; launching the application on a local device, where the application is intended to automatically collect settings; adding a unique identifier to the collected data and saving the collected data in a file on a local storage, where the file on the local storage is encrypted and sent to the device manufacturer for use in assembling and configuring a pre-configured device ordered by the user, wherein the application displays on the device request screens which collect user data which include at least a profile and user passwords, agreement with terms of the end user license agreement (EULA), installed applications, update settings, device graphic user interface (GUI) appearance preferences.

EFFECT: customising a user device when ordering a new device from a manufacturer.

18 cl, 5 dwg

FIELD: information technology.

SUBSTANCE: system for scheduling data selection for transmission in a data network includes a plurality of daughter elements as well as a credit allocator and a transmission selector. The transmission selector is communicatively connected to the credit allocator, wherein each credit can be used to transmit data. The credit allocator operates to provide credits to one of allowable daughter elements and daughter elements having a negative credit counter. The credit allocator also operates to maintain a credit balance which represents the available total volume of unallocated credits, and subtracts the provided credits from the credit balance. The transmission selector operates to select one allowable and operable daughter element for extraction from a queue and add credits to the credit balance in accordance with the amount of data selected for extraction from the queue.

EFFECT: improved queuing using weight coefficients based on reverse management of credits which can be used in case of traffic with controlled exchange rate.

19 cl, 13 dwg

FIELD: information technology.

SUBSTANCE: system and method are disclosed, according to which a media processor determines functions for creating and supporting a topology from data processing functions through the topology. The system has a control level which includes a topology generating element for generating a topology that describes a set of input multimedia streams, one or more input multimedia stream sources, a sequence of operations performed over multimedia data, and a set of output multimedia streams, and a media processor for controlling transmission of multimedia data as described in the topology, and controlling execution of the sequence of multimedia operations over the multimedia data to create a set of output multimedia streams. A core level includes input multimedia streams, input multimedia stream sources, one or more converters for handling multimedia data, stream receivers and media receivers for providing a set of output multimedia streams.

EFFECT: efficient processing of multimedia streams.

12 cl, 6 dwg

Radio system // 2494540

FIELD: radio engineering, communication.

SUBSTANCE: system includes a master radio object (RO) which transmits radio signals with given individual attributes, and ordered, numbered slave RO receiving said signals. The slave RO record the time of receiving radio signals from the master RO and are configured to transmit radio signals with individual attributes, set separately for each slave RO, in a set order through given time delays read from the time of receiving the radio signals. The receiving RO is configured to receive radio signals of the master and slave RO and determine coordinates of the phase centre of its antenna from given coordinates of phase centres of antennae of the master and slave RO and time of receiving radio signals taking into account total delay time. The system does not require overall synchronisation of the plurality of RO transmitting and receiving radio signals, enables high-speed determination of coordinates with a large number of objects and can be implemented using modern hardware components and microprocessor technology.

EFFECT: high efficiency and simplification of corresponding radio systems.

1 dwg

FIELD: information technology.

SUBSTANCE: when an HDMI source 71 performs bidirectional IP communication with an HDMI sink 72 using a consumer electronics control (CEC) line 84 and a signal line 141, a switching control unit 121 controls a switch 133 so that, when data is transmitted, the switch selects a constituent signal forming a differential signal from a converting unit 133 and, when data is transmitted, the switch selects a constituent signal forming a differential signal from a receiver 82. When bidirectional communication is performed using only the CEC line 84, the switching control unit 121 controls the switch 133 so that the CEC signal from the HDMI source 71 or the receiver 82 is selected using the switch 133.

EFFECT: unidirectional high-speed transmission of pixel data of an uncompressed image, such as High Definition Multimedia Interface (HDMI), to provide high-speed bidirectional communication while supporting compatibility.

18 cl, 40 dwg

FIELD: radio engineering, communication.

SUBSTANCE: wireless communication device, access terminal and access point perform administration of allocation of a transmission resource associated with a forward and return link, which is allocated to a transmitting object for a certain period of time and each time the transmitting object does not transmit real data packets and needs to store allocation of the selected resource, a pause indication is provided.

EFFECT: providing such a pause indication that an access point and an access terminal do not interpret said pause in transmission as an indication that allocated resources are not needed, or as an indication that allocated resources are no longer available.

9 cl, 5 dwg

FIELD: radio engineering, communication.

SUBSTANCE: method involves: determining whether a type of a current procedure allows a serving gateway (SGW) to change a tunnel endpoint identifier (TEID) and/or an internet protocol (IP) address (S110); and sending a modify bearer request message to the SGW, wherein the modify bearer request message is used for notifying the SGW on whether the SGW is allowed to change the TEID and/or the IP address (S120).

EFFECT: preventing loss of service data packets of a user or service interruption caused by that the SGW modifies the TEID or the IP address.

22 cl, 12 dwg

FIELD: information technology.

SUBSTANCE: chip components can share data using a bus system or a fixed connection system. Said technical result is achieved due to that a control unit for traffic from a source node can be used on an input line on a high-speed virtual channel of packet switched network. The control unit for traffic transmitted over a high-speed virtual channel can be transmitted to a recipient node through an output line. The control unit for traffic transmitted over a high-speed virtual channel can also be directly directed into the output line by a distribution switch.

EFFECT: providing more efficient utilisation of space on a chip and reducing the number of fixed connections between two components of a single-chip microprocessor, such as a processor, cache memory, data register etc.

20 cl, 14 dwg

FIELD: information technology.

SUBSTANCE: method for accelerated web page delivery involves running a web browser on a remote, the web browser being used by a user through streaming interactive video, providing the user with access to the web page through the web browser and displaying a web page on a client device in response to a user request.

EFFECT: shorter web page response latency.

10 cl, 40 dwg

FIELD: information technology.

SUBSTANCE: disclosed are methods which enable users to remotely collaborate on documents using corresponding browsers. These methods involve sending representations of fragments of the document to browsers and associating fragments of the document with specific users. Browsers can receive representations of commands provided by users and can determine whether to execute the commands on the browser. The methods can also include receiving from the browsers revisions of fragments of the document and storing said fragments of the document in storage regions adapted to store content that was altered relatively recently.

EFFECT: high efficiency of processing documents.

16 cl, 9 dwg

FIELD: information technology.

SUBSTANCE: apparatus comprises a whiteboard manager component which may comprise an image quantiser module to receive an image of a writing surface with pen strokes and quantise each pixel of the image into a predetermined number of colours, an attribute extractor module communicatively connected to the image quantiser module, the attribute extractor module configured to extract stroke attribute information for the pen strokes from the quantised pixels, and a whiteboard interface module communicatively connected to the attribute extractor module, the whiteboard interface module configured to send the stroke attribute information to a meeting console for rendering as digital pen strokes on a digital writing surface.

EFFECT: easy collaboration of users on a whiteboard for a multimedia conference event, avoiding the need to modify pens or the whiteboard, low consumption of communication frequency resources.

19 cl, 6 dwg

FIELD: information technology.

SUBSTANCE: collaboration session with a client, having a client media platform specific for that client, is provided. The collaboration session includes a first communication channel in which multimedia data for a media component are transmitted, and a second communication channel in which a user interface component is transmitted to the client. Server commands for reproducing multimedia data corresponding to a server media platform specific for the server are received from the client. The server commands for reproducing multimedia data corresponding to a server media platform specific for the server are converted to platform-common commands for reproducing multimedia data for transmission to the client. The platform-common commands for reproducing multimedia data are transmitted to the client, wherein the client converts the platform-common commands for reproducing multimedia data to client commands for reproducing multimedia data corresponding to a media platform specific for that client.

EFFECT: high efficiency of data communication between a server and a client.

19 cl, 6 dwg

FIELD: information technology.

SUBSTANCE: disclosed is a method of providing multi-client collaboration on structured data elements which comprises steps of: receiving at least one structured data element within a spreadsheet published at least in part in a first client system; defining a corresponding unique identifier; sending said at least one structured data element and said corresponding unique identifier to a master table; entering said at least one structured data element into the master table; calculating a value of said at least one structured data element; distributing said at least one structured data element and calculated value from the master table to a second client system and distributing the calculated value from the master table to the first client system; receiving a request to edit the master table; in response to receiving a request to edit the master table, determining whether the user making said request has privileges to edit the master table; if so, said changes are applied to the master table scheme and said changes to the master table scheme are synchronised with the first and second client systems.

EFFECT: providing multi-client collaboration on structured data elements.

12 cl, 7 dwg

FIELD: information technology.

SUBSTANCE: online video game or application hosting system has a hosting service, having one or more servers performing one or more video game or application twitches to provide one or more streams of compressed interactive streaming video with short latency, transmitted over a network which includes public network components to at least one client apparatus, situated away from at least one of the servers. The system performs operations for receiving and providing control signals to the servers, performing one or more video game or application twitches on the servers, providing streams of compressed interactive streaming video with short latency and decompressing the compressed interactive streaming video with short latency. Said operations are performed with such a short latency that a user interacting with at least one of the one or more video game or application twitches has the perception that the video game or application twitch instantly responds to control signals.

EFFECT: reproducing compressed interactive streaming video with short latency regardless of the power of the client apparatus.

25 cl, 40 dwg

FIELD: information technology.

SUBSTANCE: system includes: an information service configured to provide information distribution services through an information distribution network; user devices that device users use to communicate with said information service for receiving said information distribution services, a subset of said device users forming a social network with corresponding user devices; and a transport structure that communicates with network entities of the information distribution network, said transport structure collecting metadata for providing selected information from said information service to targeted device users. The metadata include social network metadata containing a user profile and a device profile for each device user from said subset of device users.

EFFECT: high efficiency of distributing information owing to analysis of metadata of a social network user, a user device and an advertiser.

15 cl, 14 dwg

FIELD: information technologies.

SUBSTANCE: device includes user devices, a transport device and a transport server. User devices are used to apply for communication with an information service in order to receive services of information messages transmission. Transport devices communicate with user devices along an electronic network for collection of various determined types of metadata, which are then used by the information service to provide the selected information to target users of devices. The transport server coordinates functions of transport devices, providing commands of tasks and navigations for efficient operation of transport devices.

EFFECT: higher efficiency of information distribution due to analysis of user metadata and information distributors.

13 cl, 15 dwg

FIELD: information technologies.

SUBSTANCE: in the method to implement communications and virtual journeys they receive user data, perform identification, personification and formatting of data, data is placed on named and identified sections of a machine-readable medium, an interactive system of data queries is formed, data is edited and/or formatted, and also transformed within the system with the help of appropriate software. The method also includes a stage of user/users requesting video-, audio-, photo- and text data, including serial activation of data of software responsible for graphic display of sections of a geographic map and/or sections of a graphical image and/or symbols of a list on a monitor/a display and issue of requested personified and/or reference and/or information data, corresponding to this activated data of software, to the monitor/display and/or devices of user finding with their subsequent preview, listening, reading.

EFFECT: expansion of functional capabilities due to implementation of editing and editing of data, due to serial issue of data by means of serial activation of sections of a graphic image or symbols on an interactive display.

FIELD: information technologies.

SUBSTANCE: method includes calculation of throughput capacity of information transfer for a received user identifier in accordance with the user information corresponding to the received user identifier; saving of user identifiers, for which values of throughput capacity of transfer exceed the specified threshold value, in the initial user distribution queue; and transfer of transmitted information to a client, the user identifier of which is saved in the initial user distribution queue.

EFFECT: reduction of costs for information transfer among users.

15 cl, 4 dwg

FIELD: electric engineering.

SUBSTANCE: method includes estimation of quality coefficients of electric energy in electric energy system, determining degree of matching of these coefficients to normal values, forming of control signal for correcting devices and predicting electric energy characteristics expected after effect of these devices. On basis of analysis of predicted characteristics quality coefficients are newly estimated and if necessary control signals for correction devices are formed. Estimation of not only voltage and frequency is provided, but also current. Whole cycle is repeated for each node of electric energy system.

EFFECT: higher efficiency.

1 dwg

Up!