System and method for scheduling data transfers among a plurality of data processing units to avoid conflicting data requests

• US 5,070,453 A
• Filed: 04/10/1989
• Issued: 12/03/1991
• Est. Priority Date: 04/10/1989
• Status: Expired due to Fees

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.), Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Duffany, Jeffrey L.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Hayes, Gail O.
• Application Number:
  US07/335,333
• Time in Patent Office: 967 Days
• Field of Search: 364/400-402, 364/408, 364/200, 364/900, 364/406
• US Class Current: 705/7.22
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06Q 10/06312 Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling
• CPC Class Codes: G06Q 10/06316 Sequencing of tasks or work
• CPC Class Codes: H04W 16/10 Dynamic resource partitioning
• CPC Class Codes: H04W 16/14 Spectrum sharing arrangements between different networks
• CPC Class Codes: H04W 72/541 using the level of interference

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.

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".

2. A method for scheduling data transfers among a plurality of processing devices over a predetermined number of data carrying channels according to claim 1 wherein the step of generating a signal identifying the interferences in data carrying channels among the data transfer requests includes forming a set of signals each indicative of a concurrent requirement for at least one data carrying channel by two or more of the plurality of the data transfer requests.

3. A method for scheduling data transfers among a plurality of processing devices over a predetermined number of data carrying channels according to claim 2 wherein the step of forming a set of signals each indicative of a concurrent requirement for at least one data carrying channel by two or more of the plurality of data transfer requests comprises generating an array of signals each representing the data carrying channel interferences between a pair of the plurality data transfer requests.

4. A method for scheduling data transfers among a plurality of processing devices over a predetermined number of data carrying channels according to claim 1 wherein the step of determining the correlations of the identified data carrying channel interferences among the data transfer requests comprises forming an array of first signals each representative of the compatibility of data carrying channels between a selected message transfer request and the plurality of message transfer requests responsive to the signal identifying the interferences in message carrying channels among the message transfer requests.

5. A method for scheduling data transfers among a plurality of processing devices over a predetermined number of data carrying channels according to claim 4 wherein each first signal comprises a set of element signals, each element signal having a value representative of the compatibility in message carrying channels between the selected data transfer request and one of the plurality of data transfer requests.

6. A method for scheduling data transfers among a plurality of processing devices over a predetermined number of data carrying channels according to claim 5 wherein the step of determining the correlations of the identified data carrying channel interferences among the data transfer requests further comprises generating a data carrying channel interference correlation signal array responsive to the first signal array.

7. A method for scheduling data transfers among a plurality of processing devices over a predetermined number of data carrying channels according to claim 5 wherein the compatibility signal formation further comprises forming an array of second signals each representative of the incompatibility of data carrying channels between a selected data transfer request and the plurality of data transfer requests and comprising a set of element signals, each signal having a value representative of the incompatibility in data carrying channels between the selected data transfer and one of the plurality of data transfer requests.

8. A method for scheduling data transfers among a plurality of processing devices over a predetermined number of data carrying channels according to claim 7 wherein the step of determining the correlations of the identified data carrying channel interferences among the data transfer requests further comprises combining the first and second signal arrays to generate a data carrying channel interference correlation signal array.

9. A method for scheduling data transfers among a plurality of processing devices over a predetermined number of data carrying channels according to claim 6 or 8 wherein the step of modifying the non-interfering data transfer schedule signal responsive to the determined correlations comprises:

altering the data carrying channel interferences correlation signal array by setting the values of selected elements to zero;

generating a signal corresponding to a location of the largest value element in the altered data carrying channel interferences correlation signal array, and

modifying the non-interfering data transfer schedule signal responsive to the determined correlations responsive to the location of the largest value element in the altered data carrying channel interferences correlation signal array.

10. A method for scheduling message transfers among a plurality of processing devices over a predetermined number of message carrying channels according to claim 6 or 8 wherein the step of reforming the signal identifying the interferences in message carrying channels among the message transfer requests responsive to the determined correlations comprises

