Logic synthesis for logic array modules

• US 5,754,824 A
• Filed: 05/10/1995
• Issued: 05/19/1998
• Est. Priority Date: 05/10/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Spillinger, Ilan Yitshak, Van Ginneken, Lukas Paul Pieter Pepijn, Damiano, Robert, Trevillyan, Louise Helen
• Primary Examiner(s): Trammel, James P.
• Assistant Examiner(s): Siek, Vuthe
• Application Number:
  US08/437,918
• Time in Patent Office: 1,105 Days
• Field of Search: 395/500, 364/488-491, 364/500
• US Class Current: 716/103
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]

Abstract

A general approach to the synthesis of logic array modules (LAMs) is used to implement a multilevel combinational acyclic network. The network consists of abstract gates, which perform primitive logic functions and nets to connect them. The inputs to the entire network are called the primary inputs and the outputs of the entire network are the primary outputs. The first step in the synthesis of the LAMs used to implement the network is to partition the network vertically to define a plurality of logic segments wherein each output of a logic segment can potentially be implemented in a single logic array module. The second step is to partition horizontally the plurality of logic segments to reduce the size of the segments to a size that can efficiently be implemented as a logic array module. A symbolic representation is generated in a logic array module table of an internal structure of the logic array module based on the horizontally partitioned logic segments.

Claims

1. A method for the efficient synthesis of logic array modules (LAMs) implementing a logic function said logic function being defined by a multi-level combinational acyclic logic network, inputs to the network being primary inputs and outputs from the network being primary outputs, said method comprising the steps of:

logically partitioning vertically the logic network to define a plurality of logic segments wherein each output of a logic segment can potentially be implemented in a single logic array module;

logically partitioning horizontally the plurality of logic segments to reduce the size of the segments to a size that can be efficiently implemented as a logic array module; and

generating a symbolic representation in a logic array module table of an internal structure of the logic array module based on the horizontally partitioned logic segments,

wherein in the step of logically partitioning vertically, a physical limit is imposed on the number of products in the logic array module and further comprising the step of estimating an upper bound on the number of products needed to implement said output, where the function of said output is represented as a reduced ordered binary decision diagram and where the number of products of a node in the diagram is not more than the sum of the estimates of the number of products for its inputs and where the number of products at the inputs of nodes without predecessors is zero.

2. The method of claim 1 further comprising the step of estimating an upper bound on the number of products needed to implement the output, where the number of products of a function defined by an AND gate does not contain more products than the multiplied estimates of the number of products of its inputs, where the number of products of a function defined by an OR gate does not contain more products than the sum of the estimates of the number of products of its inputs and where the number of products of a primary input is one.

3. The method of claim 2, wherein ##EQU3## is a function as a sum of products p₁, P(F)=n is the number of products of F, and ##EQU4## is the maximum number of literals in the products, and wherein, in the step of vertically partitioning, a physical limit is imposed on the number of literals in each of said products and further comprising the step of estimating an upper bound on the maximum number of literals needed to implement said output, where the maximum number of literals in a function defined by an AND gate does not contain more literals than the sum of the estimates of the number of literals of its inputs, and where the maximum number of literals in a function defined by an OR gate does not contain more literals than the largest estimate of the number of literals in each of its inputs, and where the number of literals of a primary input is one.

4. The method of claim 3, wherein said step of vertically partitioning includes the steps of:

identifying a gate whose output violates one of the physical bounds, such that it cannot be the output of a logic segment; and

breaking down said gate into smaller gates, each of which have at least two inputs, and of which input gates satisfy the physical bounds, such that the outputs of the newly created gates may be outputs of a vertical segment.

