Sponsored Links

 
Web LinkGrinder.com

Title: Scalable non-blocking switching network for programmable logic

Abstract: A scalable non-blocking switching network (SN) having switches and intermediate (stages of) conductors that are used to connect substantially a first plurality of conductors, through a first set of switches, to a second plurality sets of conductors. The conductors in each set of the second plurality of conductors substantially connect, through a second set of switches, to a third plurality of sets of conductors. Each conductor of a set of the third plurality sets of conductors either connects, physically, to one pin in each of a plurality of functional blocks or, through a third set of switches, to a subsequent fourth set of conductors. The SN is scalable for larger sets of conductors by adding additional sets of intermediate conductors in a hierarchically fashion.

Patent Number: 7,417,457 Issued on 08/26/2008 to Pani,   et al.

Inventors: Pani; Peter M. (Mountain View, CA), Ting; Benjamin S. (Saratoga, CA)
Assignee: Advantage Logic, Inc. (Mountain View, CA)
Appl. No.: 11/823,257
Filed: June 26, 2007
Related U.S. Patent Documents
Application NumberFiling DatePatent NumberIssue Date
11218419Sep., 20057256614
10814943Mar., 20046975139

Current U.S. Class: 326/41 ; 326/101; 326/47
Current International Class: H03K 19/177 (20060101)
Field of Search: 326/41,47,101

References Cited [Referenced By]
U.S. Patent Documents
4020469 April 1977 Manning
4661901 April 1987 Veneski
4700187 October 1987 Furtek
4720780 January 1988 Dolecek
4736333 April 1988 Mead et al.
4758745 July 1988 Elgamal
4815003 March 1989 Putatunda et al.
4847612 July 1989 Kaplinsky
4870302 September 1989 Freeman
4912342 March 1990 Wong et al.
4918440 April 1990 Furtek
4935734 June 1990 Austin
4992680 February 1991 Benedetti et al.
5122685 June 1992 Chan
5144166 September 1992 Camarota et al.
5187393 February 1993 Elgamal et al.
5204556 April 1993 Shankar
5208491 May 1993 Ebeling et al.
5221865 June 1993 Phillips et al.
RE34363 August 1993 Freeman
5243238 September 1993 Kean
5256918 October 1993 Suzuki
5260610 November 1993 Pederson et al.
5260611 November 1993 Cliff et al.
5296759 March 1994 Sutherland et al.
5298805 March 1994 Garverick et al.
5329470 July 1994 Sample et al.
5349691 September 1994 Harrison et al.
5369314 November 1994 Patel et al.
5376844 December 1994 Pederson et al.
5396126 March 1995 Britton et al.
5406525 April 1995 Nicholes
5444394 August 1995 Watson et al.
5455525 October 1995 Ho et al.
5457410 October 1995 Ting
5469003 November 1995 Kean
5477067 December 1995 Isomura et al.
5485103 January 1996 Pederson et al.
5519629 May 1996 Snider
5537057 July 1996 Leong et al.
5550782 August 1996 Cliff et al.
5552722 September 1996 Kean
5572148 November 1996 Lytle et al.
5581199 December 1996 Pierce et al.
5581767 December 1996 Katuski et al.
5815004 September 1998 Trimberger et al.
5818254 October 1998 Agrawal et al.
5825202 October 1998 Tavana
5835405 November 1998 Tsui et al.
5841775 November 1998 Huang
5850564 December 1998 Ting et al.
5880597 March 1999 Lee
5883526 March 1999 Reddy et al.
5894228 April 1999 Reddy
5903165 May 1999 Jones et al.
5914616 June 1999 Young
6016063 January 2000 Trimberger
6034547 March 2000 Pani et al.
6038627 March 2000 Plants
6051991 April 2000 Ting
6088526 July 2000 Ting et al.
6160420 December 2000 Gamal
6163168 December 2000 Nguyen et al.
6181162 January 2001 Lytle et al.
6417694 July 2002 Reddy et al.
6433580 August 2002 Ting
6507217 January 2003 Ting
6594810 July 2003 Reblewski
6597196 July 2003 Ting
6670825 December 2003 Lane et al.
6686768 February 2004 Comer
6693456 February 2004 Wong
7065076 June 2006 Nemazie
7123612 October 2006 Lu
2001/0007428 July 2001 Young
2002/0163357 November 2002 Ting
Foreign Patent Documents
0415542 Mar., 1991 EP
0630115 Jun., 1994 EP
2180382 Mar., 1987 GB
2295738 May., 1996 GB
9208286 May., 1992 WO
9410754 May., 1994 WO
9428475 Dec., 1994 WO
9504404 Feb., 1995 WO
9528769 Oct., 1995 WO
9605964 Apr., 1996 WO
9635261 Nov., 1996 WO
WO 03/032492 Apr., 2003 WO

Other References

