Net zeroing for efficient partition and distribution

Details Net zeroing for efficient partition and distribution Net zeroing for efficient partition and distribution

2005-03-01

2005-03-01

An, Meng-Al T. (Department: 2127)

Electrical computers and digital processing systems: virtual mac

Task management or control

C718S102000, C709S226000, C719S310000

Reexamination Certificate

active

06862731

ABSTRACT:
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 ones of the multiple computers are attached to the communication graph. Independent nets may be separated out of the communication graph. For each net, non-terminal nodes adjacent to all of terminal nodes on the net and connected to the net by non-zero weighted edges are identified For each identified non-terminal node, the smallest weight for any terminal edge is identified and the weight of each terminal edge is reduced by the value of that smallest weight, the weight of terminal edges having the smallest weight being reduced to zero. After reducing weights on any terminal edges, The min cut solution is obtained from the reduced graph and 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. Dahlhaus et al., “The Complexity of Multiterminal Cuts”, 1994 Society for Industrial and Applied Mathematics, pps. 864-894.

Affiliated with

Also associated with

Rating

Net zeroing for efficient partition and distribution does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Net zeroing for efficient partition and distribution, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Net zeroing for efficient partition and distribution will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3441935