Method for constructing a planar equal path length clock tree

A method of automatically constructing a clock tree for coupling a plurality of clock sinks to a clock source in an integrated circuit, the method comprising the computer-implemented steps of:

• (A) determining a first distance from each of a set of uncoupled clock sinks to said clock source;
• (B) choosing a first of said set of uncoupled clock sinks such that said first distance corresponding to said first clock sink is the largest amongst all of said set of uncoupled clock sinks;
• (C) forming a first branch wire of said clock tree between said first clock sink and said clock source and subsequently removing said first clock sink from said set of uncoupled clock sinks;
• (D) finding a corresponding minimal balance point on said clock tree for each of said set of uncoupled clock sinks;
• (E) determining a second distance from each of said uncoupled clock sinks to its corresponding minimal balance point;
• (F) choosing a second of said set of uncoupled clock sinks such that said second distance corresponding to said second clock sink is the largest amongst all of said set of uncoupled clock sinks;
• (G) forming a second branch wire of said clock tree between said second clock sink and its corresponding minimal balance point and subsequently removing said second clock sink from said set of uncoupled clock sinks;
• and
• (H) repeating steps (D)-(G) until said set of uncoupled clock sinks is empty.

A method of automatically creating a clock tree for coupling a plurality of clock sinks to a clock source in an integrated circuit, said method comprising the steps of:

• (A) creating a first branch wire of said clock tree between said clock source and a first of a set of uncoupled clock sinks, wherein said first clock sink is selected such that a first distance from said clock source to said first clock sink is the largest amongst all of said set of uncoupled clock sinks;
• (B) removing said first clock sink from said set of uncoupled clock sinks;
• (C) creating a second branch of said clock tree between a second of said set of uncoupled clock sinks and a corresponding balance point on said first branch,
• wherein said second clock sink is selected from said set of uncoupled clock sinks according to a maximum rule, and said corresponding balance point is selected amongst a set of possible balance points according to a minimum rule,
• wherein said maximum rule states that a distance between said second clock sink and said balance point is the largest amongst all uncoupled clock sinks, and
• wherein said minimum rule states that a distance between said second clock sink and said corresponding balance point is the smallest amongst all of said possible balance points;
• (D) removing said second balance point from said set of uncoupled clock sinks;
• and
• (E) repeating steps (C) and (D) until said set of uncoupled clock sinks is empty.

A method of automatically creating a clock tree for coupling a plurality of clock sinks to a clock source in an integrated circuit, said method comprising the steps of:

• (A) creating a first branch wire of said planar clock tree between said clock source and a first of a set of uncoupled clock sinks, wherein said first clock sink is selected such that a first distance from said clock source to said first clock sink is maximized among all of said plurality of clock sinks, and wherein said first clock sink is subsequently removed from said set of uncoupled clock sinks;
• (B) creating a second branch wire of said planar clock tree between a second of said set of uncoupled clock sinks and a corresponding balance point on said first branch,
• wherein said second clock sink is selected from said set of uncoupled clock sinks according to a maximum rule, and said corresponding balance point is selected from a set of possible balance points according to a minimum rule,
• wherein said maximum rule states that a distance between said second clock sink and said balance point is the largest amongst all of said uncoupled clock sinks, and
• wherein said minimum rule states that a distance between said second clock sink and said corresponding balance point is the smallest amongst all of said possible balance points;
• (C) removing said second clock sink from said set of uncoupled clock sinks;
• (D) creating a cluster comprising a set of said uncoupled clock sinks, wherein said cluster is bounded on a first side by said first branch wire and on a second side by said second branch wire;
• (E) creating a third branch of said planar clock tree between a third of said set of uncoupled clock sinks and its corresponding balance point according to said minimum rule and said maximum rule, wherein said minimum rule and said maximum rule are applied only to all of said set of uncoupled clock sinks comprising said cluster;
• and
• (F) removing said third clock sink from said set of uncoupled clock sinks.

A method of creating a rectilinear clock tree in an integrated circuit comprising the steps of:

• (A) providing a planar rectilinear clock tree comprising a set of horizontal and vertical wires,
• (B) deleting a first of said set of horizontal and vertical wires of said rectilinear clock tree to create a first clock subtree and second clock subtree;
• and
• (C) creating a new branch wire by reconnecting said first clock subtree and said second clock subtree, wherein said new branch wire is a length that will produce a predetermined tolerable clock skew.