Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1999-01-19
2001-08-14
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S441000, C345S442000
Reexamination Certificate
active
06275238
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a path compression system for compressing paths in graph information and a path compression method thereof and more particularly to a path compression system for compressing paths included in data (called graph information, hereinafter) having such a graphic structure as a logic circuit and a path compression method thereof.
2. Description of the Prior Art
According to conventional path compression systems, it has been necessary to hold the halfway result of a search on the way of a path upon search of the path. In case the halfway result is obtained by a computer, the large capacity of a memory has been needed. In prior art documents of the above-described types of compression systems is included “Method for Increasing Speed of Timing Analysis System HEART (1) to Large Scale Circuit” (a Fifth National Conference of Information Processing Society of Japan 7F-6) (referred to as a prior art document 1, hereinafter).
Further, a path compression system has been known in which the halfway result of a search is not held during the search of the path. In this case, however, much processing time has been required. As prior art documents of this kind of compression system is included “Delay Time Analysis System-NELTAS 2-” (Information Processing Society of Japan, Design Automation Seminar Document, Design Automation 14-3, 1982) (referred to as a prior art document 2, hereinafter).
Furthermore, in attempting to reduce the capacity of a memory, a path compression system for compressing data has been known, however, the 1 conventional compression system of this kind has not performed a sufficient compression ratio. As prior arts of this kind of compression system is incorporated Japanese Unexamined Patent Publication No. Shouwa 62-202268 (referred to as a prior art document 3, hereinafter).
As described above, in the case of a technique disclosed in the prior art document 1 in the conventional path compression systems mentioned above, the halfway result of a search must be held during the search of the path. Therefore, if the halfway result is obtained on a computer, a large capacity of a memory will be undesirably needed.
Further, in the case of a technique disclosed in the prior art document 2, there has been disadvantageously a problem that much processing time is taken.
Furthermore, in the case of a technique disclosed in the prior art document 3, there has arisen an inconvenience that a compression cannot be completed even when data is compressed in order to reduce the capacity of a memory.
SUMMARY OF THE INVENTION
Accordingly, it is a principal object of the present invention to overcome the disadvantages of the prior art systems. More specifically, an object of the present invention is the provision of a path compression system and a path compression method thereof in which the paths of graph information can be completely compressed even if any graph information is stored in a graph information storing means.
A path compression system according to the present invention comprises:
a graph information storing means for storing graph information;
a linear type path compression means for compressing a linear type path information in the graph information;
an entry type path compression means for compressing an entry type path information in the graph information;
a branch type path compression means for compressing a branch type path information in the graph information;
a multi-path type path compression means for compressing a multi-path type path information in the graph information;
a cross type path compression means for compressing a cross type path in the graph information; and
a compression control means for entirely applying the linear type path compression means, the entry type path compression means, the branch type path compression means, the multi-path type path compression means and the cross type path compression means to the graph information stored in the graph information storing means to compress the path information.
The compression control means comprises:
a means for deciding whether or not there is no compression effect even when any of the linear type path compression means, the entry type path compression means, said the branch type path compression means, the multi-path type path compression means and the cross type path compression means are applied to a noticed node in the graph information; and
a means for calling respectively the linear type path compression means, the entry path type compression means, the branch type path compression means, the multi-path type path compression means and the cross type path compression means for the noticed node when the compression effect is attained and performing respective compression control processes therefor; and
a means for making all nodes as the noticed node.
The linear type path compression means comprises:
a means for deciding whether or not the number of arcs in the input direction of the noticed node is one and the number of arcs in the output direction is one;
a means for accumulating the additional delay time of the noticed node, the delay time of the arc in the output direction, the delay time of the element of the arc in the input direction and the delay time of the arc in the input direction to have the newly delay time of the arc in the input direction, when the decided result is “YES;”
a means for regarding the delay time of the element of the arc in the output direction as the delay time of the element of the arc in the input direction;
a means for changing the output side connection of the arc in the input direction to the output side node of the arc in the output direction from the noticed node; and
a means for deleting the noticed node and the arc in the output direction.
The entry type path compression means comprises:
a means for deciding whether or not the number of arcs in the input direction of the noticed node is two or more and the number of arcs in the output direction is one;
a means for accumulating the additional delay time of the noticed node, the delay time of the arc in the output direction, the delay time of the elements of the arcs in the input direction of the noticed node and the delay time of the respective arcs in the input direction to have the delay times of the elements of the respective arcs in the input direction when the decided result is “YES;”
a means for regarding the delay time of the element of the arc in the output direction as the delay time of the elements of the respective arcs in the input direction;
a means for changing the output side connections of respective nodes in the input direction to the output side node of the arc in the output direction from the noticed node; and
a means for deleting the noticed node and the arc in the output direction.
The branch type path compression means comprises:
a means for deciding whether or not the number of arcs in the input direction of the noticed node is one and whether or not the number of arcs in the output direction is two or more;
a means for accumulating the additional delay time of the noticed node, the delay time of the arc in the input direction, the delay time of the element of the arc in the input direction and the delay time of the respective arcs in the output direction to have the delay times of the respective arcs in the output direction when the decided result is “YES;”
a means for changing the input side connections of nodes in the output direction to the input side node of the arc in the input direction from the noticed node; and
a means for deleting the noticed node and the node in the input direction.
The multi-path type path compression means comprises:
a means for deciding whether or not there exist the same combinations of input side nodes and output side nodes in all the arcs in the input direction of the noticed node; and
a means for deleting all other arcs except an arc the sum of its delay time and the delay time of the element of which is maximum among arcs to be processed when the decided result is “YES.”
Brier Jeffery
Havan Thu-Thao
NEC Corporation
Sughrue Mion Zinn Macpeak & Seas, PLLC
LandOfFree
Path compression system for compressing path in graph... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Path compression system for compressing path in graph..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Path compression system for compressing path in graph... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2500528