5. The method of claim 1, wherein ##EQU5## is a function as a sum of products p₁, P(F)=n is the number of products of F, ##EQU6## is the maximum number of literals in the products, and wherein, in the step of vertically partitioning, a physical limit is imposed on the number of literals in each of said products and further comprising the step of estimating an upper bound on the maximum number of literals needed to implement said output, where the function of said output is represented as a reduced ordered binary decision diagram and where the number of literals of a node in this diagram is not more than one plus the maximum of the estimates of the number of literals for its inputs and where the number of literals at the inputs of nodes without predecessors is zero.

6. The method of claim 5 wherein said step of vertically partitioning includes the steps of:

identifying a gate whose output violates one of the physical bounds, such that it cannot be the output of a logic segment; and

breaking down said gate into smaller gates, each of which have at least two inputs, and of which input gates satisfy the physical bounds, such that the outputs of the newly created gates may be outputs of a vertical segment.

7. The method of claim 1 wherein the step of generating a symbolic representation includes the step of optimizing the logic to reduce the number of products.

8. A method for the efficient synthesis of logic array modules (LAMs) implementing a logic function, said logic function being defined by a multi-level combinational acyclic logic network inputs to the network being primary inputs and outputs from the network being primary outputs, said method comprising the steps of:

logically partitioning vertically the logic network to define a plurality of logic segments wherein each output of a logic segment can potentially be implemented in a single logic array module;

logically partitioning horizontally the plurality of logic segments to reduce the size of the segments to a size that can be efficiently implemented as a logic array module; and

generating a symbolic representation in a logic array module table of an internal structure of the logic array module based on the horizontally partitioned logic segments,

wherein in the step of logically partitioning horizontally, a physical limit is imposed of the number of outputs of a logic array module and a physical limits is imposed on the total number of products needed to implement all outputs of a logic array module, and wherein in the step of horizontally partitioning the vertical segment horizontally partitions the segment into a plurality of logic array modules such that each horizontal segment satisfies the physical limits,

wherein, in the step of logically partitioning horizontally, the horizontal partitioning of the segment is performed by partitioning nodes of a derived graph, which graph is derived by forming a node for each output of the segment and by forming an edge in the graph for each gate in the segment, the edge connecting to each node for which there is a directed path in the logic of the segment from the gate to the output corresponding to that node, each edge having an associated partitioning cost equal to a cost of duplicating the gate in the segment.

9. A method for the efficient synthesis of logic array modules (LAMs) implementing a logic function, said logic function being defined by a multi-level combinational acyclic logic network, inputs to the network being primary inputs and outputs from the network being primary outputs, said method comprising the steps of:

logically partitioning vertically the logic network to define a plurality of logic segments wherein each output of a logic segment can potentially be implemented in a single logic array module;

logically partitioning horizontally the plurality of logic segments to reduce the size of the segments to a size that can be efficiently implemented as a logic array module; and

generating a symbolic representation in a logic array module table of an internal structure of the logic array module based on the horizontally partitioned logic segment,

wherein in the step of logically partioning horizontally, a physical limit is imposed on the number of outputs of a logic array module and a physical limits is imposed on the total number of products needed to implement all outputs of a logic array module, and wherein in the step of horizontally partitioning the vertical segment horizontally partitions the segment into a plurality of logic array modules such that each horizontal segment satisfies the physical limits,

wherein, in the step of logically partioning horizontally each horizontal segment which satisfies the limits is horizontally partitioned into two horizontal segments while estimating a delay and area of a logic array module implementation of each of the horizontal segments, and using estimates of delay and area to determine if the newly created horizontal segments are smaller or faster than the unpartitioned segment, and repeating this process as long as improvements in area or delay can be realized.

10. The method of claim 9 wherein, in the step of horizontally partitioning, the horizontal partitioning of the segment is performed by partitioning nodes of a derived graph, which graph is derived by forming a node for each output of the segment and by forming an edge in the graph for each gate in the segment, the edge connecting to each node for which there is a directed path in the logic of the segment from the gate to the output corresponding to that node, each edge having an associated partitioning cost equal to a cost of duplicating the gate in the segment.