Patent Description:
New generations of autonomous embedded systems are required to perform more and faster on-board data processing. They are autonomous in the sense that they may operate independently and do not require for example external communications in order to function. They are typically "edge" devices. Sensors, embedded processors, and hardware in general have hugely evolved in the last decade, equipping embedded systems with large numbers of sensors that will produce data at rates that have not been seen before while simultaneously having computing power capable of large data processing. However, embedded software engineering has remained virtually unchanged for the last two decades, making the development of advanced applications extremely cumbersome, error-prone, suboptimal and usually delay incurring. In this disclosure, a novel approach to parallel data processing is presented that is based on state-of-the-art algorithmic trading software techniques, which is a field that underwent a similar challenge, although at a different scale, in the early <NUM>. The approach presented here optimizes processing resources, simplifies development and makes applications much more reliable, therefore somewhat reshaping the paradigm of embedded software engineering. Benchmarks are presented for two rather different embedded application scenarios. One is for space on-board flight software in a limited computing capability platform, and the other one is for robotics on-board sensor fusion. In this disclosure, we show that the performance and determinism of the applications increase substantially with respect to traditional multi-thread approaches in both scenarios.

Examples of computing platforms in which embodiments of the invention may be implemented include the ODROID-XU4 and other similarly small computers. Other examples are Raspberry Pi4 and the Xilinx ZED-Board (used for testing described below with CAN). A common feature of embedded systems is that they are typically implemented in a single computer and thus it is to be assumed here that a "system" is implemented in a single computer unless otherwise stated.

The LMAX Disruptor is a high-performance concurrency framework based on CAS (Compare And Swap). It has drawn interest from industry due to its efficiency; the LMAX business software using it can, for instance, handle up to six million transactions per second. Further details of the LMAX disruptor can be found for example in <NPL>".

It is common ground that embedded systems have evolved hugely in the last decade. New generations of autonomous embedded systems are required to perform more and faster on-board data processing.

One of the most significant changes is the innovation and use of multicore processors. With a higher density of silicon, these systems offer increased performance per unit area, which is critical to meet the needs of modern avionics systems. Their use comes at a price, as unlike single core systems, they offer neither a deterministic environment nor predictable software execution times.

The slow progress of change in embedded software engineering is particularly relevant in the space sector, since currently available software solutions do not offer a sufficient degree of determinism for multi-core computer applications to meet the minimum requirements of this sector. A software solution providing reliable and efficient data processing to match the increasing sophistication and demands of advanced embedded applications, is therefore highly desirable.

Although embodiments of the present invention are generally applicable to all embedded systems, the specific fields where tests were performed are robotics and space. Hence, the specific discussion about the state of the art in both fields is included in this introduction.

An object of the invention is therefore the provision of a parallel processing method that overcomes the above limitations.

<NPL>and experimental evaluation of C++ multithreaded frameworks as part of a project where real time monitoring of a power generator was required. An LMAX disruptor was used in which a fixed number of slots in the C++ array were pre-allocated and a bit-wise algorithm was deployed to re-use ring buffer slots.

<NPL>, presents a study of the main principles and theories of Disruptor and applies the process algebra CSP (Communicating Sequential Process) to model it.

Additional background information is in<NPL>; and stackoverflow. com/questions which discuss cloning of objects in an LMAX Disruptor.

The embodiments described below are not limited to implementations which meet this object or solve any or all of the disadvantages of the known approaches described above, and some embodiments may meet other objects or solve other problems.

This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to determine the scope of the claimed subject matter; variants and alternative features which facilitate the working of the invention and/or serve to achieve a substantially similar technical effect should be considered as falling into the scope of the invention disclosed herein.

Some embodiments of the invention provide systems and methods for lock-free parallel data processing adapted for use with embedded systems employing a smart pointer-based data management and recycling system and circular batching queue.

In one aspect there is provided in the following a method of parallel data processing in an autonomous embedded system. The system may operate in the framework of an LMAX disruptor referred to further below. The method comprises: receiving a call to publish a data object, for example invoking the method "publish" for a data object. The data object is then cloned and placed it into a pre-allocated space in memory. The cloned data object or a pointer to the data object is placed into a batching queue. The cloned data object is delivered to one or more subscribers. The pre-allocated memory space may then be released.

