초록 ▼

A softPAL implementation and mapping method are described. The implementation utilizes both LUTs and architecture-specific logic circuits to implement softPAL functions, and selects from several implementations in order to decrease delay in function implementation. The method describes techniques

A softPAL implementation and mapping method are described. The implementation utilizes both LUTs and architecture-specific logic circuits to implement softPAL functions, and selects from several implementations in order to decrease delay in function implementation. The method describes techniques for estimating p-terms in a 2-bounded sub-graph, factoring methods, mapping strategies for LUTs and dedicated logic elements, and delay optimization of critical paths.

대표청구항 ▼

What is claimed is: 1. A method for mapping a function to logic in a programmable logic device having at least one look up table (LUT) and at least one dedicated logic element, the method comprising: factoring the function to derive a factored form of the function; placing input variables of the fu

What is claimed is: 1. A method for mapping a function to logic in a programmable logic device having at least one look up table (LUT) and at least one dedicated logic element, the method comprising: factoring the function to derive a factored form of the function; placing input variables of the function having later arrival times closer to the output location of the function than input variables having earlier arrival times; implementing the factored form of the function according to a plurality of configurations of logic using the at least one LUT and the at least one dedicated logic element; and selecting a configuration of the plurality of configurations implementing the factored form of the function having the least delay. 2. The method of claim 1, wherein implementing the factored form of the function according to a plurality of configurations using the at least one LUT and the at least one dedicated logic element comprises: implementing a first portion of the factored form of the function using the LUT; and implementing a second portion of the factored form of the function using the dedicated logic element. 3. The method of claim 1, wherein factoring the function to derive a factored form of the function comprises forming a plurality of factored cube sets for the function, wherein each factored cube set comprises a shared set and an unshared set. 4. The method of claim 3, wherein the function comprises a plurality of p-terms, and forming a plurality of factored cube sets comprises: forming a first factored cube set to accommodate a first p-term; and forming a second factored cube set to accommodate a second p-term when the first factored cube set cannot accommodate the second p-term. 5. The method of claim 4, further comprising: forming a third factored cube set to accommodate a third p-term when the first factored cube set and the second factored cube set cannot accommodate the third p-term. 6. The method of claim 3, wherein implementing the factored form of the function according to a plurality of configurations using the at least one LUT and the at least one dedicated logic element, comprises: using a first LUT to perform a first function on a first portion of the shared set of a first factored cube set; using a second LUT to perform a second function on a portion of the unshared set of the first factored cube set; and forming a first LUT chain by coupling the first LUT and the second LUT using a first dedicated logic element of the programmable logic device. 7. The method of claim 6, further comprising: using a third LUT to perform a third function on a second portion of the shared set of the first factored cube set; and expanding the first LUT chain by coupling the third LUT to the first LUT chain using a second dedicated logic element of the programmable logic device. 8. The method of claim 7, further comprising sorting variables of the shared set based on arrival time. 9. The method of claim 7, further comprising calculating a maximum variable arrival time for each LUT. 10. The method of claim 9, wherein the first LUT chain is arranged based on the maximum variable arrival time of each LUT. 11. The method of claim 6, further comprising: using a third LUT to perform a third function on a second portion of the unshared set of the first factored cube set; and expanding the first LUT chain by coupling the third LUT to the first LUT chain using a second dedicated logic element of the programmable logic device. 12. The method of claim 6, wherein the first dedicated logic element includes a carry element. 13. The method of claim 6, further comprising: forming a second LUT chain for a second factored cube set; and coupling the second LUT chain to the first LUT chain with a second dedicated logic element of the programmable logic device. 14. The method of claim 13, wherein the second dedicated logic element is a cascade element that implements the OR function. 15. The method of claim 13, further comprising: calculating an associated delay for each LUT chain; and arranging the LUT chains based on the associated delays. 16. The method of claim 3, wherein implementing the factored form of the function using a dedicated logic element, comprises: using a first combination of look up tables (LUTs) to implement a first factored cube set; using a second combination of LUTs to implement a second factored cube set; and forming a first look up table (LUT) chain by coupling the first combination of LUTs and the second combination of LUTs using a first dedicated logic element of the programmable logic device. 17. The method of claim 16, wherein the first dedicated logic element is a carry element. 18. The method of claim 17, wherein the carry element is a multiplexer configured to implement a logical OR function. 19. The method of claim 17, wherein the carry element is a multiplexer configured to implement a logical AND function. 20. The method of claim 16, further comprising: using a third combination of LUTs to implement a third factored cube set; and expanding the first LUT chain by coupling the third combination of LUTs to the first LUT chain using a second dedicated logic element of the programmable logic device. 21. The method of claim 16, further comprising calculating a LUT combination delay for each combination of LUTs. 22. A programmable logic device configured to implement a function in factored form having a plurality of factored cube sets, wherein each factored cube set comprises a shared set and an unshared set, the programmable logic device comprising: a first look up table (LUT) configured to implement a first portion of the shared set of a first factored cube set; a second LUT coupled to implement a portion of the unshared set of the first factored cube set; and a first dedicated logic element coupling the first LUT and the second LUT to form a first LUT chain having a selected configuration of a plurality of configurations of the first and second LUTs and the first dedicated logic element, the selected configuration having the least delay of the plurality of configurations when configured in the programmable logic device, wherein input variables of the function having later arrival times are placed closer to the output location of the function than input variables having earlier arrival times. 23. The programmable logic device of claim 22, further comprising: a third LUT configured to implement a second portion of the shared set of the first factored cube set; and a second dedicated logic element coupling the third LUT to the first LUT chain. 24. A programmable logic device, configured to implement a function in factored form having a plurality of factored cube sets, wherein each factored cube set comprises a shared set and an unshared set, the programmable logic device comprising: a first combination of look up tables (LUTs) configured to implement a first factored cube set; a second combination of LUTs configured to implement a second factored cube set; and a first dedicated logic element coupling the first combination of LUTs and the second combination of LUTs to form a first chain of combinatorial look up table (LUT) elements, the first chain of combinatorial LUT elements being selected from a plurality of configurations of chains of combinatorial LUT elements and dedicated logic elements implementing the function and having the least delay of the plurality of configurations of chains, wherein input variables of the function having later arrival times are placed closer to the output location of the function than input variables having earlier arrival times. 25. A method of mapping a softPAL into a programmable logic device (PLD), wherein a softPAL is a function that, when written in a sum-of-products (SOP) form, is too wide to be implemented in a single lookup table (LUT) but may be implemented using a combination of lookup tables (LUTs) and dedicated logic elements, the method comprising: expressing the softPAL as a sum-of-products (SOP) function; factoring the SOP function into at least one chain of factored cube sets (FCSs) having the form description="In-line Formulae" end="lead"F( i)=<shared set>*<unshared set>,description="In-line Formulae" end="tail" where the shared set is a logical AND function of any number of variables, and the unshared set is a logical OR function of K or fewer logically ANDed variables, where K is a number of inputs to a lookup table (LUT) in the PLD; determining a configuration of LUTs and dedicated logic elements, of a plurality of configurations of LUTs and dedicated logic elements, having the least delay for the at least one chain of FCSs; implementing the at least one chain of FCSs with the combination of LUTs and dedicated resources having the least delay, wherein input variables of the function having later arrival times are placed closer to the output location of the function than input variables having earlier arrival times. 26. The method of claim 25 further comprising: adding product terms to the unshared set to be implemented by a LUT until K is reached, then forming another FCS if additional product terms remain. 27. The method of claim 25 wherein three schemes are considered for the step of implementing the at least one chain of FCSs with a combination of LUTs and dedicated resources. 28. The method of claim 25 wherein the step of implementing implements at least one portion of the shared set in a carry chain of the PLD. 29. The method of claim 25 wherein the step of implementing implements at least one portion of the unshared set using cascade OR gates of the PLD. 30. The method of claim 25 wherein the step of implementing implements at least a portion of the unshared set in a carry chain of the PLD. 31. The method of claim 25 wherein the step of implementing comprises: calculating maximum arrival delay of variables in the unshared set; forming a LUT implementation from the variables in the unshared set; and combining the LUTs implementing the shared and the unshared sets. 32. The method of claim 25 wherein the step of implementing comprises: generating a sorted shared variable list by arranging the shared variables in order of arrival times of the shared variables; and forming a sorted LUT chain by grouping the sorted shared variables into LUTs with earliest arriving variables closest to a beginning of the LUT chain. 33. The method of claim 25 wherein the step of implementing comprises: for each FCS, implementing an FCS chain within a single CLB; and calculating delay of the FCS chain; arranging the FCS chains in increasing order of delay of the FCS chain; and connecting the FCS chains using cascade elements implementing a logical OR function. 34. The method of claim 33 wherein the step of implementing further comprises: sorting FCSs in each FCS chain in increasing order of delay of the FCSs in the FCS chain. 35. A method for mapping a function to logic elements in a programmable logic device comprising: factoring the function to derive a factored form of the function; determining arrival time for input signals to each factor in the factored form; implementing the factored form of the function such that each factor is implemented by one of a plurality of lookup tables, and factors having signals with the latest arrival times are implemented by lookup tables closest to an output location of the function; implementing the factored form of the function according to a plurality of configurations using the plurality of lookup tables and at least one dedicated logic element; and selecting a configuration of the plurality of configurations with the least delay. 36. The method of claim 35, wherein a determination of which logic elements are closest to an output location is determined by using a cost table specifying delay for each softPAL that implements a factor. 37. The method of claim 36, wherein the cost table includes softPALs listed in order of increasing delay. 38. The method of claim 36, wherein each softPAL that implements a factor is selected from a plurality of possible softPALs that can implement the factor. 39. The method of claim 36, wherein each softPAL is selected from the plurality of possible softPALs based on minimizing delay. 40. A post-mapping optimizing method comprising: (a) forming a mapped design mapped to a combination of look up tables (LUTs) and original sized softPALs, wherein a softPAL is a function that, when written in a sum-of-products (SOP) form, is too wide to be implemented in a single lookup) table (LUT) but may be implemented using a combination of lookup tables (LUTs) and dedicated logic elements; (b) calculating original critical path delay in the mapped design; (c) for each critical path in the mapped design: re-mapping the critical path node to a larger sized softPAL; if delay is reduced, accepting the large sized softPAL; if delay is not reduced, retaining the look up table (LUT) or original sized softPAL; (d) re-calculating a new critical path delay for a new mapped design; (e) if the new critical path delay for the mapped design is less than the original critical path delay, accepting the new mapped design; and (f) repeating steps (a) through (e) until the new critical path delay for the mapped design is not less than the original critical path delay. 41. A method for determining a delay of a node for implementing a softPAL using a combination of look up tables (LUTs) and dedicated logic elements, wherein a softPAL is a function that when written in a sum-of-products (SOP) form is too wide to be implemented in a single LUT but may be implemented using a combination of LUTs and dedicated logic elements, the method comprising: forming a first set of one or more factored cube set (FCS) chains representing the equation; implementing the first set of FCS chains with a first implementation scheme; assigning a delay to the node of the first implementation scheme; forming a second set of one or more FCS chains representing the equation; implementing the second set of FCS chains with a second implementation scheme; and updating the delay of the node when a delay of the second implementation scheme is less than the delay of the node. 42. A method for decreasing delay of a node in a critical path during a mapping of a function, comprising: providing a cost table, in decreasing order, of estimated delays associated with a plurality of elements for mapping the function; implementing the function in programmable logic of a programmable logic device using a first element in the cost table; obtaining a first delay for the node based on the first element in a cost table; assigning the first delay to a delay of the node; selecting a second element in the cost table to map the function, the second element in the cost table comprising a different number of inputs than the first element in the cost table; implementing the function in programmable logic of a programmable logic device using the second element in the cost table; obtaining a second delay for the node based on the second element in the cost table; and assigning the second delay to the delay of the node when the second delay is smaller than the first delay. 43. A method of mapping a function to a combination of one or more LUTs and dedicated logic elements, the method comprising: forming factored cube sets (FCSs) from the function; configuring, according to a plurality of configurations, a set of one or more vertical elements to perform a logical function; mapping, for each configuration of the plurality of configurations, the FCSs to a series of one or more LUTs performing logical functions; selecting a configuration of the plurality of configurations having the least delay; coupling the one or more LUTs with the one or more vertical elements according to the selected configuration, wherein input variables having later arrival times are placed closer to the output location of the function than variables having earlier arrival times.