System and method for scheduling data transfers among a plurality of data processing units to avoid conflicting data requests
First Claim
1. A method for scheduling data transfers among a plurality of processing devices over a predetermined number of message carrying channels comprising the steps of:
- receiving a plurality of requests for data transfers from said processing devices;
identifying conflicts in requested data transfers by generating a signal identifying the interferences in data carrying channels among the message transfer requests;
specifying an initial transfer schedule by selecting a signal representing a non-interfering data transfer schedule; and
improving the non-interfering message transfer schedule signal including;
determining correlations in the identified data carrying channel interferences signal among the message transfer requests;
comparing the determined correlations in the identified data carrying channel interferences signal to predetermined criteria,modifying the non-interfering data transfer schedule signal responsive to the determined correlations, andreforming the signal identifying the interferences in data carrying channels among the data transfer requests responsive to the determined correlations,the sequence of determining, comparing, modifying and reforming steps being repeated until the determined correlations meet the predetermined criteria in the comparing step "scheduling said data transferred to selected processing devices in response to said sequences of determining, comparing, modifying, and reforming, " and "performing said data transfers".
1 Assignment
0 Petitions
Accused Products
Abstract
A method for allocating resource use to a process having a plurality of tasks in which a set of signals identifying the interferences in resource use among the plurality of tasks is generated and a signal representing an initial non-interfering allocation is produced. The allocation signal is iteratively improved by 1) determining the correlations among the identified interferences, 2) comparing the determined correlations to prescribed criteria, 3) modifying the allocation signal in accordance with the determined correlations, and 4) reforming the interference signal set responsive to the determined correlations. When the determined correlations meet the prescribed criteria in the correlation determination, the corresponding allocation signal is selected as the optimum non-interfering allocation.
-
Citations
22 Claims
-
1. A method for scheduling data transfers among a plurality of processing devices over a predetermined number of message carrying channels comprising the steps of:
-
receiving a plurality of requests for data transfers from said processing devices; identifying conflicts in requested data transfers by generating a signal identifying the interferences in data carrying channels among the message transfer requests; specifying an initial transfer schedule by selecting a signal representing a non-interfering data transfer schedule; and improving the non-interfering message transfer schedule signal including; determining correlations in the identified data carrying channel interferences signal among the message transfer requests; comparing the determined correlations in the identified data carrying channel interferences signal to predetermined criteria, modifying the non-interfering data transfer schedule signal responsive to the determined correlations, and reforming the signal identifying the interferences in data carrying channels among the data transfer requests responsive to the determined correlations, the sequence of determining, comparing, modifying and reforming steps being repeated until the determined correlations meet the predetermined criteria in the comparing step "scheduling said data transferred to selected processing devices in response to said sequences of determining, comparing, modifying, and reforming, " and "performing said data transfers". - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. Apparatus for allocating resource use in a data transfer process among a plurality of data processors having a plurality of tasks comprising;
-
a plurality of data processing devices; a plurality of communication channels for interconnecting the plurality of data processing devices; control apparatus for controlling transfer of data between individual ones of the data processing devices and including; means for storing signals representative of data transfer resources used in the process; means for storing signals representative of the data transfer tasks of the process; means responsive to the stored resource and task signals for generating a signal identifying interferences in resource use among the tasks; means for generating a signal representing an initial non-interfering allocation of resources to the plurality of tasks; and mean for determining the correlations in the signal identifying the interferences of resource use among the tasks, means for comparing the determined correlations to predetermined criteria, means for modifying the non-interfering allocation of resource use signal responsive to the determined correlation, means for reforming the signal identifying the interferences of resource use among the tasks responsive to the determined correlations, and the control apparatus being operative for iteratively operating the determining, comparing, modifying and reforming means until the determined correlations meet the predetermined criteria in the comparing step means for scheduling use of resources. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A multi processor data processing network with controlled allocation of data transfers between processor devices;
- comprising;
a plurality of data processing devices; a first communication bus coupled, via a first plurality of switches, to input and receive data from the plurality of data processing switches; a second communication bus coupled, via a second plurality of switches, to input and receive data from the plurality of data processing switches; a control unit connected to control the first and second plurality of switches and operative to control data communication between individual ones of the plurality of data processing devices;
including;means for determining an interference between data transfers among the plurality of data processing devices in the performance of a plurality of data processing tasks by generating a representative interference signal array; means for initially assigning task performances in a sequence of time intervals by generating an allocation signal; means for evaluating compatibility of the data processing tasks by generating a correlation signal array; means for optimizing task allocations by generating a series of modified correlation signal arrays with each array having fewer elements until all elements are zero and deriving a modified interference signal array therefrom; means for scheduling data transfers; means for performing said transfers. - View Dependent Claims (22)
- comprising;
Specification