As a result of the pre-allocation of memory space the normal memory management of LMAX is not required. In the original JAVA implementation of LMAX, Java memory management was relied on. Code had to be manually crafted to work with no memory allocations by the Java Virtual Machine (which eventually made use of the operating system allocations). In the case of C++ implementation of LMAX according to embodiments of this invention, there is an implicit dependency in the operating system to perform memory allocations.

Embodiments of the invention may be realised using C++<NUM> and later versions. Notably current implementations of LMAX do not clone data. Embodiments of the invention may enforce clones in order to ensure memory allocations from the operating system in any scenario. This is a compromise that has been shown to have advantages as the following explanation will show. In general the use of clones may be considered to reduce performance. Further, no memory allocations lead to a high level of safety and determinism for critical applications.

It will be appreciated that embodiments of the invention may be implemented in embedded systems where data is published to subscribers. The data object may comprise sensor data, event data, tasks, bindings, or any other data that may be subscribed to. Subscribers may be objects in the embedded system which may then process the data, for example for use in navigation in an autonomous vehicle, or export it, for example to be stored externally. Subscribers are also referred to here as "consumers". The publication may be from multiple producers to a single subscriber, i.e. parallel-in, or from one producer to multiple subscribers, i.e. parallel out.

Some embodiments of the invention can handle tasks via the eventloop, as described further here, which makes it not only a publish-subscriber mechanism, but a scheduling system as well.

Embodiments of the invention may also be used to publish bindings, being direct connections (or hooks) between a middleware, such as ROS or CAN and the eventloop. The novelty here is that these hooks may be running on their own thread each and are acting as producer to the eventloop.

The data is published asynchronously. In other words the publishing of the data may be out of sync with the receipt of calls to publish the data.

There is also provided here a computing system comprising one or more processors and memory and being configured to implement any of the methods described here, to operate autonomously and to be embedded in an autonomous device such as but not limited to a robot or satellite.

Embodiments of the invention may be implemented in existing computers and therefore another aspect provides instructions for a computer, for example on a non-transitory or transitory computer readable medium, comprising instructions which when implemented in a computer cause the computer to operate any of the methods described here.

The invention will be better understood with the aid of the description of embodiments given by way of example and illustrated by the figures, in which:.

Embodiments of the present invention are described below by way of example only. These examples represent the best mode of putting the invention into practice that are currently known to the Applicant although they are not the only ways in which this could be achieved. The description sets forth the functions of the example and the sequence of steps or operations for constructing and operating the example. However, the same or equivalent functions and sequences may be accomplished by different examples.

Nowadays, a robot might be processing data coming from dozens of sensors. Electronics manufacturers offer more and more variety of sensors: Optical sensors, Biosensors, Touch sensors, Image sensors, etc. At the same time, the quality of sensor devices improves too, giving more and better measurements. Furthermore, a robotic system must also process data coming from other sources including: commands, messages from other robots, cloud data processing, etc. In summary, a robotic system can nowadays easily produce thousands of data events per second and the software application will have to process them.

Space applications requiring on-board data processing at high rate is a growing field. On the one hand, constellations of satellites is a growing market. LeoSat, for example, are building their high-throughput satellites that will form a mesh network interconnected through laser links, creating an optical backbone in space which is about <NUM> times faster than terrestrial fiber backbones. OneWeb, will provide a global constellation of low Earth orbit satellites that will provide low latency, high-speed broadband to even the most remote locations on Earth. These both cases, although with different purpose, face similar requirements in terms of data processing: dispatching and processing thousands of Earth requests per second, intensive satellite to satellite communications (coordination, routing, positioning) and high throughput data link to Earth. All these demanding requirements mean development of high rate data processing applications.

In a different field, vision-based navigation, there is also a challenge of data processing combined with computationally heavy algorithms. One example is rendezvous with uncooperative objects in space, e.g., debris removal. Another example of this is autonomous pinpoint planetary landing, where the number of sensors and the complexity of the Guidance Navigation and Control (GNC) algorithms make this discipline still one of the biggest challenges in space. One common element to these two use cases, is a well-known fact in control engineering: for optimal control algorithms, the higher the rate of sensor data, the better is the performance of the algorithm.

In the previous two subsections, we showed that the amount of data going through an embedded system has increased substantially in the past few years. On the other hand, we have presented two very different use cases that show that this trend is common ground in embedded systems.

