Multiprogrammed multiprocessor system with lobally controlled communication and signature controlled scheduling

• US 6,763,519 B1
• Filed: 05/05/1999
• Issued: 07/13/2004
• Est. Priority Date: 05/05/1999
• Status: Expired due to Term

• Current Assignee: Roderick C.M. Hall, Trotter J. David
• Original Assignee: Sychron, Inc.
• Inventors: Valiant, Leslie G., Donaldson, Stephen R., McColl, William F., Hill, Jonathan M. D.
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): Vo, Lilian
• Application Number:
  US09/305,570
• Time in Patent Office: 1,896 Days
• Field of Search: 712/28, 712/1, 709/100, 709/102, 709/104, 709/107, 709/202, 709/226
• US Class Current: 718/100
• CPC Class Codes: G06F 2209/5014 Reservation
• CPC Class Codes: G06F 9/5044 considering hardware capabilities

Abstract

A multiprogrammed multiprocessor system comprises a plurality of processors and some communications resources such as networks through which the processors communicate with each other. A plurality of tasks may be executed on the system, and the allocation of the communications resources among the tasks is globally controlled. The allocation of resources among the tasks running on the system can be dependent on the signature of the tasks, where one component of a task signature is a measure of the communication resources needed by the task. The scheduling of a task running on the system may also be dependent on the signature of the task. The allocation of communications resources can be globally controlled using a variety of techniques including: packet injection into the communications resources using periodic strobing or using global flow control; using global implicit acknowledgments; by destination scheduling; by pacing; or by prioritized communication scheduling. Error recovery overheads can be amortized over a plurality of jobs running at one node. A user interface allows a plurality of service level options to be specified by a user, where the system can guarantee that the service levels can be achieved. Application users as well as system administrators can choose options as are appropriate. The user interface can allow the system administrator to run a scheduling mechanism that distributes communications resources among the tasks according to a market mechanism. The user interface can also allow a task to be guaranteed a fixed fraction of the resources independent of the other tasks then running or to be run as an interactive continuous job at one of a plurality of service levels. Finally, the user interface allows a system administrator to subdivide system resources into reserved and unreserved components, where the unreserved component is made available according to a market mechansim.

Claims

1. A method for scheduling a plurality of tasks on a multi-processor system to allocate resources of the multi-processor system to the plurality of tasks, the method comprising:

determining a machine signature characterizing computation and communication resources of the multi-processor system;

generating a task signature for at least some of the plurality of tasks running on the multi-processor system, each task signature characterizing communication and computation resources required by a particular task;

scheduling the plurality of tasks on the multi-processor system based at least in part, on the task signatures and the machine signature, for allocating resources of the multi-processor system to the plurality of tasks, wherein said scheduling includes establishing a strobing interval comprising a period of time between successive strobes in which communications are transmitted and establishing a strobing duration comprising a maximum volume of data that may be communicated in a particular strobe; and

controlling communications among the plurality of tasks based on the scheduling of the plurality of tasks.

2. The method of claim 1, wherein said communication resources include network bandwidth.

3. The method of claim 1, wherein said computation resources include processing resources.

4. The method of claim 1, wherein said computation resources include memory resources.

5. The method of claim 1, wherein said determining step includes determining a machine signature based, at least in part, on communication capacity.

6. The method of claim 1, wherein said generating step includes generating a task signature based, at least in part, upon communication bandwidth required by the task.

7. The method of claim 1, wherein said generating step includes generating a task signature based, at least in part, upon processing resources required by the task.

8. The method of claim 1, wherein said generating step includes generating a task signature based, at least in part, upon synchronization requirements of the task.

9. The method of claim 1, wherein said scheduling step includes scheduling communications among the plurality of tasks.

10. The method of claim 9, wherein scheduling communications includes setting the frequency of communications by a given task.

11. The method of claim 9, wherein scheduling communications includes scheduling a volume of communications by a given task during a particular time period.

12. The method of claim 1, wherein said scheduling step includes specifying a portion of processing resources that may be utilized by a given task.

13. The method of claim 1, wherein said scheduling step includes specifying a portion of the communication resources that may be utilized by a given task.

