Patent US5889989A successfully refreshed from Google Patents.
US5889989A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Load sharing controller for optimizing monetary cost
Assignee: Research Foundation of the State University of New York
•
Filing: 1996-09-16
•
Granted: 1999-03-30
•
Expires: 2016-09-16
Abstract
Abstract A load sharing system which minimizes overall costs by assigning segments of a divisible load to distributed processors based on the monetary cost of each processor. The distributed processors are connected to a network such as a local area network or the internet. A controller divides a divisible load and assigns each segment of the load to a processor based on the processor's monetary cost which is a function of its operating cost and its processing speed. The allocation is then optimized by transferring portions of the load from the expensive processors to the cheaper processor while maintaining an acceptable finish time for all processing. The optimization can also be performed for minimizing the finish time of the processors within a cost constraint.
Inventors
- 👤 Thomas G. Robertazzi
- 👤 Serge Luryi
- 👤 Jeeho Sohn
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 04:28
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5083; G06F9/5088; G06F9/5061; G06F9/5066
Claims Analysis
Total Claims: 45
Claim 1
Independent Claim
123 words
A system for distributing an incoming computing job comprising: a plurality of processors, each with an associated monetary cost; a queue for receiving said incoming computing job; a controller for dividing said received computing job into segments and allocating said segments to at least two of said processors; and a network for connecting said processors and said controller; wherein said controller retrieves associated monetary cost data for said plurality of processors and identifies at least one processor with a low said monetary cost, wherein said allocation of said segments is responsive to said retrieved associated monetary cost data of each said processor and wherein said controller further reallocates said segments to said processors in order to minimize said computing job's overall monetary cost.
Claim 2
Independent Claim
123 words
A system for distributing an incoming computing job comprising: a plurality of processors, each with an associated monetary cost; a queue for receiving said incoming computing job; a controller for dividing said received computing job into segments and allocating said segments to at least two of said processors; and a network for connecting said processors and said controller; wherein said controller retrieves associated monetary cost data for said plurality of processors and identifies at least one processor with a low said monetary cost, wherein said allocation of said segments is responsive to said retrieved associated monetary cost data of each said processor and wherein said controller further reallocates said segments to said processors in order to minimize said computing job's overall monetary cost.
Claim 3
Dependent Claim
13 words
A system of claim 1, wherein said controller is one of said processors.
Claim 4
Dependent Claim
16 words
The system of claim 2, wherein said controller is not allocated at least one said segment.
Claim 5
Dependent Claim
17 words
The system of claim 1, wherein said processors include at least two different types of said processors.
Claim 6
Dependent Claim
26 words
The system of claim 1, wherein said monetary cost of each said processor is responsive to said processor's speed and said operating cost of said processor.
Claim 7
Dependent Claim
23 words
The system of claim 5, wherein said operating cost of each said processor is further responsive to said purchase price of said processor.
Claim 8
Dependent Claim
23 words
The system of claim 1, wherein said reallocation occurs from said processors with high monetary cost to said processors with low monetary cost.
Claim 9
Dependent Claim
29 words
A The system of claim 1, wherein said controller further reallocates said divisible jobs among said processors to reduce said computing job's monetary cost below a selected cost constraint.
Claim 10
Dependent Claim
15 words
The system of claim 1, wherein said reallocation further minimizes said computing job's finish time.
Claim 11
Dependent Claim
16 words
The system of claim 1, wherein substantially all of said processors' segment finish times are equal.
Claim 12
Dependent Claim
20 words
The system of claim 1, wherein said allocating of said segments is further responsive to each said processor's processing speed.
Claim 13
Independent Claim
47 words
A method for distributing a computing job among a plurality of processors comprising the steps of: determining a monetary cost associated with each said processor; dividing said computing job into segments; and allocating said segments to said processors responsive to said monetary cost of each said processor.
Claim 14
Independent Claim
47 words
A method for distributing a computing job among a plurality of processors comprising the steps of: determining a monetary cost associated with each said processor; dividing said computing job into segments; and allocating said segments to said processors responsive to said monetary cost of each said processor.
Claim 15
Dependent Claim
22 words
The method of claim 12, further including the step of identifying one of said processors with a low said associated monetary cost.
Claim 16
Dependent Claim
18 words
The method of claim 13, wherein said allocating step allocates one of said segments to said identified processor.
Claim 17
Dependent Claim
19 words
The method of claim 12, wherein said determining step polls each of said processors to determine said monetary cost.
Claim 18
Dependent Claim
29 words
The method of claim 15, further including the step of polling each of said processors to determine its availability and wherein said allocation step is responsive to said availability.
Claim 19
Dependent Claim
23 words
The method of claim 12, wherein said determining step checks a predesignated memory location which stores said monetary cost of each said processor.
Claim 20
Dependent Claim
32 words
The method of claim 17, further including the step of reading a predesignated memory location which stores each of said processor's availability and wherein said allocating step is responsive to said availability.
Claim 21
Dependent Claim
25 words
The method of claim 12, wherein said monetary cost of each of said processors is at least responsive to said operating cost of said processors.
Claim 22
Dependent Claim
19 words
The method of claim 19, wherein said monetary cost is further responsive to said purchase price of said processors.
Claim 23
Dependent Claim
25 words
The method of claim 12, further including the step of optimizing said distribution of said divisible job to minimize said computing job's overall monetary cost.
Claim 24
Dependent Claim
34 words
The method of claim 21, wherein said optimizing step includes reallocating portions of said segments distributed from said processors with high said associated monetary costs to said processors with low said associated monetary costs.
Claim 25
Dependent Claim
18 words
The method of claim 22, wherein said computing job's finish time is incrementally extended during said optimizing step.
Claim 26
Dependent Claim
29 words
The method of claim 12, further including the step of optimizing said distribution of said divisible job to reduce said computing job's monetary cost below a selected cost constraint.
Claim 27
Dependent Claim
34 words
The method of claim 24, wherein said optimizing step includes reallocating portions of said segments distributed from said processors with high said associated monetary costs to said processors with low said associated monetary costs.
Claim 28
Dependent Claim
16 words
The method of claim 24, wherein said optimizing step further minimizes said computing job's finishing time.
Claim 29
Dependent Claim
23 words
The method of claim 12, further including the step of distributing said allocated segments and processing said allocated segments on said allocated processors.
Claim 30
Dependent Claim
17 words
The method of claim 12, wherein substantially all of said allocated processors' segment finish times are equal.
Claim 31
Dependent Claim
18 words
The method of claim 12, wherein said allocating step is further responsive to each said processor's processing speed.
Claim 32
Independent Claim
110 words
A method for distributing a received computing job among a plurality of processors with associated monetary costs using a monetary cost ceiling, comprising the steps of: selecting said monetary cost ceiling; determining said monetary cost associated with each said processor when said computing job is received; dividing said computing job into segments and allocating said segments to said processors responsive to said monetary cost of each said processor and said monetary cost ceiling; and distributing said segments to said processors when a total monetary cost for processing said computing job comprising said determined monetary costs of said processors with allocated segments is at or below said selected monetary cost ceiling.
Claim 33
Independent Claim
110 words
A method for distributing a received computing job among a plurality of processors with associated monetary costs using a monetary cost ceiling, comprising the steps of: selecting said monetary cost ceiling; determining said monetary cost associated with each said processor when said computing job is received; dividing said computing job into segments and allocating said segments to said processors responsive to said monetary cost of each said processor and said monetary cost ceiling; and distributing said segments to said processors when a total monetary cost for processing said computing job comprising said determined monetary costs of said processors with allocated segments is at or below said selected monetary cost ceiling.
Claim 34
Dependent Claim
20 words
The method of claim 30, wherein said allocating said segments step is further responsive to each said processor's processing speed.
Claim 35
Dependent Claim
25 words
The method of claim 31, wherein said segment allocated to said processor with the greatest associated monetary cost is reallocated to said other allocated processors.
Claim 36
Dependent Claim
20 words
The method of claim 32, wherein said other allocated processors all finish processing said allocated segments at the same time.
Claim 37
Dependent Claim
18 words
The method of claim 30, wherein said processors are comprised of at least two different types of processors.
Claim 38
Dependent Claim
16 words
The method of claim 30, wherein said dividing step further minimizes said computing job's finishing time.
Claim 39
Dependent Claim
107 words
A controller for distributing a received computing job comprising: means for interfacing with a plurality of processors when said computing job is received, wherein each said processor has an associated monetary cost; means for determining said monetary costs of said processors and for segmenting said computing job into segments to be allocated among said processors, wherein said allocated processors are selected based on said monetary costs, said determining means being coupled to said interfacing means; and means for sending at least one of said allocated segments to at least one of said selected processors and for receiving intermediate results from said selected processors via said interface means.
Claim 40
Dependent Claim
107 words
A controller for distributing a received computing job comprising: means for interfacing with a plurality of processors when said computing job is received, wherein each said processor has an associated monetary cost; means for determining said monetary costs of said processors and for segmenting said computing job into segments to be allocated among said processors, wherein said allocated processors are selected based on said monetary costs, said determining means being coupled to said interfacing means; and means for sending at least one of said allocated segments to at least one of said selected processors and for receiving intermediate results from said selected processors via said interface means.
Claim 41
Dependent Claim
18 words
The controller of claim 36, wherein said processor are comprised of at least two different types of processor.
Claim 42
Dependent Claim
20 words
The controller of claim 36, wherein said monetary cost of each said processor is responsive to said processor's operating cost.
Claim 43
Dependent Claim
17 words
The controller of claim 38, wherein said monetary cost is further responsive to said processor's purchase price.
Claim 44
Dependent Claim
23 words
The controller of claim 36, wherein said controller has an associated monetary cost and is capable of being allocated one of said segments.
Claim 45
Dependent Claim
25 words
The controller of claim 37, further comprising means for reallocating said segments to said processor in order to minimize said computing job's overall monetary costs.
References Cited (Backward Citations)
US5079760A
Cited
US5392429A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-03-29 | 2002-09-28 | 2003-03-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-03-29 | 2006-09-28 | 2007-03-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-03-29 | 2010-09-28 | 2011-03-30 | $7700.00 | Window Closed / Lapsed |