Patent Publication Number: US-10312917-B2

Title: Configurable computing array for implementing complex math functions

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation-in-part of U.S. patent application Ser. No. 15/793,912, filed Oct. 25, 2017, which is a continuation of U.S. patent application Ser. No. 15/450,049, filed Mar. 6, 2017, now U.S. Pat. No. 9,838,031, issued Dec. 5, 2017, which is a continuation-in-part of U.S. patent application Ser. No. 15/450,017, filed Mar. 5, 2017, now U.S. Pat. No. 9,948,306, issued Apr. 17, 2018. 
     This application is also a continuation-in-part of U.S. patent application Ser. No. 15/793,968, filed Oct. 25, 2017, which is a continuation-in-part of U.S. patent application Ser. No. 15/450,049, filed Mar. 6, 2017, now U.S. Pat. No. 9,838,031, issued Dec. 5, 2017, which is a continuation-in-part of U.S. patent application Ser. No. 15/450,017, filed Mar. 5, 2017, now U.S. Pat. No. 9,948,306, issued Apr. 17, 2018. 
     This application is also a continuation-in-part of U.S. patent application Ser. No. 15/793,927, filed Oct. 25, 2017, which is a continuation-in-part of U.S. patent application Ser. No. 15/450,049, filed Mar. 6, 2017, now U.S. Pat. No. 9,838,031, issued Dec. 5, 2017, which is a continuation-in-part of U.S. patent application Ser. No. 15/450,017, filed Mar. 5, 2017, now U.S. Pat. No. 9,948,306, issued Apr. 17, 2018. 
     This application is also a continuation-in-part of U.S. patent application Ser. No. 15/793,933, filed Oct. 25, 2017, which is a continuation-in-part of U.S. patent application Ser. No. 15/450,049, filed Mar. 6, 2017, now U.S. Pat. No. 9,838,031, issued Dec. 5, 2017, which is a continuation-in-part of U.S. patent application Ser. No. 15/450,017, filed Mar. 5, 2017, now U.S. Pat. No. 9,948,306, issued Apr. 17, 2018. 
     These patent applications claim priorities from Chinese Patent Application No. 201610125227.8, filed Mar. 5, 2016; Chinese Patent Application No. 201610307102.7, filed May 10, 2016; Chinese Patent Application No. 201710996864.7, filed Oct. 19, 2017; Chinese Patent Application No. 201710998652.2, filed Oct. 20, 2017; Chinese Patent Application No. 201710980817.3, filed Oct. 20, 2017; Chinese Patent Application No. 201710980779.1, filed Oct. 20, 2016; Chinese Patent Application No. 201710980813.5, filed Oct. 20, 2016; Chinese Patent Application No. 201710980826.2, filed Oct. 20, 2016; Chinese Patent Application No. 201710980967.4, filed Oct. 20, 2016; Chinese Patent Application No. 201710981043.6, filed Oct. 20, 2016; Chinese Patent Application No. 201710980989.0, filed Oct. 20, 2016, in the State Intellectual Property Office of the People&#39;s Republic of China (CN), the disclosure of which are incorporated herein by reference in their entireties. 
    
    
     BACKGROUND 
     1. Technical Field of the Invention 
     The present invention relates to the field of integrated circuit, and more particularly to configurable gate array. 
     2. Prior Art 
     Complex math functions are widely used in various applications. As used hereinafter, a complex math function is a math function with multiple independent variables (independent variable is also known as input variable or argument) and can be expressed as a combination of basic math functions. On the other hand, a basic math function is a math function with a single (or, few) independent variable. Exemplary basic math functions include transcendental functions, such as exponential function (exp), logarithmic function (log), trigonometric functions (sin, cos, tan, atan) and others. 
     On a conventional processor, a small number of basic math functions are calculated by hardware (i.e. hardware computing). These basic math functions are referred to as built-in functions. The conventional hardware computing primarily uses logic-based computing, i.e. logic circuits (e.g. adders, multipliers) are primarily used to implement math functions. Because different math functions are implemented by different logic circuits, the hardware implementation of built-in functions is highly customized. Due to limited resources on a processor die, only a small number of built-in functions can be implemented by hardware. For example, only 7 built-in functions (i.e. CBRT, EXP, LN, SIN, COS, TAN, ATAN) are implemented by hardware on an Intel IA-64 processor (referring to Harrison et al. “The Computation of Transcendental Functions on the IA-64 Architecture”, Intel Technology Journal, Q4, 1999, page 6). 
     Because hardware implementation of even basic math functions (e.g. transcendental functions) is difficult, software computing has been a commonly accepted practice. On a conventional processor, all complex math functions, even most basic math functions, are calculated by software. As software computing is more complex than hardware computing, calculation of complex math functions is slow and inefficient. It is highly desired to realize hardware computing for complex math functions. It is even more desirable to realize configurable hardware computing, i.e. to use a same set of hardware to implement a large set of complex math functions. 
     A configurable gate array is a semi-custom integrated circuit designed to be configured by a customer after manufacturing. It is also referred to as field-programmable gate array (FPGA), complex programmable logic device (CPLD), or other names. U.S. Pat. No. 4,870,302 issued to Freeman on Sep. 26, 1989 (hereinafter referred to as Freeman) discloses a configurable gate array. It contains an array of configurable logic elements (also known as configurable logic blocks) and a hierarchy of configurable interconnects (also known as programmable interconnects) that allow the configurable logic elements to be wired together. Each configurable logic element in the array is in itself capable of realizing any one of a plurality of logic functions (e.g. shift, logic NOT, logic AND, logic OR, logic NOR, logic NAND, logic XOR, arithmetic addition “+”, arithmetic subtraction “−”, etc.) depending upon a first configuration signal. Each configurable interconnect can selectively couple or de-couple interconnect lines depending upon a second configuration signal. 
     In conventional configurable gate array, fixed computing elements are used to implement basic math functions. These fixed computing elements are portions of hard blocks and not configurable, i.e. the circuits implementing these math functions are fixedly connected and are not subject to change by programming. This would limit further application of the configurable gate array. To overcome these difficulties, the present invention expands the original concept of the configurable gate array by making the fixed computing elements configurable. In other words, besides configurable logic elements, the configurable gate array comprises configurable computing elements, which can realize any one of a plurality of math functions. 
     OBJECTS AND ADVANTAGES 
     It is a principle object of the present invention to extend the applications of a configurable gate array to the field of complex math computation. 
     It is a further object of the present invention to provide a configurable computing array to customize not only logic functions, but also math functions. 
     It is a further object of the present invention to provide a configurable computing array with a small physical size and a fast computational speed. 
     It is a further object of the present invention to provide a configurable computing array with a short time-to-market and good manufacturability. 
     In accordance with these and other objects of the present invention, the present invention discloses a configurable computing array for realizing complex math functions. 
     SUMMARY OF THE INVENTION 
     The present invention discloses a configurable computing array for realizing complex math functions. It comprises at least an array of configurable logic elements and at least an array of configurable computing elements. Each configurable computing element comprises at least a memory, which is preferably programmable and can be loaded with a look-up table (LUT) for a math function. Because the memory is programmable, the math functions that can be realized by the configurable computing element are essentially boundless and numerous. 
     The usage cycle of the configurable computing element comprises two stages: a configuration stage and a computation stage. In the configuration stage, the LUT for a desired math function is loaded into the memory. In the computation stage, a selected portion of the LUT for the desired math function is read out from the memory. For a rewritable memory, a configurable computing element can be re-configured to realize different math functions at different time. 
     Besides configurable computing elements, the preferred configurable computing array further comprises configurable logic elements and configurable interconnects. During operation, a complex math function is first decomposed into a combination of basic math functions. Each basic math function is realized by programming an associated configurable computing element. The complex math function is then realized by programming the appropriate configurable logic elements and configurable interconnects. 
     By using arrays of configurable computing elements, configurable logic elements and configurable interconnects, the present invention implements hardware computing of complex math functions. Compared with software computing, hardware computing is much faster and more efficient. Moreover, the hardware computing disclosed the present invention is a type of memory-based computing, i.e. the LUTs are used as a primary means to implement math functions. The best advantage of the memory-based computing over the logic-based computing is its configurability and generality. By loading the values of different math functions into an LUT at different time, a single LUT can be used to implement a large set of math functions, thus realizing configurable computing. 
     Accordingly, the present invention discloses a configurable computing array, comprising: at least an array of configurable logic elements including a configurable logic element, wherein said configurable logic element selectively realizes a logic function from a logic library; and at least an array of configurable computing elements including first and second configurable computing elements, wherein said first configurable computing element comprises a first memory for storing a first look-up table (LUT) for a first math function; and, said second configurable computing element comprises a second memory for storing a second LUT for a second math function; whereby said configurable computing array realizes a complex math function by programming said configurable logic elements and said configurable computing elements, wherein said complex math function is a combination of at least said first and second math functions. 
     The present invention further discloses another configurable computing array, comprising: at least an array of configurable interconnects including a configurable interconnect, wherein said configurable interconnect selectively realizes an interconnect from an interconnect library; at least an array of configurable logic elements including a configurable logic element, wherein said configurable logic element selectively realizes a logic function from a logic library; and at least an array of configurable computing elements including first and second configurable computing elements, wherein said first configurable computing element comprises a first memory for storing a first look-up table (LUT) for a first math function; and, said second configurable computing element comprises a second memory for storing a second LUT for a second math function; whereby said configurable computing array realizes a complex math function by programming said configurable interconnects, said configurable logic elements and said configurable computing elements, wherein said complex math function is a combination of at least said first and second math functions. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  discloses a symbol for a preferred configurable computing element; 
         FIG. 2  is a layout view of the preferred configurable computing element; 
         FIG. 3  discloses two usage cycles of a preferred re-configurable computing element; 
         FIG. 4A  shows an interconnect library supported by a preferred configurable interconnect;  FIG. 4B  shows a logic library supported by a preferred configurable logic element; 
         FIG. 5  is a circuit block diagram of a first preferred configurable computing array; 
         FIG. 6  shows an instantiation of the first preferred configurable computing array; 
         FIG. 7  is a circuit block diagram of a second preferred configurable computing array; 
         FIGS. 8A-8B  show two instantiations of the second preferred configurable computing array; 
         FIG. 9A  is a cross-sectional view of a preferred configurable computing array based on three-dimensional memory (3D-M);  FIG. 9B  is a substrate layout view of the preferred configurable computing array;  FIG. 9C  is a cross-sectional view of a preferred configurable computing array based on a four-level 3D-M; 
         FIGS. 10A-10B  are cross-sectional views of two preferred configurable computing array based on three-dimensional vertical memory (3D-M V ); 
         FIG. 11A  is a perspective view of a front side of a preferred configurable computing-array die using two-sided integration;  FIG. 11B  is a perspective view of a back side of the preferred configurable computing-array die;  FIG. 11C  is a cross-sectional view of the preferred configurable computing-array die. 
         FIG. 12  is a perspective view of a preferred configurable computing-array package; 
         FIGS. 13A-13C  are cross-sectional views of three preferred configurable computing-array packages. 
     
    
    
     It should be noted that all the drawings are schematic and not drawn to scale. Relative dimensions and proportions of parts of the device structures in the figures have been shown exaggerated or reduced in size for the sake of clarity and convenience in the drawings. The same reference symbols are generally used to refer to corresponding or similar features in the different embodiments. In the present invention, the terms “write”, “program” and “configure” have similar meanings and are used interchangeably. The symbol “/” means a relationship of “and” or “or”. 
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Those of ordinary skills in the art will realize that the following description of the present invention is illustrative only and is not intended to be in any way limiting. Other embodiments of the invention will readily suggest themselves to such skilled persons from an examination of the within disclosure. 
     Referring now to  FIG. 1 , a symbol for a preferred configurable computing element  100  is shown. The input port IN includes input data  115 , the output port OUT includes output data  135 , and the configuration port CFG includes at least a configuration signal  125 . When the configuration signal  125  is “write”, the look-up table (LUT) for a desired math function is loaded into the configurable computing element  100 ; when the configuration signal  125  is “read”, a selected portion of the LUT is read out from the configurable computing element  100 . 
       FIG. 2  is a layout view of the preferred configurable computing element  100 . The LUT is stored in at least a memory array  110 . The configurable computing element  100  further includes the X decoder  15  and Y decoder (including read-out circuit)  17  of the memory array  110 . The memory array  110  is preferably writable. It could be a RAM array or a ROM array. Exemplary RAM includes SRAM, DRAM, etc. On the other hand, exemplary ROM includes OTP (one-time-programmable) and MTP (multiple-time-programmable, including re-programmable) memories, etc. Among them, the MTP further includes EPROM, EEPROM, flash memory, 3-D writable memory (e.g. 3D-NAND, 3D-XPoint) and others, etc. 
     The LUT in the configurable computing element  100  stores numerical values related to a math function. This is different from the conventional configurable gate array where the LUT in a configurable logic element stores logic values of a logic function. The implementation of math functions is much more complex than that of logic functions. Numerical values are denoted by a large number of bits. For example, a half-precision floating-point number comprises 16 bits; a single-precision floating-point number comprises 32 bits; a double-precision floating-point number comprises 64 bits. In comparison, the logic values can be denoted by a single bit and have only two values, i.e. “true” and “false”. Accordingly, the LUT size of the configurable computing element  100  is substantially larger than that of the configurable logic element. 
     The numerical values stored in the LUT of the configurable computing element  100  include at least the functional values of a math function. When the input variable of a math function comprises a larger number of bits, the LUT size could become excessively large. For example, an LUT to store the functional values of a double-precision math function needs 2 64 *64=10 21  bits. To reduce the LUT size, Taylor-series (or other polynomial expansion) calculation is preferably used. To be more specific, the LUT not only sores the functional values, but also the derivative values of a math function, e.g. the first-order derivative values, the second-order derivative values. To perform Taylor-series calculation, the configurable computing element  100  further comprises at least an adder and a multiplier. More details on Taylor-series implementation of math functions are disclosed in a co-pending U.S. patent application Ser. No. 15/487,366, filed Apr. 13, 2017. 
     Referring now to  FIG. 3 , two usage cycles  620 ,  660  of a preferred re-configurable computing element  100  are shown. For the re-configurable computing element  100 , the memory array  110  is re-programmable. The first usage cycle  620  includes two stages: a configuration stage  610  and a computation stage  630 . In the configuration stage  610 , the LUT for a first desired math function is loaded into the memory array  110 . In the computation stage  630 , a selected portion of the LUT for the first desired math function is read out from the memory array  110 . Being re-programmable, the re-configurable computing element  100  can realize different math functions during different usage cycles  620 ,  660 . During the second usage cycle  660  (including a configuration stage  650  and a computation stage  670 ), the LUT for a second desired math function is loaded and later read out. The re-configurable computing element  100  is particularly suitable for single-instruction-multiple-data (SIMD)-type of data processing. Once the LUTs are loaded into the memory arrays  110  in the configuration stage, a large amount of data can be fed into the re-configurable computing element  100  and processed at high speed. SIMD has many applications, e.g. vector processing in image processing, massively parallel processing in scientific computing. 
     Referring now to  FIGS. 4A-4B , an interconnect library and a logic library are shown.  FIG. 4A  shows the interconnect library supported by a preferred configurable interconnect  300 . An interconnect library is a collection of all interconnects supported by a configurable interconnect. This interconnect library includes the followings: a) the interconnects  302 / 304  are coupled, the interconnects  306 / 308  are coupled, but  302 / 304  are not connected with  306 / 308 ; b) the interconnects  302 / 304 / 306 / 308  are all coupled; c) the interconnects  306 / 308  are coupled, but the interconnects  302 ,  304  are not coupled, neither are  302 ,  304  connected with  306 / 308 ; d) the interconnects  302 / 304  are coupled, but the interconnects  306 ,  308  are not coupled, neither are  306 ,  308  connected with  302 / 304 ; e) interconnects  302 ,  304 ,  306 ,  308  are not coupled at all. As used herein, the symbol “/” between two interconnects means that these two interconnects are coupled, while the symbol “,” between two interconnects means that these two interconnects are not coupled. More details on the configurable interconnects are disclosed in Freeman. 
       FIG. 4B  shows the logic library supported by a preferred configurable logic element  200 . A logic library is a collection of all logic functions supported by a configurable logic element. In this preferred embodiment, the inputs A and B include input data  210 ,  200 , and the output C includes the output data  230 . The logic library includes the following logic functions: C=A, NOT A, A shift by n bits, AND(A,B), OR(A,B), NAND(A,B), NOR(A,B), XOR(A,B), A+B, A−B. To facilitate pipelining, the configurable logic element  200  may comprise sequential logic such as flip-flops and registers. More details on the configurable logic elements are disclosed in Freeman. 
     Referring now to  FIG. 5 , a first preferred configurable computing array  400  is disclosed. It comprises first and second configurable slices  400 A,  400 B. Each configurable slice (e.g.  400 A) comprises a first array of configurable computing elements (e.g.  100 AA- 100 AD) and a second array of configurable logic elements (e.g.  200 AA- 200 AD). A configurable channel  320  is placed between the first array of configurable computing elements (e.g.  100 AA- 100 AD) and the second array of configurable logic elements (e.g.  200 AA- 200 AD). The configurable channels  310 ,  330 ,  350  are also placed between different configurable slices  300 A,  300 B. Each configurable channel (e.g.  310 ) comprise an array of configurable interconnects  300 . For those skilled in the art, besides configurable channels, sea-of-gates may also be used. 
       FIG. 6  discloses an instantiation of the first preferred configurable computing array implementing a complex math function e=a·sin(b)+c·cos(d). The configurable interconnects  300  in the configurable channel  310 - 350  use the same convention as  FIG. 4A : the interconnects with dots mean that the interconnects are connected; the interconnects without dots mean that the interconnects are not connected; a broken interconnect means that two broken sections are disconnected. In this preferred implementation, the configurable channel  310  is configured in such a way that the inputs a, b, c, d associated with four independent variables of the complex function e=a·sin(b)+c·cos(d) are coupled to the inputs of the configurable computing elements  100 AA- 100 AD, respectively. Furthermore, the configurable computing element  100 AA is configured to realize the function log( ), whose result log(a) is sent to a first input of the configurable logic element  200 A. The configurable computing element  100 AB is configured to realize the function log[sin( )], whose result log[sin(b)] is sent to a second input of the configurable logic element  200 A. The configurable logic element  200 A is configured to realize arithmetic addition “+”, whose result log(a)+log[sin(b)] is sent the configurable computing element  100 BA. The configurable computing element  100 BA is configured to realize the function exp( ), whose result exp{log(a)+log[sin(b)]}=a·sin(b) is sent to a first input of the configurable logic element  200 BA. Similarly, through proper configurations, the results of the configurable computing elements  100 AC,  100 AD, the configurable logic elements  200 AC, and the configurable computing element  100 BC can be sent to a second input of the configurable logic element  200 BA. The configurable logic element  200 BA is configured to realize arithmetic addition “+”, whose result a·sin(b)+c·cos(d) is sent to the output e. Apparently, by changing its configuration, the configurable computing array  400  can realize other complex math functions. 
     Referring now to  FIG. 7 , a second preferred configurable computing array  400  is shown. Besides configurable computing elements  100 A,  100 B and configurable logic element  200 A, this preferred embodiment further comprises a multiplier  500 . The configurable channels  360 - 380  comprise a plurality of configurable interconnects. With the addition of the multiplier  500 , the preferred configurable computing array  400  can realize more math functions and its computational power becomes more powerful. 
       FIGS. 8A-8B  disclose two instantiations of the second preferred configurable computing array  400 . In the instantiation of  FIG. 8A , the configurable computing element  100 A is configured to realize the function exp(f), while the configurable computing element  100 B is configured to realize the function inv(g). The configurable channel  370  is configured in such a way that the outputs of  100 A,  100 B are fed into the multiplier  500 . The final output is then h=exp(f)*inv(g). On the other hand, in the instantiation of  FIG. 8B , the configurable computing element  100 A is configured to realize the function sin(f), while the configurable computing element  100 B is configured to realize the function cos(g). The configurable channel  370  is configured in such a way that the outputs of  100 A,  100 B are fed into the configurable logic element  200 A, which is configured to realize arithmetic addition. The final output is then h=sin(f)+cos(g). 
     The preferred configurable computing array  400  can be constructed in many ways. In one preferred embodiment, the preferred configurable computing array  400  is a single-level configurable computing array, wherein the configurable computing elements  100  and the configurable logic elements  200  are disposed on a same physical level. To be more specific, all active elements of the preferred configurable computing array  400  (including the memory cells of the memory array  110  in the configurable computing elements  100  and the transistors in the configurable logic elements  200 ) are formed on the front surface of a same semiconductor substrate and placed side-by-side. Because all active elements are disposed on a 2-D plane, this type of integration is referred to 2-D integration; and, the single-level configurable computing array is also referred to as 2-D integrated configurable computing array. 
     In another preferred embodiment, the preferred configurable computing array  400  is a multi-level configurable computing array, wherein the configurable computing elements  100  and the configurable logic elements  200  are disposed on different physical levels. To be more specific, the memory cells of the configurable computing elements  100  are disposed on at least a memory level, the transistors of the configurable logic elements  200  are disposed on at least a logic level, wherein the memory level is disposed above (or, below) the logic level. In one preferred example, both the memory cells and the transistors are disposed on the same side of a same semiconductor substrate, but the memory cells are stacked above the transistors ( FIGS. 9A-10B ). In another preferred example, the configurable computing elements  100  and the configurable logic elements  200  are disposed on different sides of a semiconductor substrate ( FIGS. 11A-11C ). In yet another preferred example, the configurable computing elements  100  and the configurable logic elements  200  are disposed on different dice of a same package ( FIGS. 12-13C ). Because all active elements are disposed in a 3-D space, this type of integration is referred to as 3-D integration; and, the multi-level configurable computing array is also referred to as 3-D integrated configurable computing array. 
     Comparing with the single-level configurable computing array, the multi-level configurable computing array offers many advantages. First of all, because the memory cells are disposed on a separate memory level(s), the memory level(s) can be dedicated to the LUT storage. As a result, the memory level(s) has a large storage density and therefore, can be used to store a large LUT (for better precision) or more LUTs (for more math functions). Secondly, because they are formed on a separate logic level, the configurable logic elements would have a small footprint. This leads to smaller die size. Thirdly, because the configurable computing elements are disposed above (or, below) the configurable logic elements, the connections between them are relatively short. This leads to a fast speed. 
     Referring now to  FIGS. 9A-10B , several preferred multi-level configurable computing arrays based on three-dimensional memory (3D-M), more particularly three-dimensional writable memory (3D-W), are disclosed. The preferred configurable computing array is a monolithic integrated circuit comprising a configurable computing element  100  and a configurable logic element  200 . The configurable computing element  100  comprises at least a 3D-M array. In the 3D-M array, its memory cells are disposed in a three-dimensional space, i.e. the memory cells are vertically stacked above each other. Among all types of 3D-M, 3D-W is a type of 3D-M whose memory cells are electrically programmable. Based on the number of programming allowed, a 3D-W can be categorized into three-dimensional one-time-programmable memory (3D-OTP) and three-dimensional multiple-time-programmable memory (3D-MTP). Types of the 3D-MTP cell include flash-memory cell, memristor, resistive random-access memory (RRAM or ReRAM) cell, phase-change memory (PCM) cell, programmable metallization cell (PMC), conductive-bridging random-access memory (CBRAM) cell, and the like. 
     Based on the orientation of the memory cells, the 3D-M can be categorized into horizontal 3D-M (3D-M H ) and vertical 3D-M (3D-M V ). In a 3D-M H , all address lines are horizontal and the memory cells form a plurality of horizontal memory levels which are vertically stacked above each other. A well-known 3D-M H  is 3D-XPoint. In a 3D-M V , at least one set of the address lines are vertical and the memory cells form a plurality of vertical memory strings which are placed side-by-side on/above the substrate. A well-known 3D-M V  is 3D-NAND. In general, the 3D-M H  (e.g. 3D-XPoint) is faster, while the 3D-M V  (e.g. 3D-NAND) is denser. 
     The preferred 3D-M in  FIG. 9A  is a 3D-M H . It comprises a substrate circuit  0 K formed on the substrate  0 . A first memory level  16 A is stacked above the substrate circuit  0 K, with a second memory level  16 B stacked above the first memory level  16 A. The substrate circuit  0 K includes the peripheral circuits of the memory levels  16 A,  16 B. It comprises transistors  0   t  and the associated interconnects  0 M 1 - 0 M 3 . Each of the memory levels (e.g.  16 A,  16 B) comprises a plurality of first address-lines (i.e. y-lines, e.g.  2   a ,  4   a ), a plurality of second address-lines (i.e. x-lines, e.g.  1   a ,  3   a ) and a plurality of 3D-M cells (e.g.  1   aa ,  2   aa ). The first and second memory levels  16 A,  16 B are coupled to the substrate circuit  0 K through contact vias  1   av ,  3   av , respectively. 
     The 3D-M cell  1   aa  comprises a programmable layer  12  and a diode layer  14 . The programmable layer  12  could be an OTP layer (e.g. an antifuse layer, used for the 3D-OTP) or an MTP layer (e.g. a phase-change layer, used for the 3D-MTP). The diode layer  14  (also referred to as selector layer, a quasi-conduction layer or other names) is broadly interpreted as any layer whose resistance at the read voltage is substantially lower than the case when the applied voltage has a magnitude smaller than or polarity opposite to that of the read voltage. The diode could be a semiconductor diode (e.g. p-i-n silicon diode), or a metal-oxide (e.g. TiO 2 ) diode. In some embodiments, the programmable layer  12  and the diode layer  14  are merged into a single layer. 
       FIG. 9B  is a substrate layout view of the preferred configurable computing array  400 . Because the 3D-M arrays are stacked above the substrate  0 K and not located in the substrate  0 , their projections on the substrate  0 , not the 3D-M arrays themselves, are shown in the areas enclosed by dash lines. In this preferred embodiment, the LUT is stored in at least a 3D-M array  110 . The substrate circuit  0 K includes the decoders  15 ,  17 ,  19  of the 3D-M array  110 , as well as a configurable logic element  200  and/or a configurable interconnect  300  (not shown in the figure). To save the die area, the 3D-M array  110  can be stacked above and at least partially cover the configurable logic element  200 . Similarly, the 3D-M array  110  can be stacked above and at least partially cover the configurable interconnect  300 . 
       FIG. 9C  is a cross-sectional view of a preferred configurable computing array based on a four-level 3D-M. This implementation corresponds to the configurable slice  400 A of  FIG. 5 . For the configurable computing elements  100 AA- 100 AD, their 3D-M arrays  110 AA- 110 AD are vertically stacked. To be more specific, the substrate circuit  0 K comprises the configurable logic elements  200  (including  200 AA- 200 AD); the 3D-M array  110 AA for the configurable computing element  100 AA (storing the LUT A for a first math function) is disposed in the first memory level  16 A and stacked above the substrate  0 K (along the +Z direction), the 3D-M array  110 AB for the configurable computing element  100 AB (storing the LUT B for a second math function) is disposed in the second memory level  16 B and stacked above the 3D-M array  110 AA (along the +Z direction), the 3D-M array  110 AC for the configurable computing element  100 AC (storing the LUT C for a third math function) is disposed in the third memory level  16 C and stacked above the 3D-M array  110 AB (along the +Z direction), and the 3D-M array  110 AD for the configurable computing element  100 AD (storing the LUT D for a fourth math function) is disposed in the fourth memory level  16 D and stacked above the 3D-M array  110 AC (along the +Z direction). Apparently, stacking the 3D-M arrays  110 AA- 110 AD for multiple configurable computing elements  100 AA- 100 AD would save substantial die area and lead to a compact configurable computing array  400 . 
       FIGS. 10A-10B  are cross-sectional views of two preferred configurable computing array  400  based on 3D-M V . It is a monolithic integrated circuit comprising a configurable computing element  100  and a configurable logic element  200 . The configurable logic element  200  is formed on a semiconductor substrate, while the configurable computing element  100  is stacked on/above the configurable logic element  200 . The configurable computing element  100  and the configurable logic element  200  are coupled through a plurality of contact vias (not shown in these figures). The configurable computing element  100  comprises at least a 3D-M V  array. Within the 3D-M V  array, at least one set of the address lines are oriented in a direction perpendicular to the side of the substrate. Because the 3D-M V  has the largest storage density among of semiconductor memories, it can store the LUTs for a large number of functions and/or the LUTs with a high precision. 
     The preferred 3D-M V  array in  FIG. 10A  is based on vertical diodes or diode-like devices. In this preferred embodiment, the 3D-M V  array comprises a plurality of vertical memory strings  16 M- 16 O placed side-by-side. Each memory string (e.g.  16 M) comprises a plurality of vertically stacked memory cells (e.g.  7   am - 7   hm ). The 3D-M V  array comprises a plurality of horizontal address lines (word lines)  6   a - 6   h  which are vertically stacked above each other. After etching through the horizontal address lines  6   a - 6   h  to form a plurality of vertical memory wells  25 , the sidewalls of the memory wells  25  are covered with a programmable layer  21 . Alternatively, the sidewalls are further covered with a diode layer to minimize the interference between memory cells (not shown in this figure). The memory wells  25  are then filled with a conductive materials to form vertical address lines (bit lines)  23 . The conductive materials could comprise metallic materials or doped semiconductor materials. The memory cells  7   am - 7   hm  are formed at the intersections of the word lines  6   a - 6   h  and the bit line  23 . The programmable layer  21  could be one-time-programmable (OTP, e.g. an antifuse layer) or multiple-time-programmable (MPT, e.g. a resistive RAM layer). The programmable layer  21  could have an electrical characteristic like a diode per se. 
     The preferred 3D-M V  array in  FIG. 10B  is based on vertical transistors or transistor-like devices. In this preferred embodiment, the 3D-M V  array (e.g. 3D-NAND array) comprises a plurality of vertical memory strings  16 X,  16 Y placed side-by-side. Each memory string (e.g.  16 X) comprises a plurality of vertically stacked memory cells (e.g.  9   ax - 9   hx ). Each memory cell (e.g.  9   fx ) comprises a vertical transistor, which includes a gate  31 , a storage layer  33  and a vertical channel  35 . The storage layer  33  could comprise oxide-nitride-oxide layers, oxide-poly silicon-oxide layers, or the like. The vertical channels  35  of the memory cells  9   ax - 9   hx  collectively form a vertical address line. 
     In the preferred embodiments of  FIGS. 10A-10B , the transistors  0   t  are formed on the substrate  0  and they are conventional transistors. These transistors  0   t  are coupled by interconnects  0 M 1 ,  0 M 2 . In addition, the 3D-M V  array is communicatively coupled with the transistors  0   t  through a plurality of contact vias (not shown in this figure). It should be noted that the transistors  0   t  and interconnects  0 M 1 ,  0 M 2  can form not only configurable logic elements  200 , but also configurable interconnects (not shown in this figure). 
     Referring now to  FIGS. 11A-11C , a preferred configurable computing-array die  400  using two-sided integration is disclosed. It is a monolithic integrated circuit comprising a semiconductor substrate  0 . The substrate  0  has a front side  0 F (towards the +z direction) and a back side  0 B (towards the −z direction). In this preferred embodiment, the configuration logic elements  200 AA- 200 BB are formed at the front side  0 F of the substrate  0  ( FIG. 11A ), while the configurable computing elements  100 AA- 100 BB are formed at the back side  0 B of the substrate  0  ( FIG. 11B ). They are coupled through a plurality of through-substrate vias  160  (including  160   a - 160   c ). Examples of the through-substrate vias include through-silicon vias (TSV). Alternatively, the configurable computing elements  100 AA- 100 BB are formed at the front side  0 F, while the configurable logic elements  200 AA- 200 BB are formed at the back side  0 B. 
     This type of integration, i.e. forming the configurable logic elements  100 AA- 100 BB and the configurable computing elements  200 AA- 200 BB on different sides of the substrate, is referred to as two-sided integration. The two-sided integration can improve computational density and computational complexity. With the conventional 2-D integration, the die size of configurable computing array is the sum of those of the configurable computing elements and the configurable logic elements. With the two-sided integration, the configurable computing elements are moved from aside to the other side. This leads to a smaller die size and a higher computational density. In addition, because the memory transistors in the configurable computing elements and the logic transistors in the configurable logic elements are formed on different sides of the substrate, their manufacturing processes can be optimized separately. 
     Referring now to  FIGS. 12-13C , several preferred configurable computing-array packages  400  are disclosed. In the preferred embodiments of  FIG. 12 , the preferred configurable computing-array package  400  comprises a configurable computing die  100 W and a configurable logic die  200 W. The configurable computing die  100 W is formed on a first semiconductor substrate  100 S and comprises at least an array of configurable computing elements  100 AA- 100 BB. Each configurable computing element  100  comprises a memory array  110  for storing at least a portion of an LUT for a math function. On the other hand, the configurable logic die  200 W is formed on a second semiconductor substrate  200 S and comprises at least an array of configurable logic elements  200 AA- 200 BB. Each configurable logic element  200  selectively realizes a logic function from a logic library. The configurable computing die  100 W and the configurable logic die  200 W are located in a same package. In this preferred embodiment, the configurable computing die  100 W is stacked on/above the configurable logic die  200 W. The configurable computing die  100 W and the configurable logic die  200 W are communicatively coupled by a plurality of inter-die connections  160 . Exemplary inter-die connections include micro-bumps and through-silicon-vias (TSV). The preferred configurable computing array  400  further comprises a plurality of configurable interconnects, each of which selectively realizes an interconnect from an interconnect library. The configurable interconnects could be located on the configurable computing die  100 W and/or the configurable logic die  200 W. 
       FIGS. 13A-13C  show three preferred configurable computing-array packages  400 . These preferred embodiments are located in multi-chip packages (MCP). Among them, the configurable computing-array package  400  in  FIG. 13A  comprises two separate dice: a configurable computing die  100 W and a configurable logic die  200 W. The dice  100 W,  200 W are stacked on the package substrate  170  and located in a same package  180 . Micro-bumps  166  act as the inter-die connections  160  and provide electrical coupling between the dice  100 ,  200 . In this preferred embodiment, the configurable computing die  100 W is stacked on the configurable logic die  200 W; the configurable computing die  100 W is flipped and then bonded face-to-face with the configurable logic die  200 W. Alternatively, the configurable logic die  200 W could be stacked on/above the configurable computing die  100 W. Either die does not have to be flipped. 
     The configurable computing-array package  400  in  FIG. 13B  comprises a configurable computing die  100 W, an interposer  120  and a configurable logic die  200 W. The interposer  120  comprise a plurality of through-silicon vias (TSV)  168 . The TSVs  168  provide electrical couplings between the configurable computing die  100 W and the configurable logic die  200 W. They offer more freedom in design and facilitate heat dissipation. In this preferred embodiment, the TSVs  168  and the micro-bumps  166  collectively form the inter-die connections  160 . 
     The configurable computing-array package  400  in  FIG. 13C  comprises at least two configurable computing dice  100 W,  100 W{grave over ( )} and a configurable logic die  200 W. These dice  100 W,  100 W{grave over ( )},  200 W are separate dice and located in a same package  180 . Among them, the configurable computing die  100 W{grave over ( )} is stacked on the configurable computing die  100 W, while the configurable computing die  100 W is stacked on the configurable logic die  200 W. The dice  100 W,  100 W{grave over ( )},  200 W are electrically coupled through the TSVs  168  and the micro-bumps  166 . Apparently, the LUT in  FIG. 13C  has a large capacity than that in  FIG. 13A . Similarly, the TSVs  168  and the micro-bumps  166  collectively form the inter-die connections  160 . 
     Although their active elements are disposed in a 3-D space, the configurable computing die  100 W and the configurable logic die  200 W are separate dice. Accordingly, this type of integration is generally referred to as 2.5-D integration. The 2.5-D integration excels the conventional 2-D integration (i.e. single-level configurable computing array) in many aspects. First of all, the footprint of a conventional 2-D integrated configurable computing array is roughly equal to the sum of those of the configurable computing elements, the configurable logic elements and the configurable interconnects. On the other hand, because the 2.5-D integration moves the configurable computing elements from aside to above, the configurable computing-array package  400  becomes smaller and computationally more powerful. Secondly, because they are physically close and coupled by a large number of inter-die connections  160 , the configurable computing die  100 W and the configurable logic die  200 W have a larger communication bandwidth than the conventional 2-D integrated configurable computing array. Thirdly, the 2.5-D integration benefits manufacturing process. Because the configurable computing die  100 W and the configurable logic die  200 W are separate dice, the memory transistors in the configurable computing die  100 W and the logic transistors in the configurable logic die  200 W are formed on separate semiconductor substrates. Consequently, their manufacturing processes can be individually optimized. 
     The preferred embodiments of the present invention are field-programmable computing-array (FPCA) package. For an FPCA package, all manufacturing processes of the configurable computing die and the configurable logic die are finished in factory. The function of the FPCA package can be electrically defined in the field of use. The concept of FPCA package can be extended to mask-programmed computing-array (MPCA) package. For a MPCA package, the wafers containing the configurable computing elements and/or the wafer containing the configurable logic elements are prefabricated and stockpiled. However, certain interconnects on these wafers are not fabricated until the function of the MPCA package is finally defined. 
     While illustrative embodiments have been shown and described, it would be apparent to those skilled in the art that many more modifications than that have been mentioned above are possible without departing from the inventive concepts set forth therein. The invention, therefore, is not to be limited except in the spirit of the appended claims.