System and method executing decentralized software

Field of invention

The present invention relates to a system and a method of executing distributed software. Specifically, the present invention relates to such systems and methods that meet hard real-time requirements.

Brief description of related technologies

Traditional systems running distributed software can include multiple nodes and one communication channel, which is configured to allow the nodes to transmit data over the communication channels. Examples of such systems also include so-called embedded systems, in which nodes that perform software tasks, also called electronic control units or computers, are encapsulated by the devices they control. .. Examples of embedded systems include automotive systems, automation systems, and avionics systems. For example, an automotive system may include, among other things, multiple devices that actuate brakes, multiple devices that sense wheel speed, devices that sense vehicle speed, and so on, and these devices communicate over communication channels. It is configured to perform anti-blocking system (ABS) operations. Since the operation of the anti-blocking system is safety critical to the vehicle and its passengers, it is necessary that repeated sensor reads, calculations, and actuator updates be performed periodically, eg, every 5 ms. is there. In practice, such a system must meet the hard real-time requirements, which means that the correctness of the action depends not only on the logical correctness of the action, but also on the time when the action is performed. Means to do. Actions performed after the deadline defined in the system are clearly inappropriate and usually of no value.

Traditional distributed software is typically configured so that the software is separated into multiple tasks that the system must perform, where these tasks can be performed by different nodes, with each single node performing. You can also perform multiple tasks. With respect to the operation of the software, it is possible for a task to use the output signal of a sensor as its input, for a task to output a signal to an actuator, and for different tasks to communicate with each other by exchanging data. Therefore, task scheduling and execution may depend on external events that can be detected by the system by one or more sensors. Therefore, the mode of operation of any system on any node can change over time, and the demand for bandwidth-related communication channels can also change over time. However, in a hard real-time system, the given bandwidth provided by the communication channel ensures unimpeded operation of the hard real-time system during each possible combination of operating modes of all contained nodes. Must be guaranteed to be sufficient.

It is well known in the art that it is not always easy to design distributed software to meet hard real-time requirements.

Various efforts have already been made to improve the design of distributed software. For example, a project called "Giotto" at the University of California, Berkeley, USA, probably provided a programming methodology for embedded control systems running on distributed platforms. This methodology includes the concept of defining the logical execution timing of task execution under hard real-time conditions. This concept is called "LET" (Logical Execution Time), and TA Henzinger et al., "Giotto: A time-triggered language for embedded programming", Proceedings of the First International Workshop on Embedded Software (EMSOFT), Lecture Notes in Computer Science 2211, Springer-Verlag, 2001, pp. 166-184, for more detail. The entire contents of this document are incorporated herein by reference.

A language that specifies the timing behavior of distributed software was developed by Wolfgang Pree and his team in a personal research project at the University of Salzburg-Paris Rodron, Salzburg, Austria. This language is called "TDL" (Timing Definition Language) and is defined in Josef Templ's Report, TDL Specification Report, Technical Report T004 (revises T001), November 2004, pp. 1-24. There is. The entire contents of this document are incorporated herein by reference.

The data exchange formats that can be used within a distributed software system for data exchange over communication channels are the document "FIBEX-Field Bus Exchange Format", MCD-2 [FBX] Version 1.1, Release Version, Association for Standardization of Automation and Measuring. Systems, January 25, 2005, ASAM eV, defined on pages 1-82. The entire contents of this document are incorporated herein by reference.

It has proven difficult to design distributed software that guarantees unobtrusive operation in all possible modes of operation contained in the system.

The present invention has been made to overcome the drawbacks of the prior art described above.

According to embodiments of the present invention, a system running distributed software allows efficient use of the bandwidth provided by the communication channels of the system.

According to another embodiment of the invention, a system running distributed software ensures that the timing requirements for data communication over a communication channel are met under all possible combinations of operating modes, while at the same time the system. Allows you to operate in several different modes of operation.

