Electrical computers and digital processing systems: virtual mac – Task management or control
Reexamination Certificate
2000-09-29
2004-11-23
An, Meng-Al T. (Department: 2127)
Electrical computers and digital processing systems: virtual mac
Task management or control
C718S102000, C718S104000
Reexamination Certificate
active
06823510
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to distributed processing and more particularly, the present invention relates to efficiently assigning tasks across multiple computers for distributed processing.
2. Background Description
Any large, multifaceted project, such as a complex computer program, may be segmented into multiple smaller manageable tasks. The tasks then may be distributed amongst a group of individuals for independent completion, e.g., an engineering design project, distributed processing or, the layout of a complex electrical circuit such as a microprocessor. Ideally, the tasks are matched with the skills of the assigned individual and each task is completed with the same effort level as every other task. However, with such an ideal matched task assignment, intertask communication can become a bottleneck to project execution and completion. Thus, to minimize this potential bottleneck, it is important to cluster together individual tasks having the highest level of communication with each other. So, for example, in distributing eight equivalent tasks to pairs of individuals at four locations, (e.g., eight design engineers in four rooms) optimally, pairs of objects or tasks with the highest communication rate with each other are assigned to individual pairs at each of the four locations.
Many state of the art computer applications are, by nature, distributed applications. End-users sit at desktop workstations or employ palmtop information appliances on the run, while the data they need to access resides on distant data servers, perhaps separated from these end-users by a number of network tiers. Transaction processing applications manipulate data spread across multiple servers. Scheduling applications are run on a number of machines that are spread across the companies of a supply chain, etc.
When a large computer program is partitioned or segmented into modular components and the segmented components are distributed over two or more machines, for the above mentioned reasons, component placement can have a significant impact on program performance. Therefore, efficiently managing distributed programs is a major challenge, especially when components are distributed over a network of remotely connected computers. Further, existing distributed processing management software is based on the assumption that the program installer can best decide how to partition the program and where to assign various-program components. However, experience has shown that programmers often do a poor job of partitioning and component assignment.
So, a fundamental problem facing distributed application developers is application partitioning and component or object placement. Since communication cost may be the dominant factor constraining the performance of a distributed program, minimizing inter-system communication is one segmentation and placement objective. Especially when placement involves three or more machines, prior art placement solutions can quickly become unusable, i.e., what is known as NP-hard. Consequently, for technologies such as large application frameworks and code generators that are prevalent in object-oriented programming, programmers currently have little hope of determining effective object placement without some form of automated assistance. En masse inheritance from towering class hierarchies, and generation of expansive object structures leaves programmers with little chance of success in deciding on effective partitioning.
This is particularly true since current placement decisions are based solely on the classes that are written to specialize the framework or to augment the generated application.
Furthermore, factors such as fine object granularity, the dynamic nature of object-based systems, object caching, object replication, ubiquitous availability of surrogate system objects on every machine, the use of factory and command patterns, etc., all make partitioning in an object-oriented domain even more difficult. In particular, for conventional graph-based approaches to partitioning distributed applications, fine-grained object structuring leads to enormous graphs that may render these partitioning approaches impractical.
Finally, although there has been significant progress in developing middleware and in providing mechanisms that permit objects to inter-operate across language and machine boundaries, there continues to be little to help programmers decide object-system placement. Using state of the art management systems, it is relatively straightforward for objects on one machine to invoke methods on objects on another machine as part of a distributed application. However, these state of the art systems provide no help in determining which objects should be placed on which machine in order to achieve acceptable performance. Consequently, the initial performance of distributed object applications often is terribly disappointing. Improving on this initial placement performance is a difficult and time-consuming task.
Accordingly, there is a need for a way of automatically determining the optimal program segmentation and placement of distributed processing components to minimize communication between participating distributed processing machines.
SUMMARY OF THE INVENTION
It is therefore a purpose of the present invention to improve distributed processing performance;
It is another purpose of the present invention to minimize communication between distributed processing machines;
It is yet another purpose of the invention to improve object placement in distributed processing applications;
It is yet another purpose of the invention to determine automatically how objects should best be distributed in distributed processing applications
it is yet another purpose of the invention to minimize communication between objects distributed amongst multiple computers in distributed processing applications.
The present invention is a task management system, method and computer program product for determining optimal placement of task components on multiple machines for task execution, particularly for placing program components on multiple computers for distributed processing. First, a communication graph is generated representative of the computer program with each program unit (e.g., an object) represented as a node in the graph. Nodes are connected to other nodes by edges representative of communication between connected nodes. A weight is applied to each edge, the weight being a measure of the level of communication between the connected edges. Terminal nodes representative of the multiple computers are attached to the communication graph. Independent nets may be separated out of the communication graph. A cut is made at each terminal node and the weights of the cut edges are summed. The second heaviest terminal is identified from the cut and edges connected to at least in one internal node and not connected to the second heaviest edge are compared against the weight of the second heaviest edge. Any edge found in the comparison to be at least as heavy as the second heaviest terminal node need not be included in the min cut for the communication graph and so, is removed from consideration for the final min cut solution. Finally, program components which may be a single program unit or an aggregate of units are placed on computers according to the communication graph min cut solution.
REFERENCES:
patent: 6266053 (2001-07-01), French et al.
patent: 6437804 (2002-08-01), Ibe et al.
patent: 6629123 (2003-09-01), Hunt
M. Padberg et al., “An Efficient Algorithm For The Minimum Capacity Cut Problem”,Mathematical Programming47 (1990) pps. 19-36 North-Holland.
E. Dahlaus et al., “The Complexity of Multiterminal Cuts”, 1994 Society for Industrial and Applied Mathematics, pps. 864-894.
Hogstedt Karin
Kimelman Douglas N.
Rajan Vadekkadathu T.
Roth Tova
Wegman Mark N.
Ali Syed J
An Meng-Al T.
Herzberg Louis P.
International Business Machines Corp.
Law Office of Charles W. Peterson, Jr.
LandOfFree
Machine cut task identification for efficient partition and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Machine cut task identification for efficient partition and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Machine cut task identification for efficient partition and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3304444