Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-09-24
2002-12-17
Homere, Jean R. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C709S241000, C709S241000, C709S241000, C709S201000
Reexamination Certificate
active
06496823
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to computer-implemented processing systems, and, in particular, to a technique for apportioning a work unit to execute in parallel in a heterogeneous environment.
2. Description of Related Art
A relatively recent innovation in computer systems has been to distribute processing of units of work (e.g., a unit of work may be a computer task that selects data from a database) to multiple computer systems connected by a network. Each distributed computer system has one or more processors for executing units of work. A distributed computer system has many advantages over a centralized scheme with regard to flexibility and cost effectiveness.
When a computer system consists of multiple processors (i.e., central processors or “CPs”), each processor may have a different processing power. A processor is part of a computer system that executes instructions to complete a unit of work. Processor power indicates how quickly a processor is able to execute a unit of work. Typically, the processing power is represented with reference to how many millions of instructions per second (MIPS) that a processor executes.
A multitude of configurations are possible for a multi-processor computer system. For example, a user might wish to run a query (i.e., which is an example of a unit of work) in a computer system that consists of a 2-way system (i.e., a computer system that includes 2 processors) and an 8-way system (i.e., a computer system that includes 8 processors).
In a distributed environment, work generated at one computer system on the network may be divided and distributed to other computer systems on the network for processing. In many situations, the workload is not distributed efficiently. For example, a slower processor may be given the same amount of work as a faster processor. If this were to happen, the faster processor would complete its processing and wait for the slower processor to complete its processing. It is a waste of resources to let the faster processor wait idly. Thus, to efficiently utilize the processors, it is desirable to make optimal assignments of work to each available processor.
Some conventional computer systems that distribute work across processors require a homogeneous configuration. In a homogeneous configuration, each processor has the same processing power. In a homogeneous configuration, work is simply apportioned evenly across each processor (i.e., each processor is given the same amount of work). However, the homogeneous configuration is not always the way users grow their computer systems.
One implication of the ability of networked computer systems to grow or shrink with time is that processors within each computer system may be entirely different. Some processors may be purchased at later times and have advantages due to improved technology, and some processors may have more processing power than others. Additionally, the networked computer systems may originally contain processors optimized for different purposes, from desktop computers to massively parallel processors (MPP's).
In a heterogeneous environment, each processor may have a different processing power. Therefore, apportioning work in a heterogeneous environment is challenging. Some conventional computer systems divide a work unit into even portions and distribute the same amount of work to each processor, regardless of the processing power of each processor. In this case, it is likely that slower processors will create a bottleneck that can affect the total elapsed time of processing the work unit. Additionally, dividing a work unit up evenly may prevent the full use of a faster processor's capabilities since the slowest processor in the configuration will always be the last to finish.
One aspect of the flexibility of networked computer systems is that their configuration can be changed easily. For example, a processor in a computer system assigned to the accounting department might be available to every computer system belonging to the network of computer systems most of the time; but, when the accounting department has a peak load, that processor may be made unavailable to the network of computer systems for a day to dedicate it to the work of the accounting department. Additionally, due to fluctuations in the workload, or due to imperfections in the work allocation technique, some processors may develop a backlog of work that has been assigned to them, while other processors are idle.
There is a need for improved allocation technique to provide efficient allocation of work to processors.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method, apparatus, and article of manufacture for a computer-implemented apportioning system.
In accordance with the present invention, work is distributed to processors in a multi-processor computer system. Initially, during bind-time, a scaling factor is determined for each processor. The scaling factor represents relative processing power in relation to each other processor. Then, portions of a total amount of work are distributed to each processor based on the determined scaling factor of that processor and a determined amount of work for an average processor.
An object of the invention is to provide an improved technique for distributing work across processors in one computer system. Another object of the invention is to provide a technique for distributing work across computer systems having one or more processors and connected by a network. Yet another object of the invention is to provide a technique for distributing work across processors so that each of the processors completes processing at approximately the same time.
REFERENCES:
patent: 4403286 (1983-09-01), Fry et al.
patent: 5271003 (1993-12-01), Lee et al.
patent: 5283897 (1994-02-01), Georgiadis et al.
patent: 5325525 (1994-06-01), Shan et al.
patent: 5369570 (1994-11-01), Parade
patent: 5535322 (1996-07-01), Hecht
patent: 5537319 (1996-07-01), Schoen
patent: 5581737 (1996-12-01), Dahlen et al.
patent: 5590319 (1996-12-01), Cohen et al.
patent: 5630129 (1997-05-01), Wheat
patent: 5694602 (1997-12-01), Smith
patent: 5898870 (1999-04-01), Okuda et al.
patent: 5970495 (1999-10-01), Baru et al.
patent: 6058267 (2000-05-01), Kanai et al.
patent: 6185601 (2001-02-01), Wolff
patent: WO 97/04384 (1997-02-01), None
“Dynamic Load Sharing for Distributed Computing Environment”,IBM® Technical Disclosure Bulletin,38(7):511-515 (Jul. 1995).
“Workload Balancing in a Distributed Environment,”IBM® Technical Disclosure Bulletin,38(11):273-276 (Nov. 1995).
“Data-Dependent Workload Balancing”,IBM® Technical Disclosure Bulletin,39(1):65-68 (Jan. 1996).
“Rendering OpenGL in a Processor Subsystem”,IBM® Technical Disclosure Bulletin,39(3):137-139 (Mar. 1996).
“Scheduling Enhancement—Process Locking”IBM® Technical Disclosure Bulletin,39(8):227-229 (Aug. 1996).
Kerin, R. et al., “Product Hierarchy and Brand Strategy Influences on the Order of Entry Effect for Consumer Packaged Goods”,J. Prod. Innov Manag,13:21-34 (1996).
Blank Ted Eric
Dang Tammie
Lin Fen-Ling
Nakagawa Randy Mitchell
Smith Bryan Frederick
Homere Jean R.
Sughrue Mion Zinn Macpeak & Seas, PLLC
LandOfFree
Apportioning a work unit to execute in parallel in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apportioning a work unit to execute in parallel in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apportioning a work unit to execute in parallel in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2962946