According to an exemplary embodiment of the invention, a system running distributed software includes a plurality of nodes and communication channels. For example, this system is a collection of nodes linked by a communication channel. Communication channels physically link nodes of the system to each other, which means that if a particular node contains at least one controller connected to the communication channel, that node is part of this system. means. Specifically, the system can include only one single communication channel with broadcasting semantics, commonly referred to as the "bus". However, the present invention is not limited to systems with broadcasting semantics or systems with only one single communication channel, but systems with multiple communication channels of any topology, such as stars and rings, and systems. Systems with different semantics, such as point-to-point semantics, can also be included.

A node is a device commonly referred to as an electronic control unit in some areas, which provides an interface with a sensor to convert the output signal of an actuator, engine, or sensor into data that can be processed by software. It can include circuits configured to control physical devices, such as devices that do. Nodes can also contain more complex circuits, also known as computers, which can include memory and processors, and perform software tasks that rely on input data to supply output data. Can be programmed as.

Distributed software involves multiple tasks. A task represents some of the functionality provided by the software. For example, different tasks can be performed by different nodes, and each of one or more nodes can perform multiple tasks. In addition, nodes can be configured or programmed to provide different modes of operation, in which different tasks are performed.

According to one aspect of the invention, the distributed software includes at least a first task and a second task that are not performed at the same time. Therefore, only one of the first task and the second task is being executed at a given time.

According to a particular embodiment here, the first task is repeatedly executed with a first frequency such that subsequent calls to the first task have a certain time interval with each other, and the time interval corresponds to the first frequency. Equal to the first period to do. Specifically, the duration of the first cycle can be calculated as one-third of the first frequency. The task can generate data to be sent to the communication channel, and the data transmission of the first data is also repeated at the first frequency corresponding to the first cycle. Corresponding data transmissions over the communication channel occur within each time window that has a start time and an end time. Therefore, the data transmission and the corresponding time window can also be understood as a repetitive event that occurs on the communication channel.

Similarly, according to this exemplary embodiment of the present invention, the second task repeatedly generates the second data and transmits the second data to the communication channel in the second cycle, and the data of the second data. The transmission occurs within the second communication time window, and each of the second communication time windows has a start time and an end time. In addition, the data transmission of the second data and the second communication time window can be understood as repetitive events occurring on the communication channel.

According to this exemplary embodiment, the operation of the communication channel can be understood to conform to a transmission schedule consisting of repetitive communication time intervals of a predetermined constant duration, the first period and the first. Each of the two cycles is an integral multiple of a given constant duration.

According to certain exemplary embodiments, a given constant duration is defined as the greatest common divisor of the first and second cycles.

According to the illustrated exemplary embodiments, the first and second tasks, which are not performed at the same time, are a common time portion of the iterative communication time interval of the communication channel schedule with respect to the transmission of the first and second data, respectively. Share. Specifically, the start time of the first communication time window for each communication time interval is smaller than the end time of the second communication time window for each communication time interval. Similarly, the start time of the second communication time window for each communication time interval is smaller than the end time of the first communication time window for each communication time interval.

According to an embodiment of the present invention, the communication bandwidth of distributed software is saved by sharing the available communication time portion of each communication time interval related to the operation schedule of the communication channel among different tasks of the software. It is possible to do.

According to an exemplary embodiment of the invention, the system includes one or more controllers, each controller connecting one or more nodes to a communication channel. Therefore, the controller is a dedicated hardware device that performs data transmission to and from the communication channel, separate from the node.

According to an exemplary embodiment of the invention, distributed software can be defined with respect to a plurality of software modules, the software modules being the plurality of software having an application programming interface (API). Specifically, each module can contain at least one task. According to a particular embodiment of the invention, multiple modules of software can be defined by the Timing Definition Language TDL specified in the Joseph Templ document "TDL Specification and Report" above.

According to an exemplary embodiment, a module can be defined as having a plurality of different modes, and mode switching changes a module's mode from one mode to another. Specifically, a module can be in exactly one mode at any given time. Therefore, the operating mode of the system can be represented by the corresponding mode of the software module. In addition, the mode of the module can be specified by the Timing Definition Language TDL.

According to embodiments of the present invention, the behavior of a task can be specified by logical execution time (LET), the task is configured to have a predetermined logical execution time interval associated with it, and at a node. The physical execution of the task call is started at or after the start of the logical execution time interval, and the physical execution of the task call on the node is completed before or at the end of the logical execution time interval.