There is another important factor, which is the evolution of embedded computers. As the computational capabilities of embedded processor increase, and the data processing need grows, some parallel processing limitation might appear as the well-known Amdahl's Law. In computer architecture, Amdahl's law (or Amdahl's argument, <FIG>) is a formula which gives the theoretical speedup in latency of the execution of a task at fixed workload that can be expected of a system whose resources are improved. If not addressed properly, this situation can become a bottleneck for future embedded applications.

This parallel data processing problem has been around a long time and has been successfully solved in other sectors like financial trading. In general, the use of lock-free programming techniques have largely improved performance and determinism in parallel data processing applications. In this disclosure, a novel solution is presented that accelerates parallel data processing applications by means of applying some of these lock-free programming techniques developed in the financial trading sector. The solution has application in space and robotics applications to produce data processing rates that are substantially faster than traditional parallel processing approaches, as well as other applications.

Based on this pattern and combining it with the new smart pointers in C++<NUM> and wrapping it within a publisher subscriber pattern, an aspect of the present invention provides a simple API (application programming interface), miniaturization of the LMAX disruptor for embedded systems. The functionality of the disruptor pattern is described here in relation to two main approaches. The term "smart pointer" is used here to refer to a pointer used to make sure that an object is deleted if it is no longer used (referenced), as known for example in C++<NUM>.

The first approach is the sensor multiplexer as shown in <FIG>, which is a single producer, multiple consumer solution. Consumers are also referred to here as "subscribers". The term "producer" is used here to refer to the source of the data which might be for example a sensor and is not necessarily part of a system according to embodiments of the invention. The data is published by a publisher and hence the publisher may receive a call to publish the data, typically in the form of a data object, from a producer. Alternatively a single producer/publisher object may be provided, in other words the publisher may be considered to be a producer.

The second approach is an event loop (<FIG>) loosely based on this development for financial systems, the event loop presented here is lock-free, high performance and with a degree of determinism that has not been seen before in embedded systems. An event loop is a programming construct or design pattern well known to those in the art of computer science. In <FIG> it can be seen that there are multiple producers but possibly only one subscriber. The term "event loop" is used here according to the definition in NodeJS programming language, found for example at https://nodejs. dev/learn/the-nodejs-event-loop, which is the most common definition. It means that data arrives from multiple sources in parallel in a multi-threaded manner, but data is consumed in a single-threaded manner, without new consumer workers being created or spawned.

In both approaches data is processed in parallel, either incoming in parallel or outgoing in parallel.

Although there are two separate testing scenarios, they both share some common design, these are the specific features:.

The following two subsections show the specific details for spacecraft and robotic system experiments.

The robotic testbed was based in the Robot Operating System (ROS). The ROS is by far the most used software development framework for robotics applications. It is also clearly dominant in aerospace, and self-driving cars. ROS was originally built for academia and its purpose was to accelerate the development of prototypes for robotic research. However, requirements like performance and reliability were not taken into account when designing this framework, which is why ROS really struggles with fast data processing. ROS offers two ways of delivering messages or sensor data to the application:.

The most common one is the single thread spinner. Here, ROS delivers the messages sequentially to the application. It is similar to a simple event loop.

The second way to do that is by using the async multithread spinner. In this case, there is no event loop and messages are delivered concurrently to the application.

Applications using this approach must have some thread contention code in order to function correctly.

In this disclosure we present a third alternative kind of parallel data processing. In this case we combine the multithread implementation of ROS with a lock-free event-loop as described in the previous section. This implementation is very well suited for situations like high frequency sensor fusion and it should enhance the performance of ROS substantially.

A simple benchmark test was developed. It consists of a set of eight sensor providers in the form of publishers. In the client side, we subscribe to these eight sources of data and do some simple data processing consisting of fusion of the data in a JSON object and save it to file.

The results show that by combining ROS with an eventloop as described further here, for example with reference to <FIG>, robotic applications run faster and more stable than without our solution. Sensor fusion with ROS and our solution can be done with a degree of reliability and performance that otherwise has not been seen before with ROS.

Embodiments of the invention are not limited to the use of event loops and may also be used for data multiplexing as described further here.

The application for the single-threaded solution is represented in <FIG>.

In the subscription rate chart, as shown in <FIG>, it can be seen that the single thread approach is unable to keep up with the required rate of data processing. This means that we are losing hundreds of precious sensor data events every second. In the subscription time chart, as shown in <FIG>, it can be seen that each subscriber takes very little time to process the event. This is mainly because no concurrency contention code is needed with the single-thread approach. The CPU consumption, as shown in <FIG>, is quite low and so is the memory usage, as shown in <FIG>. This is a very well-known sub-optimal performance scenario: there is plenty of CPU to use, and yet the system is unable to cope with the load of data. In this case, the issue comes from ROS single thread spinning implementation, which is far from optimal.

Let us now continue with the traditional multi-thread scenario, also shown in <FIG>. In the subscription rate chart, shown in <FIG>, we see that this solution is also unable to cope with the high frequency data publishing. Again, hundreds of events are lost every second without us knowing as this is kept internally to ROS. More importantly, in the subscription time, as shown in <FIG>, the time taken is one order of magnitude bigger than the single thread approach and with a large standard deviation, which is a well-known issue in highly concurrent applications. CPU consumption, as shown in <FIG>, is higher than the single thread approach, which is expected in a multi-thread scenario. Memory consumption, as shown in <FIG>, is the highest of all approaches.

Finally, let us look at the results of the solution according to some embodiments of the present invention using an event loop, for example as shown in <FIG>. We see that our fast performance event loop copes comfortably with the publishing data rate, as shown in <FIG>, and therefore, no messages are lost in the application. In the subscription time <FIG> it can be seen that it is very similar to the one in the single thread. This is due to the fact that with this event loop applications do not need any thread contention code either. CPU consumption <FIG> is slightly higher than that of the multi-threaded approach. The reason for that is that our solution spends more time processing data than any other approach, while the multi-thread approach spends a big portion of the time doing context switches. RAM <FIG> is higher than the other solutions, but because we use a deterministic data allocation procedure, it remains constant throughout all different sensor data rates.

The base application is quite like the one presented above for the robotics test bed. In this case, however, the data was received in a mix of SDO (Service Data Object), SDO blocks and PDO (Process Data Object) CAN (controller area network) open messages.

The testing of this solution was performed in two different environments. First in Zybo boards with Petalinux installed, and secondly in Zedboard with Xillinux installed.

The results presented here are for the Petalinux setup which performs substantially better than Xilinux. The reason behind is that Petalinux is optimised for Zynq boards, while Xilinux is more oriented to development and prototyping.

The sensor fusion benchmark test was performed with the parameters presented in table I below.

Throughput: The main performance criteria is the rate at which data is processed, or throughput. The traditional multithread and the event-loop approaches described here start to diverge when the total rate of all messages reaches <NUM> and when tested at a total of <NUM>, the difference between both approaches is substantial, around <NUM>%, as shown in <FIG>.

One noticeable feature is the small variability over time of eventloop data processing in comparison with the traditional approach, where the application has a big variability.

<FIG> shows the overall performance results with respect to increasing data rate. Firstly, the throughput of the traditional multi-thread application starts to degrade at <NUM> and is really noticeable reaching <NUM>% degradation when close to <NUM> data date. The eventloop disclosed here has a throughput that matches the input data rate, i.e., it is the best possible scenario.

Secondly, the standard deviation of the execution time, shows that the eventloop disclosed here has negligible value, while for the multi-thread application, this value is quite large, making any application quite unpredictable.

Regarding resources utilization, the solution described here needs up to <NUM>% less CPU for data processing. The reason is mainly the cost of context switching in traditional multi-thread applications. As for RAM usage, the solution described here needs more RAM than the alternative application, which is the only trade-off needed when using this software.

In the ROS test, the eventloop described here outperformed ROS alone with an impressive <NUM>% increase. However, here we have seen a <NUM>% increase instead. The reason for this difference is twofold. First, CAN-open is quite a complex protocol with a big overhead of data, which makes it hard to scale given the amount of data exchanged back and forth. Second, this particular Linux distribution, is quite optimal in terms of performance. However, the solution described here achieves the same level of predictability and scalability found in the ROS test. The main difference in the space scenario, is that the solution described here can also reduce the CPU consumption. The reason for that comes from the cost of context switch in this setup limited in resources.

In most use cases, there is a combination of sensors producing data at high rates simultaneously with a slow and heavy data processing block. In a traditional operating system, this is solved by using different threads that deal with different parts of the application, e.g., one thread reads images from camera, another thread does the filtering/processing, etc..

In real-time operating systems, one would use the same sort of concepts: Threads for the various classes of activities and protected synchronization and inter-task communication. The scheduling methods are different though in order to prefer predictability in comparison to average case behaviour. Just a few examples of issues:.

The software application described here provides, in some embodiments, for lock-free parallel data processing in autonomous embedded systems, such as, by way of example, robotic embedded systems or space embedded systems. Other systems which may benefit from the advantages offered by this system, include autonomous drones, vision navigation systems, autonomous rovers, self-driving vehicles, and others.

Advantageously, the software application is not restricted to a particular platform but may be installed in most computers, Linux distributions and in a variety of microcontrollers and embedded systems.

In this application external data, such as, but not limited to, sensor data, are received by a producer and placed, for example by the publisher object, in pre-allocated object instances of a "Smart Object Pool" described further below, thus creating event objects for the received data. In other words, the "Smart Object Pool" comprises memory with pre-allocated spaces, also referred to here as "slots" into which data is placed, for example according to the type of data or to a subscriber. A plurality of data may be received concurrently or, optionally, sequentially in time. It is important that the allocation of the memory space does not change during the processes according to embodiments of the invention. The allocation of space, for example according to data type as described elsewhere here, does not change. Only the occupation of the space may change, for example by being replaced with more recent data, for example after previous data has been used as required.

The producer may be a sensor, but may be any other external provider of data, in particular numerical data.

The Smart Object Pool may be a lock-free memory management system employing smart pointers, but embodiments of the invention are not limited to this.

In some embodiments of the invention, event data are copied by the asynchronous publisher into event objects located in the Smart Object Pool and subsequently moved into a circular lock-free batching queue, for example a ring buffer. By default, a copy operation may be performed, that is the data is duplicated in the batching queue, but this behaviour can be modified in special variants of the invention. Some members of the event object may not be copied, or copied by reference only.

In some embodiments of the present invention, the batching queue could hold events of variable size up to a settable maximum, and the user may be given the flexibility to manage memory allocation.

Event objects may be subsequently transferred from the ring buffer to an asynchronous subscriber, for example by a handler object.

According to some embodiments of the present invention, the asynchronous subscriber or consumer may comprise a "container" or group of listeners and may pass a reference to the object contained in the ring buffer to each registered listener. Once the system has determined that no further transfer of the event data to consumers is required, the asynchronous subscriber may send an appropriate message to the object pool, which frees the event as available for reuse.

In some embodiments of the present invention, the overall functionality of the method can be configured in the following manner:.

In the first configuration, one producer/multiple subscribers, the memory may be pre-allocated to the producer.

In the second configuration, one subscriber/multiple producers, the memory may be allocated such that, for example, different kinds of data are allocated to different memory spaces, or "pools". The size of the pool may be allocated in various ways, for example according to the frequency at which the data is generated by the producer. The frequency may correspond to the frequency of requests to publish data objects. Examples of different kinds of data may include but are not limited to working state, temperature, battery status and others.

In both examples, one smart object pool is provided per producer.

However the memory is allocated, the allocation remains constant during the cycle of publishing data to one or more subscribers.

A system according to some embodiments of the invention may be configured as a sensor multiplexer, in which case a listening thread may be is created for each registered consumer linked to the publisher. The listening threads may pass the event data by reference to its corresponding consumer. Once all consumers have processed the event object, they may be returned to the Smart Object Pool.

A system according to some embodiments of the invention may be configured as a lock-free event loop, in which case the event object may be passed to an event emitter, which invokes the consumer. The event emitter may take the form of an LMAX disruptor configured to work as a multiple producer / single consumer setup. Once the consumer has processed an event object, this event object is returned to the Smart Object Pool.

According to some embodiments of the invention, placing copies as opposed to original event objects into the batching queue for processing and recycling processed event objects in the Smart Object Pool avoids the need to periodically and actively free up memory at high cost to CPU, and prevents memory space from being cluttered with event data, which have been processed and are no longer required, thus rendering the overall system more deterministic.

Employing the Smart Object Pool to for data management has several advantages:.

This efficiency is demonstrated in the increased data processing rate when compared to conventional multi thread or single thread processing systems (<FIG>).

As a further advantage over conventional multi-thread processing methods, some embodiments of the present invention may significantly decrease standard deviation for processing time, for example at least <NUM>- fold or better, as evidenced in the CANopen system for CubeSat (<FIG> and <FIG>).

The improved standard deviation of this method renders it particularly suitable for embedded system with a need for a high degree of reliability, reproducibility and determinism.

A system according to some embodiments of the invention is illustrated in <FIG>. The system comprises an asynchronous publisher <NUM>, a memory pool <NUM>, a ring buffer <NUM> and an asynchronous subscriber <NUM>. The memory pool <NUM> may contain a number of pre-allocated object instances (not shown in <FIG>).

A method according to some embodiments of the invention will now be described with reference to <FIG>. The method may comprise receiving a call at operation <NUM> to publish a data object, such as an event, for example at the asynchronous publisher <NUM>. The call might come from a producer such as a sensor or other device external to the computer implementing the method. The call may identify a memory space that has been pre-allocated to the sensor or a group of sensors producing similar data. The allocation of memory space may be transparent to the producer.

The publisher <NUM> may initiate the copying, or cloning, of the data object and placing it into the pre-allocated space in the memory at operation <NUM>. The data object or, optionally, a pointer to the object, may then be placed into a batching queue, for example the ring buffer <NUM>, at operation <NUM>.

The ring buffer, or ring buffers consumer sequence, may publish the cloned data object, in other words notify subscribers of newly available cloned data. This may take place by delivering the cloned event to one or more subscribers, for example the asynchronous subscriber <NUM>, at operation <NUM>. The subscriber <NUM> may comprise one or more listeners as mentioned above, in which case the subscriber may then invoke all listeners associated to the publisher <NUM>. A decision is made at operation <NUM> whether all listeners have finished processing the data. In the affirmative, i.e. after the subscriber, or all listeners comprised in the subscriber, have finished processing the data as indicated at operation <NUM>, the cloned data object is recycled back to the pool <NUM> at operation <NUM>. In other words part of the memory space previously occupied by the cloned data object is released for the publication of a new data object. However, if the subscriber, or all the listeners comprised in the subscribers, have not finished processing data, as indicated by decision <NUM>, the system waits for all the subscriber, or all the listeners 19a-b comprised in the subscribers to finished processing data, at operation <NUM> before the decision operation <NUM> is repeated.

It is known in the art how to check whether subscribers no longer require a data object. For example, references in code to a pointer to a data object, such as may be generated by subscribers, may be monitored. When no more such references are detected, it may be assumed that the data object is no longer required. This may be achieved using smart pointers as known in C++<NUM> onwards. An important aspect of embodiments of the invention is that when new data is to be published it is not necessary to request a memory space from the operating system, as would normally be required. Because the memory is pre-allocated and the allocation does not change, the memory space is always available for the data. This contributes to the speed of operation of methods according to embodiments of the invention. Asking the operating system for memory is costly in terms of processing power and time, and more importantly it is not a predictable operation and takes an undetermined amount of time.

An example of a container of listeners is two or more listeners that are interested in different parts of a data object. <FIG> shows an example of a single consumer <NUM> in the form of a container comprising two listeners A and B, 19a and 19b. For example, one listener 19a may require only a part of the data comprised in the data object. To take the example of camera image data, one listener 19a may require only intensity, e.g. black and white, data while another 19b may additionally require colour data.

Two embodiments of the system shown in <FIG> are shown in more detail in <FIG> and <FIG>. In these figures like items are indicated with like reference numerals. <FIG> shows a one producer/multiple subscriber <NUM> embodiment, i.e. a multiplexer embodiment, and <FIG> shows a multiple producer/single subscriber 20a, 20b, embodiment, i.e., an event loop embodiment. In each case the data delivery mechanism is shown in more detail.

<FIG> shows, in addition to the features of <FIG>, a consumer sequence barrier <NUM> between the ring buffer <NUM> and multiple consumers <NUM>.

Sequence barriers are part of the LMAX original disruptor pattern. They keep pointers to the next element in the ring buffer: in the case of consumer barrier, it is the pointer to the next data to be processed, in the case of producer barrier (see <FIG>), is the pointer to the next free slot in the buffer.

The smart object pool <NUM> is shown to be divided into separate slots 12a-<NUM>. Notably also in <FIG> the asynchronous publisher <NUM> as shown in <FIG> is replaced by a producer <NUM>. As noted previously the producer and publisher are interchangeable.

In the case of the data multiplexer, one instance of the data multiplexer may be provided for each of different types of data. One data multiplexer may be able to handle one type of data only, hence, only one smart object pool is needed. Smart object pools may also be data type dependent.

The embodiment of <FIG> operates in a similar way to the embodiment of <FIG>. In addition the following operations may take place:.

When the producer <NUM> is invoked, for example via a publish API, to publish certain data, an object memory slot corresponding to the data is requested from the smart object pool <NUM> and a pointer or other identifier of the slot containing the data to be published is returned to the producer <NUM>. The producer <NUM> sends the object address/pointer to the next available sequence in the ring buffer <NUM>. The data itself can then be accessed via the ring buffer <NUM> using the address/pointer.

In this embodiment, the ring buffer <NUM> is connected to a consumer sequence barrier <NUM>. The consumer sequence barrier <NUM> is connected to the consumers <NUM> and the single smart object pool <NUM>. The consumer sequence barrier <NUM> handles/regulates access to the data in the ring buffer <NUM>, for the consumers <NUM>, for example based on policy data associated with specific consumers <NUM>. For example, a consumer A may only access data from slot <NUM> of the ring buffer <NUM>, if a certain policy is satisfied. The barrier <NUM> may have a most recent data policy for the consumers <NUM> so that old events are discarded.

According to some embodiments of the invention, a policy may be that of independent consumer (subscriber) rates, In other words, different consumers may consume data at different rates. Embodiments of the invention may be used to ensure access to the most recent data and that data will be kept in the batching queue until processing by the subscribers is finished.

Supposing that the consumed data was provided from memory slot 12a, when the last consumer has finished processing the data, the memory slot 12a is returned to the smart memory pool, or released to be available for new data. This may be for example by the customers <NUM> notifying the consumer sequence barrier <NUM> and the consumer sequence barrier <NUM> notifying the smart object pool, as indicated in <FIG>.

In the multiple producer 20a, 20b/single customer <NUM> embodiment shown in <FIG>, a producer sequence barrier <NUM> is positioned between the producers 20a, 20b and the ring buffer <NUM> in addition to a consumer sequence barrier <NUM> as shown in <FIG>. Notably also there are multiple smart memory pools <NUM>, <NUM>, one for each producer 20a, 20b, each having pre-allocated slots 12a-g, <NUM> a-g. As shown in <FIG>, the single consumer <NUM> comprises multiple listeners <NUM>, <NUM>. In this embodiment, the subscriber communicates directly with the smart object pools <NUM>, <NUM>, rather than via the consumer sequence barrier <NUM>. Each smart object pool comprises a plurality of object memory slots 12a-g, 13a-g, wherein at least memory slot 12a of the plurality of memory slots 12a-g, 13a-g may comprise a number of pre-allocated object instances. The single consumer is served by a single thread which is constantly running waiting for data to come from the ring buffer.

The operations performed in the system of <FIG> are similar to those performed in the system of <FIG> and are explained in more detail in the flowchart of <FIG>.

<FIG> is a flow diagram illustrating an example data publishing process, according to some embodiments of the present invention, that may be implemented in either of the systems shown in <FIG> and <FIG>.

Referring to <FIG>, in operation <NUM> when a producer <NUM>, 20a,20b, is invoked (for example, via a publish API), to publish data, a request (s) for a memory slot, e.g. 12a, for the data is sent to a smart access pool, e.g. pool <NUM>, or in the case of multiple producers to the pool for that producer. Based on the received request, the smart access pool <NUM> sends the address or a pointer to the appropriate memory slot to the producer.

In operation <NUM>, upon receiving the address/pointer for the memory slot e.g. 12a, from the smart object pool <NUM>, the producer sends the object address to the next available address in the ring buffer as shown in <FIG>. In an alternate embodiment, multiple producers may send the object address to the next available address in the ring buffer via the producer sequence barrier <NUM> as shown in <FIG>.

In operation <NUM>, the consumer sequence barrier <NUM> receives a request from a consumer or multiple consumers to access data in the ring buffer <NUM>. The consumer sequence barrier <NUM> checks the received request (s), against at least one policy associated with the consumer (s) making the request (s). Based the result of the check(s) (operation <NUM>), the consumer sequence barrier <NUM> either allows the consumer (s) to access the one data in the ring buffer <NUM> at operation <NUM> or ends the process by returning a null at operation <NUM>.

In operation <NUM>, the consumer sequence barrier determines if the consumer (s) have processed/accessed all required data from the ring buffer. The determination could be made based on at least one policy associated with the consumer(s). Based on the determination, the consumer sequence barrier <NUM> returns the object memory slot to the one smart object pool at operation <NUM> as shown in <FIG>, or waits for all of the consumer(s) to process/access all the data from the ring buffer (at operation <NUM>. In an alternate embodiment, the consumer sequence barrier may direct the consumer(s), or listeners associated with a consumer to return the object memory slot to the smart object pool (operation <NUM>) (as shown in <FIG>). In the foregoing one memory slot is discussed but it will be appreciated that the same process may be implemented for multiple memory slots. Once the listeners of the consumer are done processing the data, and all consumers are past that point in the ring-buffer, the data memory slot can be released back to the smart object pool.

<FIG> are graphs comparing one thread-safe queues and multiple thread-safe queues with methods according to some embodiments of the invention using an event loop, performed using an Odroid-XU4. The graphs show Odroid memory only CPU usage in <FIG>, Odroid memory only data throughput in <FIG>, Odroid ROS CPU usage in <FIG> and Odroid ROS data throughput in <FIG>. Similar improvements would be expected for multiplexer embodiments of the invention.

<FIG> shows, in addition to the features of <FIG> and <FIG>, a middleware <NUM> (such as ROA and CAN) which connects to the eventloop <NUM> via multiple threads (such as thread <NUM>, thread <NUM>, and thread <NUM>). Each thread comprises a middleware listener and a producer. In an example, thread <NUM> comprises a middleware listener A 11a coupled to producer 20a. The middleware listener 11a publishes the data to the event loop <NUM> using a publish call via the producer A and/or publisher (as illustrated in <FIG>).

The claimed method may be carried out on a physical entity, whereby producers and consumers are independent software entities, which may either be part of the same physical entity or run independently from said entity.

As noted previously, in the described embodiments of the invention the system may be implemented as a single computing device. Such a device may comprise one or more processors which may be microprocessors, controllers or any other suitable type of processors for processing computer executable instructions to control the operation of the device. The device may also comprise memory, e.g. random access memory, as well as storage optionally in the form of flash memory. Depending on the system requirements, additional capabilities may be provided as is well known in the art such as external inputs and outputs, wireless connectivity and others.

Variants should be considered to be included into the scope of the invention.

The figures illustrate exemplary methods. While the methods are shown and described as being a series of acts or operations that are performed in a particular sequence, it is to be understood and appreciated that the methods are not limited by the order of the sequence. For example, some acts or operations can occur in a different order than what is described herein. In addition, an act can occur concurrently with another act. Further, in some instances, not all acts may be required to implement a method described herein.

Moreover, the acts or operations described herein may comprise computer-executable instructions that can be implemented by one or more processors and/or stored on a computer-readable medium or media. The computer-executable instructions can include routines, sub-routines, programs, threads of execution, and/or the like. Still further, results of acts of the methods can be stored in a computer-readable medium, displayed on a display device, and/or the like.

Claim 1:
A method of parallel data processing in an autonomous embedded system operating in the framework of an LMAX disruptor, implemented using C++ version <NUM> onwards, the method comprising:
receiving a call to publish a data object(<NUM>);
cloning the data object (<NUM>) and placing it into a pre-allocated space in a memory (<NUM>), wherein the memory comprises a lock-free memory management system employing smart pointers, wherein a separate smart object memory pool (<NUM>, <NUM>) is provided for each producer (20a, 20b) and each smart object pool comprises a plurality of object memory slots (12a-g, 13a-g);
placing the cloned data object or a pointer to the data object into a batching queue (<NUM>), wherein a producer barrier is implemented between multiple producers and the batching queue; asynchronously publishing (<NUM>) the cloned data object by the batching queue by delivering or notifying the cloned data object the subscriber (<NUM>); and
releasing the pre-allocated space in the memory (<NUM>) after the subscriber has finished processing the data object (<NUM>).