Computer graphics processing and selective visual display system – Display driving control circuitry – Controlling the condition of display elements
Reexamination Certificate
1997-10-23
2002-08-20
Bayerl, Raymond J. (Department: 2173)
Computer graphics processing and selective visual display system
Display driving control circuitry
Controlling the condition of display elements
C709S223000, C345S215000
Reexamination Certificate
active
06437804
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to automatic partitioning of graphs and more particularly to automatic partitioning of communication networks and other physical systems.
2. Discussion of the Related Art
Many physical systems can be modeled by a graph. These include communication networks, distributed computing systems, production systems and printed circuit board layouts.
Graph partitioning belongs to a class of problems called NP-complete problems (Garey, M. R. and D. S. Johnson,
Computers and Intractability: A Guide to the Theory of NP Completeness
, W.H. Freeman & Co., 1979). An NP-complete problem is a problem which can only be solved by the complete enumeration of all the feasible solutions (i.e., those that satisfy all the constraints imposed on the problem) from which the best solution will be chosen. This is a very inefficient method of solving large problems. Unfortunately, there is no known efficient method of solving this class of problems, and this has often necessitated the use of heuristic methods. Heuristic methods are intended to produce good, but not necessarily optimal, solutions.
One of the earliest methods of solving the problem is the spectral partitioning method (Pothen, A. et al., “Partitioning Sparse Matrices with Eigenvectors of Graphs,” SIAM J. of Matrix Analysis. and Applications, 11(3):430-452 (1990); Hendrickson, B. and R. Leland, “A Multilevel Algorithm for Partitioning Graphs,” Technical Report, SAND93-1301, Sandia National Labs (1993)). However, this method is very expensive since it requires the computation of the eigenvector corresponding to the second smallest eigenvalue. Thus, the method is limited in practice to graphs of very small sizes.
Another method of solving the problem is the geometric partitioning method (Miller, G. et al., “A Unified Geometric Approach to Graph Separators,”
Proc of
31
st Annual Symposium on Foundation of Computer Sci
., 538-547 (1991); Heath, M. and P. Raghavan, “A Cartesian Nested Dissection Algorithm,” Tech. Report UIUCDCS-R-92-1772, Dept. of Computer Sci., Univ. of Ill., Urbana, Ill. (1992); Nour-Omid, B. et al., “Solving Finite Element Equations on Concurrent Computers,”
Am. Soc. of Mech. Engineers
, 291-307, (A. K. Noor, ed. 1986)). However, this method provides partitions that are worse than those of the spectral method. A major limitation of this method is that it requires knowledge of the coordinates of the vertices of the graph. Unfortunately, in many areas, such as communication networks and VLSI design, there is no geometry or “coordinates” associated with the graph.
A multilevel partitioning method has also been proposed (Bui, T. and C. Jones, “A Heuristic for Reducing Fill in Sparse Matrix Factorization,”
Proc. of
6
th SIAM Conf. on Parallel Processing for Scientific Computing
, 445-452 (1993); Cheng, C. and Y. Wei, “An Improved Two-way Partitioning Algorithm with Stable Performance,”
IEEE Trans on Computer
-
Aided Design
, 10(12):1502-1511 (1991); Hagen, L. and A. Kahng, “Fast Spectral Method for Ratio Cut Partitioning and Clustering,”
Proc of IEEE International Conf on Computer
-
Aided Design
, 10-13 (1991); Hagen, E. and A. Kahng, “A New Approach to Effective Circuit Clustering,”
Proc of IEEE International Conf on Computer-Aided Design
, 422-427 (1992); Garbers, J. et al., “Finding Clusters in VLSI Circuits,”
Proc. of IEEE International Confon Computer
-
Aided Design
, 520-523 (1990); Karypis, G. and V. Kumar, “A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs,” Technical Report 95-035, Dept. of Computer Sci., Univ of Minn., Minnesota, Minn. (1995)). This method coarsens the graph (i.e., reduces the size of the graph) by collapsing the nodes and edges; it partitions the smaller graph, and then uncoarsens it to construct a partition of the original graph. Unfortunately this method is very complicated and has not yet been shown to be better than the other two methods.
In all the above methods, it is assumed that the graph is not weighted. This means that all the nodes are essentially identical and the only objective is to partition the graph to generate an equal number of nodes in each partition. When weights are associated with either the nodes or the edges, none of these methods will work adequately. Moreover, the cost of solving the problem will be very high. None of these methods has been proposed for use in a communication network.
SUMMARY OF THE INVENTION
The present invention is a method for automatically partitioning node-weighted, edge-constrained graphs. In contrast with the prior art, the present invention automatically manipulates the nodes of a graph to partition the graph without the need for manually configuring each node. The present invention uses a software control mechanism to partition the graph and, if necessary, to re-partition the graph, without the need to manually intervene in the configuration of the network.
According to one embodiment of the present invention, a method is provided for partitioning a network comprising modeling the network as a graph comprising nodes which represent network devices, and edges which represent links between the devices, and automatically partitioning the graph into domains. Preferably, the method further includes a step of assigning a weight to each node in the graph, and the partitioning step includes balancing partitions as a function of the weight of each node in a respective partition.
In another embodiment of the invention, a method is provided for developing a partitioning scheme for a communication network having a plurality of interconnected devices. The method includes automatically determining a topology of the communication network, automatically partitioning the communication network into a number of domains, each including a number of the plurality of devices, and informing each of the number of devices in each of the domains of partitioning information.
In another embodiment of the invention, a method is provided for automatically partitioning a graph into domains, the graph having a plurality of nodes interconnected by a plurality of edges. The method includes identifying a number of anchor nodes in the graph, combining the nodes into a number of control groups which number is the same as the number of domains, such that each control group includes only one anchor node.
In yet another embodiment of the invention, a method is provided for operating a partitioned communication network having a plurality of network devices interconnected by a plurality of communication links. The method comprises detecting a failure of a network device, automatically generating a new partition based on a topology of the network without the failed device and operating the communication network using the automatically-generated partition. The automatic generating step includes determining the topology of the network without the failed device. The topology is a graph representation of the communication network having nodes representing the network devices and edges representing the communication links. The method further includes identifying supernodes in the graph representation, forming a plurality of clusters of nodes based on the identified supernodes and generating new domains based on the clusters.
Such an automated system has the advantage that it can have a built-in mechanism that allows the network control agents to monitor one another's status. They cooperatively take over the control of a domain whose control agent has failed. Similarly, when the failed device comes up again, the other agents relinquish control of its domain.
Another advantage of an automated system is load balancing. A manually configured system is generally static and does not respond easily to the load changes in the system. An automated system partitions the system into as many domains as there are available control agents and ensures that each agent has a fair share of the load (or traffic). Typically, there is in the background a continuous monitoring of the load distribu
Dev Roger
Ibe Oliver
Vaishnavi Vick
Aprisma Management Technologies, Inc
Bayerl Raymond J.
Coryea Paul M.
Hailu Tadesse
LandOfFree
Method for automatic partitioning of node-weighted,... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for automatic partitioning of node-weighted,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for automatic partitioning of node-weighted,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2916856