According to a particular embodiment of the invention, a system running distributed software is used for a hard real-time application. From the viewpoint of satisfying the hard real-time requirements, an exemplary embodiment of the present invention has a duration of the first and second cycles of 10 during the operation of the system.^-3Better relative accuracy, 10^-4Better relative accuracy, or 10^-5Or 10^-6It provides a system configured to remain constant with better relative accuracy.

Similarly, exemplary embodiments of the invention provide a system configured such that the communication time interval associated with the schedule of the communication channel has a duration of less than 0.01 seconds or less than 0.001 seconds.

The data transmitted on the communication channel within each communication time window can have various data formats. According to an exemplary embodiment of the invention, data transmission of data indicates a representation of the data to be transmitted and the task that generated the data, allowing the recipient of the message to identify the task that generated the data. Includes sending messages that include tags. Therefore, the recipient of the message can distinguish whether each message and the data contained therein originated from one task or another task.

According to a further exemplary embodiment of the invention in which software is defined for a module, a tag can indicate a module that contains the task that generated the data. Therefore, the message recipient can also determine which module was responsible for producing a particular received message.

Further, in an exemplary embodiment of the invention, where the software is defined for modules with different modes, the tag may also indicate the mode of the module when the data contained in each message was generated. ..

Usually, the data transmission of the generated data involves a representation of the data encoded by a certain number of bytes. According to an exemplary embodiment of the invention, the number of bytes used to represent the first data generated by the first task is the number of bytes used to represent the second data generated by the second task. Different from numbers. Therefore, the first data and the second data can have different data lengths.

Similarly, tag data transmission includes a representation of the tag encoded by a certain number of bytes. According to an exemplary embodiment of the invention, the number of bytes used to represent the first tag that forms the first message with the representation of the first data is the second message along with the representation of the second data. Different from the number of bytes used to represent the second tag that forms. Therefore, the first tag and the second tag can have different data lengths.

According to an exemplary embodiment of the invention, a method of running distributed software involves a step of operating a communication channel to allow communication between a plurality of nodes, and a first task and a first task on the plurality of nodes. At least one step to execute the first task and the second task, and the first task generates the first data and communicates the first data so that only one of the two tasks is executed at a given time. The step of repeatedly transmitting data to the channel in the first cycle, in which the transmission of the first data is within the first communication time window having the same start time and end time for the iterative communication time interval of a predetermined constant duration. And the step of generating the second data by the second task and repeatedly transmitting the second data to the communication channel in the second cycle, and the transmission of the second data is for the iterative communication time interval. Each of the first and second cycles is an integral multiple of a predetermined constant duration, including steps that occur within a second communication time window that has the same start and end times, and the first communication time. The start time of the window is smaller than the end time of the second communication time window, and the start time of the second communication time window is smaller than the end time of the first communication time window.

The aforementioned and other advantageous features of the invention will become more apparent from the following detailed description of exemplary embodiments of the invention with respect to the accompanying drawings. It should be noted that not all possible embodiments of the invention necessarily represent each and / or all of the benefits identified herein.

<figref num="1">It is a schematic diagram which shows the system which executes the distributed software.</figref><figref num="2">FIG. 5 is a schematic representation of an exemplary module of software for the system shown in FIG.</figref><figref num="3">It is a schematic diagram which shows the concept of a logical execution time (LET).</figref><figref num="4">It is a schematic diagram which shows the simultaneous execution of different tasks on the same node.</figref><figref num="5">It is a schematic diagram which shows the simultaneous execution of different tasks which are executed by different nodes and communicate with each other through a communication channel.</figref><figref num="6">(a) to (c) are diagrams showing various communication time windows sharing frames within the communication time interval.</figref><figref num="7">It is a figure which shows the method of determining the communication schedule used for data transmission in the system shown in FIG.</figref><figref num="8">It is another diagram showing how to determine the communication schedule used for data transmission in the system shown in FIG.</figref><figref num="9">It is another diagram showing how to determine the communication schedule used for data transmission in the system shown in FIG.</figref><figref num="10">It is another diagram showing how to determine the communication schedule used for data transmission in the system shown in FIG.</figref>