altering the message carrying channel interferences correlation signal array of setting the values of selected elements to zero

generating a signal corresponding to a location of the largest value element in the altered message carrying channel interferences correlation signal array, and

modifying the signal identifying the interferences in message carrying channels among the message transfer requests responsive to the signal corresponding to the location of the largest value element in the altered message carrying channel interference correlation signal array.

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.

12. Apparatus for allocating resource use in a data transfer process among a plurality of data processors having a plurality of tasks according to claim 11 wherein the means for generating a signal identifying the interferences of resource use among the tasks includes means for forming a set of signals each indicative of a concurrent requirement for at least one resource by two or more of the plurality of tasks.

13. Apparatus for allocating resource use in a data transfer process among a plurality of data processors having a plurality of tasks according to claim 12 wherein the means for forming a set of signals each indicative of a concurrent requirement for at least one resource by two or more of the plurality of tasks comprises means for generating an array of signals each representing the resource interference between a pair of the plurality of tasks.

14. Apparatus for allocating resource use in a data transfer process among a plurality of data processor having a plurality of tasks according to claim 11 wherein the means for determining the correlations of the identified interferences of resource use among the tasks comprises means for forming a signal representative of the compatibility in resource use among the plurality of tasks.

15. Apparatus for allocating resource use in a data transfer process among a plurality of data processors having a plurality of tasks according to claim 14 wherein the means for forming the compatibility signal comprises means for generating an array of first signals each representative of the compatibility in resource use between a selected task and the plurality of tasks responsive to the identified interferences in resource use among the tasks and comprising a set of element signals, each element signal having a value representative of the compatibility in resource use between the selected task and one of the plurality of tasks.

16. Apparatus for allocating resource use in a data transfer process among a plurality of data processors having a plurality of tasks according to claim 15 wherein the means for determining the correlations of the identified interferences of resource use among the tasks further comprises means for forming a resource interference correlation signal responsive to the first signal array.

17. Apparatus for allocating resource use in a data transfer process among a plurality of data processors having a plurality of tasks according to claim 15 wherein the compatibility signal forming means further comprises means for forming a second signal array each representative of the incompatibility in resource use between a selected task and the plurality of tasks and comprising a set of element signals each signal having a value representative of the incompatibility in resource use between the selected task and one of the plurality of tasks.

18. Apparatus for allocating resource use in a data transfer process among a plurality of data processors having a plurality of tasks according to claim 17 wherein the means for determining the correlations of the identified interferences of resource use among the tasks further comprises means for combining the first and second signal arrays to generate a resource use correlation signal array.

19. Apparatus for allocating resource use in a data transfer process among a plurality of data processors having a plurality of tasks according to claim 16 or claim 18 wherein the means for modifying the non-interfering allocation of resource use signal comprises:

means for altering the resource correlation signal array by setting the values of selected elements to zero.

means for generating a signal corresponding to a location of the largest value element in the altered resource use correlation signal array, and

means for modifying the non-interfering allocation of resource use signal responsive to the location of the largest value element in the altered correlation signal array.

20. Apparatus for allocating resource use in a data transfer process among a plurality of data processors having a plurality of tasks according to claim 16 or claim 18 wherein means for reforming the signal identifying the interferences of resource use among the tasks responsive to the determined correlations comprises:

means for altering the resource correlation signal array by setting the values of selected elements to zero,

means for generating a signal corresponding to a location of the largest value element in the altered resource use correlation signal array, and

means for modifying the signal identifying the interferences of resource use among the tasks responsive to the signal corresponding to the location of the largest value element in the altered correlation signal array.

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.

22. A multi processor data processing network as claimed in claim 21, comprising:

the means for determining an interference includes;

means for generating an interference matrix signal with unity elements denoting interferences between available task performance resources; and

the means for optimizing task allocations includes;

means for modifying the allocation signal to provide an optimun task sequence.