Method and apparatus for timing information flow in a distributed system

• US 20060130030A1
• Filed: 11/02/2005
• Published: 06/15/2006
• Est. Priority Date: 11/19/2004
• Status: Active Grant

• Current Assignee: United States Air Force
• Original Assignee: United States Air Force
• Inventors: Kwiat, Kevin A., Ravindran, Kaliappanadar, Sabbir, Ali S.
• Granted Patent: US 7,877,748 B2
• Time in Patent Office: Days
• US Class Current: 717/159
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

A computer and software method and apparatus for distributed data processing which provides agreement between data sources (sensors) and data sinks (actuators) as to what data has been written into a shared buffer. The invention further provides methods and means for meeting data timeliness requirements. Invention employs a programming primitive which recognizes semantics so as to provide a consistent view of computation modules over prescribed time intervals, called “epochs”. Application-level control of the asynchrony and timing of information flow between various computation modules is realized. The invention has applications which include sensor fusion and network gaming.

Claims

1. In a distributed data processing system, a software program method comprising a set of instructions, stored on a computer-readable media, wherein said instructions, when executed by a computer, perform the necessary steps for timely processing time sensitive tasks executing data from data sources and by data sinks, comprising:

writing at least one source'"'"'s data di into a buffer as an unordered set during an epoch;

processing said source'"'"'s data from said buffer in sinks;

temporally ordering said source'"'"'s data during said epoch by enforcing state consistency and integrating the passage of real time in a varying degree specific to the application;

partitioning a task into subtasks;

synchronizing said subtasks'"'"' results;

extracting parallelism in the execution of said tasks, further comprising;

a first step of identifying the functional dependencies between each said task and the data needed for the execution of each said task;

a second step of identifying task execution points requiring input of a sensor data item “

x”

, relative to the processing of other said data items in the execution of said task; and

scheduling said tasks accordingly.

2. Method of claim 1, wherein said step of writing further comprises:

agreeing among said sources and said sinks as to what data items have been written into said buffer.

3. Method of claim 1, wherein said step of writing further comprises:

prescribing a time budget for processing said source data so as to produce composite outputs.

4. Method of claim 1, further comprising computing said epoch according to

ε

+β

+max({ζ

k}),k=1, . . . , M

where ε

comprises the maximum time skew allowed between the data samples of various said data sources in a given epoch, β

comprises the time to process said data, and ζ

comprises the time to transition from the current said epoch to the next said epoch.

5. Method of claim 1, further comprising invoking by each of said data source ui( . . . ) a write_buf primitive after data di becomes available for processing, so as to form a wrtset of successful writes to said buffer during each said epoch, wherein

wrtset:

=write_—

buf(di,ε

,grp,e),

wherein wrtset comprises the set of successful writes on the buffer in said epoch e and wherein grp comprises the broadcast group address to which process p is subscribed to.

6. Method of claim 5, further comprising:

a first step of defining the parameter wrtset as;

1≦

|wrtset|≦

nwrt≦

|W′

|

and a second step of defining the parameter nwrt as the maximum number of processes that are allowed to write to said buffer in a current epoch.

7. Method of claim 1, further comprising invoking by each of said data sink a read_buf primitive so as to read said buffer, wherein

wrtset:

=read_—

buf(grp,e)

wherein wrtset comprises the set of successful writes on the buffer in said epoch e and wherein grp comprises the broadcast group address to which process p is subscribed to.

8. Method of claim 1, wherein said step of scheduling further comprises determining local computation schedules relative to an overall task deadline by employing a dataflow dependency graph.

9. Method of claim 8, wherein said dataflow dependency graph ensures that the last said data sink to receive data due to latency, in a plurality of data sinks, is the data sink which triggers action by said process task.

10. Method of claim 5, wherein timely processing data from data sources ui( . . . ) further comprises:

waiting for the start time of said epoch Tj (j=0, 1, . . . )

obtaining W′ and

ε

parameters from session manager;

determining whether ui ε

W′

;

IF ui ε

W′

, THEN

waiting for either of said duration of time ε

or until the availability of said data di;

determining whether said data di is ready on time;

IF said data di is ready on time, THEN

computing wrtset;