14. The method of claim 13, wherein specifying a portion of communication resources that may be utilized by a given task includes specifying a volume of data that may be transmitted by the given task during a particular time period.

15. The method of claim 13, wherein specifying a portion of communication resources that may be utilized by a given task includes specifying a frequency of communication by the given task.

16. The method of claim 1, wherein said controlling step includes substeps of:

designating an interval for transmission of communications;

holding communications of a given task in a staging area; and

regulating the volume of communications of the given task transmitted from the staging area during a particular interval.

17. The method of claim 1, wherein said scheduling step includes specifying a volume of data to be transmitted by a given task during a particular strobe.

18. The method of claim 1, wherein said scheduling step includes specifying whether communications of a given task are to be transmitted during a particular strobe.

19. The method of claim 1, wherein said controlling step includes limiting communications of a given task to a portion of said strobing duration during a particular strobe.

20. The method of claim 1, further comprising:

determining a volume of data corresponding to all communications the plurality of tasks are requesting to send during a particular strobe; and

if said volume of data does not exceed the strobing duration, transmitting all communications of the plurality of tasks during the particular strobe.

21. The method of claim 20, further comprising:

otherwise, if said volume of data is greater than the strobing duration, determining a portion of the communications of a given task that may be transmitted during the particular strobe.

22. A system allocating resources of a plurality of processors to a plurality of tasks based upon signatures of the tasks, the system comprising:

a plurality of tasks, at least some tasks having a task signature characterizing processing and communication resources required by the task;

a plurality of processors having processing resources for executing the plurality of tasks,

communication resources which allow the plurality of processors to communicate with one another;

a task scheduler for allocating processing resources and communication resources to the plurality of tasks based, at least in part, on the task signatures, wherein said task scheduler establishes a strobing interval comprising a period of time between successive strobes in which communications are transmitted and establishes a strobing duration comprising a maximum volume of data that may be communicated in a strobe; and

a communication module for regulating usage of communication resources based on the allocation of communication resources by the task scheduler.

23. The system of claim 22, wherein said communication resources include network bandwidth.

24. The system of claim 22, wherein said processing resources include computer processing unit (CPU) resources.

25. The system of claim 22, wherein said task scheduler establishes a frequency of communications by a given task.

26. The system of claim 22, wherein said task scheduler specifies a volume of communications by a given task during a particular time period.

27. The system of claim 22, wherein said task scheduler designates an interval for transmission of communications.

28. The system of claim 27, wherein said communication module holds communications of a given task in a staging area for possible transmission during a particular interval.

29. The system of claim 28, wherein said communication module regulates a volume of communications sent by the given task during the particular interval.

30. The system of claim 22, wherein said task signature is based on a selected one of communication resources required by the task, computation resources required by the task, and synchronization resources required by the task.

31. The system of claim 22, wherein said task scheduler specifies a portion of the processing resources that may be utilized by a given task.

32. The system of claim 22, wherein said task scheduler specifies a portion of the communication resources that may be utilized by a given task.

33. The system of claim 32, wherein specifying a portion of communication resources that may be utilized by a given task includes specifying a volume of data that may be transmitted by the given task during a particular time period.

34. The system of claim 32, wherein specifying a portion of communication resources that may be utilized by a given task includes specifying a frequency of communication by the given task during a particular time period.

35. The system of claim 22, wherein said task scheduler specifies a volume of data to be transmitted by a given task during a particular strobe.

36. The system of claim 22, wherein said task scheduler specifies whether communications of a given task are to be transmitted during a particular strobe.

37. The system of claim 22, wherein said task scheduler determines a portion of said strobing duration that may be utilized by communications of a given task.

38. The system of claim 22, wherein said communication module determines a volume of data corresponding to all communications the plurality of tasks are attempting to send during a particular strobe.

39. The system of claim 38, wherein said communication module transmits all communications of the plurality of tasks during the particular strobe if the determined volume of data does not exceed the strobing duration.

40. The method of claim 38, wherein said communication module transmits a portion of all communications of the plurality of tasks during the particular strobe if the determined volume of data is greater than the strobing duration.