Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
5128871
Schmitz
July 7, 1992
Title
Apparatus and method for allocation of resoures in programmable logic devices
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.
Inventors:
Schmitz; Nicholas A.
(Cupertino,
CA
)
Assignee:
Advanced Micro Devices, Inc.
(Sunnyvale,
CA
)
Appl. No.:
490817
Filed:
March 7, 1990
Current U.S. Class:
716/17
Current International Class:
G06F 17/50 (20060101)
Field of Search:
307/440,465 364/488-490,491
U.S. Patent Documents
4612618
September 1986
Pryor et al.
4786904
November 1988
Graham, III et al.
4792909
December 1988
Serlet
4849928
July 1989
Hauck
4916627
April 1990
Hathaway
4918614
April 1990
Modarres et al.
Other References
Pal Device Data Book, Advanced Micro Devices, Sunnyvale, CA, pp. 4-1 to 4-198, (1988). .
Pal Device Handbook, Advanced Micro Devices, Sunnyvale, CA, pp. 2-66 to 2-70, (1988)..~
Primary Examiner:
Cangialosi; Salvatore
Attorney, Agent or Firm:
Skjerven, Morrill, MacPherson, Franklin & Friel
Claims
I claim:
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.
Description
BACKGROUND OF THE INVENTION
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
FIELD OF THE INVENTION
This invention relates generally to design packages for allocating resources in a programmable logic device to user logic designs and more particularly to a resource allocation means for programmable logic devices having programmable logic blocks interconnected by a switch matrix.
DESCRIPTION OF THE PRIOR ART
Programmable logic devices are available for a variety of applications. Typically, a programmable logic device is a circuit on an integrated circuit chip which can be configured by a user to perform one or more logic functions. Most programmable logic devices include an AND array and an OR array either or both of which is programmable. In a programmable array logic (PAL) device, input signals are fed to a programmable AND array which performs programmed AND functions and generates product terms. The product terms are fed to a fixed, i.e., non-programmable, OR array. The OR array sums the product terms from the AND array to form the logic function desired by the user.
To use a programmable logic device, a user must specify the logic function for the device and then program the device to perform the logic function. Typically, a programmable logic device is programmed by setting the state of array logic cells, such as fuses or electrically erasable cells, so that a desired connection of two signal lines within the AND array of the device is achieved. Similarly, architectural cells are often used to configure multiplexers and/or flip-flops in a programmable logic device.
A variety of support tools have been developed to assist a user in implementing a logic function in a programmable logic device. Typically, the design support tools consist of design software and a logic programmer.
A typical block diagram of a design support system available to a user of a programmable logic device is illustrated in FIG. 1. Programmable logic design software 11 is loaded in a computer 10. The user supplies a circuit description 12 to logic design software executing in computer 10 which in turn typically generates a Joint Electronic Device Engineering Council (JEDEC) file 13. In general, a JEDEC file is a computer file containing information about the programming of a programmable device. The file format is a JEDEC-approved standard describing which fuses are to be programmed.
JEDEC file 13 is downloaded to logic programmer 14 which is coupled to programmable logic device 15 . Logic programmer 14 uses the information in JEDEC file 13 to program logic device 15 to perform the logic function in circuit description 12.
Most design software packages perform essentially these same tasks. The design is first specified with relatively high-level constructs such as boolean equations or state machine diagrams. The software processes the design and converts the design to a form which the logic programmer uses to configure the programmable logic device. Most software packages include logic simulation which allows debugging of the design prior to programming the programmable logic device.
One design software package for programmable logic devices is the PALASM 2 software available from Advanced Micro Devices, 901 Thompson Place, Sunnyvale Calif. 94088. (PALASM 2 is the U.S. registered trademark of Advanced Micro Devices, Inc.) A software flow diagram of the PALASM 2 software for PAL devices is illustrated in FIG. 2.
As explained more completely below, a design input file 20 is provided to parse 21. Parse 21 checks the syntax of input file 20 and passes the information to expand 22. Expand 22 expands the input equations and converts state machine syntax to Boolean equations. Subsequently, minimize 23 minimizes the logic equations from expand 22. The results from minimize 23 are provided to xplot 24 and sim 25. Xplot 24 assembles PAL device designs and generates a PLD fuse map data file and a PLD fuse JEDEC data file. Sim 25 simulates PAL device designs and generates a simulation history data file, a simulation trace data file, and a file containing PLD fuse JEDEC data and JEDEC test vectors.
The PALASM 2 software executes on Digital Equipment Corp. VAX minicomputers under either Digital Equipment Corp. VMX operating system or Berkeley 4.2 UNIX operating system as well as on IBM or IBM compatible personal computers operating under the Microsoft Corp. MS-DOS operating system version 3.2 or above.
PALASM 2 software includes an interactive menu program that simplifies user interface to the software. Menu screens display all user options on one screen, enable the use of function keys to run all the programs, and allow the user to view the output. Help screens and message windows are used to facilitate user interaction with the software.
Design input file 20 contains information describing the circuit to be implemented on the programmable logic device. The information in the design input file varies with the design software used, but one skilled in the art know the required information for the design input file. For example, for PALASM 2 software, a first design input file is used for Boolean equation design and another design input file is used for state machine design.
For Boolean equation design, the design input file for the PALASM 2 software contains two segments, a declaration segment and an equations segment. The declaration segment contains design identification, device and pin data, and optionally string substitutions. Information in the declaration segment documents the input and output signals of the design. The equations segment contains Boolean logic functions that define output signals in terms of input signals and feedback signals as well as the configuration of the other programmable functions. A more detailed description of the Boolean equation design input file and the information in the file is given in PAL Device Databook, Advanced Micro Devices, Sunnyvale Calif., pp. 4-61 to 4-93
(1988) which is incorporated herein by reference. Also, a sample design for a four bit counter is given in FIG. 3A. A description of the design file in FIG. 3A is given in PAL Device Handbook, Advanced Micro Devices, Sunnyvale, Calif, pp. 2-66 to 2-70
(1988), which is incorporated herein by reference.
For state machine design, the design input file for the PALASM 2 software contains three segments, a declaration segment, a state segment, and a conditions segment. The declaration segment contains design identification, device and pin data, and string substitutions. The state segment contains information about the design and equations that describe functions of the state machine. The state segment information is derived from the state diagram for the state machine. The state segment includes (i) statements that specify the kind of machine, and the output signals; (ii) equations that assign register-values as a bit code for each state; and (iii) equations that specify the transitions between states and the polarity and behavior of the output signals. The conditions segment contains labels that give names to unique sets of input signals and associated equations that identify the branching conditions used in the state segment to determine transitions and output signals.
A state machine design input file is given in FIGS. 3B and 3C. A more detailed description of the state machine design input file and the information in the file is given in PAL Device Databook, Advanced Micro Devices, Sunnyvale Calif., pp.
4-95 to 4-135 (1988) which is incorporated herein by reference.
Parse 21 (FIG. 2A) checks the syntax of design input file 20. If parse 21 detects an error in file 20, the location of the error is indicated and an error message is displayed. The error messages are stored in a file that is accessed by parse
21 when an error is detected. To facilitate completion of a design, parse 21 attempts to recover after detection of each error and continue with the syntax checking. If the design input file 20 is error free, parse 21 creates an intermediate file for processing by expand 22.
Using the intermediate file from parse 20, expand 22 expands the input equations and converts state machine syntax to Boolean equations.
If the programmable device specified in design input file 20 does not contain an XOR gate, expand 22 expands any XOR expressions to AND and OR expressions. In general, expand 22 performs logic substitutions for logic expressions in the user design which are not included within the selected programmable logic device. Expand 22 creates another intermediate file that contains expanded Boolean equations.
Minimize 23 processes either the intermediate file from parse 21 or the intermediate file from expand 22. Minimize 23 looks for logic redundancy and minimizes the AND and OR expressions. Minimize 23 enables the user to program the logic device more efficiently. When minimize 23 detects an XOR gate and the logic device includes XOR gates, the equations on either side of the XOR gate are minimized independently leaving the XOR intact. Minimize 23 produces yet another intermediate file that is used by subsequent programs. Intermediate file 26 has a TRE format.
Xplot 24 validates the architectural design of an input PAL design to the logic device limits and produces fuse maps and JEDEC data. Xplot can process the intermediate file containing Boolean equations created by parse 21, expand 22, and minimize 23. Xplot 24 checks the Boolean equations for consistency and correctness for the specified device. When an error is encountered xplot 24 attempts immediate recovery.
Using architectural information about the device specified in a product design file, which is read and stored in the computer memory by the design software, xplot fits the Boolean equations to the programmable logic device. Xplot 24, as well as most other software design tools, works with an excess of resources and employs simple book-keeping methods to allocate the resources in a systematic fashion. After xplot 24 has fit the Boolean equations to the programmable logic device without error, the output fuse maps and JEDEC data are generated. A more detailed description of the PALASM 2 design software is given in PAL Device Databook, Advanced Micro Devices, Sunnyvale Calif., pp. 4-1 to 4-198 (1988) which is incorporated herein by reference.
The PALASM 2 software and programmable logic device design software in general is typically limited to processing a design for a single programmable logic device. The programmable logic device may contain, for example, dedicated input pins, dedicated output pins, I/O pins, clock input pins, a programmable logic array, programmable macrocells, programmable buried macrocells, programmable output signal polarity, and programmable feedback. Typically, the programmable logic array provides a fixed number of product term lines to each macrocell and a fixed number of product term control lines to each macrocell. Equivalent processing steps exist for other prior art PLDs.
Another design software package for programmable logic devices is the Advanced Boolean Expression Language available from Data I/O, 10525 Willows Road, Redmond, Wash. 98073 which is identified as ABEL version 3.2. As illustrated in FIG. 2B, this design package is equivalent to the PALASM 2 design software design package described above. Design file 30 and parse 31 perform functions which are equivalent to design file 20 and parse 21 in FIG. 2A. Transform 32 (FIG. 2B) transforms state machine equations into Boolean logic equations and expands nested logic functions.
Similarly, expresso 33 is a logic minimizer which forms a function equivalent to minimize 23 (FIG. 2A). Expresso 33 generates a PLA file which may be used in fuse map 34 to generate a JEDEC file and output documentation file or alternatively in sim 35 to simulate the functional operation of the user design. The PLA file format of file 36 is a relative standard having been adapted by several industrial companies after its design within the academic environment.
Typically, PLD design software does not have a capability for fitting the user's logic equations to a multiplicity of programmable logic modules within a programmable logic device. However, there are several known processes for partitioning of logic designs. See for example, B. Kernigham & S. Lin, "An efficient procedure for partitioning graphs", Bell System Tech Journal, 1970; C. Fiduccia & R. Matteyses, "A linear time heuristic for improving network partitions", Proceedings 19th DAC, June
1982; and C. Palesko & L. Akers, "Logic Partitioning for Minimizing Gate Arrays", IEEE Transaction on CAD of IC's and Systems, April 1983. Each of these processes accepts a logic design and breaks the design into partitions, constrained for minimum pinout or logic resources in each of the partitions.
All of these algorithms make the assumption that there are no restrictions in connectivity between partitions, i.e. any signal declared in the top-level interconnect can freely go between any or all of the top modules. The algorithms seek to minimize the number of these signals, hence the name Min-Cut associated with these algorithms. Min-Cut seeks to achieve the lowest overall number of connections between partitions. However, when applied to PLDs, this generally results in additional processing because reduction of the connections below the device resource limits is unnecessary. The user design will fit in the PLD even if the partition is not at an overall minimum. Moreover, Min-Cut fails to produce partitions, i.e., logic blocks, that have the same size. The Min-Cut partitions may be of different sizes and may be either too big or too small for PLD implementation.
Thus, if a programmable logic devices has restrictions on interconnections between programmable logic blocks (partitions) and/or restrictions on signal routing between programmable logic blocks, the above algorithms are not applicable. Further, if the programmable logic blocks have the same size, the above algorithms do not effectively utilize the blocks. Any process used to partition a logic design for multiple programmable logic modules must take into account both the restricted interconnections present between logic modules, and the resources available in the logic modules.
Each of the three processes noted above begins with an initial partition, and via interchanges seek to improve the metric characterizing the partitioning. In theory, one could modify the calculation of the metric to include constraints on the interconnections present between modules and module size within a programmable logic device, but this calculation is along the critical path, i.e., the calculation is performed many times during the course of partitioning improvement. Therefore, such a modification would result in a process that required extremely long processing time.
Further, these processes only swap one logic module at a time, neglecting any "affinities" present between logic functions in a larger group of modules. Local "hills" and "valleys" in the optimization function almost certainly preclude finding any multiple module swap that is the global "best" choice.
Placement and routing processes in gate array and standard cell logic design tools, such as those described above, have successfully solved several general and specific forms of the placement and routing problem. Nearly all of these processes rely on the assumption that the physical coordinates of logic modules are directly related to wire delay, congestion and probability of success in creating the final physical device layout. This assumption also runs counter to the basic arrangement of interconnects present in programmable logic devices with multiple modules. Any nonlocal interconnect between modules costs the same as any other. A small change in position is unrelated to metrics of success. Placement optimizations based on such metrics will directly fail.
Thus, at present, a means for fitting a logic design to a programmable logic device having a variable number of clumped product terms per macrocell is not available. In addition, a means for fitting a logic design to a multiplicity of programmable logic modules with limited interconnections between the modules is not available.
SUMMARY OF THE INVENTION
According to the principles of this invention, resources in a programmable logic device (PLD) having at least two programmable logic blocks, usually of the same size, interconnected by a switch matrix are assigned to user logic equations using a novel resource allocation method and system. The system is operable in a computer system having a main memory and secondary memory. In a first operation, the resource allocation system (system) partitions the user logic equations into a multiplicity of modules based upon affinities between the user logic equations. There is one module in the multiplicity of modules for each of the programmable logic blocks in the programmable logic device. In a second operation, the system assigns resources in the programmable logic device to each of the user logic equations in each of the multiplicity of modules.
Initially, the system reads a user design and then information from databases located on secondary memory characterizing the PLD specified in the user design, or alternatively the PLD selected by the system based upon the user design. The system stores the user design and the product information in several data structures in main memory. The data structures include links and pointers for dynamically generating table information and other data required by the system. In this initialization process, a Boolean vector is created for each user logic equation. The Boolean vector has n bits where n is the total number of input signals in all the user logic equations. The bits are ordered to correspond to each of the n input signals.
In one embodiment, the bits in Boolean vectors are all set to a first determined value and then in each Boolean vector, the bits corresponding to the input signals to the logic equation associated with that Boolean vector are set to a second predetermined value to represent the presence of the input signals in the logic equation. This initialization process also determines the resource limits for each of the modules in the block partitioning process.
The partitioning system uses a similarity means to determine a similarity measure S for each pair of said user logic equations using the Boolean vectors associated with the pair of user logic equations. In one embodiment, only similarity measures greater than a predetermined limit are retained by the system for further processing. 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.
After the similarity measures are determined, the partitioning system places any user preplaced logic equations in the modules and decrements the resources for each module by the number of resources required to support the preplaced user logic equations. If the user does not preplace any equations, the partitioning system randomly assigns a user logic equation to each module and decrements the available resources.
The partitioning system uses a receptivity means to determine a receptivity of each module for each of said user logic equations. The receptivity is based upon the similarity between the logic equation input signals for an equation to be placed and the input signals of the logic equations already placed in the module. The use of input signals as a measure of similarity is only illustrative of the principles of the invention. Any parameter common to the logic equations may be used in the partitioning process, e.g., output signals.
Each user logic equations is assigned to the module having (i) the largest receptivity for the user logic equation and (ii) resources to support the user logic equation thereby partitioning the user logic equations into modules based upon the affinity of the logic equations input signals. When an equation is added to a module, the available resources in the module are decremented. If a module does not have sufficient available resources to support a user logic equation, the equation is assigned to a virtual module and a variable FulCnt for the module, which indicates the number of times the system attempted to add an equation to that full module, is incremented.
To ascertain the receptivity of a module for a user logic equation, the receptivity means determines, for each of the multiplicity of modules and one of said pairs of user logic equations, (i) a first similarity measure S1 for the Boolean vector for the first user logic equation in a pair and a Boolean vector for the input signals to the user logic equations already placed in the module and (ii) a second similarity measure S2 for the Boolean vector for the other user logic equation in a pair and the Boolean vector for the input signals to the user logic equations already placed in the module.
For each pair of module similarity measures S1, S2 in said multiplicity of modules, the maximum similarity measure SM is determined for that module. The maximum similarity measure SMMAX of the module maximum similarity measures SM is determined thereby determining the module that has the greatest receptivity for the user logic equation is the pair of user logic equations. In one embodiment, the maximum similarity measure SM for each module is adjusted by the value of the variable FulCnt for that module, i.e., the value of variable FulCnt is subtracted from SM. This process assures that the user logic equation is assigned to the most receptive module with available resources.
The user logic equation is placed in the module having the greatest receptivity only if that module has sufficient available resources to support the equation. Otherwise, the equation is assigned to a virtual module. If one equation in a pair of equations has been placed in a module, the partitioning means attempts to place the other equation in the same module. If sufficient resources are available in the module, the co-placement is made. Otherwise, the equation is assigned to the virtual module. If both equations in a pair have been placed in different modules, the partitioning means examines the available resources in both modules to determine if the modules can be merged. If sufficient resources are available in any of the modules, the modules are merged.
The similarity measure S is determined by a similarity means which includes a means for determining the input signals common to a pair of Boolean vectors and a means for determining the input signals in a first Boolean vector that are different from the input signals in a second Boolean vector. Both means generate an n bit Boolean vector. The bits in a Boolean vector C generated by the common input signal means represent the presence of common input signals in the pair of Boolean vectors while the bits in a Boolean vector D generated by the different input signal means represent the presence of different input signals in the vector pair.
In one embodiment a bit-wise AND of the pair of Boolean vectors associated with the pair of user logic equations is used to generate Boolean vector C. In this embodiment, a bit-wise Exclusive OR of the pair of Boolean vectors associated with the pair of user logic equations is used to generate Boolean vector D.
The similarity system counts the number bits in Boolean vector C having a first predetermined number, where the first predetermined number indicates the presence of common input signals. The similarity system also counts the number bits in Boolean vector D having the first predetermined number, where the first predetermined number indicates the presence of different input signals. The measure of similarity is generated by dividing the number D by a predetermined weight to form a number D1
and then subtracting the number D1 from the number C.
After all the logic equations are assigned to a module, the partitioning system attempts to place any equations in the virtual module in any module with sufficient resources to support the equation or equations. After all the equations are placed in a module associated with a programmable logic block, the number of interconnections and the fanout of signals are determined using the logic equations in each module. The modules are sorted by interconnection requirements so that the equations in the module requiring the greatest number of interconnection resources are assigned resources in the PLD when the maximum number of resources are available.
The resource assignment means assigns each of the modules to one of the programmable logic blocks in the programmable logic device. Note the block partitioning use the available resources in a programmable logic block to define the resource limits for a module, but the block partitioning does not associate a particular module with any particular programmable logic block. The resource assignment means uses the Hungarian assignment process to assign modules to programmable logic blocks.
The Hungarian assignment process uses a cost matrix where the rows of the matrix represent available resources in the programmable logic block and the columns represent elements in the module to be assigned to the rows. The number in the cost matrix at the intersection of a row and a column is the cost associated with using the resource represented by the row for the element, e.g. module, logic equation, or dedicated input signal, represented by the column. The Hungarian assignment process determines the optimal mapping of the columns in the cost matrix to the rows.
After assignment of blocks to modules, the resource assignment means assigns the resources in the blocks to the logic equations in the modules. In one embodiment, the logic equations, output logic equations and then buried logic equations, are assigned resources using the Hungarian assignment process. After the logic equations are assigned resources, the dedicated input signals are assigned resources. When a logic equation or input signal is assigned resources, the available resources in the block are decremented. A logic equation or input signal is allocated resources only if sufficient resources are available to support the equation or signal.
After all the equations in the modules have been allocated resources, the allocation system documents the user design and generates a JEDEC file that may be used to program the PLD. If the resource allocation fails, the user is provided diagnostic messages.
The block partitioning process has been described in terms of assigning user logic equations to modules associated within programmable logic blocks in a single programmable logic device. However, the partitioning process is suitable for a wide variety of applications. For example, an electronic device may have several interconnected PLDs where each PLD has resources to support several user designs. In this case, the PLDs correspond to programmable logic blocks and the designs correspond to user logic equation Thus, the block partitioning process assigns each of the user designs to modules based upon common input signals to the PLDs, for example. The modules may then be assigned to PLDs in the electronic device. Hence, the method and system of the invention provide a broad range of capability for rapidly and efficiently allocated resources in a device to user specified functions.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram of a typical prior art design support system for a programmable logic device.
FIG. 2A is a block diagram of the prior art PALASM 2 software design package for PAL devices.
FIG. 2B is a block diagram of the prior art ABEL software design package for PAL devices.
FIG. 3A is a listing of a four bit counter design input file for the PALASM 2 software design package.
FIGS. 3B and 3C are a listing of a state machine design input file for the PALASM 2 software design package.
FIG. 4 is a general block diagram of one of the families of electrically programmable logic device 400 for which the resource allocation means of this invention assigns resources to a user's logic design.
FIG. 5 is a block diagram of the resource allocation means of this invention.
FIG. 6 is a more detailed block diagram of the resource allocation means of this invention.
FIG. 7 is a block diagram illustrating one embodiment for generation of user design 100.
FIG. 8A illustrates the logic equation section of user design 100 in the TRE file format.
FIGS. 8B and 8C are an example of an ABEL user input file 100A (FIG. 7) for an eight bit counter.
FIGS. 8D and 8E are an example of a user design 100 for the eight counter design (FIGS. 8B and 8C) in the PLA file format for processing by resource allocator means 110 according to the principles of this invention.
FIG. 9 is a more detailed block diagram of the symmetric programmable logic block of device 400.
FIG. 10 is a detailed block diagram illustrating one embodiment of the first family of programmable logic devices 400.
FIG. 11 is a detailed block diagram illustrating one embodiment of the second family of programmable logic devices 400.
FIG. 12 is a schematic diagram of the programmable logic block in the first family of programmable logic devices 400.
FIG. 13 is a schematic diagram of the programmable logic block in the second family of programmable logic devices 400.
FIGS. 14A through 14C illustrate the router elements in the logic allocator of the first family of programmable logic devices.
FIGS. 15A, 15B, 15C, and 15D illustrate the router elements in the logic allocator of the second family of programmable logic devices.
FIG. 16 is a schematic diagram of a programmable logic macrocell in programmable logic devices 400.
FIG. 17 is a schematic diagram of a programmable buried logic macrocell in programmable logic devices 400.
FIG. 18 is a schematic diagram of an I/O macrocell in programmable logic devices 400.
FIGS. 19A and 19B are a representation of the input lines and the output lines to the programmable multiplexers in switch matrix 401A.
FIGS. 20A through 20D are a representation of the input lines and output lines of the programmable multiplexers in switch matrix 401B.
FIGS. 21A through 21E illustrate the information in the device database for the programmable logic device illustrated in FIG. 10 according to the principles of this invention.
FIG. 22 is a block diagram illustrating the input lines to a typical programmable multiplexer in the switch matrix and the definition of the product terms in the product term array driven by the multiplexer output line according to the principles of this invention.
FIG. 23 illustrates the structure of the symbol array, symbol records, and character records according to the principles of this invention.
FIG. 24 defines the symbol array, character array, and symbol record illustrated in FIG. 23.
FIG. 25 illustrates the signal array and the equation records stored in the signal array according to the principles of this invention.
FIG. 26 defines the signal array, the equation array, the equation record and the common record which are illustrated in FIG. 25.
FIG. 27 illustrates the physical array and the physical record structure used to store data according to the principles of this invention.
FIG. 28 defines the physical record, switch matrix array, fanout array, resource record and resource header record according to the principles of this invention.
FIG. 29 illustrates the data structure and main memory used to maintain the switch matrix array and the fanout matrix array including the record structure within the array.
FIG. 30 illustrates the structure in the main memory of the computer system for the pin array including the pin records.
FIG. 31 defines the pin array, the pin record, as well as other structures required for the means of this invention.
FIG. 32 defines two of the data structures used in the Hungarian assignment process according to the principles of this invention.
FIGS. 33A and 33B define constants and pointer declarations used in the resource allocation means of this invention.
FIGS. 33C through 33E define other data structures used in the resource allocation means of this invention.
FIG. 34 is a process flow diagram for the database initialization means of this invention.
FIG. 35 is a process flow diagram for reading a user design in the PLA file format according to the principles of this invention.
FIG. 36 is a process flow diagram for reading a user design in the TRE file format according to the principles of this invention.
FIG. 37 is a process flow diagram for reading the device database according to the principles of this invention.
FIG. 38 is a process flow diagram for the general crystallization process of this invention.
FIG. 39 is a process flow diagram for the block partitioning means of this invention.
FIG. 40 is a process flow diagram for grow modules (FIG. 39) in more detail.
FIGS. 41A through 41C are process flow diagrams for the processes within grow modules (FIG. 40) according to the principles of this invention.
FIGS. 42A through 42H illustrate one application of the Hungarian assignment process used in the resource assignment means of this invention.
FIGS. 43A through 43D is a process flow diagram for the resource assignment means of this invention.
FIG. 44 is a process flow diagram for map macro (FIG. 42B).
FIG. 45 is an example of the initial data in the output file according to the principles of this invention.
FIG. 46 is an example of a logic map produced by document generation 145 according to the principles of this invention.
FIG. 47 is an example of a pin map produced by document generation 145 according to the principles of this invention.
FIG. 48 is an example of a feedback map produced by document generation 145 according to the principles of this invention.
FIG. 49 is an example of a signal list produced by document generation 145 according to the principles of this invention.
FIGS. 50A through 50D is an example of a JEDEC file produced by document generation 145 according to the principles of this invention.
DETAILED DESCRIPTION
According to the principles of this invention, 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, unlike the prior art fitters, requires minimal programmable logic device resources to achieve the allocation of resources within the programmable logic device to the user logic design.
In one embodiment, as explained more completely below, 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. A general block diagram of the families of electrically programmable logic devices 400 for which one embodiment of the fitting means of this invention is useful is given in FIG. 4.
Each programmable logic device 400 includes a plurality of identical programmable logic blocks 402 arranged in an array. Programmable logic blocks 402 are interconnected through programmable switch matrix 401. Programmable logic blocks 402
communicate with each other only through switch matrix 401. Moreover, in this embodiment, programmable logic blocks 402 receive all input signals on lines 426 from switch matrix 401. Thus, programmable logic blocks 402 may be viewed as independent programmable logic devices on the same integrated circuit chip.
Each programmable logic block 402 may receive a first plurality of input signals from input/output (I/O) pins 403 through switch matrix 407. Dedicated input pins 404 provide a plurality of input signals to switch matrix 401. The input signals from pins 404 are available to each programmable logic block 402. Each programmable logic block 402 may also provide a first plurality of output signals for I/O pins 403.
As explained more completely below, each programmable logic block includes (i) a programmable logic array having a multiplicity of products terms; (ii) a multiplicity of programmable logic macrocells, which may include programmable buried logic macrocells, with each logic macrocell having a feedback line to the programmable switch matrix; (iii) a logic allocator for steering product terms to a particular logic macrocell and for decoupling the programmable logic array from the programmable logic macrocells; (iv) programmable I/O macrocells for configuring the I/O pins and for decoupling the programmable logic macrocells from the I/O pins.
Resource allocation means 110 (FIG. 5) of this invention includes a unification of two main processes--block partitioning 120 and resource assignment 130. Block partitioning means 120 attempts to partition a user design 100 into modules which have a logic affinity, e.g., in one embodiment, common input signals to the logic equations within the module.
After user design 100 is partitioned into modules, resource assignment 130 first assigns each module to one of programmable logic blocks 402 within programmable logic device 400 (FIG. 4). If logic device 400 is symmetric, the assignment of a particular module to a programmable logic block 402 is independent of the resources within the programmable logic block.
However, some programmable logic devices include programmable logic blocks having diagonal symmetry. See for example, the programmable logic devices described in U.S. patent application Ser. No. 07/243,574, entitled "Flexible, Programmable Cell Array Interconnected By A Programmable Switch Matrix" of Om P. Agrawal, et al., now U.S. Pat. No. 4,963,768 issued Oct. 16, 1990, which is incorporated herein by reference in its entirety. In such devices, modules are assigned to programmable logic blocks based upon the module's utilization of the resources within the programmable logic block. In general, the block assignment processes blocks without symmetry and in fact, may process arbitrarily sized blocks.
After resource assignment means 130 (FIG. 5) decides in which programmable logic block 402 (FIG. 4) to locate modules containing individual logic equations in user design 100, resource assignment means 130 sequentially determines for each programmable logic block 402 where to locate individual logic terms within programmable logic block 402 and how to configure both within the programmable logic block and within switch matrix 401 the programmable connections necessary to realize the desired user function.
Upon completion of resource assignment 130, resource allocation means 110, as explained more completely below, generates design documentation 140 for the user design and a JEDEC file 150 which may be downloaded to a programmer for actually programming programmable logic device 400.
Resource allocation means 110 is shown in more detail in FIG. 6. Resource allocation means 110 of this invention includes, (i) a database initialization means 115, (ii) block partitioning means 120 (iii) resource assignment means 130, and (iv) documentation generating means 145. Sometimes these means are referred to as processes within resource allocation means 110.
In database initialization means 115, user design 100 is processed. Typically, as described more completely below, user design 100 includes (i) a logic description encoded in a Boolean sum of products format, i.e., Boolean logic equations, (ii) a programmable logic part type, i.e. a PLD, chosen for this design and (iii) signal declarations provided by the user in a Pin/Node list.
Database initialization means 115 first initializes data structures used by resource allocation means 110 as described more completely below, and then reads the user's logic description and the programmable logic part type chosen for this design from user design 100. Database initialization means 115 also reads the signal declarations provided by the user in the Pin/Node list. Specifically, database initialization means 115 determines which signals are specified as input signals, output signals and buried nodes of the design.
The database initialization process also reads user supplied pin pre-placements for signals in the logic equations from PLC database 122. The initialization process locates the signals and related equations at the specified positions. If the specified positions result in contradictions, i.e., some of the input or output signals are unreachable with the connection resources provided within the programmable logic device, the user is notified.
Signals preplaced on specified pins are useful when design changes are anticipated after an initial prototype system is fabricated. Unless signal pre-placement is allowed, each time resource allocation means 110 maps a user design to the programmable logic device the pin-out would change. Such a change requires rewiring of the board or system in which the programmable logic device was used.
In addition to user design 100, database initialization means 115 reads the internal architecture description for the specified programmable logic device from a product database (PDB) 121 and checks the user logic design for compliance with the general size limits and resource usage of that device. If no errors are encountered, upon completion of the database initialization process, the user's design is ready for processing by block partition means 120.
In block partitioning means 120, the user's design is partitioned into modules that fit within the resource limits of individual programmable logic blocks 402 within programmable logic device 400. Initially, in the block partitioning process, logic equations that use common input signals are grouped together. The process then scans for "affinities," as described more completely below, between the groups of the logic equations and allocates the groups of logic equations within modules based upon these affinities In the partitioning process, the available logic resources are monitored so that the logic resources required by a module are not greater than the resources in a programmable logic block.
In one embodiment of block partition means 120, a different user logic equation is initially seeded, i.e., placed in each of the modules. The "affinity" used to subsequently place user logic equations in each of the modules is the similarity between the input signals to a user logic equation and the input signals for the user logic equation or equations already placed in the module. In this embodiment, each user logic equation is placed in the module having the maximum affinity, i.e., similarity, for the user logic equation, if sufficient resources are available in the module to support the equation.
While block partitioning means 120 automatically partitions the user's logic equations into modules that fit within the programmable logic blocks, an expert user may impart his choices for block partitioning by preplacing logic equations in particular programmable logic blocks. In this case, the block resource totals are decreased by the number of resources preplaced by the user prior to beginning the block partitioning process.
After the user's logic equations are segmented into programmable logic modules, resource assignment means 130 assigns the modules to programmable logic blocks and individual logic equations in the modules to physical resources with the programmable logic blocks. This process is done sequentially for each programmable logic block within the device starting with the block which uses the largest number of connection resources, as determined by block partitioning means 120, and proceeds finally to the block with the smallest number of connections. Thus, resource assignment means 130 performs the most difficult signal routing, i.e. resource assignment, when the programmable logic block and switch matrix 401 are the emptiest, i.e., when the maximum number of resources are available for signal routing.
As explained more completely below, resource assignment means, in one embodiment, performs a series of mapping processes. For example in a first process, equations containing independent output enable product terms are mapped to resources in the PLD. In a second process, I/O pin mapping to resources in the PLD is performed based upon product term usage. A subsequent process maps buried logic equations to resources in the PLD. Note "mapping" and "resource assignment" are the same operation. "Mapping" views the operation from the perspective of the user logic equations while "resource assignment" views the operation from the perspective of the PLD.
Prior to any resource assignment, logic equations assigned to pins by the user are allocated resources first. Next, in another embodiment of resource assignment means 130, the product terms required for each logic equation are placed in groups based on size (product term count), referred to as groups of similar size. For example, equations requiring 9-12 product terms are a first group. Equations requiring 5-8 product terms are a second group and so forth. Typically, groups of a similar size are determined by the multiples of product terms clumps available from the logic allocator. The equations in the first group are each assigned to an I/O pin from the available I/O pins, and then equations in the second group are processed and so on. When a logic equation is assigned to an I/O pin, the product terms associated with realizing each of the assigned logic equations are routed to form an OR-tree of the proper size to realize the logic equation, as explained below in more detail.
In yet another process, typically performed after the I/O pin mapping process, buried logic functions are placed in the "holes" remaining, i.e., unutilized resources, after the I/O pin mapping. Finally, any remaining dedicated input signals are assigned to any available free pins, either unused I/O pins or those I/O pins associated with a buried logic cell.
At each stage within resource assignment means 130, connection resources needed are "marked" as used. The used resources affect the later resource assignment decisions. Iterative trial and error cycles for this assignment process are avoided by having a slight excess in the number connections available and by simultaneously evaluating alternative feasible assignments, as explained more completely below.
Upon successful completion of resource assignment 130, documentation means 145 generates in design documentation 140 three outputs that reflect results of mapping user design 100 to the programmable logic device resources. A logical map (FIG.
46) depicts, as described more completely below, (i) the mapping of the user logic onto programmable logic blocks and (ii) the interconnects provided by switch matrix 401. A pin map (FIG. 47), as described more completely below, depicts user signal names associated with package pins. The pin map is a "customized" package outline, which allows the user to quickly locate signals on a breadboard.
Finally, a signal list is provided in design documentation 140. The signal list (FIG. 49) is a comprehensive tabulation detailing (i) the signal location, (ii) the type of equation, e.g., combinatorial, D-type flip-flop or T-type flip-flop, (iii) whether the signal is used as a feedback signal and (iv) the logic equations driven by the signal. Also, the programmable logic block and the macrocell location for the signal is given. Additionally, as previously described, JEDEC file 150 for programming the device in a suitable programmer may be generated.
In one embodiment, resource allocation means 110 is operating within a computer system. The computer system includes main memory which holds at least the computer operating system, resource allocation means 110 data, secondary memory (typically, disks) which typically holds PLC database 122, PDB 121 and user design 100. The computer system also includes a means for user input, printing and a video display screen.
One system suitable for use with this invention is the Apple MacIntosh SE computer system with a 20 Megabyte hard disk drive. Alternatively, an IBM or IBM compatible AT class computer with a 80.times.86 microprocessor, a 40 Megabyte hard disk drive, a 1.2 Megabyte floppy disk drive and 640 Kbytes of main memory is suitable for use with this invention.
In either computer system, the Pascal computer programming language was used in one embodiment of this invention. In particular Turbo Pascal, Version 1.1 for the Apple MacIntosh computer system and Turbo Pascal for the IBM PC, Version 5.0 for the IBM and IBM compatible computer systems was used. Both of these computer languages and the associated compilers were obtained from Borland International of Scotts Valley, Calif. The two versions of this invention are portable between Apple MacIntosh computers and the IBM compatible computers with only minor changes.
User design 100 (FIGS. 5 and 6) may be either a design for several interconnected PAL-like devices or a design for one monolithic device. In this embodiment, user design 100 is, in one embodiment, a file with a PLA format and in another embodiment a file with a TRE format. The resource allocation means 110 of this invention is suitable, for example, for replacing either xplot 24 (FIG. 2A) or fuse map 34 (FIG. 2B) in the prior art software design packages. Thus, user design 100 may be generated in multiple ways. For example, as illustrated in FIG. 7, user design 100 may be generated starting with a design input file 100A in a PALASM 2 format, which was described above and is incorporated herein by reference.
However, to use the prior art software design packages with the resource allocation means 110 of this invention, these software design packages must be modified so that they can process syntax associated with the description of programmable logic devices 400, which are described more completely below. Also, the packages must be modified to include the expanded logic capability of devices 400. Accordingly, while the operations of the prior art software packages necessary to generate the PLA file format are not essential to this invention, the general operations that must be modified in such packages to handle programmable logic devices 400 are briefly described below.
Parse 21A (FIG. 7) checks the syntax of design input file 100A. Parse 21A is substantially identical to parse 21 (FIG. 27), 31 (FIG. 2B) with additions for processing syntax associated with programmable logic devices 400. Such additions are apparent to those skilled in the art in view of the description of programmable logic devices 400. If parse 21A detects an error in file 100A, the location of the error is indicated and a message displayed on the video display screen. The error messages are stored in a file that is accessed by parse 21A. To facilitate completion of a design, parse 21A attempts to recover after detection of each error and continue with the syntax checking. If design input file 100A is error free, parse 21A creates an intermediate file with a TRE file format for processing by expand 22A.
Using the intermediate file from parse 20A, expand/transform 22A expands the input equations and converts state machine syntax to Boolean equations. Again, expand/transform 22A is substantially identical to expand 22 (FIG. 2A) and transform 32
(FIG. 2B) described above. Expand/transform 22A creates another intermediate file that contains expanded Boolean equations.
Logic minimizer 23A processes either the intermediate file from parse 21A or the intermediate file from expand 22A. Logic minimizer 23A looks for logic redundancy and minimizes the AND and OR expressions. Logic minimizer 23A is also substantially identical to minimizer 23 (FIG. 2A) and expresso (33) as described above. Minimizer 23A produces yet another intermediate file. Typically, the file produced by minimize 23A is user design 100.
Of course, parse 21A, expand/transform 22A and logic minimizer 23A have been modified to process the features of the programmable logic devices having multiple programmable logic blocks interconnected by a switch matrix and both D-type flip-flop and T-type flip-flop capability. Specifically, the processes are modified to handle the syntax associated with the new devices such as the floating pin/node syntax and signal pre-placement within logic blocks. Also, minimizer 23 must handle D/T flip-flop equation minimization and transfer equations linking input storage functions. The required modifications will be apparent to those skilled in the art in view of the following more detailed description of the logic devices and the form of the various data structures that are processed.
While one embodiment for generating user design 100 has been described, those skilled in the art may use equivalent processes to generate user design 100. The important aspect is that user design 100 includes the information, described more completely below, in either the TRE format or preferably the PLA format. Both of these file formats contain similar information and in fact are constructed very similarly. Therefore, resource allocation means 110 of this invention assumes that either another computer program has generated user design 100 or alternatively that user design 100 has been thoroughly checked out and contains correct information. The data in the user design 100 must be in the proper low-level format whether the file is generated by a computer program or some other means.
Further, resource allocation means 110 of this invention could be used without minimizing the logic equations, but such a use may result in an inefficient utilization of resources within the programmable logic device. Similarly, the state machine equation conversion to Boolean equations performed by expand 21A could be performed in numerous ways. Again the important aspect is that Boolean equations are generated for the state machine.
Typically, user design 100 includes a part number for the programmable logic device selected by the user and a global pin/node list of all signals interfaced to the "outside world", e.g., the signals that are supplied to or generated by programmable logic device 400. If the information is a pin list, each signal has a number associated with the signal that refers to a physical device pin. Otherwise, the number associated with a signal refers to sequential logical nodes, which are not directly associated with physical device resources.
If too many of the signals are constrained to specific pins, resource allocation means 110, described more completely below, may fail to map user design 100. Specifically, if too many pins are constrained, some contradictions may be detected when locating a logic function because some of the function's input signals or output signals may be unreachable.
Each of the signals in the global pin/node list is marked with an attribute of the signal (Input, I/O Pin, buried equation). However, if the signal attribute is not specified, the attribute is determined in database initialization means 115 by looking at the signal usage within the logic equations. Other signal attributes, such as registered (D-type and T-type flip-flops) latched, combinatorial, signal polarity, are also provided in user design 100.
Typically, in the TRE file format, user design 100 has, in addition to the part name and the pin/node section, an equation section. The equation section contains Boolean logic equations for each module of the design. Specially, the logic for each module in the user design is specified in the form of a Boolean AND/OR equation (Sum of Products--SOP format). There are no restrictions on the number of terms in the logic equations or the number of product terms. Further, there are no restrictions on the number of logic equations in user design 100. However, the number of logic equations must fit within the selected programmable logic device or the mapping will not be successful.
In general, the Boolean logic equations may be either registered or combinatorial and may be isolated from other equations or may directly feed other equations, e.g., a design module may have independent input and output signals or two design modules may share input signals. An output signal of one design module may be an input signal to a second design module. Auxiliary equations for register clock, output enable, set, reset, etc., are allowed in user design 100.
The equation section of the TRE file is depicted graphically in FIG. 8A using a simple example of two logic equations "XYZ" and "CAS" where:
Each of the circled variables represent nodes or records in a structured database. Each node contains two pointers to its children. Overall, the information in FIG. 8B represents the Pre-fix parse tree generated by standard LL(1) language compilers created to process language grammars.
The highest nodes 610, 620 are the equation labels, containing the equation name, and linked to the next equation. Each equation has its own functional definition given in the lower level nodes 611-617 and 621-627, respectively. In traversing the operations, a right branch, left branch order is used, proceeding to its end.
The equation data can also be stored in a sequential manner (610, 611, 612, . . . 627), using numerical codes to identify each element, its datatype, and optionally provide a signal name ("Abc") if present. This equation section is a fragment of the disk-based TRE user design 100.
Various codes have been defined for the symbols used in the equation section of a TRE file, e.g., ":=" registered transfer, "=" combinatorial transfer, "*" logic AND, "+" logic OR, "/" logic not or complement, as well as others.
In the computer memory resident device 400 data structure (equation EQU.sub.-- ARY (FIG. 26), described below), single byte values (0-255) represent both the logic operations and the logic variables to be manipulated--thus the entire structure can be stored quite compactly. If additional variables or operations have to be handled beyond the 255 codes defined, an extension code points to additional data. The exact codings used are quite arbitrary and so are not considered further.
As explained above, user design 100 may be generated by a prior art software design package that has been modified to include a capability for processing programmable logic devices 400, which are explained more completely below.
An example of a user design file 100 in the PLA format is illustrated in FIGS. 8D and 8E. The file in FIGS. 8D and 8E is a eight bit counter file for the eight bit counter specified in the ABEL user input file 100A (FIGS. 8B and 8C). The important aspect for user design 100 is that it is error free and has the proper PLA file format, which is presented below. As explained more completely below in data initialization 115 the only error checking performed on user design 100 is that of syntax and the error recovery is limited to skipping to the next record in the user design 100 after providing the user with a brief error message.
User design 100 in the PLA file format is described by a series of AND/OR expressions written as a sequence of the characters {"0", "1", "-", " "} within lines of a programmable logic array (PLA). The PLA file format was developed at the University of California at Berkeley and is documented in the "Expresso - UNIX programmer's Manual" (March/1985), "Berkeley Logic Interchange Format (BLIF)" April/1987, and also R. Braytons, et al., Logic Minimization Algorithms for VLSI Synthesis, Klewer Academic Publishers, 1984.
In the PLA file format, the first element on a line introduces the data that is to follow. A pound sign "#" introduces a comment line. Eight data types, as illustrated in Table 1, are introduced by a period "." followed by a unique type name. In the case where a multiplicity of items may follow, a decimal number field [d], comes next to specify the number of objects to follow--zero and all positive numbers are legal parameters. The data in Table 1 is from the UCB Expresso Programmers Manual.
TABLE 1 ______________________________________ A Description of the PLA File Format for User Design 100 ______________________________________ .i [d] Specifies the number of input variables. .o [d] Specifies the number of output variables. .ilb signal.sub.-- list Specifies the list of output signal variables. signal.sub.-- list Consists of an Alphanumeric signal name, followed by (i) an optional signal extension, (ii) an optional active-low polarity indicator ("-"), and finally (iii) an optional node number field (":[d]") using a colon and decimal number. (The signal extension is a member of the list (D, T, G, C, AR, AP, RE, LE, where D = D-type FF, T = T-type FF, G = Latch, D = Clock Equation, AR = Async Reset, AP = Async Preset, RE = Reset, and LE = Latch Enable) describing the function for configuring the macrocell realizing the output variable. For a description of the members of this list see, "OPEN ABEL Specification" DRAFT, Feb. 27, 1990, which is available from DATA I/O. .ob signal.sub.-- list Specifies the list of output signal variables. .type [s] Specifies the logical interpretation of the PLA lines -- i.e., whether on-set, off-set or both are provided. - Both ("fr") is most usual. .phase Specifies how the output boolean.sub.-- vector variables are to be defined, in terms of on-set ("1") or off-set ("0") for the minimal realization. A full vector of ones is assumed if no phase is provided. .p [d] Specifies the number of product terms (one per line) to follow. Each product term consists of two fields -- an input string and an output string. The input string uses the characters {"1", "0", "-"} for the inclusion of a logic variable, its complement or a "don't care" at that position of the AND. The output string uses the characters {"0", "1", ".about."} for definition of a logic function ("on-set"), its complement ("off- set") or no inclusion at that position of the OR sum term. At least one space separates the input and output strings. In this embodiment, additional spaces and line breaks can be inserted within the input and output strings. .e Marks the end of the PLA description. ______________________________________
Various extensions to the PLA file format have been proposed in the form of user comments, i.e., lines beginning with the characters {"#$"}, followed by a keyword.
Typically, these user comments are used to target the design within a specific PLD architecture, or within a user design environment, and to provide additional labeling of physical device pins and circuit nodes.
Five extensions--{TITLE, JEDECFILE, DEVICE, PINS, NODES} have been implemented in resource allocation means 110, and others may be considered in future embodiments. Each of the names are descriptive of the type of information contained on the line in user design 100.
PINS and NODES data types contain a number and a signal list (including the optional polarity and optional number filed ("-" and ":[d]"). A number of zero ("abc/0") is interpreted to allow that pin or node to float to any circuit point at the discretion of resource allocation means 110.
TITLE, JEDECFILE, and DEVICE introduce an ASCII string of characters, terminated by the end-of-line. These user comments are more informational, indicating choices made by the designer of the logic function implemented.
The lines of the PINS statement for devices 400, described below, are typically rather long. The UCB standard and DATA I/O's implementation provide for no specific breaking point in long line. Accordingly, resource allocation means 110 allows line breaks to be inserted at any space, and comments also to be placed in-line.
Resource allocation means 110 supports programmable logic device architectures consisting of a network of interconnected programmable logic blocks with each programmable logic block having both programmable and fixed connections. Resource allocation means 110 is adaptable to a variety of device configurations and architectures because resource allocation means 110 reads information on chip physical resources from product database (PDB) 121. The use of PDB 121 allows resource allocation means 110 to be used with a range of architectures.
Herein, PDB 121 is described in terms of two families of programmable logic device 400. To understand the structure of PDB 121, the structure of the two families of programmable logic device 400 must be understood. Thus, prior to describing PDB
121 in more detail, the two families of programmable logic device 400 are described. A more complete description of the two logic device families is given in copending, commonly assigned, and commonly filed U.S. patent application Ser. No. 07/490,808, entitled "Multiple Array High Performance Logic Device Family" of Om P. Agrawal et. al, now U.S. Pat. No. 5,015,884, issued on May 14, 1991, which is incorporated herein by reference in its entirety.
As illustrated in more detail in FIG. 9, each programmable logic block 402 in programmable logic device 400 contains a programmable logic array, for example a product-term array 410, a logic allocator 411, logic macrocells 412, and I/O macrocells
413. Product-term array 410 generates the basic logic using signals provided by switch matrix 401 Logic allocator 411 is programmable so that product terms from array 410 are distributed to logic macrocells 412 as required by the user of device 400. Logic macrocells 412 configure the signals from logic allocator 411 as explained more completely below. Each logic macrocell includes a programmable flip-flop.
The output signals from logic macrocells 412 are provided to I/O macrocells 413 and feedback to switch matrix 401 over lines 427. Each logic macrocell that may be used to generate an output signal is coupled to an I/O macrocell I/O macrocells
413 deliver the output signals from macrocells 413 to I/O pins 403. Alternatively, I/O macrocells 413 provide input signals from I/O pins 403 to switch matrix 401 over lines 428. If an I/O cell is used to configure an I/O pin as an input pin, the logic macrocell associated with that I/O cell can function as a buried logic macrocell.
Each programmable logic block 402 additionally contains, in this embodiment, an asynchronous reset product term and an asynchronous preset product term. These product terms are used to initialize all flip-flops within programmable logic block
402. In addition, in one embodiment, each programmable logic block 402 contains two output enable product terms for every eight I/O macrocells in the block. In each programmable logic block 402, I/O macrocells 413 are divided into banks where each bank, in this embodiment, contains eight I/O macrocells. Each bank of I/O macrocells 413 receives two of the output enable product terms.
Thus, each programmable logic block 402, in this embodiment, has a multiplicity of product terms in product term array 410 which provide control functions to all macrocells in block 402. Symmetric programmable logic device 400 with programmable switch interconnect matrix 401 is further subdivided into two families. A first family 400A (FIG. 10) includes 44, 68, and 84 pin devices with 32 to 64 logic macrocells respectively. This family, with a high pin-to-logic ratio, is targeted to address I/O intensive applications.
Conversely, a second family 400B (FIG. 11), with a high logic-to-pin ratio, is targeted to address logic intensive applications. The second family offers twice the logic capability of the first family in the same package. The use of two families provides a convenient way for migrating designs up or down with little difficulty. The I/O and logic intensive nature of the families offers system designers broader options, allowing them to suit their designs to appropriate devices.
FIG. 10 illustrates the first family of programmable logic devices 400A, according to the principles of this invention. Logic device 400A is a 44 pin device which has 32 I/O pins 403A-1, 403A-2 and six dedicated direct input pins 404A. Each of the programmable logic blocks 402A-1, 402A-2 are identical and include a product term array 410A-1, 410A-2, a logic allocator 411A-1, 411A-2, 16 logic macrocells 412A-1, 412A-2, and 16 I/O macrocells 413A-1, 413A-2.
In the figures, a line with a slash through the line and then a number N is used to indicate that the line represents N lines. Hence, switch matrix 401A provides twenty-two input signals to product term array 410A-1 over twenty-two input lines
426A-1. Similarly, logic macrocells 412A-1 provide feedback signals to switch matrix 401A over sixteen lines 427A-1 and I/O macrocells 413A-1 provide I/O pin feedback signals to switch matrix 401A over sixteen lines 428A-1.
FIG. 11 is a block diagram of the second family of programmable logic devices 400B according to the principles of this invention. As previously described, this family of logic devices 400B has a higher logic to pin ratio than the first family
400A. Thus, in this embodiment, each programmable logic block 402B has only eight I/O pins 403B. Product term array 410B, logic allocator 411B and logic macrocells 412B in programmable logic block 402B are similar to the corresponding devices in programmable logic block 402A (FIG. 10). However, logic macrocells 412B include output logic macrocells 412BA (FIG. 11) and buried logic macrocells 412BB.
In one embodiment of second family 400B, each programmable logic block 402B (FIG. 11) is connected to only eight I/O pins 403B. Thus, only eight of logic macrocells 412B are coupled to eight I/O macrocells 413B which in turn are coupled to eight I/O pins 403B (FIG. 11). The other eight logic macrocells are buried lo