In the exemplary embodiments described below, components that are similar in function and structure are indicated by similar symbols wherever possible. Therefore, in order to understand the characteristics of the individual components of a particular embodiment, one must refer to the description of other embodiments of the invention and the abstract of the invention.

An exemplary system running distributed software is outlined in Figure 1.

FIG. 1 is a system 1 containing three nodes 3 connected to a communication channel 5 labeled as "node 1", "node 2", and "node 3" and labeled as "bus", respectively. Is shown. The bus is used for data communication between nodes 3. Nodes are electronic devices called electronic control units (ECUs) in some areas of application such as the automotive industry. Each node may include dedicated hardware, commonly referred to as a controller, that connects the node to the communication channel. In the example shown in Figure 1, the communication channel is implemented as a bus with broadcasting semantics, which means that data transmitted from one of the nodes to the communication channel can be received by all of the other nodes. Means. However, the present invention is not limited to such communication channels, but also includes communication channels of other suitable topologies and semantics.

System 1 is configured to run software consisting of multiple modules M1, M2, M3, and M4. Modules are an example of how to configure complex software, and modules are generally one piece of software that has an application programming interface (API). Software consisting of multiple modules allows transparent distribution of the software across multiple nodes running the software. In the example shown in FIG. 1, node 1 executes modules M1 and M2, node 2 executes module M3, and node 3 executes module M4.

A more specific example of software consisting of two modules is shown in Figure 2. The exemplary software shown in FIG. 2 includes a first module 7 labeled as "module service" and a second module 8 labeled as "module client". Each module may consist of a set of sensors 9, a set of actuators 10, and a set of modes 11. The sensor 9 of module 7 is labeled "S1", "S2", and the sensor 9 of module 8 is labeled "S". Actuator 10 of module 7 is labeled as "A1", "A2", and "A3", and actuator 10 of module 8 is labeled as "A1" and "A2". Module 7 has two modes 11 labeled as "mode 1" and "mode 2". Module 8 has three modes 11 labeled as "mode 1", "mode 2", and "mode 3".

Each module 7, 8 can only be in one mode at a given time. Mode 1 of Module 7 contains two tasks labeled as "Task 1" and "Task 2", where Task 1 has a first period of 10 milliseconds as indicated by "[10ms]". It is executed repeatedly, and task 2 is executed repeatedly with a period of 20 milliseconds (indicated by "[20ms]").

In this example, the task call can adhere to the LET semantics introduced by the Giotto programming model (see TA Henzinger et al., Supra). The task call according to LET is shown in the schematic diagram of FIG. The task input is read at the beginning of the LET cycle. The beginning of the LET cycle is indicated by an arrow labeled "release" in Figure 3. The newly calculated output of the task is available exactly at the end of the LET cycle, which is indicated by the arrow labeled "End" in Figure 3. Physical execution of the task on this node begins at the time indicated by the arrow labeled "Start" and ends at the time indicated by the arrow labeled "Stop", where. Physical execution of the task is interrupted at the time indicated by the arrow labeled "suspended" and resumed at the time indicated by the arrow labeled "resume".

The time of physical execution is not exactly defined by LET. However, it is a requirement that the physical execution of the task must be completed before the end of the LET cycle. In other words, the start of the physical execution of the task can occur at the beginning or after the start of the LET cycle, and the end of the physical execution of the task must occur before or at the end of the LET cycle. According to LET semantics, the result of a task's calculation can only be used outside the task at the end or after the end of the LET cycle, not at the end of the physical execution of the task. This means that the result of a previous call to the task is available before the end of the LET cycle.

Looking back at Figure 2, task 1 in mode 1 of module 7 is repeated in a cycle of 10 ms, and the sensor is read exactly at the beginning of that 10 ms cycle to calculate task 1. The result will be available for actuator A1 exactly at the end of its 10ms cycle.

Figure 2 also shows the communication between tasks. For example, task 1 in mode 1 of module 8 takes its output as input and delivers it to task 2 and task 3.

