Literal sharing method for fast sum-of-products logic
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-017/50
출원번호
US-0847965
(2004-05-18)
발명자
/ 주소
Kaviani, Alireza S.
출원인 / 주소
Xilinx, Inc.
인용정보
피인용 횟수 :
2인용 특허 :
14
초록▼
A method and apparatus for implementing fast sum-of-products logic in a field programmable gate array (FPGA) is disclosed. The method includes literal-sharing decomposition of the sum-of-products logic to reduce the number of configurable logic block (CLB) slices required to implement wide fan-in lo
A method and apparatus for implementing fast sum-of-products logic in a field programmable gate array (FPGA) is disclosed. The method includes literal-sharing decomposition of the sum-of-products logic to reduce the number of configurable logic block (CLB) slices required to implement wide fan-in logic functions on an FPGA. The decomposition is performed by combining product terms having similar literal patterns. The apparatus includes a CLB including a plurality of slices and a second-level logic (separate from the slices) circuit to combine the outputs of the slices. Typically, the second-level logic is an OR gate or its equivalent that implements the sum portion of the sum-of-products expression. Alternatively, a combining gate may be included within the slice to combine the output of the slice with the output of another slice preceding the first slice.
대표청구항▼
1. A literal-sharing decomposition method for implementing a combinational logic function expressed in sum-of-products format having product terms, the method comprising:a. identifying a product term having a most number of literals;b. defining the identified product term as a product chain;c. selec
1. A literal-sharing decomposition method for implementing a combinational logic function expressed in sum-of-products format having product terms, the method comprising:a. identifying a product term having a most number of literals;b. defining the identified product term as a product chain;c. selecting, from remaining product terms, another product term having a next most number of literals;d. performing, for the selected product term, the following:i. determining whether the selected product term fits into any product chain;ii. defining the selected product term as a new product chain if the selected product term does not fit into any product chain;iii. combining the selected product term into one of the product chains if the selected product term fits into any existing product chain; ande. repeating steps c and d until all the remaining product terms have been selected.2. The method recited in claim 1 wherein each of the product chains can be implemented on at least one configurable logic block slice having configurable function generators including lookup tables (LUTs) and a carry circuit, and wherein the step of determining whether the selected product term fits into any product chain comprises the step of determining, for the selected product term and a product chain, the following:a. whether the carry circuit of a slice within the product chain is used as an OR gate or as an AND gate;b. whether the selected product term can be added to a LUT within the product chain; andc. whether a sum of non-shared literals between the product chain and the selected product term is bounded within a predetermined bound limit.3. The method recited in claim 2 wherein the selected product term can be added to a LUT within the product chain if the number of literals of the selected product term is less than or equal to a predetermined number.4. The method recited in claim 3 wherein the predetermined number is four.5. The method recited in claim 2 wherein the predetermined bound limit is four.6. The method recited in claim 1 wherein the step of combining the selected product term into one of the product chains defined if the selected product term fits into any existing product chain comprises:identifying all product chains to which the selected product term fits;selecting a product chain from all product chains; andjoining the selected product term with the selected product chain.7. The method recited in claim 6 wherein the step of identifying all product chains to which the selected product term fits comprises the step of comparing the selected product term with each of the product chains.8. The method recited in claim 6 wherein the step of selecting a product chain comprises the step of selecting a product chain for which increase in the number of literals when the selected product term is combined with the selected product chain is minimum.9. A programmable logic device (PLD) configured to implement a combinational logic function mapped to the PLD in accordance with the method of claim 1.10. A literal-sharing decomposition method for a combinational logic function expressed in sum-of-products format having product terms, said method comprising:a. identifying a product term having a most number of literals;b. defining the identified product term as a product chain;c. ordering all other product terms in descending order of number of literals of each product term;d. performing, for each row in the order, the following:i. defining the following product term as a current product term;ii. determining whether the current product term fits into any product chain;iii. defining the current product term as a new product chain if the current product term does not fit into any product chain; andiv. combining the current product term into one of the product chains if the current product term fits into any existing product chain.11. A literal-sharing decomposition method for a combinational logic function, said method comprising:a. forming a personality matrix for the combinational logic, the personality matrix having rows comprising literals;b. sorting the personality matrix in descending order of number of literals in each row, resulting in a sorted matrix having a first row and a last row;c. defining the first row as a product chain;d. performing, for rows following the first row, the following:i. defining the following row as a current row;ii. determining whether the current row fits into any product chain;iii. if the current row does not fit into any product chain, defining the current row as a new product chain; andiv. if the current row fits into any existing product chain, combining the current row into one of the product chains.12. A technology mapping system comprising:a processor;a storage connected to the processor; anda program stored in the storage, the program having instructions that when executed by the processor cause the system to decompose a combinational logic function expressed in sum-of-products format having a product term bya. identifying a product term having a most number of literals;b. defining the identified product term as a product chain;c. selecting, from remaining product terms, another product term having a most number of literals;d. performing, for the selected product term, the following:i. determining whether the selected product term fits into any product chain;ii. if the selected product term does not fit into any product chain, defining the selected product term as a new product chain;iii. if the selected product term fits into any existing product chain, combining the selected product term into one of the product chains; ande. repeating steps c and d until all product the remaining terms have been selected.13. An article of manufacture for a computer, the article comprising:a computer memory; anda program stored in the computer memory, the program, when executed, causing the computer to decompose a combinational logic function expressed in sum-of-products format having a product term by:a. identifying a product term having a most number of literals;b. defining the identified product term as a product chain;c. selecting from remaining product terms another product term having a next most number of literals;d. performing, for the selected product term, the following:i. determining whether the selected product term fits into any product chain;ii. if the selected product term does not fit into any product chain, defining the selected product term as a new product chain;iii. if the selected product term fits into any existing product chain, combining the selected product term into one of the product chains; ande. repeating steps c and d until all the remaining product terms have been selected.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (14)
Bonadio Allan R. (562 Shoreline Hwy. Mill Valley CA 94941), Apparatus and method for interactively manipulating mathematical equations.
Freeman ; deceased Ross H. (late of San Jose CA by Dennis Hersey ; executor), Configurable electrical circuit having configurable logic elements and configurable interconnects.
Kaviani, Alireza S.; Mohan, Sundararajarao; Wittig, Ralph D.; Young, Steven P.; New, Bernard J., Configurable logic block for PLD with logic gate for combining output with another configurable logic block.
Goetting F. Erich (Cupertino CA) Trimberger Stephen M. (San Jose CA), Logic cell for field programmable gate array having optional internal feedback and optional cascade.
Hsieh Hung-Cheng (583 Loch Lomond Ct. Sunnyvale CA 94087) Carter William S. (3024 Aspen Dr. Santa Clara CA 95051) Erickson Charles S. (3412 Atwater Ct. Fremont CA 94536) Cheung Edmond Y. (1302 Shelby, Logic structure and circuit for fast carry.
Tobias David F., Logic system and method employing multiple configurable logic blocks and capable of implementing a state machine using a minimum amount of configurable logic.
Chiang David (Saratoga CA) Lee Napoleon W. (Fremont CA) Ho Thomas Y. (Milpitas CA) Harrison David A. (Cupertino CA) Kucharewski ; Jr. Nicholas (Pleasanton CA) Seltzer Jeffrey H. (San Jose CA), Macrocell with product-term cascade and improved flip flop utilization.
Cliff Richard G. (Milpitas CA) Cope L. Todd (San Jose CA) McClintock Cameron R. (Mountain View CA) Leong William (San Francisco CA) Watson James A. (Santa Clara CA) Huang Joseph (San Jose CA) Ahanin , Programmable logic array integrated circuits.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.