PCT Search Report mailed Aug. 31, 2005, International Application No. PCT/US05/06583, International Filing Date Feb. 28, 2005, 8 pages. cited by other .
Altera Corporation Date Sheet, Flex EPF81188 12,000 Gate Programmable Logic Device, Sep. 1992, Ver. 1, pp. 1-20. cited by other .
ATMEL Field Programmable Arrays, AT 6000 Series, 1993, p. 1-16. cited by other .
Britton, et al., "Optimized Reconfigurable Cell Array Architecture for High-Performance Field Programmable Gate Arrays," Proceedings of the IEEE 1993 Custom Integrated Circuits Conference, 1993, pp. 7.2.1-7.2.5. cited by other .
Buffoli, E., et al., "Dynamically Reconfigurable Devices Used to Implement a Self-Tuning, High Performances PID Controller," 1989 IEEE, pp. 107-112. cited by other .
Bursky, D., "Fine-Grain FPGA Architecture Uses Four Levels of Configuration Hierarchy," 2328 Electronic Design, 41, No. 20, Cleveland, OH, Oct. 1, 1993, pp. 33-34. cited by other .
Cliff, et al., "A Dual Granularity and Globally Interconnected Architecture for a Programmable Logic Device", IEEE '93 pp. 7.3.1-7.3.5. cited by other .
Devades, S., et al., "Boolean Decomposition of Programmable Logic Arrays," IEEE 1988, pp. 2.5.1-2.5.5. cited by other .
F. Zlotnick, P. Butler, W. Li, D. Tang, "A High Performance Fine-Grained Approach to SRAM Based FPGAs", p. 321-326, Wescon Sep. 28-30, 1993. cited by other .
Liu, D.L., et al., "Design of Large Embedded CMOS PLA's for Built-In Self-test," IEEE Transactions on Computed-Aided Design, vol. 7, No. 1, Jan. 1988, pp. 50-53. cited by other .
Minnick, R.C., "A Survey of Microcellular Research", vol. 14, No. 2, Apr. 1967, pp. 203-241. cited by other .
Motorola Project Brief, "MPA10xx Field Programmable Gate Arrays," Sep. 27, 1993, 2 pages. cited by other .
Robert H. Krambeck, "ORCA: A High Performance, Easy to Use SRAM Based Architecture", p. 310-320, Wescon Sep. 28-30, 1993. cited by other .
Shoup, R. G., "Programmable Cellular Logic Arrays," Abstract, Ph.D. Dissertation, Carnegie Mellon University, Pittsburgh, PA, Mar. 1970, (partial) pp. ii-121. cited by other .
Sinan Kaptanoglu, Greg Bakker, Arun Kundu, Ivan Corneillet, Ben Ting, "A New High Density and Very Low Cost Reprogrammable FPGA Architecture", 10 pages, Actel Corporation. cited by other .
Spandorfer, L.M., "Synthesis of Logic Functions on an Array of Integrated Circuits," Contract No. AF 19 (628) 2907, Project No. 4645, Task No. 464504, Final Report, Nov. 30, 1965. cited by other .
Sun, Y., et al., "An Area Minimizer for Floorplans with L-Shaped Regions," 1992 International Conference on Computer Design, 1992 IEEE, pp. 383-386. cited by other .
Vidal, J. J., "Implementing Neural Nets with Programmable Logic," IEEE Transactions on Acoustic, Speech, and Signal Processing, vol. 36, No. 7, Jul. 1988, pp. 1180-1190. cited by other .
Wang, P. et al. IEEE, "A High Performance FPGA with Hierarchical Interconnection Structure", pp. 239-242 (May 30, 1994). cited by other .
Xilinx, "The Programmable Gate Array Data Book", 1992. cited by other .
EP Communication 05724178.8-2215 (PCT/US2005006583) dated Jul. 26, 2007 and Supplementary European Search Report (date of completion of the search Jul. 19, 2007), 05724178.8-2215 (PCT/US2005006583). cited by other.

Primary Examiner: Tan; Vibol
Attorney, Agent or Firm: Blakely, Sokoloff, Taylor & Zafman LLP
Parent Case Text


REFERENCE TO RELATED APPLICATION

This application is a continuation of U.S. application Ser. No. 11/218,419 filed Sep. 1, 2005, now U.S. Pat. No. 7,256,614, which is a continuation of Application Ser. No. 10/814,943, now U.S. Pat. No. 6,975,139 filed Mar. 30, 2004 now U.S. Pat. No. 6,975,139, which are hereby incorporated by reference.
Claims


What is claimed is:

1. An integrated circuit, comprising: a first switching network (SN) comprising: a first plurality of M number of conductors; a second plurality of N sets of k number of conductors, where N is greater than two and where k is greater than two; a third plurality of I number of conductors comprising a fourth plurality of N sets of I0 number of conductors, wherein I0 approximately equals to M/N; and a first plurality of switches, wherein through the first plurality of switches, each of the M number of conductors of the first plurality of M conductors selectively couples to the third plurality of I number of conductors, wherein at least M-N+1 number of conductors of the first plurality of M conductors selectively couples to one of the I0 number of conductors of each of the fourth plurality of N sets of I0 number of conductors; and a second plurality of switches, wherein through the second plurality of switches, each of the I0 number of conductors of each set of the fourth plurality of N sets of the I0 number of conductors selectively couples to all conductors in one set of a respective set of the second plurality of N sets of k number of conductors without requiring any selectable connection of another conductor.

