Partitioning of Boolean logic equations into physical logic devices

• US 5,140,526 A
• Filed: 01/06/1989
• Issued: 08/18/1992
• Est. Priority Date: 01/06/1989
• Status: Expired due to Term

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Minc Incorporated
• Inventors: Bush, Kevin M., McDermith, William O., Banki, Mehrdad
• Primary Examiner(s): Shaw, Dale M.
• Assistant Examiner(s): Huntley, David
• Application Number:
  US07/294,470
• Time in Patent Office: 1,320 Days
• Field of Search: 364/200 MS File, 364/400, 364/402, 364/488, 364/489, 364/900 MS File, 364/464.01, 364/578
• US Class Current: 705/28
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 30/343 Logical level
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders
• CPC Class Codes: G06Q 30/0283 Price estimation or determination
• CPC Class Codes: G06Q 30/0627 using item specifications

Abstract

An automated system for partitioning a set of Boolean logic equations onto one or more devices selected from a plurality of commercially available devices. The system utilizes a processor having a memory containing information on the different architectural types of devices, physical device information on individual devices and user generated design constraints, weighting factors and partitioning directives. Based upon this stored information, the system of the present invention selects all acceptable architectural types of devices wherein at least one of the Boolean logic equations can be placed thereon. For all physical devices associated with the acceptable architectural types only those devices which fall within the selected user constraints are selected. The system then evaluates the weighting factors to order the devices in order of cost value and then fits the equations according to the partitioning directives to the devices. During the fitting process, an optimum device solution is attained having a least cost value for which the system produces an output map suitable for the user of the system to configure the selected devices to implement the set of equations.

Claims

1. An automated partitioning method for implementing, on a processor, a given set of Boolean logic equations to one or a plurality of discrete manufactured physical logic devices, each of said discrete manufactured physical logic devices having an architectural type number, pins, pin assignments, manufacturer identity, model number, and price, said processor having an input, a memory, and an output, said method comprising the steps of:

storing template information on different architectural types of said discrete manufactured physical logic devices in a template file of said memory of said processor in response to receiving said template information from said input, said template information at least providing one of the following said architectural type number, number of said pins, and said pin assignments,

storing device information corresponding to each said different architectural type in a device information file of said memory of said processor in response to receiving said device information from said input, said device information at least providing one of the following said manufacturer identity, said model number, and said price,

storing available device information corresponding to selected user device information in an available device file in said memory of said processor in response to receiving said available device information from said input, said available device file selectively overriding said device information in said device information file,

storing selected user constraints and weighing factors for device selection in a criteria file in said memory of said processor in response to receiving said constraints and factors from said input, said constraints defining selection limits for said device information and said weighing factors defining a cost value for said device information,

identifying, via said processor, in a memory table at least one low cost solution comprising one or plurality of discrete manufactured physical logic devices in the template and device information files that implements said set of Boolean logic equations while meeting the selected user constraints in said criteria file.

2. An automated partitioning method for implementing, on a processor, a given set of Boolean logic equations to one or a plurality of discrete manufactured physical logic devices, each of said discrete manufactured physical logic devices having an architectural type number, pins, pin assignments, manufacturer identity, model number, and price, said processor having an input, a memory, and an output, said method comprising the steps of:

storing template information on different architectural types of said discrete manufactured physical logic devices in a template file of said memory of said processor in response to receiving said template information from said input, said template information including at least the architectural type number, the number of pins and the pin assignments,

storing device information corresponding to each said different architectural type in a device information file of said memory of said processor in response to receiving said device information from said input, said device information including at least said identity of manufacturer, said price, device performance values, and the device logic family,

storing available device information corresponding to selected user device information in an available device file in said memory of said processor in response to receiving said available device information from said input, said available device file selectively overriding said device information in said device information file,

storing selected user constraints and weighing factors for device selection in a criteria file in said memory of said processor in response to receiving said constraints and factors from said input, said constraints defining selection limits for said device information and said weighing factors defining a cost value for said device information,

storing selected user partitioning directives for device selection in a partitioning directives file in said memory of said processor in response to receiving said partitioning directives from said input, said partitioning directives defining predetermined physical relationships for partitioning of said Boolean logic equations,

identifying, via said processor, in a memory table at least one low cost solution comprising one or plurality of discrete manufactured physical logic devices in the template and device information files that implements said set of Boolean logic equations while meeting the selected user constraints and selected user partitioning directives in said criteria and partitioning directives files.

3. An automated partitioning method for implementing, on a processor, a given set of Boolean logic equations to one or a plurality of discrete manufactured physical logic devices, each of said discrete manufactured physical logic devices having an architectural type number, pins, pin assignments, manufacturer identity, model number, and price, said processor having an input, a memory, and an output, said method comprising the steps of:

storing template information on different architectural types of said discrete manufactured physical logic devices in a template file of said memory of said processor in response to receiving said template information from said input, said template information at least providing one of the following said architectural type number, number of said pins, and said pin assignments,

storing device information corresponding to each said different architectural type in a device information file of said memory of said processor in response to receiving said device information from said input, said device information at least providing one of the following said manufacturer identity, said model number, and said price,

storing available device information corresponding to selected user device information in an available device file in said memory of said processor in response to receiving said available device information from said input, overriding said device information in said device information file,

storing selected user constraints and weighing factors for device selection in a criteria file in said memory of said processor in response to receiving said constraints and factors from said input, said constraints defining selection limits for said device information and said weighing factors defining a cost value for said device information,

storing selected user partitioning directives for device selection in a partitioning directives file in said memory of said processor in response to receiving said partitioning directives from said input, said partitioning directives defining predetermined physical relationships for partitioning of said Boolean logic equations,

identifying, via said processor, in a possible solutions list in said memory, all discrete manufactured physical logic devices that have (1) a template of an architectural type wherein at least one of said Boolean logic equations in said set fits and (2) an information file wherein all said selected user constraints are met,

ordering, via said processor, the discrete manufactured physical logic devices in said possible solutions list based upon said weighing factors in order of increasing cost values,

fitting, via said processor, each of said equations to each of said discrete manufactured physical logic devices in said ordered list of possible solutions according to said partitioning directives, said processor generating a list of device solutions in order of increasing cost values,

mapping, via said processor, said set of Boolean equations onto the discrete manufactured physical logic devices in said list of device solutions.

4. A system for selecting one or more discrete manufactured physical logic devices from a plurality of discrete manufactured physical logic devices to implement a given set of Boolean logic equations, each of said discrete manufactured physical logic devices having an architectural type number, pins, pin assignments, manufacturer identity, model number, and price, said system comprising:

a processor, said processor being receptive of said Boolean logic equations,

said processor having a memory containing;

a template file for storing template information on different architectural types of said devices, said template information at least providing one of the following said architectural type number, number of said pins, and said pin assignments, a device information file for storing device information corresponding to each said different architectural type, said device information at least providing one of the following said manufacturer identity, said model number, and said price and a criteria file for storing selected user constraints, said constraints defining selection limits for said device information,

means in said processor for scanning said template file for all acceptable architectural types wherein at least one of said Boolean logic equations in said set fits, said scanning means being further capable of scanning said device information file for all possible discrete manufactured physical logic devices having said acceptable architectural types that fall within said selected user constraints, said processor producing a list of said possible discrete manufactured physical logic devices,

means in said processor for fitting the devices in said list of possible discrete manufactured physical logic devices to said set of Boolean equations, said fitting means generating a list of device solutions,

means in said processor for mapping said set of Boolean equations onto the devices in said device solutions set.

5. A system for selecting one or more discrete manufactured physical logic devices from a plurality of discrete manufactured physical logic devices to implement a given set of Boolean logic equations, each of said discrete manufactured physical logic devices having an architectural type number, pins, pin assignments, manufacturer identity, model number, and price, said system comprising:

a processor, said processor being receptive of said Boolean logic equations,

said processor having a memory containing;

a template file for storing template information on different architectural types of said devices, said template information at least providing one of the following said architectural type number, number of said pins, and said pin assignments, a device information file for storing device information corresponding to each said different architectural type number, said device information at least providing one of the following said manufacturer identity, said model number, and said price, a criteria file for storing selected user constraints and weighing factors, said constraints defining selection limits for said device information and said weighing factors defining cost values for said device information,

means in said processor for scanning said template file for all acceptable architectural types wherein at least one of said Boolean logic equations in said set fits, said scanning means being further capable of scanning said device information file for all possible discrete manufactured physical logic devices having said acceptable architectural types that fall within said selected user constraints, said processor determining the cost values for said possible discrete manufactured physical logic devices and said processor sorting said possible discrete manufactured physical logic devices into a list of increasing cost values,

means in said processor for fitting the discrete manufactured physical logic devices in said list of possible discrete manufactured physical logic devices to said set of Boolean equations, said fitting means generating a list of device solutions in order of increasing cost values,

means in said processor for mapping said set of Boolean equations onto the discrete manufactured physical logic devices in said device solutions list.

6. A system for selecting one or more devices from a plurality of discrete manufactured physical logic devices to implement a given set of Boolean logic equations, each of said discrete manufactured physical logic devices having an architectural type number, pins, pin assignments, manufacturer identity, model number, and price, said system comprising:

a processor, said processor being receptive of said Boolean logic equations,

a template file memory means in said processor for storing template information on different architectural types of said devices, said template information at least providing one of the following said architectural type number, said number of pins, and said pin assignments,

a device information memory means in said processor for storing device information corresponding to each said different architectural type, said device information at least providing one of the following said manufacturer identity, said model number, and said price,

means connected to said processor for loading into said template file memory means and into said device information memory means said template information and said device information,

a criteria file memory means in said processor for storing selected user constraints and weighing factors for said device selection for said implementation, said constraints defining selection limits for said device information and said weighing factors defining cost values for said device information,

means connected to said processor for inputting said selected user constraints to said criteria file memory means,

means in said processor for scanning said template file memory means for all acceptable architectural types wherein at least one of said Boolean logic equations in said set fits, said scanning means being further capable of scanning said device information memory means for all possible discrete manufactured physical logic devices having said acceptable architectural types that fall within said selected user constraints, said processor determining the cost values of said possible discrete manufactured physical logic devices and said processor sorting said possible discrete manufactured physical logic devices into a list of increasing cost values,

means in said processor for fitting the discrete manufactured physical logic devices in said list of possible devices to said set of Boolean equations, said fitting means generating a list of device solutions in order of increasing cost values,

means in said processor for mapping said set of Boolean equations onto the discrete manufactured physical logic devices in said device solutions list.

7. A system for selecting one or more devices from a plurality of discrete manufactured physical logic devices to implement a given set of Boolean logic equations, each of said discrete manufactured physical logic devices having an architectural type number, pins, pin assignments, manufacturer identity, model number, and price, said system comprising:

a processor, said processor being receptive of said Boolean logic equations,

a template file memory means in said processor for storing template information on different architectural types of said discrete manufactured physical logic devices, said template information including at least one of the following said architectural type number, the number of said pins and said pin assignments,

a device information memory means in said processor for storing device information corresponding to each said different architectural type number, said device information including at least one of the following the identity of said manufacturer, said price, device performance values, and the device logic family,

means connected to said processor for loading into said template file memory means and into said device information memory means said template information and said device information,

an available device file memory means in said processor for storing available device information corresponding to selected user device information, said available device file memory selectively overriding said device information in said device information memory means,

a criteria file memory means in said processor for storing selected user constraints and weighing factors for said device selection for said implementation, said constraints defining selection limits for said device information and said weighing factors defining a cost value for said device information,

a partitioning file memory means in said processor for storing selected user partitioning directives for said device selection for said implementation, said partitioning directives defining predetermined physical relationships for partitioning of said equations,

means connected to said processor for inputting said available device information to said available device file memory means, said selected user constraints to said criteria file memory means, and said partitioning directives to said partitioning file memory means,

means in said processor for scanning said template file memory means for all acceptable architectural types wherein at least one of said Boolean logic equations in said set fits, said scanning means being further capable of scanning said device information memory means for all possible discrete manufactured physical logic devices having said acceptable architectural types that fall within said selected user constraints, said processor determining the cost values for said possible devices and said processor sorting said possible devices into a list of increasing cost values,

means in said processor for fitting the devices in said list of possible devices to said set of Boolean equations according to said partitioning directives in said partitioning file memory means, said fitting means generating a list of device solutions in order of increasing cost values,

means in said processor for mapping said set of Boolean equations onto the discrete manufactured physical logic devices in said device solutions list.

8. A system for selecting one or more devices from a plurality of discrete manufactured physical logic devices to implement a given set of Boolean logic equations, each of said discrete manufactured physical logic devices having an architectural type number, pins, pin assignments, manufacturer identity, model number, and price, said system comprising:

a processor, said processor being receptive of said Boolean logic equations,

a template file memory means in said processor for storing template information on different architectural types of said devices, said template information including at least one of the following said architectural type number, the number of said pins and said pin assignments,

a device information memory means in said processor for storing device information corresponding to each said different architectural type number, said device information including at least one of the following the identity of said manufacturer, said price, device performance values, and the device logic family,

means connected to said processor for loading into said template file memory means and into said device information memory means said template information and said device information,

an available device file memory means in said processor for storing available device information corresponding to selected user device information, said available device file memory selectively overriding said device information in said device information memory means,

a criteria file memory means in said processor for storing selected user constraints and weighing factors for said device selection for said implementation, said constraints defining selection limits for said device information and said weighing factors defining a cost value for said device information,

a partitioning file memory means in said processor for storing selected user partitioning directives for said device selection for said implementation, said partitioning directives defining predetermined physical relationships for partitioning of said equations,

means connected to said processor for inputting said available device information to said available device file memory means, said selected user constraints to said criteria file memory means, and said partitioning directives to said partitioning file memory means, and

said processor based upon said available device information, said partitioning directives, said weighing factors and said constraints selecting from said template file memory means and said device information memory means at least one low cost solution identifying said one or plurality of devices that implements said set of Boolean logic equations.