In addition, Figure 2 shows task communication across module boundaries. The output of Task 2 in Mode 1 of Module 7 is labeled "task2.o" and is supplied as input to Task 1 in Mode 1 of Module 8.

The configuration of software in a set of modules according to LET semantics and the definition of task in a module allow for transparent distribution of software across one or more nodes, where the temporal behavior of the software is guaranteed. Specifically, the addition of new modules, if the worst case execution time (wcet) and execution rate are known for all tasks, as long as the internal scheduling mechanism of each node guarantees LET compliance. It never affects the observable temporal behavior of other modules.

FIG. 4 is a diagram of the execution of modules M1 and M2 by node 1 shown in FIG. Module M1 has one task "task 1" with LET1 and module M2 has one task "task 2" with LET2. Task 2 uses the output of task 1 as input, and LET1 of task 1 is twice as long as LET2 of task 2. The gray rectangle in FIG. 4 schematically shows the physical execution time of task 1 and task 2. The output of task 1 is made available by task 2 at the end of task 1's logical execution time LET1, as indicated by arrow 13. This can be achieved by copying the value from the memory location associated with task 1 to the memory location associated with task 2. Such a copy takes a time close to 0 on a single node.

Both the third and fourth invocations of task 2 shown in Figure 4 use the output of the first invocation of task 1. This means that when the physical execution of the fourth call of task 2 is started, the fourth call of task 2 will be the task, even if the physical execution of the second call of task 1 has already been completed. Means that the output of the second call of 1 is not used.

Communication between module tasks can take a considerable amount of time if the modules with which the software communicates are executed by different nodes. This is because communication involves sending data over a communication channel, and only one node can send data at a given time.

FIG. 5 shows an example of communication between module M1 on node 1 of system 1 and module M4 on node 3 shown in FIG.

In the example shown in FIG. 5, task 4 of module M4 has a logical execution time period LET4 which is half of the logical execution time period LET1 of task 1. Comm1 and comm3 in FIG. 5 indicate memory buffers of the communication ports of node 1 and node 3, respectively. The earliest possible time for a message to be sent from node 1 to node 2 is after the physical execution of task 1 is complete, which forms the message release constraint. According to the LET requirement, the message must arrive at node 2 before the end of LET1, which forms the message deadline constraint.

The algorithm that generates the communication schedule for System 1 must consider all message release constraints and all message deadline constraints for all messages that need to be communicated over the communication channel. These constraints usually change depending on each particular mode of the communication module. For example, a communication schedule, statistically, for example, as a table, describes when and which message should be sent from which source node to which destination node. The message sending activity described in the communication schedule is repeated after a certain length of time, which can be called a communication time interval. In an application example in which a bus is used as a communication channel, the communication time interval is generally referred to as a bus cycle.

6 (a)-(c) are diagrams of three exemplary communication time intervals that may occur at a later time in a system running distributed software according to an embodiment of the present invention. Each instance of the communication time interval 21 has a start time t0 and an end time that coincides with the start time t0 of the next instance of the communication time interval.

The communication schedule of this example includes frame 23 within the communication time interval 21 having a fixed duration and position relative to the start time t0 of that communication time interval. Multiple messages can be bound to one frame 23, which is data at different absolute times, all within the communication time of frame 23 when measured relative to the communication time interval 21. Can be sent. The absolute start and end times of a message transmission, measured relative to the repetitive communication time interval, define the communication time window for that message.

Each transmission of data from the node includes sending a message containing a representation of the tag and sending a representation of the data, each of which is within its respective communication time window 25. Each representation of the data uses a predetermined number of bytes to encode the data generated by one or more tasks. Similarly, each representation of a tag identifies the node from which the message is sent, the task that generated the data, the module that contains the task that generated the data, and the mode of the module when the task generated the data. Includes a predetermined number of bytes to encode additional information such as identification and other information that may be useful for a particular application.

From (a) to (c) of FIG. 6, it is clear that the start time and end time of the frame 23 are fixed within the communication time cycle 21. For each communication time interval 21, the start time t1 and end time t2 of the different communication time windows 25 associated with different messages bound to that frame are different for one communication time interval 21 and another communication time interval. can do. However, the start time t1 and end time t2 of the communication time window 25 related to one message are fixed at one communication time interval 21 and another communication time interval.