2. The integrated circuit as set forth in claim 1, wherein through the first plurality of switches, at least M-N+1 number of conductors of the first plurality of M conductors selectively couples to one of the I0 number of conductors of each of the fourth plurality of N sets of I0 number of conductors without requiring any selectable connection of another conductor.

3. The integrated circuit as set forth in claim 1, wherein the first switching network (SN) further comprises: a fifth plurality of D1 sets of I1 number of conductors of the third plurality of I number of conductors, wherein D1 is at least two, wherein the fourth plurality of N sets of I0 number of conductors are divided into D1 sets of N/D1 sets of I0 number of conductor, wherein N/D1 is at least two, wherein through the first plurality of switches, at least I1-D1+1 number of conductors of each one of the D1 sets of the fifth plurality of D1 sets of I1 number of conductors selectively couples to one of the I0 conductors in each of a respective set of the N/D1 sets of I0 number of conductors of the D1 sets of N/D1 sets of I0 number of conductors without requiring any selectable connection of another conductor.

4. The integrated circuit as set forth in claim 3, wherein through the first plurality of switches, each of the M number of conductors of the first plurality of M conductors selectively couples to one of the I1 number of conductors of each of the fifth plurality of D1 sets of I1 number of conductors without requiring any selectable connection of another conductor.

5. The integrated circuit as set forth in claim 3, wherein the first switching network (SN) further comprises: a sixth plurality of D2 sets of I2 number of conductors of the third plurality of I number of conductors, wherein D2 is at least two; wherein the fifth plurality of D1 sets of I1 number of conductors are divided into D2 sets of D1/D2 sets of I1 number of conductors, wherein D1/D2 is greater than one, wherein through the first plurality of switches, each of the I2 number of conductors of each one of the D2 sets of the sixth plurality of D2 sets of I2 number of conductors selectively couples to one of the I1 conductors in each of a respective set of the D1/D2 sets of I1 number of conductors of the D2 sets of D1/D2 sets of I1 number of conductors without requiring any selectable connection of another conductor.

6. The integrated circuit as set forth in claim 5, wherein through the first plurality of switches, each of the M number of conductors of the first plurality of M conductors selectively couples to one of the I2 number of conductors of each of the sixth plurality of D2 sets of I2 numbers of conductors without requiring any selectable connection of another conductor.

7. The integrated circuit as set forth in claim 1, wherein N is greater than four and k is greater than four.

