Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-03-13
2002-04-09
Maung, Zarni (Department: 2755)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000
Reexamination Certificate
active
06370560
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a load sharing controller for optimizing the resource utilization cost of computation of the distributed processors within a networked system.
BACKGROUND OF THE INVENTION
Parallel processing techniques divide computer jobs among at least two separate processors to gain computational efficiencies when operating on a large group of data, called a load, or when multiple tasks are required to be performed to complete the operation. It is often more efficient, where possible, to divide a job for concurrent processing among multiple processors in order to complete the computations in a shorter period of time. Loads and tasks to be processed can either be characterized as indivisible or divisible. An indivisible load or task is one that cannot be divided into two or more smaller fragments to be distributed among multiple processors but requires that the load be processed by a single processor.
A divisible load is a load that can be arbitrarily partitioned in a linear fashion for data or by task and can be distributed to more than one processor to achieve a faster solution time. An example of a divisible load is a very long linear data file associated with a simple operation such as the summation of a large set of numbers. Intermediate sums of the list of numbers can be computed on different distributed processors and then later recombined and added together to gain the final solution. A simple example of a divisible task can be shown in the form (3+5)×(8+2). The first two numbers can be added together at the same time as the last two numbers. Of course, this principle of a divisible task is typically applied to much more complex operations where parallel efficiencies would be beneficial.
A more sophisticated example of a divisible load is data representing an input waveform which is to be applied to a series of digital filters to identify the waveform. The data can be segmented and processed on different processors in order to expedite the required computation period. In general, the class of divisible loads includes problems where a number of repetitive and independent operations are performed on very large data files. Examples of divisible loads commonly appear in the areas of signal processing, image processing, massive experimental data, cryptography and experimental data processing. Divisible load theory has the benefit of being completely deterministic without requiring any statistical or probabilistic assumptions. Divisible load theory is generic and therefore robust to changes in underlying network and processing technologies.
Divisible tasks can also be used in the example of these digital filters. Different processes can be used to apply different portions of the filter to an input signal. By segmenting necessary operations, the overall speed of the calculation will be reduced greatly when complex operations are being performed. A divisible task can be an operation that is repeated a very large number of times. For example, a cryptographic operation may attempt to decode enciphered information using one million keys. The individual key attempts can be spread over a number of processors to decrease both the time and dollar cost of performing the operation.
When a divisible load or task is distributed to a number of processors, there is a need for a central controller, which can be one of the processors, to select which processor gets which portion of the load or task and in what order. One scheme is to assign the fastest processor (in terms of computational speed) with as much data as possible within a given time constraint. This speed based load sharing approach must take into account the number of available processors, the speed of each processor, the speed of the communication links, the load origination point and the network architecture.
Previous allocations of controllers have been based solely upon processor speed among networked processors in order to gain time efficiencies by parallel processing the divisible load or task. As computer hardware and communications technology are quickly advancing, an opportunity to link processors located at different remote sites together to compute a load is promising. The Internet currently allows for the fast and cheap communication between processors irrespective of their physical locations. Indeed, the Internet allows for worldwide communication on a relatively inexpensive basis.
Communication costs of the conduit linking a distributed process to the controller (e.g., telephone line charges) are one of the resource utilization costs associated with distributed processing. Different processors also have varied associated resource utilization costs themselves. One minute of processor time on a supercomputer is many orders of magnitude more expensive to operate than on a simple 486 computer platform. Businesses now have the capability of renting out their idle processor time to other users when connected in a global network such as the Internet. Ross Perot, founder of Electronic Data Systems of Texas, made a business out of renting idle time on private mainframe computer installations to run programming. The increased number of different types of processors with varied associated resource utilization costs creates a need for a load sharing controller which assigns divisible loads among distributed processors to minimize the overall resource utilization cost to process the load or task.
SUMMARY OF THE INVENTION
The present invention includes a controller for the allocation of divisible load jobs among a plurality of distributed processor platforms based on their resource utilization costs. The system includes a plurality of processors and a network for connecting the distributed processors where one of the processors is a controller for dividing the computer job to be processed into segments and assigning the segments to the distributed processor platforms based on each processor platform's associated resource utilization cost. The allocation can also be further based on an associated data link cost with each processor platform.
The resource utilization cost of a processor includes the operational cost of the processor itself and the platform upon which it runs. The resource utilization cost can also include a percentage of the purchase price of the computer platform so that the owner of the processor can recoup some of its initial investment. Alternatively, the resource utilization cost can be preselected by the manager of the processor platform and based on such factors as the supply and demand of the processor platform. The controller determines the resource utilization cost of a distributed processor by either polling the processor, checking a predetermined memory location with the information or by calculating the resource utilization cost based on known information.
The controller also optimizes its distribution by allocating portions of the load from a more expensive processor platform to a less expensive processor platform while still maintaining an acceptable finish time to complete the job. The controller can also minimize the finish time of the processors while remaining at or below the cost ceiling.
REFERENCES:
patent: 4769771 (1988-09-01), Lippmann et al.
patent: 5079760 (1992-01-01), Nemirovsky et al.
patent: 5283897 (1994-02-01), Georgiadis et al.
patent: 5392429 (1995-02-01), Agrawal et al.
patent: 5418953 (1995-05-01), Hunt et al.
patent: 5524077 (1996-06-01), Faaland et al.
patent: 5694602 (1997-12-01), Smith
patent: 6014612 (2000-01-01), Larson et al.
patent: 6223205 (2001-04-01), Harchol-Balter et al.
Alonso, “An experimental evaluation of load balancing strategies,”Miami Technicon '87, vol. 21, No. 5, Oct. 1987, pp. 225-228.
Banawan et al., “A comparative study of load sharing in heterogeneous multicomputer systems,” 25th Annual Simulation Symposium, Apr. 1992, pp. 22-31.
Bataineh et al., “Bus-oriented load sharing for a network of sensor driven processors,”IEEE Transactions on Systems, Man and Cybernetics, vol. 21, No. 5, Sep. 1991, p
Charcranoon Saravut
Luryi Serge
Robertazzi Thomas G.
Baker & Botts LLP
Maung Zarni
Opie George L.
Research Foundation of State of New York
LandOfFree
Load sharing controller for optimizing resource utilization... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Load sharing controller for optimizing resource utilization..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Load sharing controller for optimizing resource utilization... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2858839