In the present specification, the number of bytes of the tag representation and the number of bytes of the data representation can be different between one data transmission and the next data transmission.

An example of an algorithm for creating a communication schedule is shown below.

In this example, the software is assumed to consist of modules that adhere to LET semantics. Further, the communication channel is assumed to be based on broadcast semantics so that data sent by one node can be received by all other nodes at the same time. In this example, it is further assumed that a frame is the smallest unit of data that can be transmitted and that frames transmitted by different nodes cannot be combined into a single frame. However, the present invention is also applicable to a system such as EtherCAT in which a frame can be shared by a plurality of nodes.

According to this example, access to the communication channel is collision free via a time division multiple access (TDMA) technique.

In this example, it is further assumed that the software can be specified by a LET-based description language such as TDL, which limits mode switching so that task calls are never interrupted by mode switching. Therefore, mode switching is referred to as harmonic, which means that mode switching must not occur during the LET of all task calls in the currently active mode.

The desired schedule should be a static schedule so that the size of the schedule is finite. Therefore, the schedule is repeatedly executed in a duration cycle called a communication time interval, or in this example using a bus, the communication time interval is referred to as a bus cycle.

The bus cycle is calculated as follows.

For each module M that sends data to the communication channel, mspGCD is the greatest common divisor (GCD) of the mode cycle and mode switching cycle in all modes of module M._MTo define. N mspGCD_MFrom (N + 1) mspGCD_MWithin the time period until_MIt is clear that there is no mode switching within. In other words, the moment of mode switching is mspGCD_MCan be expressed as an integral multiple of.

Next, the bus cycle is the nmspGCD of each module M that sends data to the communication channel._MCalculated as the greatest common divisor of.

Each mode period then consists of an integral multiple of the bus period, and the term "phase" is introduced to distinguish between these mutually exclusive parts of the mode.

As shown above, the data is sent to the communication channel within the communication time window where the tag and the representation of the message containing the data are sent. Each message has its own timing constraint, the release constraint is the earliest moment when the message transmission can start, and the message deadline constraint is the latest moment when the message transmission must end. It is possible to set the release constraint by adding the worst case execution time (wcet) to the release time of the task call that creates the message. Deadline constraints arise from the end of the LET of a call to the task that creates the data. Message release and deadline are for the phase in which the task call ends.

For efficient use of communication channels, phase messages can be mapped to these communication frames so that one or more reserved communication frames in the bus cycle can be used for all phases of the module. it can.

In order to create a communication schedule, it is necessary to determine the frame and bind each message to exactly one frame. At runtime, the phases of a particular mode of node, task invocation, and module determine which subset of frame-bound messages are actually sent. Tags are useful for identifying messages, as the contents of the frame change at runtime.

The release constraint for a frame is the maximum release constraint for messages bound to that frame. Similarly, the deadline constraint for a frame is the minimum deadline constraint for all messages bound to that frame. An exemplary module that has three phases and is supposed to make two messages 3 and 4 with 4 bytes in phase 1, 3 bytes in phase 2, and 1 byte in phase 3, respectively. Is schematically shown in FIG. Depending on size and timing constraints, all messages can be bound to the same frame with a size of 4 bytes. The left and right boundaries of the box representing the message and frame represent the release constraint and the deadline constraint, respectively.

Figure 8 shows the release and deadline constraints for individual messages and the frames to which those messages are bound throughout the mode period, which consists of three separate phases.

The algorithm that binds the message to the frame can be represented by the following pseudocode. createFrames (Module M) returns Set { let frames be anempty set for each mode mof module M { for each phasep of m { let msgs be anempty set for each taskinvocation instance tthat ends in p { add newMessage (M, m, t, p) to msgs } bindMsgs (msgs, frames) } } return frames } bindMsgs (Set msgs, Setframes) { reset the available bytes of allframes to the size of each frame for each msg inmsgs { if (frames is empty) { createFrame (msg, frames) } else { for each framein frames { computeMetric (msg, frame) } select theframe selFrame with thehighest metric if (selFrame.metric&gt; threshold) { bind (msg, selFrame) } else { createFrame (msg, frames) } } } }

