Pulse or digital communications – Repeaters – Testing
Patent
1995-07-31
1998-06-30
Oberley, Alvin E.
Pulse or digital communications
Repeaters
Testing
375708, 375705, G06F 945
Patent
active
057747300
ABSTRACT:
A method and apparatus for coloring an interference graph yields a higher number of colored nodes by taking into consideration the colors of neighbors of a node's uncolored constrained neighbors. By assigning a color to a node that is also the color of a neighbor of an uncolored constrained neighbor, one color constraint is removed, increasing the probability of coloring the uncolored constrained neighbor. If more than one of the neighbors of the uncolored constrained neighbors are colored, one of the colors may be selected over the others using an appropriate heuristic.
REFERENCES:
patent: 4571678 (1986-02-01), Chaitin et al.
patent: 5249295 (1993-09-01), Briggs et al.
Peter E. Bergner, Peter J. Dahl, and Matthew T. O'Keefe, Spill Code Minimization Via Arc Spilling, Unversity of Minnesota Manuscript, Department of Electrical Engineering, 1993.
Preston Briggs, Register Allocation via Graph Coloring, PhD Thesis, Rice University, 1992.
Preston Briggs, Keith D. Cooper, and Linda Torczon, Coloring Register Pairs, ACM Letters on Programming Languages and Systems, ACM Press, vol. 1, No. 1, Mar. 1992, pp. 3-13.
David Callahan & Brian Koblenz, "Register Allocation via Hierarchical Graph Coloring", Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, SIGPLAN Notices, vol. 26, No. 6, pp. 192-203 (Jun. 1991).
Fred C. Chow & John L. Hennessy, "The Priority-Based Coloring Approach to Register Allocation", ACM Transaction on Programming Languages and Systems, vol. 12, No. 4, pp. 501-536 (Oct. 1990).
David Bernstein, Dina Goldin, Martin Golumbic, Hugo Krawczyk, Yishay Mansour, Itai Nahshon and Ron Pinter, Spill Code Minimization Techinques for Optimizing Compilers, ACM SIGPLAN Conference on Programming Languages Design and Implementation, 1989.
Preston Briggs, Keith D. Cooper, Ken Kennedy, and Linda Torczon, Coloring Heuristics for Register Allocation, ACM SIGPLAN Conference on Programming Languages Design and Implementation, 1989.
Fred C. Chow & John L. Hennessy, "Register Allocation by Priority-Based Coloring", Proceedings of the ACM Symposium on Compiler Construction, pp. 222-232 (Jun. 1984).
Auslander & Hopkins, An Overview of the PL.8 Compiler, ACM SIGPLAN Notices, vol. 17, No. 6, Jun. 1982.
Gregory J. Chaitin, "Register Allocation & Spilling via Graph Coloring", Proceedings of the ACM Symposium on Compiler Construction, pp. 98-105 (Jun. 1982).
Gregory J. Chaitin, Marc A. Auslander, Ashok E. Chandra, John Cocke, Martin E. Hopkins and Peter W. Markstein, Register Allocation via Graph Coloring, Computer Languages, 6:47-57, 1981.
Aizikowitz Nava Arela
Asnash Liviu
Bar-Haim Roy
Edelstein Orit
Namolaru Mircea
International Business Machines - Corporation
Martin Derek P.
Oberley Alvin E.
Rosenholm R. S.
LandOfFree
Method and apparatus for improving colorability of constrained n 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 and apparatus for improving colorability of constrained n, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for improving colorability of constrained n will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1870891