Method for determining the characteristics of a logic block graph diagram to provide an indication of path delays between the blocks

• US 4,263,651 A
• Filed: 05/21/1979
• Issued: 04/21/1981
• Est. Priority Date: 05/21/1979
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Donath, Wilm E., Hitchcock, Robert B. Sr.
• Primary Examiner(s): Wise, Edward J.
• Application Number:
  US06/040,785
• Time in Patent Office: 701 Days
• Field of Search: 364/300, 364/490-491
• US Class Current: 716/108
• CPC Class Codes: G06F 30/3312 Timing analysis

Abstract

A method is provided which is applied to a logic block diagram, referred to as a block graph, which consists of a plurality of logic blocks interconnected by nets which carry logic signals between the logic blocks. The method is used to determine the characteristics of the given block graph, and more particularly to analyze the block graph to identify critical paths wherein logic signals must arrive at designated blocks at a critical time, and to determine whether the path delays of such critical paths are too long or too short. When critical paths are identified which have path delays that are too long or too short, the block graph can be redesigned to avoid such delays. The method includes three basic, broad steps each of which incorporates a plurality of subsidiary implementation steps. First, from the logic block graph, special blocks defined as storage elements because of their unique function are identified and classified as "level zero" elements. Second, a procedure is carried out which "levelizes" the remaining blocks in the block graph, that is, the blocks will be designated level two, level three, level four etc. in accordance with rules defined within the method. Finally, the long and short path delays, referred to as the extreme characteristics and identified by extreme values are determined for each block in level one, followed by a determination of the extreme characteristics of each block in level two, level three, etc. The extreme characteristics thus identify the critical paths within the logic block which are too long or too short so that a redesign can be made.

Claims

1. A method for determining critical paths within a logic block circuit of the type including a plurality of functional logic block elements interconnected by a plurality of input and output signal conductor paths wherein said plurality of logic blocks includes blocks having a storage element function and wherein said logic block circuit also includes external input conductor paths connected to given ones of said blocks, comprising levelizing of said logic blocks and determining the extreme characteristics of said logic blocks, said levelizing procedure including the steps of:

A. recording in a record means a first list consisting of said logic blocks of said block circuit wherein each of said logic blocks is assigned a different number of a numerical sequence in said list and wherein each of said storage element blocks in said list is designated as a storage element by a unique indicator,

B. selecting from said record means one of said storage element logic blocks recorded in said numerical list and recording in said record means said selected storage element logic block as the initial entry in a second list referred to as an "in-process chain", and assigning a level number "L" of ZERO to said storage element logic block in said second list and designating in said second list that said storage element logic block has been assigned a level,

C. selecting each logic block in said logic block circuit having an input conductor connected to an output conductor of said ZERO level number storage element and recording in said record means each said selected logic blocks in a third list referred to as a "to-be-leveled" chain,

D. determining from said logic block circuit those logic blocks listed in said "to-be-leveled chain" third list which have other input conductors which are connected only to external input conductors and to output conductors from zero level number logic blocks, and removing such determined logic blocks from said "to-be-leveled chain" third list in said record means,

E. assigning a level number "L" of ONE to each of said logic blocks determined in step D, adding said logic blocks to said "in-process chain" second list on said record means, and designating in said second list that said logic blocks have been assigned a level number "L" of ONE,

F. determining from said logic block circuit each of those logic blocks having input conductors connected to output conductors from said logic blocks previously determined in step D and which are not recorded on said "to-be-leveled chain" third list and which are not storage element blocks and which do not have a level number "L" assigned thereto and recording each of said determined logic blocks in said "to-be-leveled chain" third list in said record means,

G. and continually repeating steps E and F for the remaining blocks in said logic block circuit and increasing said level number "L" by one increment for each repeat until no block is assigned to the last incremented level number values or no blocks remain listed in said "to-be-leveled chain" third list such that all said logic blocks in said logic circuit have been assigned to a level designated by a level number "L" wherein level ZERO blocks are storage element blocks, level ONE blocks have inputs only from external input conductors and storage element block outputs, and blocks assigned to successive levels have inputs only from external input conductors, storage element blocks and outputs from logic blocks of proceeding levels.

2. A method according to claim 1 wherein steps C and F include the sub-step of recording in said record means a "global block assignment" indication to indicate that at least one logic block has been assigned a level "L" and wherein step D and G include the sub-step of removing said "global block assignment" indication from said record means when said level "L" has been increased by one increment, "said global block assignment" indication serving to provide an indication when a level has been reached to which no logic blocks have been assigned so that steps F and G are no longer repeated.

3. A method according to claim 1 wherein said steps C and F include the sub-step of recording in said record means a "being-leveled" indication for each logic block recorded in said "to-be-leveled" third list.

4. A method according to claim 3 wherein said steps E and G include the sub-step of removing from said record means said "being-leveled" indication and recording a "leveled" indication for each of said logic blocks which have been assigned a level number "L".

5. A method according to claim 1 wherein each of said logic blocks including said storage element blocks of said logic block circuit have a specified internal function value effecting the passage of a signal to the output conductors of said blocks referred to as block function value, and

wherein each of said external input conductors to said logic blocks have a specified input function valve effecting signals applied as inputs to said logic blocks,

said extreme characteristic determination procedure of the method of claim 1 including the steps of:

H. from said specified input function values of said external input conductors connected as inputs to said logic blocks assigned to level ONE and from said specified block function values of said ZERO level storage elements connected as inputs to said level ONE logic blocks, in combination with said block function values of said level ONE logic blocks connected to said external input conductors and storage elements, determining output function values for the outputs of each of said logic blocks assigned to level ONE, one of which output function values for each level ONE logic block being the most extreme of said block output function values,

I. from said specified input function values of said external input conductors connected as inputs to logic blocks assigned to level TWO from said specified block function values of said ZERO level storage elements connected as inputs to said level TWO logic blocks and from said outputs of said level ONE logic blocks connected as inputs to said level TWO logic blocks, combined with said block function values of said level TWO logic blocks, determining output function values for the outputs of each of said logic blocks assigned to level TWO, one of which output function values for each level TWO block being the most extreme of said block output function values,

and continually repeating step I for determining the output function values for each of the logic blocks assigned to successive levels of said logic block circuit, using said specified input function values of said external input conductors, said specified block function values of said ZERO level storage element blocks and said determined output function values of said preceding level logic blocks which are connected as inputs to said successive level logic blocks until the output function value including the extreme output function value for each of said logic blocks in each of said levels of said logic block circuit has been determined.

6. A method according to claim 5 wherein said specified internal function value is the amount a signal is time delayed in each of said logic blocks, wherein said input function value of said external input conductors is the arrival time of a signal at a logic block connected to said external input conductors, wherein said output function values for the outputs of said logic blocks are the arrival times of the signals to said logic blocks combined with said time delay in said logic blocks, and wherein said extreme output function value is the maximum time delay at the output of each logic block as a factor of the said combination of the latest arrival time of an input signal to each block and the amount said latest arrived signal is time delayed in each logic block.

7. A method according to claim 5 wherein said specified internal function value is the amount a signal is time delayed in each of said logic blocks, wherein said input function value of said external light conductors is the arrival time of a signal at a logic block connected to said external input conductors, wherein said output function values for the outputs of said logic blocks are the arrival times of the signals to said logic blocks combined with said time delay in said logic blocks, and wherein said extreme output function value is the minimum time delay at the output of each logic block as a factor of the said combination of the earliest arrival time of an input signal to each block and the amount said earliest arrived signal is time delayed in each logic block.