Method for minimizing the number of input terminals used in an operator

• US 5,946,494 A
• Filed: 07/31/1997
• Issued: 08/31/1999
• Est. Priority Date: 08/02/1996
• Status: Expired due to Fees

• Current Assignee: Magnachip Semiconductor Limited (Magnachip Semiconductor)
• Original Assignee: LG Semicon Co Ltd (SK Hynix Inc.)
• Inventors: Kim, Young-No
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Khatri, Anil
• Application Number:
  US08/903,990
• Time in Patent Office: 761 Days
• Field of Search: 395/708, 395/709, 395/705, 395/763, 395/790, 364/146, 364/188, 209/580, 356/326
• US Class Current: 716/132
• CPC Class Codes: G06F 30/30 Circuit design

Abstract

A method for minimizing the number of input terminals used in an operator includes generating a conflict graph having nodes with regard to an output path of data to be processed by the operator, coloring the nodes so that no two nodes directly connected to each other have the same color, and selectively inputting data from the nodes with a first color to a first input terminal of the operator and selectively inputting data from the nodes with a second color to a second input terminal of the operator.

Claims

1. A method for minimizing the number of input terminals used in an operator, comprising:

generating a conflict graph having nodes with regard to an output path of data to be processed by the operator;

selectively coloring the nodes with first and second colors, so that no two nodes directly connected to each other have the same color; and

selectively inputting data from the nodes with a first color to a first input terminal of the operator and data from the nodes with a second color to a second input terminal of the operator.

2. The method of claim 1, wherein in the generating step, first and second nodes are directly connected to each other by an edge a control step.

3. The method of claim 1, wherein the coloring step is performed according to a graph coloring algorithm.

4. The method of claim 1, wherein in the selectively inputting step, when a third color other than the first and second colors is allocated to at least one node, the at least one node is commonly connected to the first and second input terminals of the operator.

5. The method of claim 1, further comprising:

coloring a third node, which is directly connected to both a first node with the first color and a second node with the second color, with a third color.

6. The method of claim 5, further comprising:

selectively inputting data from the third node to both the first and second input terminals of the operator.

7. The method of claim 1, wherein the selectively inputting step directly inputs the data from the nodes with the first color to at least one input terminal of a first multiplexer in the operator.

8. The method of claim 7, wherein the selectively inputting step directly inputs the data from the nodes with the second color to at least one input terminal of a second multiplexer in the operator.

9. The method of claim 8, further comprising:

coloring a third node, which is directly connected to one of the nodes with the first color and one of the nodes with the second color, with a third color.

10. The method of claim 9, further comprising:

selectively inputting data from the third node to both the first and second input terminals of the operator.

11. The method of claim 10, wherein the step of selectively inputting the data from the third node directly inputs the data from the third node to both the at least one input terminal of the first multiplexer and the at least one input terminal of the second multiplexer.

12. The method of claim 8, wherein the operator performs addition.

13. The method of claim 8, wherein outputs of the first and second multiplexers are directly input to an adder of the operator.

14. The method of claim 1, wherein the operator performs one of addition, subtraction, multiplication and division.