8. The integrated circuit as set forth in claim 2, further comprising: a plurality of switching networks (SN's), each of which is substantially similar to the first SN.

9. The integrated circuit as set forth in claim 4, further comprising: a plurality of switching networks (SN's), each of which is substantially similar to the first SN.

10. The integrated circuit as set forth in claim 6, further comprising: a plurality of switching networks (SN's), each of which is substantially similar to the first SN.

11. The integrated circuit as set forth in claim 8, wherein the first plurality of switches and the second plurality of switches and the third plurality of I number of conductors for each of the respective plurality of switching networks are substantially located in proximity within a first region.

12. The integrated circuit as set forth in claim 9, wherein the first plurality of switches and the second plurality of switches and the third plurality of I number of conductors for each of the respective plurality of switching networks are substantially located within proximity of a first region.

13. The integrated circuit as set forth in claim 10, wherein the first plurality of switches and the second plurality of switches and the third plurality of I number of conductors for each of the respective plurality of switching networks are substantially located within proximity of a first region.

14. The integrated circuit as set forth in claim 11, wherein the integrated circuit is a Field Programmable Gate-array.

15. The integrated circuit as set forth in claim 12, where the integrated circuit is a Field Programmable Gate-array.

16. The integrated circuit as set forth in claim 13, where the integrated circuit is a Field Programmable Gate-array.

17. The integrated circuit as set forth in claim 2, further comprising: a second switching network substantially similar to the first SN, wherein each respective k conductors of each of the N sets of conductors form a respective set of k ports, and wherein each k conductors of a first port of the set of k ports are connected to the first plurality of M number of conductors of the second switching network.

18. The integrated circuit as set forth in claim 4, further comprising: a second switching network substantially similar to the first SN, wherein each respective k conductors of each of the N sets of conductors form a respective set of k ports, and wherein each k conductors of a first port of the set of the k ports are connected to the first plurality of M number of conductors of the second switching network.

19. The integrated circuit as set forth in claim 6, further comprising: a second switching network substantially similar to the first SN, wherein each respective k conductors of each of the N sets of conductors form a respective set of k ports, and wherein each k conductors of a first port of the set of the k ports are connected to the first plurality of M number of conductors of the second switching network.

20. The integrated circuit as set forth in claim 17, wherein the integrated circuit is a Field Programmable Gate-array.

21. The integrated circuit as set forth in claim 18, wherein the integrated circuit is a Field Programmable Gate-array.

22. The integrated circuit as set forth in claim 19, wherein the integrated circuit is a Field Programmable Gate-array.

23. A method comprising, providing a first switching networks (SN) in an integrated circuit; providing the first SN with a first plurality of M number of conductors; providing the first SN with a second plurality of N sets of k number of conductors, where N is greater than two and where k is greater than two; providing the first SN with a third plurality of I number of conductors comprising a fourth plurality of N sets of I0 number of conductors wherein I0 is M/N; providing the first SN with a first plurality of switches; selectively coupling each of the M number of conductors of the first plurality of M conductors to the third plurality of I number of conductors through the first plurality of switches; selectively coupling at least M-N+1 number of conductors of the first plurality of M conductors to one of the I0 number of conductors of each of the fourth plurality of N sets of I0 number of conductors; providing the first SN with a second plurality of switches; and selectively coupling each of the I0 number of conductors of each set of the fourth plurality of N sets of the I0 number of conductors to all conductors in one set of a respective set of the second plurality of N sets of k number of conductors without requiring any selectable connection of another conductor.

24. The method as set forth in claim 23, further comprising: selectively coupling at least M-N+1 number of conductors of the first plurality of M conductors to one of the I0 number of conductors of each of the fourth plurality of N sets of I0 numbers of conductors through the first plurality of switches without requiring any selectable connection of another conductor.

25. The method as set forth in claim 23, further comprising: providing the first SN with a fifth plurality of D1 sets of I1 number of conductors of the third plurality of I number of conductors, wherein D1 is at least two; dividing the fourth plurality of N sets of I0 number of conductors into D1 sets of N/D1 sets of I0 number of conductor, wherein N/D1 is at least two; and selectively coupling at least I1-D1+1 number of conductors of each one of the D1 sets of the fifth plurality of D1 sets of I1 number of conductors to one of the I0 conductors in each of a respective set of the N/D1 sets of I0 number of conductors of the D1 sets of N/D1 sets of I0 number of conductors through the first plurality of switches without requiring any selectable connection of another conductor.

26. The method as set forth in claim 25, further comprising: selectively coupling each of the M number of conductors of the first plurality of M conductors to one of the I1 number of conductors of each of the fifth plurality of D1 sets of I1 number of conductors through the first plurality of switches without requiring any selectable connection of another conductor.

27. The method as set forth in claim 25, further comprising: providing the first SN with a sixth plurality of D2 sets of I2 number of conductors of the third plurality of I number of conductors, wherein D2 is at least two; dividing the fifth plurality of D1 sets of I1 number of conductors into D2 sets of D1/D2 sets of I1 number of conductors, wherein D1/D2 is greater than one; and selectively coupling each of the I2 number of conductors of each one of the D2 sets of the sixth plurality of D2 sets of I2 number of conductors to one of the I1 conductors in each of a respective D1/D2 sets of I1 number of conductors of the D2 sets of D1/D2 sets of I1 number of conductors through the first plurality of switches without requiring any selectable connection of another conductor.

28. The method as set forth in claim 27, further comprising: selectively coupling each of the M number of conductors of the first plurality of M conductors to one of the I2 number of conductors of each of the sixth plurality of D2 sets of I2 numbers of conductors through the first plurality of switches without requiring any selectable connection of another conductor.

29. The method as set forth in claim 23, wherein N is greater than four and k is greater than four.

30. The method as set forth in claim 24, further comprising: providing a plurality of switching networks (SN's), each of which is substantially similar to the first SN.

31. The method as set forth in claim 26, further comprising: providing a plurality of switching networks (SN's), each of which is substantially similar to the first SN.

32. The method as set forth in claim 28, further comprising: providing a plurality of switching networks (SN's), each of which is substantially similar to the first SN.

33. The method as set forth in claim 30, wherein the first plurality of switches and the second plurality of switches and the third plurality of I number of conductors for each of the respective plurality of switching networks are substantially located in proximity within a first region.

34. The method as set forth in claim 31, wherein the first plurality of switches and the second plurality of switches and the third plurality of I number of conductors for each of the respective plurality of switching networks are substantially located within proximity of a first region.

35. The method as set forth in claim 32, wherein the first plurality of switches and the second plurality of switches and the third plurality of I number of conductors for each of the respective plurality of switching networks are substantially located within proximity of a first region.

36. The method as set forth in claim 33, wherein the integrated circuit is a Field Programmable Gate-array.

37. The method as set forth in claim 34, wherein the integrated circuit is a Field Programmable Gate-array.

38. The method as set forth in claim 35, wherein the integrated circuit is a Field Programmable Gate-array.

39. The method as set forth in claim 24 further comprising: providing a second switching network substantially similar to the first SN, wherein each respective k conductors of each of the N sets of conductors form a respective k port; and coupling each k conductor of the first of the k ports to the first plurality of M number of conductors of the second switching network.

40. The method as set forth in claim 26, further comprising: providing a second switching network, wherein each respective k conductors of each of the N sets of conductors form a respective k port; and coupling each k conductor of the first of the k ports to the first plurality of M number of conductors of the second switching network.

41. The method as set forth in claim 28, further comprising: providing a second switching network, wherein each respective k conductors of each of the N sets of conductors form a respective k port; and coupling each k conductor of the first of the k ports to the first plurality of M number of conductors of the second switching network.

42. The method as set forth in claim 39, wherein the integrated circuit is a Field Programmable Gate-array.

43. The method as set forth in claim 40, wherein the integrated circuit is a Field Programmable Gate-array.

44. The method as set forth in claim 41, wherein the integrated circuit is a Field Programmable Gate-array.
Description


TECHNICAL FIELD

Embodiments of this invention relate to switching networks and, in particular to switching networks used with programmable logic circuits.

BACKGROUND

A programmable logic circuit, also referred to as field programmable gate array (FPGA) is an off the shelf integrated logic circuit which can be programmed by the user to perform logic functions. Circuit designers define the desired logic functions and the circuit is programmed to process the signals accordingly. Depending on logic density requirements and production volumes, programmable logic circuits are superior alternatives in terms of cost and time to market. A typical programmable logic circuit is composed of logic cells where each of the logic cells can be programmed to perform logic functions on its input variables. Additionally, interconnect resources are provided throughout the programmable logic circuit which can be programmed to conduct signals from outputs of logic cells to inputs of logic cells according to user specification.

As technology progresses to allow for larger and more sophisticated programmable logic circuits, both the number of logic cells and the required interconnect resources increases in the circuit. Competing with the increased number of logic cells and interconnect resources is the need to keep the circuit size small. One way to minimize the required circuit size is to minimize the interconnect resources while maintaining a certain level of connectivity. Therefore, it can be seen that as the functionality implemented on the chip increases, the interconnection resources required to connect a large number of signals can be quickly exhausted. The trade-offs are either to provide for a lower utilization of logic cells in a circuit while keeping the circuit size small or to provide more routing resources that can increase the circuit size dramatically.

There has been a progression of increasingly complex connection styles over the last forty years in the field of programmable logic circuits. L. M. Spandorfer in 1965 describes possible implementation of a programmable logic circuit using neighborhood interconnection, and connections through multiple conductors using switches in a Clos network. R. G. Shoup in his PhD thesis of 1970 describes both the use of a neighborhood interconnect and the use of a bus for longer distance interconnect.

Freeman in the U.S. Pat. No. 4,870,302 of 1989 describes a commercial implementation of a FPGA using neighborhood interconnects, short (length one, called single) distance interconnects, and global lines for signals such as clocks. The short distance interconnects interact with the inputs and outputs of logic cells where each input is connected through switches to every short wire neighboring to a logic cell and horizontal and vertical short wires connect through a switch box in a junction. El Gamal et al. in U.S. Pat. No. 4,758,745 introduces segmented routing where inputs and outputs of logic cells interact with routing segments of different lengths in one dimension.

Peterson et al. in U.S. Pat. No. 5,260,610 and Cliff et al. in U.S. Pat. No. 5,260,611 introduce a local set of conductors interfacing with a set of logic elements where every input of the logic elements is connected, through switches, to every local conductor in the set; additional chip length conductors are introduced both horizontally and vertically where the horizontal conductor can connect to the vertical conductors and the horizontal conductors connect to multiple local conductors. In U.S. Pat. No. 4,870,302, U.S. Pat. No. 4,758,745, U.S. Pat. No. 5,260,610, and U.S. Pat. No. 5,260,611, the input conductor of a logic cell has full connections to the set of local conductors (e.g. for n-inputs and k-local conductors, there is n.times.k switches connecting the inputs to the local conductors. A multiplexer (MUX) scheme may also be used so that the number of transistors is reduced.). In U.S. Pat. No. 4,870,302, U.S. Pat. No. 4,758,745, U.S. Pat. No. 5,260,610, and U.S. Pat. No. 5,260,611, the general interconnect resources are limited to one or two different lengths (i.e. singles of U.S. Pat. No. 4,870,302, local and chip length in U.S. Pat. No. 5,260,610 and U.S. Pat. No. 5,260,611) or limited in one dimension (i.e. different lengths horizontally in U.S. Pat. No. 4,758,745, local vertically in U.S. Pat. No. 5,260,610 and U.S. Pat. No. 5,260,611).

Camarota et al. in U.S. Pat. No. 5,144,166 and Kean in U.S. Pat. No. 5,469,003 introduce a routing scheme with more than two different lengths in both dimensions with limitations in the reach of those conductors. While U.S. Pat. No. 5,144,166 allows each wire to be selectively driven by more than one possible driving source, U.S. Pat. No. 5,469,003 is limited to be unidirectional in that each wire is hardwired to a MUX output. The connectivity provided in both U.S. Pat. No. 5,144,166 and U.S. Pat. No. 5,469,003 are very low, based on the premises that either connections are neighborhood or relatively local, or logic cells itself can be used as interconnection resources instead of performing logic functions. Ting in U.S. Pat. No. 5,457,410, U.S. Pat. No. 6,507,217, U.S. Pat. No. 6,051,991, U.S. Pat. No. 6,597,196 describe a multiple level architecture where multiple lengths of conductors interconnect through switches in a hierarchy of logic cells.

Young et al. in U.S. 2001/0007428 and U.S. Pat. No. 5,914,616 describe an architecture with multiple lengths of wires in two dimensions (three in each dimension) where for short local connections, a near cross-bar scheme is used where a set of logic cells outputs are multiplexed to a reduced set of output ports which then interface to other interconnect resources. The longer wires generally fan-in into shorter length wires in a respective dimension. Reddy et al. in U.S. Pat. No. 6,417,694 discloses another architecture where inter-super-region, inter-region, and local conductors are used. A cross-bar scheme is used at the lowest level (using MUXs) for the local wires to have universal access to the inputs of the logic elements. Reddy et al. in U.S. Pat. No. 5,883,526 discloses various schemes having circuit reduction techniques in the local cross-bar.

At the base level of circuit hierarchy, four-input Look Up Table (LUT) logic cells are commonly used. There are two advantages in using a LUT as the base logic cell. One advantage is that the circuit allows any four-input, one output Boolean functions with programmable controls. Another advantage is that the four inputs are exchangeable and logically equivalent. Hence it does not matter which signal connecting to which input pin of the LUT for the LUT to function correctly as long as those four signals connect to the four inputs of the LUT.

A common problem to be solved in any programmable logic circuit is that of interconnectivity, namely, how to connect a first set of conductors carrying signals to multiple sets of conductors to receive those signals where the logic cells originating the signals and the logic cells receiving the signals are spread over a wide area in an integrated circuit (i.e., M outputs of M logic cells where each output connects to inputs of multiple number of logic cells). A highly desirable but in most cases impractical solution is to use a cross bar switch where every conductor of the first set is connectable to every conductor in the multiple sets of conductors directly through a switch. Prior solutions in one degree or another try to divide the connectivity problem into multiple pieces using a divide and conquer strategy where local clusters of logic cells are interconnected and extended to other clusters of logic, either through extensions of local connections or using longer distance connections. These prior interconnect schemes are ad hoc and mostly based on empirical experiences. A desired routing model or interconnect architecture should guarantee full connectability for a large number of inputs and outputs (through programmable interconnect conductors) connecting to multiple sets of conductors over a large part of the circuit all the time.

Complicated software is necessary to track interconnect resources while algorithms are used to improve interconnectability during the place and route stage implementing a custom design using the programmable logic circuit. Thus, it is desirable to have a new interconnect scheme for programmable logic circuits where the routability or interconnectability may be guaranteed in a more global scale while the cost of interconnections remains low in terms of required switches and the software efforts in determining a place and route for custom design implementation are simplified.

BRIEF DESCRIPTION OF THE DRAWINGS

The objectives, features, and advantages of the present invention will be apparent from the following detailed description in which:

FIG. 1 illustrates an embodiment of a circuit with four four-input logic cells and two flip flops using a scalable non-blocking switching network (SN).

FIG. 2 illustrates one embodiment of a circuit using a stage-0 scalable non-blocking switching network (0-SN) with eleven M conductors accessing four sets of four N conductors.

FIG. 3 illustrates one embodiment of a circuit using two stage-0 scalable non-blocking switching networks with each 0-SN having five M conductors accessing four sets of two N conductors.

FIG. 4 illustrates one embodiment of a circuit using a stage-1 scalable non-blocking switching network (1-SN) with eleven M conductors accessing four sets of four N conductors through N sets of four intermediate conductors.

FIG. 5 illustrates one embodiment of a circuit using a stage-1 scalable non-blocking switching network with twelve M conductors accessing four sets of four N conductors through fewer intermediate conductors.

FIG. 6 illustrates one embodiment of a circuit using a stage-1 scalable non-blocking switching network with twelve M conductors accessing four sets of four N conductors with stronger connectivity property.

FIG. 7 illustrates one embodiment of a reduced stage-1 scalable non-blocking switching network with fewer switches.

FIG. 8 illustrates one embodiment of a larger size stage-1 scalable non-blocking switching network.

FIG. 9 illustrates one embodiment of a stage-1 scalable non-blocking switching network with sixteen M conductors.

FIG. 10 is a block diagram illustrating one embodiment of a stage-2 scalable non-blocking switching network (2-SN) and a circuit with four logic circuits of FIG. 1, each using the scalable non-blocking switching network of FIG. 9.

FIG. 11A illustrates a block diagram embodiment of the stage-2 scalable non-blocking switching network of FIG. 10.

FIG. 11B illustrates one embodiment of the first part of the stage-2 scalable non-blocking switching network of FIG. 11A.

FIG. 12 illustrates one embodiment of a stage-1 scalable non-blocking switching network implementing the second part of the 2-SN of FIG. 11A.

DETAILED DESCRIPTION

An innovative scalable non-blocking switching network (SN) which uses switches and includes intermediate stage(s) of conductors connecting a first plurality of conductors to multiple sets of conductors where each conductor of the first plurality of conductors is capable of connecting to one conductor from each of the multiple sets of conductors through the SN, is first described. The scalable non-blocking switching network can be applied in a wide range of applications, when used, either in a single stage, or used hierarchically in multiple stages, to provide a large switch network used in switching, routers, and programmable logic circuits. A scalable non-blocking switching network is used to connect a first set of conductors, through the SN, to multiple sets of conductors whereby the conductors in each of the multiple sets are equivalent or exchangeable, for example, the conductors of one of the multiple sets are the inputs of a logic cell (which can be the inputs of a LUT or inputs to a hierarchy of logic cells). The scalable non-blocking switching network in this present invention allows any subset of a first set of conductors to connect, through the SN, to conductors of a second multiple sets of conductors, so that each conductor of the subset can connect to one conductor from each set of the multiple sets of conductors.

In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent to one skilled in the art that embodiments of the present invention may be practiced without these specific details. In other instances, well-known structures and circuits are shown in block diagram form in order to avoid unnecessarily obscuring the present invention. For purpose of description, unless otherwise specified, the terms program controlled switch and switch are interchangeable in the context of this description: the terms program configured logic cell, logic cell, cell, Look Up Table (LUT), programmable logic cell are interchangeable in the context of this description; the terms conductor, signal, pin, port, line are interchangeable in the context of this description. It should also be noted that the present invention describes embodiments which use program control means to set the states of switches utilized, this control means can be one time, such as fuse/anti-fuse technologies, or re-programmable, such as SRAM (which is volatile), FLASH (which is non-volatile), Ferro-electric (which is non-volatile), etc. Hence the present invention pertains to a variety of processes, including, but not limited to, static random access memory (SRAM), dynamic random access memory (DRAM), fuse/anti-fuse, erasable programmable read-only memory (EPROM), electrically erasable programmable read-only memory (EEPROM) such as FLASH, and Ferro-electric processes.

The concept of scalable non-blocking switching networks utilized in a programmable logic circuit described herein can be generally applied to allow unrestricted connections between a plurality of conductors to multiple sets of conductors, as long as the connection requirements do not exceed the available conductors.

When a program controlled switch is used to interconnect one conductor to another conductor, a driver circuit may be coupled to the switch to improve the speed of the signal traversing those conductors. Additionally, if multiple conductors (signals) fan-in to a conductor through program controlled switches, it is possible to use a MUX scheme, if desired, to either reduce loading on the conductor or to reduce circuit size, or both, depending on the process technology used. In the case where a MUX is used, the multiple switches are converted into a new switch mechanism where, the number of effective states are the same as the number of switches, connectivity is enabled by choosing the particular state (corresponding to the switch if multiple switches were used) in connecting two conductors and the states are determined by programmable control.

Various types of scalable non-blocking switching networks are described including, but not limited to: stage-0 scalable non-blocking switching network (0-SN), stage-1 scalable non-blocking switching network (1-SN), stage-2 scalable non-blocking switching network (2-SN) and extensions to multi-stage scalable non-blocking switching networks and the use of those scalable non-blocking switching networks hierarchically in providing interconnectivity to programmable logic circuits.

FIG. 1 shows an embodiment of a cluster (CLST4) circuit 100 including a scalable non-blocking switching network 200 and including k number of four-input logic cells (where k=4 in this embodiment) 10, 20, 30 and 40 and two Flip-Flops 50 and 60. Each of the logic cells 10-40 has four inputs 101-104 (N0[0-3]) for cell 10, four inputs 105-108 (N1[0-3]) for cell 20, four inputs 109-112 (N2[0-3]) for cell 30 and four inputs 113-116 (N3[0-3]) for cell 40, with four conductors 121-124 as the four outputs for cells 10-40 respectively. Switches 151-156 and 159, 160 are used to control whether a logic cell output drives a Flip-Flop or the logic cell outputs to circuit 100 outputs 125-128 directly. The Flip-Flops 50, 60 output to circuit 100 outputs 125-128 using switches 157, 158, 161 and 162. Additionally, conductor 131 can drive conductor 101 of cell 10 through switch 141 and conductor 105 of cell 20 through switch 142. Similarly, conductor 132 can drive cells 30 and 40 through switches 143 and 144, respectively. Cell 20 can drive a neighboring CLST4 circuit (not shown in FIG. 1) through output 122 using switches 145 to conductor 133. Output 124 of cell 40 drives out to conductor 134 through switch 146 in FIG. 1. Three other signals 135-137 are used to control the Flip-Flops as SET, CLOCK, and CLEAR, respectively. Additionally, FIG. 1 has (X+1) conductors 180 (M[0-X]) fanning in to drive the sixteen inputs 101-116 using a switch network MTX 200. The conductors M[0-X] 180 are called M conductors where M is equal to the number of conductors (X+1) in the embodiment of FIG. 1. The input conductors Ni[0-3] for i=[0-(k-1)] 101-116 are called the Ni conductors where Ni is equal to the number of inputs which is four in the embodiment of FIG. 1. For purpose of illustration, the size Ni=N=4 is shown in FIG. 1. Alternatively, each Ni can have a different size without changing the connectivity property described herein.

FIG. 2 shows an embodiment where MTX 200 of FIG. 1 is represented by a stage-0 scalable non-blocking switching network (0-SN) 300; each N conductor 101-116 is connectable to (M-N+1) conductors of the M conductors (e.g., conductors 180 of FIG. 1) 201-211 (M[0-10]), the number of switches shown in FIG. 2 for each input conductor of conductors 101-116 is thus (M-N+1)=8 for the 0-SN 300 of FIG. 2. The switch network 0-SN 300 allows any subset of M conductors 201-211 to drive one input conductor of each of the logic cells 10-40 using the switches of 300 without any blocking as long as the number of connections do not exceed the available interconnect resources (i.e., the number of M conductors driving the inputs of any of the logic cells can not exceed the number of inputs of the logic cell). The scheme of FIG. 2 is an improvement over a cross bar connection where instead of a full switch matrix comprising M.times.(k.times.N) =11.times.(4.times.4)=176 switches, the number of switches is (M-N+1).times.(k.times.N)=128. The 0-SN 300 in FIG. 2 allows the above stated connectivity by assuming the four inputs for each of the logic cells as exchangeable or logically equivalent (i.e., conductors 101-104 of cell 10 of FIG. 1 are equivalent or exchangeable) so it is only necessary to connect a particular M conductor (i.e. M[4] conductor 205) to any input pin of a given logic cell (i.e., conductor 101 out of conductors 101-104 of cell 10 of FIG. 1 using switch 222) if the connection requirement is to connect the particular M conductor to the given logic cell.

Depending on technology used in the programmable circuits, some area minimization can be accomplished. For example, using a SRAM memory cell with six transistors as the program control for each switch implemented using a passgate, the eight switches 221-228 of FIG. 2 per input line 101 will require fifty six transistors. Instead, an eight input MUX using three memory bits can be used to control eight states to effectively replace the eight SRAM bits and eight switches. In the MUX scheme, three bits, fourteen passgates and perhaps one inverter (to regenerate the signal) uses thirty four transistors which is a large reduction from the fifty six transistors used with eight SRAM memory cells as the program control for each switch. The loading on conductor 101 will be reduced using the MUX implementation while there are additional delays due to the eight to one MUX.

FIG. 3 shows an embodiment where MTX 200 of FIG. 1 is represented by using two stage-0 scalable non-blocking switching networks 330 and 320 with M=Ma+Mb=10 conductors 301-310 composed of subgroups Ma=[A0-A4]=5 301-305 conductors and Mb=[B0-B4]=5 306-310 conductors. Each Nb=2 for the upper two input conductors of each of the four logic cells (composed of conductors 101-102 for cell 10, conductors 105-106 for cell 20, conductors 109-110 for cell 30 and conductors 113-114 for cell 40) and Na=2 for the lower two input conductors for each of the k=four logic cells (composed of conductors 103-104 for cell 10, conductors 107-108 for cell 20, conductors 111-112 for cell 30 and conductors 115-116 for cell 40). A full sized stage-0 scalable non-blocking switching network of FIG. 3 would have (M-N+1)=10-4+1=7 program controlled switches per input conductor. Instead, in the embodiment of FIG. 3, the number of input switches is only four because of the separate Ma conductors and Mb conductors (with Ma=Mb=5) and the number N is broken into two parts (with Na=Nb=2). As such, the number of program controlled switches per input conductor in network 33





DISCLAIMER

Snappy Quick is a free service that searches the Internet and indexes all files found so that you may search quickly and easily for shared files. These files are created and made available individually by users whose identity we are not aware of and who we have no control over. In essence we function like a search engine tool; these files ARE NOT STORED OR SERVED BY OUR NETWORK. We are not responsible for any materials obtained by using our service. We do not monitor any of the contents of these files. These files may contain viruses, illegal materials, materials inappropriate for minors, offensive files and the like. BY USING OUR SERVICE, YOU ASSUME FULL RESPONSIBILITY FOR DOWNLOADING THESE MATERIALS AND WILL INDEMNIFY US FOR ANY DAMAGES THAT MAY BE INCURRED.

For More Specific Information VIEW OUR TERMS OF SERVICE.

Thank you and Enjoy!