Mapping algorithm for large-scale field programmable analog array

Mapping Algorithm for Large-scale Field Programmable ∗ Analog Array Faik Baskaya, Sasank Reddy, Sung Kyu Lim, Tyson Hall, and David V. Anderson School of Electrical and Computer Engineering Georgia Institute of Technology Atlanta, GA 30332 {baskaya, sreddy, limsk, tyson, dva}@ece.gatech.edu ABSTRACT + WR_OTA Modern advances in reconfigurable analog technologies are allowing field-programmable analog arrays (FPAAs) to dra- + WR_OTA + WR_OTA matically grow in size, flexibility, and usefulness. With these advances, analog circuits and systems can be programmable, + + WR_OTA reconfigurable, adaptive, implemented on standard CMOS WR_OTA + WR_OTA to take advantage of scaled CMOS technology, and at a den- sity comparable to digital memories. Our goal in this paper is to develop the first physical design automation toolset for floating-gate based FPAA with focus on minimization of parasitic effects on FPAA interconnect. We provide graph- based analog circuit and FPAA device modeling suitable for efficient mapping. Our FPAA clustering algorithm con- structs Computational Analog Blocks (CAB) from analog Figure 1: An analog circuit and its mapping onto circuit elements while improving the utilization of the de- our floating-gate based FPAA. vice and reducing its impact on the total number of routing switches used. Experimental results demonstrate the effec- tiveness of our approach. analog technologies are allowing field-programmable analog arrays (FPAAs) to dramatically grow in size, flexibility, and usefulness. With these advances, analog circuits and sys- Categories and Subject Descriptors tems can be programmable, reconfigurable, adaptive, im- B.7.2 [Design Aid]: Placement and routing plemented on standard CMOS to take advantage of scaled CMOS technology, and at a density comparable to digital General Terms memories. Our goal in this paper is to develop the first phys- ical design automation toolset for floating-gate based FPAA Algorithms, Design with focus on minimization of parasitic effects on FPAA in- terconnect. Keywords On the otherhand, FPAAs still have not achieved the same Floating gates, Field Programmable Analog Array, mapping success as FPGAs in the digital domain even with the grown interest, availability and use of FPAAs. This results from 1. INTRODUCTION several factors, including the lack of CAD tools, small circuit density, small bandwidth and layout dependent noise figures. While digital processors can perform the desired func- These factors are all related to each other, making the design tions, there are many cases where an analog design can offer of a high performance FPAA a multi-dimensional problem. the same functionality at a fraction of the power required A critical reason behind these difficulties is the non-ideal for the digital solution. Modern advances in reconfigurable programming technology, which contributes a large portion ∗This research has been supported by the National Science of parasitics into the sensitive analog system. Foundation under contract CNS-0411149. The floating-gate transistors used in our FPAAs are stan- dard pFET devices whose gate terminals are not connected to signals except through capacitors. Because the gate ter- minal is well insulated from external signals, it can main- Permission to make digital or hard copies of all or part of this work for tain a permanent charge, and thus, it is an analog memory personal or classroom use is granted without fee provided that copies are cell similar to an EEPROM cell. We propose to develop not made or distributed for profit or commercial advantage and that copies the first mapping algorithm for floating-gate based large- bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific scale FPAA. The possibility of programmable analog tech- permission and/or a fee. nology has potential to penetrate the market from simple ISPD’05, April 3–6, 2005, San Francisco, California, USA. one-parameter programmable elements to large-scale signal Copyright 2005 ACM 1-59593-021-3/05/0004 ...$5.00. processing front-end systems. A few companies have already 152  CAB started investigating using analog floating-gate elements as simple trimming elements for analog applications, but these approaches only start to unlock the potential of this tech- nology. An illustration of analog circuit mapping using our FPAA is shown in Figure 1. The existing CAD works for FPAAs target switch capacitor- based FPAAs (Motorola) and include behavioral synthesis [10, 3], technology mapping [2], and place-and-route [10, 9, 1]. However, these algorithms are designed for small- scale FPAAs and thus are not applicable for our large-scale floating-gate based FPAA. In addition, the placement and routing constraints in our floating-gate based FPAA are rad- local global ically different from the switch capacitor-based FPAA. Since switch switch the major parasitic effects on FPAA chips are due to para- sitic resistance and capacitance on FPAA interconnects, our Figure 3: Illustration of graph-based FPAA device goal is to minimize the overall routing switches used while modeling. satisfying various device/wire-related constraints. The remainer of this paper is organized as follows. Sec- max in tion II presents the analog circuit and FPAA device mod- + eling. Section III presents the problem formulation. Sec- tion IV presents the signal degradation modeling. Section min 4x4 out V presents our FPAA clustering algorithm. Experimental vector results are shown in Section VI, and we conclude in Section multiplier out VII. in 2. DEVICE AND CIRCUIT MODELING 2.1 FPAA Device Modeling A floating-gate element is a polysilicon layer that has no in op ps contacts to other layers; this floating-gate can be the gate m1 of a MOSFET and can be capacitively connected to other gnd cg ps ps out ca layers. Charge on the floating-gate is stored permanently, vm providing a long-term memory, because it is completely sur- vdd pf ps c4 m2 ps out rounded by a high-quality insulator. Since the floating-gate voltage can modulate a MOSFET’s channel current, the in nf ps gnd floating-gate is not only a memory, but also can be an inte- gral part of a computation. The charge on the floating-gate is modified through a combination of hot-electron injection Figure 4: Illustration of analog circuit modeling and electron tunneling, and the modifications can occur si- multaniously to the computation being performed [4, 6, 7]. The small size and scalability make these approaches ideal wires. We model the given analog circuit with a directed for integration with classical analog techniques (e.g. voltage graph G(V, E), where V denotes a set of passive, active, references, filters, ADCs or DACs) as well as larger-scale pseudo, and I/O elements in the circuit and E denotes a set analog signal processing techniques (e.g. compression or of connections among the elements. An illustration of our classification for audio or image signal processing). There- architecture modeling is shown in Figure 3. fore, with both digital and analog signal processing modali- ties feasible, more options are now available when designing 2.2 Analog Circuit Modeling a signal processing system. Analog circuit modeling can be divided into two phases: The computational logic in the FPAA is organized in a analog circuit description and element modeling. Analog compact computational analog block (CAB) that consists of circuit description, the process in which a circuit that will op-amps, transistors, multiplier, programmable capacitors, be analyzed is represented in terms of its topology and ele- edge detectors and filters. An illustration is shown in Fig- ment values, has two major challenges. The first challenge ure 2. CABs are tiled across the chip in a regular mesh-type is to make the description human readable, and the sec- architecture with busses and local interconnects in-between. ond challenge is to make it programmatically friendly. In The major parasitic effects on FPAA chips are due to par- order to satisfy these constraints, a SPICE-like netlist was asitic resistance and capacitance on FPAA interconnects. chosen to describe the circuits. Each element in the cir- Therefore, the primary objective during mapping is to mini- cuit is specified by an element line that contains the name mize the total number of wires and switches involved in each and the circuit nodes to which the element is connected to. interconnect. The element name is an alphanumeric string which begins We model the given FPAA architecture with an undi- with a reserved name and ends with a number representing rected graph A(V, E), where V denotes a set of CABs, I/O a unique node. Thus, vm1, vm2, cg1, ca1, and op1 are all cells, local crossbars, and global crossbars, and E denotes valid element names representing different nodes in a circuit. a set of local wires, crossbar wires, global wires, and I/O Input and output pins are described in a similar fashion. 153  Analog Circuit Components C4 (AFGA) + WR_OTA In Out 40x48 CAB 40x48 CAB x-bar x-bar + 16x16 16x16 WR_OTA x-bar x-bar 40x48 CAB 40x48 CAB + x-bar x-bar WR_OTA 16x16 16x16 x-bar x-bar (a) (b) (c) Figure 2: (a) Computational Analog Block (CAB) for an FPAA based on floating-gate devices, where each CAB contains a four-by-four matrix multiplier, three wide-range operational transconductance amplifiers (OTAs), three fixed–value capacitors, a capcatively coupled current conveyor (C 4 ), a signal-by-signal multi- plier, one pFET, and one nFET. (b) overall block diagram for a large-scale FPAA. The switching interconnects are fully connectable crossbar networks built using floating-gate transistors, (c) layout of a single CAB and its crossbar. More complex circuits can be created by using sub-circuit ondary objectives include total/maximum wirelength files. Basically, a generic circuit is described with an in- and reduced congestion (= improved routability). put/output node interface list and a similar netlist as a reg- • FPAA Routing: the FPAA routing problem is to map ular circuit but without unique numbers representing each each edge in G to a set of wires in the given FPAA element. This sub-circuit then can be used multiple times architecture. Each intra-cluster edge in G may use in a circuit description without having to re-write every ele- local wires, whereas each inter-cluster edge may only ment in the sub-circuit description. Element modeling is the use vertical and possibly horizontal global wires. The next phase after analog circuit description. Each element is objective is to complete the routing while minimizing modeled as one or more vertices in a directed graph depend- the performance degradation. Our goal is to minimize ing on the number of output terminals. Unlike digital gates, the total parasitics along the interconnect, and this analog devices may have multiple output terminals. Also, is done by minimizing the number of various types of each vertex must drive only one net. In order to support wires and switches along the interconnects. such a device, pseudo vertices and pseudo nets are intro- duced into the graph. Figure 4 illustrates a sample analog The focus of this paper is to develop algorithms for FPAA circuit and its corresponding directed graph. clustering. There are three types of possible interconnects between 3. PROBLEM FORMULATION the components. These can be called as intra-CAB, inter- CAB/intra-column and inter-column interconnects. Each We divide the FPAA physical synthesis process into three of these interconnects are essentially wires which are con- steps, namely, FPAA clustering, FPAA placement, and FPAA nected to the components or other types of interconnects routing: via floating-gate transistor switches. Due to the fact that • FPAA Clustering: the input is the netlist along with each interconnect type contains different number of switches FPAA architecture. The output is a clustered netlist and the switches still have a loading effect on the circuits that satisfies the device-related resource constraints, even when they are closed, different interconnect types have i.e., number of components and IO ports in each CAB. different effects on the circuit performance. The primary objective is to minimize the amount of Intra-CAB interconnects are local interconnects within inter-cluster connection, which has positive impact on every CAB. For this reason, they are also referred to as total number of switches needed after routing. The internal nets, or i-nets in this paper. These interconnects secondary objective is to pack each cluster to its capac- correspond to the local wires and several switches on them, ity in order to minimize the number of CABs needed. which can only be used to connect the components within a CAB. Since they don’t go all the way from the top row • FPAA Placement: the FPAA placement problem is to of CABs to the bottom and contain less total number of seek a 1-to-1 mapping between the set of clusters we switches than other types of interconnects along the wire, obtain from FPAA clustering and the set of CABs in the overall parasitic effect of switches on the interconnect is the given FPAA architecture. In addition, we map I/O less and is desirable for connections that require less load- nodes in the given circuit to I/O cells in the FPAA. ing. These interconnects can not be used for connecting a The primary objective is to minimize the estimated component to another component if they are clustered in number of switches needed after routing. The sec- different CABs. 154  Inter-CAB interconnects correspond to the vertical global sponding output attenuation factor. On the other hand, the wires on columns of the FPAA. Since these wires (along with computation of Dint is much harder due to its high runtime their inter-column counterparts to be described below) es- and space complexity. For a given output v, we need to ex- tablish connections between the components clustered into amine all possible paths that connect to v. However, there different CABs, they are also called as external nets, or x- exists an exponential number of directed external paths for nets in this paper. There are also switches enabling access to a single output in a directed graph G. In addition, for each the inter-column interconnects on these wires. When a con- CAB-to-CAB connection e, we may need to store sensitivity nection has been established on an inter-CAB/intra-column value for all output cells since e may lead to all output nodes. interconnect, that wire is dedicated to this connection from Thus the time complexity is exponential and space complex- the very top row to the bottom. Hence, these interconnects ity is quadratic. During our physical synthesis optimization, have to be shared between the CABs in a column, and are therefore, it is desirable to compute estimated values of Dint very valuable resources. An inter-CAB/intra-column inter- and Dext instead of exact values. The parasitics of wires and connect has more loading effect on the circuit compared to switches along the paths to output cells play the major role. an intra-CAB interconnect. Therefore, we focus on minimizing the number of switches In order to establish connection between the components on the intra-CAB and inter-CAB interconnect as mentioned in different FPAA columns, a horizontal global wire, namely, in Section 3 for performance degradation minimization. an inter-column interconnect is required. These wires have accesses to the vertical global wires via floating-gate tran- 5. FPAA CLUSTERING ALGORITHM sistor switches. Since these wires go all the way from the first column to the last, they cause a considerable loading 5.1 Constraints, Objectives and Challenges on the circuit as well. There are two main types of structural constraints in the Intra-CAB and inter-CAB/intra-column interconnects are FPAA architectures, namely, device and net constraints. all determined at the end of clustering phase. On the other There is a certain number of each device or analog circuit hand, inter-column interconnects can be determined only block in each CAB. These numbers determine the device after the placement phase. constraints. Furthermore, we don’t have infinitely many wires and switches for connecting the devices and circuit 4. PERFORMANCE DEGRADATION blocks to each other. The wires for connecting components The impact of interconnect parasitics strongly depends of the same CAB to each other are called as internal nets on whether the interconnect is an internal or an external whereas the remaining wires that are used to connect de- signal path. An internal path connects two elements in a vices from different CAB’s to each other are called as exter- single CAB, two CABs, or one CAB and input I/O cell. An nal nets. Each type of net has its own limits and all these external path connects a CAB to an output I/O cell. The limits in addition to the device constraints are given in a performance degradation from an external path, denoted device file. Dext , is simply given by the sum of all wires and switches In the proposed FPAA clustering algorithm, we accept parasitics along the path. user defined constraints in addition to the structural con- By introducing the capacitor attenuation parameter α, the straints. The components specified by the user defined con- parasitic effects on FPAA interconnects are modeled as ca- straints have to be clustered into the same group under all pacitor attenuation. In order to estimate the circuit per- conditions. Due to the hierarchical support of the cell data formance degradation caused by the parasitics on an FPAA structure, we can create a new cell which will cover all the signal path i, the capacitors that are charged or discharged cells in this group and treat the whole cluster as a single through the signal path i are attenuated by a factor of α cell. during the circuit analysis. The capacitance attenuation pa- Unfortunately, the x-net limits described above are not rameter αi for path i is defined to be the ratio between the exclusive to each CAB but they must also be observed by capacitance at the destination CAB and the source CAB. the CABS which will share the same column at the end of The computation of αi involves computing parasitics along the placement phase. This x-net sharing condition shapes i between the source and sink CABs. Let Vlid denote the our objective during FPAA clustering, which is to minimize ideal voltage of internal paths contributing to the output the number of used CAB’s while keeping the number of i- l. Thus, Vlid is a function of capacitors along the paths: nets as high and the number of x-nets as low as possible. Vlid = fl (c1 , c2 , . . . , ck ). Let Scl j denote the sensitivity of The constraint on number of x-nets for the proposed FPAA architectures is so hard that at this time we had to give output signal l with respect to capacitor cj . Then, Scl j = priority to reducing the cut size between the clusters rather (∂fl /∂cj ) × (cj /fl ). Finally, the performance degradation than being concerned with the weight of the nets. from an internal path is given by: Another challenge comes from one of the components in   L  kj  the FPAA structure, which is called as Vector Matrix Mul- X X  Dint = wl  Scl j (αj − 1) tiplier (VM). Since it is a rather large circuit compared to l=1  j=1  the others, it comes with only a few of all CAB’s. So, this component is given higher priority in determining the order where αj is the capacitor attenuation factor for a path that for clustering the cells. drives capacitor cj . This is not the only challenge brought on by VMs. Due Assuming a single CAB is driving an output cell, the com- to its high number of input and output terminals, a VM putation of Dext is straightforward. For each output, we can easily violate the x-net limitation by itself. Actually, compute the total wire resistance between the CAB output not only VM but also the cell groups formed by the user and the output cell, which will in turn determine the corre- defined constraints described above can introduce similar 155  CAB Selection x-net reduce(c) 1: best = NULL; 1: while (x net(c) > x net limit) 2: for (each ordered cell i) 2: for (each neighbor n of c) 3: for (each CAB c) 3: if (c is available for n) 4: if (c is available for i) 4: pkey[n] = # nets in n not link to c; 5: if (rank(c) > rank(best)) 5: skey[n] = # nets in n link to c; 6: best = c; 6: if (no n is available) 7: if (best == NULL) 7: return FALSE; 8: for (each CAB x with x-net violation) 8: add n with max skey[n] with min skey[n]; 9: if (x-net reduce(x)) 9: return TRUE; 10: best = x; 11: return best; Figure 6: Pseudo code for x-net reduction algo- rithm. Figure 5: Pseudo code for CAB select algorithm. x-net-violate-only cabs in an order such that the cabs with challenges. This would cause problems in a straightforward lower overflow value are in front. These cabs are tested for clustering algorithm since there would be times that there x-net reduction algorithm (line 10) in the case that no avail- are no available CAB’s in sight and the search would stop. able CAB’s may be found for assignment. X-net reduction This problem is overcome by the x-net reduction algorithm algorithm is explained in the following section. we propose later. In the following sections, different steps of FPAA cluster- 5.4 X-net Reduction ing algorithm are described. X-net reduction algorithm described in Figure 6 is inspired by Prim’s minimum spanning tree algorithm [8]. The objec- 5.2 Pre-clustering and Cell Ordering tive of this algorithm is to reduce the number of x-nets of the cluster assigned to the given cab to an acceptable level. This In this step, cells corresponding to the components that value could be the x-net limit or even lower. Every neigh- have to be in the same cluster under all conditions due boring cell available for this cluster is given a key, which to user defined constraints or other possible reasons are is the number of nets of this neighbor cell not shared with grouped together under a higher level cell. The I/O cells the cluster. Then the neighbor with the minimum key is are also separated from the remaining cells in this step. selected for assignment to the cab containing the cluster. Once the groups are formed, all non I/O cells are put If there are several cells all having the same minimum key into an order for clustering. The atomic cells already pre- value, then we look at the maximum secondary key holder clustered will be exempt from ordering and clustering. In- among these cells. Secondary key is the number of nets of a stead their parent cells will be ordered and clustered. cell which are also shared with the given cluster. During ordering, the three main groups are treated differ- X-net reduction continues until the number of x-nets are ently. VM type cells and other cells that include VM type below the desired value (success), or the cab is no more cells are given the highest priority. Then comes the user de- available for neighboring cells (no success). fined groups of cells. Finally, the remaining cells follow after being ordered according to Modified Hyper Edge Coarsen- ing scheme [5]. The motivation is to give higher priority 6. EXPERIMENTAL RESULTS to the cells in the same net to group together first, thereby We implemented our algorithms using C++/STL, com- reducing the inter-CAB connection. piled with gcc v3.3, and tested on an Apple Powerbook loaded with MAC OS X Panther v10.3, running with a 1.5 5.3 CAB Selection GHz PowerPC G4 processor, and containing 1 GB of RAM. A pseudocode for the CAB selection algorithm is pre- The benchmark generation and clustering processes were in- sented in Figure 5. The cells to be clustered are already or- dependent C++/STL programs. dered in the previous step. Next, for each of these cells every The algorithms were tested in 4 different FPAA architec- CAB is scanned for availability and then ranked. Ranking tures of various sizes with 5 benchmark circuits using each is done based on the improvement of occupancy of the cab, architecture. Currently, there are two available CAB types. increase in the number of i-nets and decrease in the num- These types are given in Table 1. Table 2 summarizes dif- ber of x-nets when the given cell is assigned to the CAB ferent FPAA architectures. Due to the different number of of interest. The CAB with the highest rank is selected for rows in each architecture, each FPAA column may accomo- assignment. date more CABs. Thus, inter-CAB/intra-column intercon- A CAB may be unavailable for a given cell due to de- nect limitations have to be adjusted accordingly. Therefore, vice and net constraints. If addition of the cell violates the different number of global wires per column are allowed for device constraints or i-net constraints (local switch limits), each architecture. The 20 benchmark circuits being used are there is no way that this selection may be feasible. X-net displayed in Table 3. Sizes of the benchmark circuits range violation, on the other hand, is a different issue. Allowing from 10 components with 17 nets up to 500 components and temporary violation of x-net constraints may later result in 707 nets. an increase in i-nets within acceptable limits. Thus, the cabs Clustering algorithm has been applied to 20 benchmark which violate only x-nets are kept in a separate list, called as circuits in 4 different FPAA architectures and the results 156  Table 3: FPAA clustering results benchmark circuits total usage average utilization time ckt #comp #nets arch CAB lsw gsw comp i-nets x-nets (ms) a1 10 17 fpaa1 2 18 18 47.70% 45.00% 40.00% 10 a6 20 27 fpaa1 4 40 19 48.41% 50.00% 22.50% 20 a9 16 23 fpaa1 4 28 20 38.41% 35.00% 22.50% 20 a12 18 22 fpaa1 4 29 17 45.00% 35.00% 20.00% 20 a15 10 18 fpaa1 2 22 16 47.27% 55.00% 35.00% 10 b4 89 128 fpaa2 16 151 119 53.24% 46.25% 33.75% 770 b11 74 115 fpaa2 14 117 136 50.13% 40.71% 41.43% 240 b12 111 160 fpaa2 17 192 144 62.67% 55.29% 38.82% 630 c1 187 253 fpaa2 37 269 262 49.21% 35.68% 32.70% 2060 c5 207 300 fpaa2 47 292 350 42.30% 30.64% 33.19% 8010 d1 267 384 fpaa3 60 399 427 42.68% 32.50% 31.50% 16080 d2 302 434 fpaa3 63 419 503 46.20% 32.70% 36.19% 22420 d3 307 438 fpaa3 62 461 473 47.55% 36.61% 34.03% 22830 d4 297 411 fpaa3 62 415 455 46.51% 32.90% 33.39% 19610 d5 265 371 fpaa3 50 368 431 51.20% 36.00% 38.20% 15290 e1 423 602 fpaa4 92 639 638 44.34% 34.24% 31.20% 103470 e2 396 555 fpaa4 80 563 617 47.98% 34.75% 34.63% 84770 e3 403 567 fpaa4 75 626 568 51.87% 41.07% 34.53% 89150 f4 500 707 fpaa4 101 792 707 47.70% 38.32% 31.68% 163820 f5 474 680 fpaa4 106 734 734 42.96% 33.77% 30.38% 143990 lization of external connections is lower than that of internal Table 1: FPAA CAB types connections and components, which is also not a bad thing, comp cab0 cab1 for it will make the further steps of mapping easier by giving opamp 3 3 more room to sharing of external connections in a column. cap 1 1 Internal connections, on the other hand could be better uti- cap (grounded) 2 2 lized than the obtained results, since it would further reduce vm multiplier 0 1 the number of external connections and this limitation will minmax 1 1 not be revisited in further steps once the clustering is com- pfet 1 1 plete. nfet 1 1 c4 filter 1 1 local wires 10 10 7. CONCLUSIONS In this paper we present the problem formulation and al- gorithms for clustering targeting floating-gate based FPAA. Table 2: FPAA architectures Since the major parasitic effects on FPAA chips are due to comp fpaa1 fpaa2 fpaa3 fpaa4 parasitic resistance and capacitance on FPAA interconnects, dimension 4 × 4 8 × 8 12 × 12 16 × 16 our goal is to minimize the overall routing switches used cab0 4 16 36 64 while satisfying various device/wire-related constraints. Our cab1 12 48 108 192 ongoing work includes placement and routing as well as path global wires/col 6 10 15 20 length balancing heuristics. Signal degradation modeling total global wires 24 80 180 320 and analysis is also underway. Our FPAA mapping tool will be used to evaluate and improve candidate FPAA architec- tures for a variety of signal processing designs. obtained are displayed in Table 3. Depending on the bench- mark circuit complexity, number of generated clusters range 8. REFERENCES from 2 up to 106. The number of local switches obtained at the clustering phase will be the final total number of [1] S. Ganesan and R. Vemuri. FAAR: a router for switches whereas the number of global switches given in the field-programmable analog arrays. In Proc. Intl. Conf. table represent only those which connect the CABs to the on VLSI Design, pages 556–563, 1999. vertical global wires. The total number of global switches [2] S. Ganesan and R. Vemuri. Technology mapping and can be known only after the placement is finished and the retargeting for field-programmable analog arrays. In switches connecting vertical wires to the horizontal wires are Proc. Design, Automation and Test in Europe, 2000. determined. [3] S. Ganesan and R. Vemuri. Behavioral partitioning in For each cluster, average utilization of components is within the synthesis of mixed analog-digital systems. In Proc. 40% to 60% margin, which is acceptable due to the fact that ACM Design Automation Conf., 2001. priority is given to reducing the number of external connec- [4] P. Hasler, C. Diorio, B. A. Minch, and C. A. Mead. tions and the limited number of internal connections. Uti- Advances in Neural Information Processing Systems 7, 157  chapter Single transistor learning synapses, pages [8] R. C. Prim. Shortest connection networks and some 817–824. MIT Press, Cambridge, MA, 1995. generalizations. Bell Systems Technical Journal, [5] G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. 36:1389–1401, 1957. Multilevel hypergraph partitioning : Application in [9] H. Wang and S. Vrudhula. Performance driven VLSI domain. In Proc. ACM Design Automation placememnt and routing for field programmable Conf., pages 526–529, 1997. analog arrays. In Proc. Intl. Conf. on Mixed Design of [6] M. Kucic, P. Hasler, J. Dugger, and D. V. Anderson. Integrated Circuits and Systems, pages 207–212, 2001. Programmable and adaptive analog filters using arrays [10] H. Wang and S. Vrudhula. Behavioral synthesis of of floating-gate circuits. In E. Brunvand and C. Myers, field programmable analog array circuits. ACM Trans. editors, 2001 Conference on Advanced Research in on Design Automation of Electronics Systems, pages VLSI, pages 148–162. IEEE Computer Society, March 563–604, 2002. 2001. [7] M. Kucic, A. Low, P. Hasler, and J. Neff. A programmable continuous-time floating-gate fourier processor. IEEE Transactions on Circuits and Systems II, 48(1), 2001. 158