The method bindMsgs associates a message with an existing frame when possible. If not possible, a new frame is created and the message is bound to that new frame. The method createFrame creates a frame, binds the message to that frame, sets the size of the message to the size of the frame, and adds the frame to the set of frames. The method createFrame also checks if the size of the frame exceeds the maximum allowed by the communication channel so that the frame can be sent within the communication time interval, the bus cycle.

The decision to bind a message to a frame depends on the result of a metric calculation that depends on the number of bytes available from the size of the frame. Therefore, the instance variable available is defined frame by frame and reset to the size of the frame at the beginning of each phase. The method bindMsgs binds the message to the frame and reduces the number of bytes available in the frame by the message size. An example of a heuristic method computeMetric is illustrated below herein.

In this example, the method computeMetric computes a real number between 0 and 1 and stores that number in the frame's instance variable metric. For each message, the computeMetric value is calculated on a frame-by-frame basis, identifying the frame that results in the maximum value for that metric, and the message is bound to that frame if the value for that metric exceeds a given threshold. To. Therefore, allocating messages to existing frames introduces a trade-off between bandwidth savings and narrowing of timing constraints. To this end, the algorithms and heuristics presented herein can be used advantageously. However, these algorithms and heuristics represent only exemplary embodiments of the invention, and other algorithms and heuristics that may even result in further optimizations are conceivable.

The exemplary metrics shown below have two parts, called overlapping metrics and enlargement metrics, which are timing constraints between frames and messages. And to measure the compatibility of size constraints. The overlapping metric measures the degree of overlap between a message and a frame, for example, according to the following equation:<maths num="1"><img file="JP2012133789A_D0001.tif" /></maths>here, overlapping = Min (frame.d, msg.d)-Max (frame.r, msg.r) here, frame.r represents the frame release constraint frame.d represents the frame deadline constraint msg.r represents the message release constraint msg.d represents the message deadline constraint.

Enlargement metrics measure how much the frame size needs to be increased to accommodate a message. The enlargement metric is calculated by the following formula.<maths num="2"><img file="JP2012133789A_D0002.tif" /></maths>here, enlargement = Max (0, msg.size-frame.available) here, frame.size represents the size of the frame frame.available represents the amount of frame size still available msg.size represents the size of the message.

The value of computeMetric can then be calculated by averaging the overlapping metric and the enlargement metric according to the following equation:<maths num="3"><img file="JP2012133789A_D0003.tif" /></maths>Here, this formula is applied only when both the enlargement metric and the overlapping metric give positive values. The value of computeMetric is also calculated to be 0 when either the overlapping metric or the enlargement metric yields a value less than or equal to 0.

An example of creating a calculation schedule according to the above algorithm is provided below for module M3 executed by node 2 of system 1 shown in FIG.

In this example, module M3 has two modes M1 and M2 and three tasks t1, t2, and t3, as shown in Table 1 below.<tables num="1"><img file="JP2012133789A_D0004.tif" /></tables>

Details of tasks t1, t2, and t3, such as worst-case execution time (wcet) and the size of the representation of the output data, are shown in Table 2 below.<tables num="2"><img file="JP2012133789A_D0005.tif" /></tables>

Module M3 mspGCD because mode switching must not occur during the LET of a task call in the currently active mode._MIs calculated as follows. mspGCD_M3= GCD (5,10) = 5ms

Bus cycle is mspGCD of each module M_MCalculated as the greatest common divisor of. In this example, where only module M3 is trying to send data to the communication channel, only module M3 needs to be included in this GCD calculation. Therefore, the bus cycle is mspGCD_M3Is equal to 5ms.

Table 3 below lists all the messages that a task must send in all modes. The release time and deadline time are relative to the mode cycle of the task sending the message. The release time is equal to the beginning of the LET plus the worst case execution time (wcet), and the deadline time is equal to the end of the LET.<tables num="3"><img file="JP2012133789A_D0006.tif" /></tables>

Table 4 below lists the messages in Table 3 with release and deadline constraints shown for the bus cycle of all phases in the two modes.<tables num="4"><img file="JP2012133789A_D0007.tif" /></tables>