=write_buf(di,e,grp,j);

determining whether ui ∉

{wrtset.id};

 

IF ui ∉

{wrtset.id}, THEN

 

deferring attempted write of said di to said epoch j+1;

 

OTHERWISE;

 

ceasing processing data;

OTHERWISE;

ceasing processing data;

OTHERWISE;

ceasing processing data.

11. Method of claim 7, wherein timely processing data in data sinks vk( . . . ) further comprises:

waiting for the start time of said epoch Tj (j=0, 1, . . . );

computing wrtset;

=read_buf(grp,j);

identifying xset {overscore (⊂

)} wrtset to process in current said epoch;

determining whether xset≠

Ø

;

IF xset≠

Ø

;

THEN

computing result;

=f(k,j) ({xset.dt},par);

sending result to other functions;

computing local component of global state Sj+1

ceasing processing data;

OTHERWISE,

computing result;

=f(k,j) (NULL, par); and

returning to said step of sending result to other functions.

12. In a distributed data processing system, a computer apparatus and a set of software code, said software code being executable therein so as to timely process time sensitive tasks executing data from data sources and by data sinks input thereinto by providing means for:

writing at least one source'"'"'s data di into a buffer as an unordered set during an epoch;

processing said source'"'"'s data from said buffer in sinks;

temporally ordering said source'"'"'s data during said epoch by enforcing state consistency and integrating the passage of real time in a varying degree specific to the application;

partitioning a task into subtasks;

synchronizing said subtasks'"'"' results;

extracting parallelism in the execution of said tasks, further comprising;

a first step of identifying the functional dependencies between each said task and the data needed for the execution of each said task;

a second step of identifying task execution points requiring input of a sensor data item “

x”

, relative to the processing of other said data items in the execution of said task; and

scheduling said tasks accordingly.

13. The computer apparatus and set of software code as in claim 12, further comprising computer-executable instructions so as to provide means for agreement among said sources and said sinks as to what data items have been written into said buffer.

14. The computer apparatus and set of software code as in claim 12, wherein said means for writing further comprises:

means for prescribing a time budget for processing said source data so as to produce composite outputs.

15. The computer apparatus and set of software code as in claim 12, further comprising means for computing said epoch according to

ε

+β

+max({ζ

k}),k=1, . . . , M

where ε

comprises the maximum time skew allowed between the data samples of various said data sources in a given epoch, β

comprises the time to process said data, and ζ

comprises the time to transition from the current said epoch to the next said epoch.

16. The computer apparatus and set of software code as in claim 12, further comprising means for computing by each of said data source a write_buf primitive after data di becomes available for processing, so as to form a wrtset of successful writes to said buffer during each said epoch, wherein

wrtset:

=write_—

buf(di,ε

,grp,e),

wherein wrtset comprises the set of successful writes on the buffer in said epoch e and wherein grp comprises the broadcast group address to which process p is subscribed to.

17. The computer apparatus and set of software code as in claim 16, further comprising:

a first means for defining the parameter wrtset as;

1≦

|wrtset|≦

nwrt≦

″

W′

|; and

a second means for defining the parameter nwrt as the maximum number of processes that are allowed to write to said buffer in a current epoch.

18. The computer apparatus and set of software code as in claim 12, further comprising means for invoking by each of said data sink a read_buf primitive so as to read said buffer, wherein

wrtset:

=read_—

buf(grp,e)

wherein wrtset comprises the set of successful writes on the buffer in said epoch e and wherein grp comprises the broadcast group address to which process p is subscribed to.

19. The computer apparatus and set of software code as in claim 12, wherein said means for scheduling further comprises means for determining local computation schedules relative to an overall task deadline by employing a dataflow dependency graph.

20. The computer apparatus and set of software code as in claim 19, wherein said dataflow dependency graph further comprises means for ensuring that the last said data sink to receive data due to latency, in a plurality of data sinks, is the data sink which triggers action by said process task.

21. The computer apparatus and set of software code as in claim 16, wherein said means for timely processing data from data sources ui( . . . ) further comprises means for:

22. The computer apparatus and set of software code as in claim 18, wherein said means for timely processing data in data sinks vk( . . . ) further comprises means for: