Apparatus and method for allocation of resoures in programmable logic devices

• US 5,128,871 A
• Filed: 03/07/1990
• Issued: 07/07/1992
• Est. Priority Date: 03/07/1990
• Status: Expired due to Term

• Current Assignee: Lattice Semiconductor Corporation
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Schmitz, Nicholas A.
• Primary Examiner(s): Cangialosi, Salvatore
• Application Number:
  US07/490,817
• Time in Patent Office: 853 Days
• Field of Search: 307/440, 307/465, 364/488-490, 364/491
• US Class Current: 716/102
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]

Abstract

Programmable logic device design software is provided for allocating specific resources in a programmable logic device having a multiplicity of programmable logic blocks interconnected by a programmable switch matrix to logic equations in a user logic design. In particular, a resource allocation means for fitting a logic design to a multiplicity of programmable logic blocks with limited interconnectivity between the modules is provided. The resource allocation means requires minimal programmable logic device resources to achieve the allocation of resources within the programmable logic device to the user logic design. The resource allocation means employs block partitioning means and resource assignment means to map user logic to a programmable logic device (PLD) having multiple programmable AND fixed OR arrays interconnected by a programmable switch matrix, i.e., allocate the PLD resources to the user logic.

Claims

1. A system for allocation of resources of a programmable logic device (PLD) having a multiplicity of programmably interconnected programmable logic blocks to user logic equations comprising:

means for inputting user logic equations,

means, operatively, coupled to said user logic equations, for partitioning said user logic equations into a multiplicity of modules wherein each user logic equation is placed in one of said modules based upon an affinity between that user logic equation and other user logic equations in said one module;

means, operatively coupled to said partitioning means to receive said modules of partitioned user logic equations, for allocating resources in a programmable logic device wherein each of said user logic equations in said modules is assigned to specific components in said PLD; and

means, operatively coupled to said resource allocation means, for generating the state of each programmable connection in said PLD.

2. A system for allocation of resources as in claim 1 with each of said user logic equations having at least one input signal, said partitioning means further comprising:

similarity means, operatively coupled to said logic equation input signals, for generating a similarity measure S for two Boolean vectors;

wherein said similarity means generates said measure S for each pair of said user logic equations using a first Boolean vector representing the presence of input signals to the first user logic equation in said pair of user logic equations and a second Boolean vector representing the presence of input signals to the other user logic equation in said pair of said user logic equations.

3. A system for allocation of resources as in claim 2, said similarity means further comprising:

means, responsive to said similarity measure, for selecting for each user logic equation similarity measures greater than a predetermined limit wherein for each similarity measure greater than the predetermined limit, said selecting means stores the similarity measure and the associated Boolean vector for each user logic equation in said pair of equations and only the stored pairs of user logic equations are subsequently processed.

4. A system for allocation of resources selected from any one of claims 2 or 3, said partitioning means further comprising:

seeding means, operatively coupled to said similarity means, for placing a different user logic equation in each of said multiplicity of modules.

5. A system for allocation of resources as in claim 4, said partitioning means further comprising:

receptivity means, operatively coupled to said similarity means, for generating a receptivity of each module for each of said user logic equations based upon said similarity measures;

wherein said receptivity means assigns the user logic equation to the module having the largest receptivity thereby partitioning the user logic equations into modules based upon the affinity of the logic equations input signals.

6. A system for allocation of resources as in claim 5 wherein said similarity means further comprises

means, operatively coupled to said user logic equations, for generating for each of said multiplicity of modules and a pair of said user logic equations, (i) a first similarity measure S1 for the Boolean vector for the input signals to the first user logic equation in said pair and a Boolean vector for the input signals to the user logic equations in a module, and (ii) a second similarity measure S2 for the Boolean vector for the input signals to the other user logic equation in said pair and said Boolean vector for the input signals to the user logic equations in said module wherein each pair of measures S1 and S2 are stored for subsequent processing.

7. A system for allocation of resources as in claim 6 wherein said receptivity means further comprises:

meaning, operatively coupled to said means for generating similarity measures S1 and S2, for selecting a maximum similarity measure;

wherein said maximum similarity measure selection means selects a maximum similarity measure SM for each module from said pairs of similarity measures S1 and S2 for that module; and

said maximum similarity measure selection means subsequently selects a maximum similarity measure SMMAX from said maximum of similarity measures SM for said modules thereby locating the module that has the greatest receptivity for the user logic equation is said pair of user logic equations.

8. A system for allocation of resources as in claim 7 wherein said receptivity means further comprises:

means, operatively coupled to said maximum similarity measure selection means, for assigning said user logic equation associated with the maximum similarity measures SMMAX to the module associated with maximum similarity measure SMMAX thereby placing said user logic equation in the module having the greatest affinity for said equation.

9. A system for allocation of resources as in claim 8 said partitioning means further comprising:

means, operatively coupled to a source specifying the resources available for each of said multiplicity of modules and to said assigning means, for monitoring available resources in a module wherein;

said monitoring means, upon one of said user logic equations being placed in a module by said receptivity means, decrements the available resources in said module by the number of resources required for said one user logic equation.

10. A system for allocation of resources as in claim 9 wherein said assigning means places said user logic equation in the module having the highest affinity for the equation only if said module has sufficient resources for said user logic equation.

11. A system for allocation of resources as in claim 2, said similarity means further comprising;

means, operatively coupled to said logic equation input signals, for determining a total number n of input signals to a user logic equation wherein said Boolean vector representing the input signals to said user logic equation has n bits and each bit represents one of said n input signals.

12. A system for allocation of resources as in claim 11, said similarity means further comprising:

means, operatively coupled to said total number determining means, for setting each bit in a Boolean vector to a predetermined value;

wherein said setting means sets a bit to a first predetermined value when the input signal represented by said bit is an input signal to the user logic equation associated with said Boolean vector; and

said setting means sets said bit to a second predetermined value otherwise.

13. A system for allocation of resources as in claim 12, said similarity means further comprising:

means, operatively coupled to said bit setting means, for determining input signals common to Boolean vectors

wherein said means for determining common input signals generates an n bit Boolean vector C where for each common input signal, the bit in Boolean vector C for that input signal is set to said first predetermined value to represent the presence of said common input signal.

14. A system for allocation of resources as in claim 13, said means for determining common input signals further comprising:

means, operatively coupled to said bit setting means, for generating a bit-wise logic AND function (AND) of any pair of said Boolean vectors wherein said bit-wise AND generating means generates said Boolean vector C.

15. A system for allocation of resources as in claim 13, said similarity means further comprising:

means, operatively coupled to said bit setting means, for determining the input signals in a first Boolean vector that are different from the input signals in a second Boolean vector;

wherein said means for determining different input signals generates an n bit Boolean vector D where

for each different input signal, the bit in Boolean vector D for that input signal is set to said first predetermined value to represent the presence of said different input signal.

16. A system for allocation of resources as in claim 15, said means for determining different input signals further comprising:

means, operatively coupled to said bit setting means, for generating a bit-wise logic Exclusive OR function (Exclusive OR) of any pair of Boolean vectors wherein said Exclusive OR means processes said first and second Boolean vectors to generate said Boolean vector D.

17. A system for allocation of resources as in claim 15, said similarity means further comprising:

means, operatively coupled to said means for determining common input signals and said means for determining different input signals, for counting the number of bits in a Boolean vector having a predetermined value;

wherein said counting means counts the number bits in said Boolean vector C having said first predetermined number and stores said count as a number c; and

said counting means counts the number bits in said Boolean vector D having said first predetermined number and stores said count as a number d.

18. A system for allocation of resources as in claim 17, said similarity means further comprising:

means, operatively coupled to said counting means, for generating said similarity measure S;

wherein said generating means divides the number d by a predetermined weight to form a number D1; and

said generating means subtracts the number D1 from the number c to form said measure of similarity S.

19. A system for allocation of resources as in claim 1, said allocating means further comprising:

means, operatively coupled to said partitioning means, for assigning each of said multiplicity of modules to one of said programmable logic blocks in said programmable logic device.

20. A system for allocation of resources as in claim 19, said allocating means further comprising:

means, operatively coupled to said module assigning means, for assigning each of said user logic equations in one of said modules to resources in said programmable logic block assigned to said one of said modules;

wherein said logic equation assigning means assigns logic equations requiring similar number of product terms as a group; and

the groups of logic equations are processed sequentially by the required number of product terms starting with the group that requires the greatest number of product terms.

21. A system for allocation of resources as in claim 20, said user logic equations including output logic equations and buried logic equations, wherein said logic equation assigning means first assigns each of said output logic equations and subsequently assigns each of said buried logic equations.

22. A system for allocation of resources as in claim 21, said user logic equations including the same input signals for user logic equations in at least two modules, and said programmable logic device having dedicated input pins, said allocating means further comprising:

means, operatively coupled to said module assigning means, for assigning said input signals for user logic equations in at least two modules to said dedicated input pins.

23. A system for allocation of resources as in any one of claims 19, 20 or 22, said allocating means further comprising:

means, operatively coupled to a source specifying the resources available for said interconnections means and for each programmable logic block of said PLD and to said assigning means, for monitoring resources available in each of said programmable logic blocks and said interconnections means wherein upon allocation of resources by any of said assigning means, said allocated resources are identified as used and removed from the available resources by said resource monitoring means.

24. A system for allocation of resources as in claim 23 said allocating means further comprising:

means, operatively coupled to each of said assigning means, for locating all available resources for one of said assigning means;

means, operatively coupled to each of said assigning means, for determining a cost for use of each of said available resources by said one assigning means; and

each of said assigning means further comprises means, operatively coupled to said available locating resource means and to said cost determining means, for building a two-dimensional matrix wherein;

the rows of said matrix are available resources and the columns of said matrix are one of (i) logic equations to be assigned for said logic equation assigning means and (ii) input signals to be assigned for said input signal assigning means; and

the element at the intersection of a row and a column is the cost of using said available resource for the assignment associated with said column.

25. A system for allocation of resources as in claim 24 said allocating means further comprising:

Hungarian assignment means, operatively coupled to said two dimensional matrix building means in each of said assigning means, for determining the optimal assignment of resources in said matrix.

26. A method, operative in a computer system, for allocation of resources of a programmable logic device (PLD) having a multiplicity of programmably interconnected programmable logic blocks to user logic equations comprising:

inputting user logic equations

partitioning said user logic equations into a multiplicity of modules wherein each user logic equation is placed in one of said modules based upon an affinity between that user logic equation and other user logic equations in said one module;

allocating resources in a programmable logic device wherein each of said user logic equations in said modules is assigned to specific components in said PLD; and

generating the state of each programmable connection in said PLD.

27. A method for allocation of resources as in claim 26 with each of said user logic equations having at least one input signal, said partitioning step further comprising:

generating a similarity measure S for two Boolean vectors;

wherein said measure S is generated for each pair of said user logic equations using a first Boolean vector representing the presence of inputs signals to the first user logic equation in said pair of user logic equations and a second Boolean vector representing the presence of input signals to the other user logic equation in said pair of said user logic equations.

28. A method for allocation of resources as in claim 27, said similarity measure generating step further comprising:

selecting for each user logic equation similarity measures greater than a predetermined limit wherein for each similarity measure greater than the predetermined limit, the similarity measure and the associated Boolean vector for each user logic equation in said pair of equations are stored and only the stored pairs of user logic equations are subsequently processed.

29. A method for allocation of resources selected from any of claim 27 or 28, said partitioning step further comprising:

placing a different user logic equation in each of said multiplicity modules.

30. A method for allocation of resources as in claim 29, said partitioning step further comprising:

generating a receptivity of each module for each of said user logic equations based upon said similarity measures;

wherein the user logic equation is assigned to the module having the largest receptivity thereby partitioning the user logic equations into modules based upon the affinity of the logic equations input signals.

31. A method for allocation of resources as in claim 30 wherein said receptivity step includes generating for each of said multiplicity of modules and a pair of said user logic equations, (i) a first similarity measure S1 for the Boolean vector for the input signals to the first user logic equation in said pair and a Boolean vector for the inputs signals to the user logic equations in a module, and (ii) a second similarity measured S2 for the Boolean vector for the input signals to the other user logic equation in said pair and said Boolean vector for the input signals to the user logic equations in said module and wherein each pair of measures S1 and S2 are stored for subsequent processing.

32. A method for allocation of resources as in claim 31 wherein said receptivity step further comprises:

selecting a maximum similarity measure;

wherein said maximum similarity measure selection step selects a maximum similarity measure SM for each module from said pairs of similarity measures S1 and S2 for that module; and

said maximum similarity measure selection step subsequently selects a maximum similarity measures SMMAX from said maximum of similarity measures SM for said modules thereby locating the module that has the greatest receptivity for the user logic equation is said pair of user logic equations.

33. A method for allocation of resources as in claim 32 wherein said receptivity step further comprises:

assigning said user logic equation associated with the maximum similarity measure SMMAX to the module associated with maximum similarity measure SMMAX thereby placing said user logic equations in the module having the greatest affinity for said equation.

34. A method for allocation of resources as in claim 33 said partitioning step further comprising:

monitoring available resources in a module wherein;

upon one of said user logic equations being placed in a module in said receptivity step, the available resources in said module are decremented by the number of resources required for said one user logic equation.

35. A method for allocation of resources as in claim 34 wherein said assigning step places said user logic equation in the module having the highest affinity for the equation only if said module has sufficient resources for said user logic equation.

36. A method for allocation of resources as in claim 27, said similarity measure generating step further comprising:

determining the total number n of said input signals to a user logic equation wherein said Boolean vector representing the input signals to said user logic equation has n bits and each bit represents one of said n input signals.

37. A method for allocation of resources as in claim 36, said similarity step further comprising:

setting each bit in a Boolean vector to a predetermined value;

wherein said setting step sets a bit to a first predetermined value when the input signal represented by said bit is an equal signal to the user logic equation associated with said Boolean vector; and

said setting step sets said bit to a second predetermined value otherwise.

38. A method for allocation of resources as in claim 37, said similarity measure generating step further comprising:

determining the input signals common to a first Boolean vector and to a second Boolean vector;

wherein said common input signals are represented in an n bit Boolean vector C wherein

for each common input signal, the bit in Boolean vector C for that input signal is set to said first predetermined value to represent the presence of said common input signal.

39. A method for allocation of resources as in claim 38, said step for determining common input signals comprising:

generating a bit-wise logic AND function (AND) for a pair of said Boolean vectors wherein said bit-wise AND of said pair of Boolean vectors generates said Boolean vector C.

40. A method for allocation of resources as in claim 38, said similarity measure generating step further comprising:

determining the input signals in a first Boolean vector that are different from the input signals in a second Boolean vector;

wherein said different input signals are represented in an n bit Boolean vector D; and

for each different input signal the bit in Boolean vector D for that input signal is set to said first predetermined value to represent the presence of said different input signal.

41. A method for allocation of resources as in claim 40, said step for determining different input signals further comprising:

generating a bit-wise logic Exclusive OR function (Exclusive OR) of a pair of Boolean vectors wherein said Exclusive OR step processes said first and second Boolean vectors to generate said Boolean vector D.

42. A method for allocation of resources as in claim 40, said similarity measure generating step further comprising:

counting the number bits in said Boolean vector C having said first predetermined number and storing said count as a number c; and

counting the number bits in said Boolean vector D having said first predetermined number and storing said count as a number d.

43. A method for allocation of resources as in claim 42, said similarity measure generating step further comprising:

dividing the number d by a predetermined weight to form a number D1; and

subtracting the number D1 from the number c to form said measure of similarity S.

44. A method for allocation of resources as in claim 26, said allocating step further comprising:

assigning each of said multiplicity of modules to one of said programmable logic blocks in said programmable logic device.

45. A method for allocation of resources as in claim 44, said allocating step further comprising:

assigning each of said user logic equations in one of said modules to resources in said programmable logic block assigned to said one of said modules;

wherein said logic equation assigning step assigns logic equations requiring similar number of product terms as a group; and

the groups of logic equations are processed sequentially by the required number of product terms starting with the group that requires the greatest number of product terms.

46. A method for allocation of resources as in claim 45, said user logic equations including output logic equations and buried logic equations, wherein said logic equation assigning step first assigns each of said output logic equations and subsequently assigns each of said buried logic equations.

47. A method for allocation of resources as in claim 45, said user logic equations including the same input signals for user logic equations in at least two modules, and said programmable logic device having dedicated input pins, said allocating step further comprising:

assigning said input signals for user logic equations in at least two modules to said dedicated input pins.

48. A method for allocation of resources as in any one of claims 44, 45, or 47, said allocating step further comprising:

monitoring resources available in each of said programmable logic blocks and said interconnections means wherein upon allocation of resources in any of said assigning steps, said allocated resources are identified as used and removed from the available resources.

49. A method for allocation of resources as in claims 48 said allocating step further comprising:

locating all available resources for one of said assigning steps;

determining a cost for use of each of said available resources by said assigning step; and

building a two-dimensional matrix wherein;

the rows of said matrix are available resources and the columns of said matrix are one of (i) logic equations to be assigned for said logic equation assigning step and (ii) input signals to be assigned for said input signal assigning step; and

the element at the intersection of a row and a column is the cost of using said available resource for the assignment associated with said column.

50. A method for allocation of resources as in claim 40 said allocating step further comprising:

using a Hungarian assignment process for determining the optimal assignment of resources in said matrix.

51. In a computer system including a stored product data (PDB) having information characterizing at least one programmable logic device (PLD), a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design comprising:

initialization means, operatively coupled to said PDB, for (i) initializing data structures and (ii) inputting user design that includes logic equations and signals wherein said initialization means reads said user design and information from said PDB and in turn uses the read information in initializing data structures in said main memory including data structures representing signals and logic equation in the user design;

means, operatively coupled to said data structures representing the signals and logic equations in the user design, for partitioning logic equations into a multiplicity of modules wherein each logic equation is placed in one of said modules based upon an affinity between that logic equations and other logic equations in said one module and further wherein said modules are structures in said main memory;

means, operatively coupled to said multiplicity of modules, for allocating resources in a programmable logic device wherein each of said logic equations in said modules in assigned to specific components in said PLD; and

means, operatively coupled to said resource allocation means, for generating the state of each programmable connection in said PLD.

52. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 51, said partitioning means further comprising:

similarity means, operatively coupled to said data structures representing signals and logic equations, for determining a similarity measure S for two Boolean vectors;

wherein said similarity means determines said measure S for each pair of said logic equations using a first Boolean vector representing the presence of input signals to the first logic equation in said pair of logic equations and a second Boolean vector representing the presence of input signals to the other logic equation in said pair of said logic equations.

53. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, or allocating resources of a programmable logic device to a user design as in claim 52, said similarity means further comprising;

means, responsive to said similarity measure, for selecting for each logic equations similarity measures greater than a predetermined limit wherein for each similarity measure greater than the predetermined limit, said selecting means stores the similarity measure and the associated Boolean vector for each logic equation in said pair of equations in said main memory for subsequent processing.

54. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design selected from any one of claims 52 or 53, said partitioning means further comprising:

seeding means, operatively coupled to said similarity means, for placing a different logic equation in each of said multiplicity of modules.

55. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 54, said partitioning means further comprising:

receptivity means, operatively coupled to said similarity means, for generating a receptivity of each module for each of said logic equations based upon said similarity measures;

wherein said receptivity means assigns the logic equations to the modules having the largest receptivity thereby partitioning the logic equations into modules based upon the affinity of the logic equations input signals.

56. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 55 wherein said similarity means further comprises:

means, operatively coupled to said logic equations, for generating for each of said multiplicity of modules and a pair of said logic equations, (i) a first similarity measure S1 for the boolean vector for the input signals to the first logic equation in the pair and a Boolean vector for the input signals to the logic equations in a module, and (ii) a second similarity measure S2 for the Boolean vector for the input signals to the other logic equation in the pair and said Boolean vector for the input signals to the logic equations in said module wherein said measures S1 and S2 are stored in said main memory.

57. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 56 wherein said receptivity means further comprises:

means, operatively coupled to said pairs of measures S1 and S2, for selecting a maximum similarity measure;

wherein said maximum similarity selection means selects a maximum similarity measure S for each module from said pairs of similarity measures S1, S2 for that module; and

said maximum similarity selection means subsequently selects a maximum similarity measure SMMAX from said maximum of similarity measures SM for said modules thereby locating the module that has the greatest receptivity for the logic equation in said pair of user logic equations.

58. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 57 wherein said receptivity means further comprises:

means, operatively coupled to said maximum similarity measure selection means, for assigning said logic equation associated with the maximum similarity measure SMMAX to the module associated with the maximum similarity measure SMMAX thereby placing said logic equation in the module having the greatest affinity for said logic equation.

59. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 58 said partitioning means further comprising:

means, operatively coupled to a source specifying the resources available for each module and to said assigning means, for monitoring available resources in a module wherein;

said monitoring means, upon one of said logic equations being placed in a module by said receptivity means, decrements the available resources in said module by the number of resources required for said one logic equation.

60. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 58 wherein said assigning means placed said logic equation in the module having the highest affinity for said logic equation only if said module has sufficient resources for said logic equation.

61. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 52, said similarity means further comprising:

means, operatively coupled to said logic equation input signals, for determining a total number n of input signals to a logic equation wherein said Boolean vector representing the input signals to said logic equation has n bits and each bit represents one of said n input signals.

62. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operatively in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 61, said similarity means further comprising:

means, operatively coupled to said total number determining means, for setting each bit in a Boolean vector to a predetermined value;

wherein said setting means sets a bit to a first predetermined value when the input signal represented by said bit in an input signal to the logic equation associated with said Boolean vector; and

said setting means sets said bit to a second predetermined value otherwise.

63. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 62, said similarity means further comprising:

means, operatively coupled to said bit setting means, for determining input signals common to a first Boolean vector and to a second Boolean vector;

wherein said means for determining common input signals generates an n bit Boolean vector C where for each common input signal, the bit in Boolean vector C for that input signals is set to said first predetermined value to represent the presence of said common input signal.

64. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 63, said means for determining common input signals comprising:

means, operatively coupled to said bit setting means, for generating a bit-wise logic AND function (AND) of any pair of said Boolean vectors wherein said bit-wise AND generating means creates said Boolean vector C.

65. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 62, said similarity means further comprising:

means, operatively coupled to said bit setting means, for determining the input signals in a first Boolean vector that are different from the input signals in a second Boolean vector;

wherein said means for determining different input signals generates an n bit Boolean vector D where for each different input signal, the bit in Boolean vector D for that input signal is set to said first predetermined value to represent the presence of said different input signal.

66. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 65, said means for determining different input signals further comprising:

means, operatively coupled to said bit setting means, for generating a bit-wise logic Exclusive OR function (Exclusive OR) of any pair of Boolean vectors wherein said Exclusive OR means processes said first and second Boolean vectors to generate said Boolean vector D.

67. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operatively in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 65, said similarity means further comprising:

means, operatively coupled to said means for determining common input signals and said means for determining different input signal, for counting the number of bits in a Boolean vector having a predetermined value;

wherein said counting means counts the number bits in said Boolean vector C having said first predetermined number and stores said count as a number c; and

said counting means counts the number bits in said Boolean vector D having said first predetermined number and stores said count as a number d.

68. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 67, said similarity means further comprising:

mean, operatively coupled to said counting means, for generating said similarity measure S;

wherein said generating means divides the number d by a predetermined weight to form a number D1; and

said generating means subtracts the number D1 from the number c to form said measure of similarity S.

69. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operatively in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 51, said allocating means further comprising:

means, operatively coupled to said partitioning means, for assigning each of said multiplicity of modules to one of said programmable logic blocks in said programmable logic device.

70. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 69, said allocating means further comprising:

means, operatively coupled to said module assigning means, for assigning each of said logic equations in one of said modules to resources in said programmable logic block assigned to said one of said modules;

wherein said logic equation assigning means assigns logic equations requiring similar number of product terms as a group; and

the groups of logic equations are processed sequentially by the required number of product terms starting with the group that requires the greatest number of product terms.

71. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 70, said logic equations including output logic equations and buried logic equations, wherein said logic equation assigning means first assigns each of said output logic equations and subsequently assigns each of said buried logic equations.

72. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claim 71, said logic equations including the same input signals for logic equations in at least two modules, and said programmable logic device having dedicated input pins, said allocating means further comprising:

means, operatively coupled to said module assigning means, for assigning said input signals for user logic equations in at least two modules to said dedicated input pins.

73. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in any one of claims 69, 70, or 72, said allocating means further comprising:

means, operatively coupled to a source specifying the resources available for said interconnections means and each programmable logic block of said PLD and to said assigning means, for monitoring resources available in each of said programmable logic blocks and said interconnections means wherein upon allocation of resources by any of said assigning means, said allocated resources are identified as used and removed from the available resources by said resource monitoring means.

74. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claims 73 said allocating means further comprising:

means, operatively coupled to each of said assigning means, for locating all available resources for one of said assigning means;

means, operatively coupled to each of said assigning means, for determining a cost for use of each of said available resources by said one assigning means; and

each of said assigning means further comprises means, operatively coupled to said available locating resource means and to said cost determining means, for building a two-dimensional matrix wherein;

the rows of said matrix are available resources and the columns of said matrix are one of (i) logic equations to be assigned for said logic equation assigning means and (ii) input signals to be assigned for said input signal assigning means; and

the element at the intersection of a row and a column is the cost of using said available resource for the assignment associated with said column.

75. In a computer system including a stored product database (PDB) having information characterizing at least one programmable logic device, a system, operative in main memory of said computer system, for allocating resources of a programmable logic device to a user design as in claims 74 said allocating means further comprising:

Hungarian assignment means, operatively coupled to said two dimensional matrix building means in each of said assigning means, for determining the optimal assignment of resources in said matrix.