According to the algorithm shown by the pseudocode above, the iterations are performed across all modes and phases and the evaluation is done with respect to whether the message is assigned to an existing frame or a new frame is created. The procedure with this algorithm begins in mode M1 and phase 1, which is the only phase in this mode. At the beginning of this procedure, no frame was created, and the frame created for this mode inherits its timing constraints from the first message. The frame size is then equal to the sum of the message size and the tag size chosen to be 1 byte in this example.

Table 5 below lists the frames and bound messages at this stage of the procedure.<tables num="5"><img file="JP2012133789A_D0008.tif" /></tables>

In the next step, mode M2 is considered for phase 1, where data transmission is not performed in phase 1 of mode M2. Therefore, Phase 2 Message 2 is considered next. The metric is evaluated to determine whether to bind message 2 to an existing frame. In this example, a threshold of 0.5 is used. The overlapping metric is calculated as follows: overlapping = Min (5,5)-Max (1,0) = 4<maths num="4"><img file="JP2012133789A_D0009.tif" /></maths>

It is clear that the frame will not grow in this phase, as the available space in all frames will be reset in every new phase, and the size of message 2 is 3 bytes (1 byte tag). Including). Therefore, the value of the enlargement metric is 1. The overall metric value is calculated to be 0.95 by averaging 0.9 and 1.0. 0.95 is well above the threshold, so message 2 is bound to frame 1 and the available space in this phase is reduced to 2 bytes. Table 6 shown below represents the frames and bound messages at this stage of this procedure.<tables num="6"><img file="JP2012133789A_D0010.tif" /></tables>

Message 3 of Phase 2 is considered next. The timing requirement for message 3 is the same as the timing requirement for message 2, so the result of the overlapping metric is still 0.90.

The size of message 3 is 3 bytes, which contains a 1-byte tag. Therefore, msg.size = 3, frame.available = 2, and frame.size = 5. Using these values, the enlargement metric can be calculated as follows. enlargement = Max (0, (3-2)) = 1<maths num="5"><img file="JP2012133789A_D0011.tif" /></maths>

The overall metric yields 0.87 by averaging 0.90 and 0.83, which is well above the selected threshold of 0.5. Therefore, message 3 is also bound to frame 1 and its size is increased to 6 bytes, which is shown in Table 7 below.<tables num="7"><img file="JP2012133789A_D0012.tif" /></tables>

In this example presented, it is possible to bind all messages into one single frame. For this identified frame, a suitable bus schedule must be generated taking into account release and deadline constraints. Such a schedule can be determined according to the latest release time scheduling algorithm LRT, as shown in JWSLiu, "Real-Time Systems", Prentice-Hall, 2000. This results in the bus schedule shown in FIG. 9, where frame 1 is scheduled so that its transmission ends in 5 ms.

FIG. 10 is a diagram of dynamic multiplexing resulting from message binding by the algorithm shown above for modes m1 and m2 of module M3. Frame 1 with a capacity of 6 bytes is filled with message 1 having a size of 5 bytes in mode m1, or message 2 having a size of 3 bytes and message 3 having a size of 3 bytes in mode m2. Alternatively, this frame is left empty.

An embodiment of a system that runs distributed software under hard real-time conditions includes multiple nodes and one communication channel. Nodes are allowed to send data over the communication channel within the time window for the iterative communication time interval of the communication channel, and the number of bytes sent within this communication time window varies from communication time window to communication time window. can do. The data can be sent as a message containing a representation of the identifying tag and a representation of the data. In addition, the number of bytes representing each tag can be changed for each communication time interval.

The systems and methods shown above that run distributed software can be included in an application to control the functionality or performance of any technical application. For example, this system and method can be included in vehicles such as automobiles, aircraft, ships, missiles, and others.

Although the present invention has been described for certain exemplary embodiments of the invention, it is self-evident that a number of alternative, modified, and modified forms will be apparent to those skilled in the art. Accordingly, the exemplary embodiments of the invention presented herein are intended to be exemplary and not intended to be limiting in any way. Various changes can be made without departing from the spirit and scope of the invention as defined in the appended claims.