Method and apparatus for function decomposition
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-017/50
G06F-009/45
출원번호
UP-0754264
(2007-05-25)
등록번호
US-7610566
(2009-11-10)
발명자
/ 주소
Caldwell, Andrew
Teig, Steven
출원인 / 주소
Tabula, Inc.
대리인 / 주소
Adeli & Tollen LLP
인용정보
피인용 횟수 :
23인용 특허 :
180
초록▼
Some embodiments provide a method of performing circuit synthesis that receives a design that has a function with several inputs. The method identifies a set of early arriving inputs of the function and performs a function decomposition on the function based on one of the early arriving inputs. In
Some embodiments provide a method of performing circuit synthesis that receives a design that has a function with several inputs. The method identifies a set of early arriving inputs of the function and performs a function decomposition on the function based on one of the early arriving inputs. In some embodiments, the method estimates the number of circuits a signal has to travel through to reach each input of the function and selects a set of inputs with signals that travel through fewer numbers of circuits compared to signals of inputs that are not selected. In some embodiments in which the design has more than a particular number of inputs, the method recursively identifies early arriving signals and performs function decomposition until function decomposition results in a set of functions all of which with fewer than the particular number of inputs. In some embodiments, the function decomposition is Shannon decomposition.
대표청구항▼
What is claimed is: 1. A computer implemented method for defining configuration data sets that direct an integrated circuit (IC) to perform a function based on a plurality of inputs, the method comprising: a) receiving, via a computer system, a design comprising said function; b) identifying a set
What is claimed is: 1. A computer implemented method for defining configuration data sets that direct an integrated circuit (IC) to perform a function based on a plurality of inputs, the method comprising: a) receiving, via a computer system, a design comprising said function; b) identifying a set of early arriving inputs of said function; c) performing a function decomposition on said function that (i) selects one of said early arriving inputs and (ii) defines at least a first sub-function and a second sub-function, each sub-function for producing a partial result of said function based on a set of the plurality of inputs that excludes said selected early arriving input; d) for a particular logic circuit of the IC, defining (i) a first configuration data set for configuring said particular logic circuit to perform said first sub-function and (ii) a second configuration data set for configuring said particular logic circuit to perform said second sub-function, wherein said particular logic circuit comprises at least one less input than the plurality of inputs; and e) defining said selected early arriving input as a signal of the IC for determining which of said first and second configuration data sets to supply to the particular circuit. 2. The method of claim 1, wherein the function decomposition is Shannon decomposition. 3. The method of claim 1, wherein performing the function decomposition to select one of said early arriving inputs comprises: a) estimating a number of circuits a signal has to travel through to reach each input of the function; and b) selecting a set of inputs with signals that travel through fewer numbers of circuits compared to signals of inputs that are not selected as the set of early arriving inputs. 4. The method of claim 3, wherein said circuits that a signal has to travel through are logic circuits. 5. The method of claim 1, wherein said design has more than a particular number of inputs, the method further comprising recursively performing operations a) to e) until the function decomposition results in a set of functions all of which having fewer than said particular number of inputs. 6. The method of claim 5, wherein the particular number of inputs is less than or equal to number of inputs of said particular logic circuit used to implement the circuit design. 7. The method of claim 5, wherein the particular number of inputs is at least three. 8. The method of claim 1, wherein the function decomposition is performed on said function based on an input that is an earliest arriving input. 9. The method of claim 1, wherein the function decomposition is performed on an input in the set of early arriving inputs that minimizes a cost function. 10. The method of claim 9, wherein the input that minimizes the cost function is determined by trial and error. 11. A computer readable storage medium storing a computer program for defining configuration data sets that direct an integrated circuit (IC) to perform a function based on a plurality of inputs, the computer program is executable by at least one processor, the computer program comprising: a) a set of instructions for receiving a design comprising said function; b) a set of instructions for identifying a set of early arriving inputs of said function; c) a set of instructions for performing a function decomposition on said function that (i) selects one of said early arriving inputs and (ii) defines at least a first sub-function and a second sub-function, each sub-function for producing a partial result of said function based on a set of the plurality of inputs that excludes said selected early arriving input; d) a set of instructions for defining (i) a first configuration data set for configuring a particular logic circuit of the IC to perform said first sub-function and (ii) a second configuration data set for configuring said particular logic circuit to perform said second sub-function, wherein said particular logic circuit comprises at least one less input than the plurality of inputs; and e) a set of instructions for defining said selected early arriving input as a signal of the IC for determining which of said first and second configuration data sets to supply to the particular circuit. 12. The computer readable storage medium of claim 11, wherein the function decomposition is Shannon decomposition. 13. An integrated circuit (IC) comprising: a) a plurality of configurable logic circuits for configurably performing a set of logic functions based on a plurality of configuration data sets, said plurality of configurable logic circuits comprising a particular configurable logic circuit with a particular number of inputs, wherein the particular configurable logic circuit produces a result of a particular function that requires more inputs than the particular number of inputs by performing a first sub-function and a second sub-function of the particular function, each sub-function producing a partial result of the particular function; and b) a selector circuit for supplying configuration data sets to the particular configurable circuit, said configuration data sets for configuring the particular configurable circuit to perform the first sub-function and the second sub-function based on an early arriving input of said particular function that is not used as an input to neither of the first and second sub-functions. 14. The IC of claim 13, wherein the particular configurable circuit performs the first sub-function at a first context and performs the second sub-function at a second context. 15. The IC of claim 14, wherein the first and second contexts comprise different subcycles of a user clock cycle at which the IC operates. 16. The IC of claim 13, wherein the early arriving input of said function is a user signal that is generated within the IC during runtime operation of the IC. 17. A computer implemented method for defining configuration data sets that direct an integrated circuit (IC) to perform a function based on a plurality of inputs, the method comprising: a) receiving, via a computer system, a design comprising said function; b) identifying a particular early arriving input from said plurality of inputs of said function, wherein the particular early arriving input arrives before a specified time threshold; c) performing a function decomposition on said function that defines at least a first sub-function and a second sub-function, each sub-function for producing a partial result of said function based on a set of the plurality of inputs that excludes said particular early arriving input; and d) defining configuration data sets that are supplied to at least one particular logic circuit of the IC based on a value of said extracted early arriving input, said configuration data sets for configuring the particular logic circuit to perform at least one of said first and second sub-functions, wherein the particular logic circuit comprises at least one less input than said plurality of inputs. 18. The method of claim 17, wherein defining the configuration data sets to configure the particular logic circuit comprises configuring the particular logic circuit to perform said first and second sub-functions at different cycles of the IC. 19. The method of claim 18, wherein said cycles are different sub-cycles of a user defined clock cycle. 20. The method of claim 17, wherein defining the configuration data sets to configure the particular logic circuit comprises configuring a first logic circuit to perform the first sub-function and a second logic circuit to perform the second sub-function.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (180)
Ting, Benjamin S., Architecture and interconnect scheme for programmable logic circuits.
Trimberger Stephen M. (San Jose CA) Carberry Richard A. (Los Gatos CA) Johnson Robert A. (San Jose CA) Wong Jennifer (Fremont CA), Configuration modes for a time multiplexed programmable logic device.
Wakayama Shigetoshi,JPX ; Gotoh Kohtaroh,JPX ; Saito Miyoshi,JPX ; Ogawa Junji,JPX, Destructive read type memory circuit, restoring circuit for the same and sense amplifier.
Inoue Kazunari (Hyogo JPX) Fudeyasu Yoshio (Hyogo JPX), Dual port memory effecting transfer of data between a serial register and an arbitrary memory block.
Nguyen Bai ; Agrawal Om P. ; Sharpe-Geisler Bradley A. ; Wong Jack T. ; Chang Herman M., Efficient interconnect network for use in FPGA device having variable grain architecture.
Kant,Shree; Tam,Kenway; Kongetira,Poonacha P.; Lin,Yuan Jung D; Liu,Zhen W.; Aingaran,Kathirgamar, Efficient method of data transfer between register files and memories.
Agrawal, Om P.; Fontana, Fabiano; Bosco, Gilles M., Enhanced CPLD macrocell module having selectable bypass of steering-based resource allocation and methods of use.
Tavana Danesh (Mountain View CA) Yee Wilson K. (Tracy CA) Holen Victor A. (Saratoga CA), FPGA architecture with repeatable tiles including routing matrices and logic matrices.
Iadanza Joseph Andrew ; Kilmoyer Ralph David ; Laramie Michael Joseph ; Seidel Victor Paul ; Zittritsch Terrance John, Field programmable memory array.
Bennett David Wayne (Louisville CO) Dellinger Eric Ford (Boulder CO) Manaker ; Jr. Walter A. (Boulder CO) Stern Carl M. (Boulder CO) Troxel William R. (Longmont CO) Young Jay Thomas (Louisville CO), Frequency driven layout and method for field programmable gate arrays.
Rostoker Michael D. ; Koford James S. ; Scepanovic Ranko ; Jones Edwin R. ; Padmanahben Gobi R. ; Kapoor Ashok K. ; Kudryavtsev Valeriy B.,RUX ; Andreev Alexander E.,RUX ; Aleshin Stanislav V.,RUX ; , Hexagonal field programmable gate array architecture.
Vorbach,Martin; M체nch,Robert, Internal bus system for DFPS and units with two-or multi-dimensional programmable cell architectures, for managing large volumes of data with a high interconnection complexity.
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.
Norman Kevin A. ; Patel Rakesh H. ; Sample Stephen P. ; Butts Michael R., Look-up table based logic element with complete permutability of the inputs to the secondary signals.
Furumochi Kazuto,JPX ; Seino Junji,JPX, MOS static RAM with improved soft error resistance; high-level supply voltage drop detection circuit and complementary.
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.
Clinton Kim P. N. ; Iadanza Joseph Andrew ; Keyser ; III Frank Ray ; Seidel Victor Paul ; Zittritsch Terrance John, Memory cells for field programmable memory array.
Poplingher Mircea ; Chen Wenliang ; Suryanarayanan Ganesh ; Chen Wayne W. ; Lo Roger Y., Memory device for a microprocessor register file having a power management scheme and method for copying information between memory sub-cells in a single clock cycle.
Larsen Wendell Ray (Essex Junction VT) Keyser Frank Ray (Colchester VT) Worth Brian A. (Milton VT), Memory mapping method and apparatus to fold sparsely populated structures into densely populated memory columns or rows.
Fuller Christine Marie ; Hartman Steven Paul ; Millham Eric Ernest, Method and system for optimizing a critical path in a field programmable gate array configuration.
Craft David John ; Gould Scott Whitney ; Keyser ; III Frank Ray ; Worth Brian, Method and system for programming a gate array using a compressed configuration bit stream.
Bailis, Robert Thomas; Kuhlmann, Charles Edward; Lingafelt, Charles Steven; Rincon, Ann Marie, Method and system for use of a field programmable function within a chip to enable configurable I/O signal timing characteristics.
Bailis, Robert Thomas; Kuhlmann, Charles Edward; Lingafelt, Charles Steven; Rincon, Ann Marie, Method and system for use of a field programmable function within a standard cell chip for repair of logic circuits.
Bailis, Robert Thomas; Kuhlmann, Charles Edward; Lingafelt, Charles Steven; Rincon, Ann Marie, Method and system for use of a field programmable interconnect within an ASIC for configuring the ASIC.
Bailis, Robert Thomas; Kuhlmann, Charles Edward; Lingafelt, Charles Steven; Rincon, Ann Marie, Method and system for use of an embedded field programmable gate array interconnect for flexible I/O connectivity.
Gould Scott Whitney ; Iadanza Joseph Andrew ; Keyser ; III Frank Ray ; Zittritsch Terrance John, Method of operating a field programmable memory array with a field programmable gate array.
Trimberger Stephen M. (San Jose CA) Carberry Richard A. (Los Gatos CA) Johnson Robert A. (San Jose CA) Wong Jennifer (Fremont CA), Method of time multiplexing a programmable logic device.
Gould Scott Whitney ; Iadanza Joseph Andrew ; Keyser ; III Frank Ray ; Zittritsch Terrance John, Programmable address decoder for field programmable memory array.
Clinton Kim P. N. (Essex Junction VT) Gould Scott W. (South Burlington VT) Hartman Steven P. (Jericho VT) Iadanza Joseph A. (Hinesburg VT) Keyser ; III Frank R. (Colchester VT) Millham Eric E. (St. G, Programmable array interconnect network.
El Gamal Abbas A. (Palo Alto CA) El-Ayat Khaled A. (Cupertino CA) Greene Jonathan W. (Palo Alto CA) Guo Ta-Pen R. (Cupertino CA) Reyneri Justin M. (Los Altos CA), Programmable interconnect architecture.
Motomura Masato,JPX, Programmable logic IC having memories for previously storing a plurality of configuration data and a method of reconfigurating same.
New Bernard J. ; Johnson Robert Anders ; Wittig Ralph ; Mohan Sundararajarao, Rapidly reconfigurable FPGA having a multiple region architecture with reconfiguration caches useable as data RAM.
Blodget, Brandon J.; McMillan, Scott P.; James-Roxby, Philip B.; Sundararajan, Prasanna; Keller, Eric R.; Curd, Derek R.; Kalra, Punit S.; LeBlanc, Richard J.; Eck, Vincent P., Reconfiguration of a programmable logic device using internal control.
Om P. Agrawal ; Claudia A. Stanley ; Xiaojie (Warren) He ; Larry R. Metzger ; Robert A. Simon ; Kerry A. Ilgenstein, Scalable architecture for high density CPLD's having two-level hierarchy of routing resources.
Clinton Kim P. N. ; Gould Scott Whitney ; Iadanza Joseph Andrew ; Keyser ; III Frank Ray ; Kilmoyer Ralph David ; Laramie Michael Joseph ; Seidel Victor Paul ; Zittritsch Terrance John, Selective connectivity between memory sub-arrays and a hierarchical bit line structure in a memory array.
Agrawal Om P. ; Chang Herman M. ; Sharpe-Geisler Bradley A. ; Tran Giap H., Symmetrical, extended and fast direct connections between variable grain blocks in FPGA integrated circuits.
Iadanza Joseph Andrew ; Keyser ; III Frank Ray ; Kilmoyer Ralph David ; Laramie Michael Joseph, System for implementing write, initialization, and reset in a memory array using a single cell write port.
Balasubramanian,Rabindranath; Zhu,Limin; Speers,Theodore; Bakker,Gregory, System-on-a-chip integrated circuit including dual-function analog and digital inputs.
Trimberger Stephen M. (San Jose CA) Carberry Richard A. (Los Gatos CA) Johnson Robert Anders (San Jose CA) Wong Jennifer (Fremont CA), Time multiplexed programmable logic device.
Redgrave, Jason; Caldwell, Andrew; Teig, Steven, Method and apparatus for performing an operation with a plurality of sub-operations in a configurable IC.
Manohararajah, Valavan; Chiu, Gordon Raymond; Freeman, John Stuart, Method and apparatus for performing look up table unpacking and repacking for resynthesis.
Schmit, Herman; Butts, Michael; Hutchings, Brad L.; Teig, Steven, Method of mapping a user design defined for a user design cycle to an IC with multiple sub-cycle reconfigurable circuits.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.