Accelerator for k-means clustering with memristor crossbars

A crossbar array includes a number of memory elements. A vector input register has N voltage inputs to the crossbar array. A vector output register has M voltage outputs from the crossbar array. An analog-to-digital converter (ADC) is electronically coupled to the vector output register. A digital-to-analog converter (DAC) is electronically coupled to the vector input register. A clustering processor is electronically coupled to the ADC and to the DAC. The clustering processor is configured to program columns of the crossbar array with a set of k cluster center values; apply voltages to rows of the crossbar array where the applied voltages represent a set of data values; and determine a minimum distance of each data value to each k cluster center values based on the voltage output from the output register of each of the plurality of the programmed columns.

BACKGROUND

K-means clustering is a method that may be used for clustering data points for a variety of applications. The k-means clustering method groups or segments t data points in an n-dimensional space into a set of k clusters. In other words, k-means clustering aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean. K-means clustering is an iterative approach to classification of the data points.

A memristor crossbar array structure can carry out vector-matrix multiplication. By applying a vector of voltage signals to the rows of a memristor crossbar array, multiplication by each element's conductance is carried out. The memristor crossbar array structure may be further configured to accelerate performance of k-means clustering for vector data sets over traditional digital ASIC processing.

SUMMARY

Embodiments of the present disclosure are directed to a memristive dot product system for vector processing, and related method and non-transitory computer storage device storing instructions operable to cause one or more computer processors to perform the method.

In one embodiment, a crossbar array includes a number of memory elements. The crossbar array has N rows, M columns and N×M memory elements. A vector input register has N voltage inputs to the crossbar array. A vector output register has M voltage outputs from the crossbar array. An analog-to-digital converter (ADC) is electronically coupled to the vector output register. A digital-to-analog converter (DAC) is electronically coupled to the vector input register. A clustering processor is electronically coupled to the ADC and to the DAC. The clustering processor is configured to program columns of the crossbar array with a set of k cluster center values, to apply voltages to rows of the crossbar array where the applied voltages represent a set of data values, and to determine a minimum distance of each data value to each k cluster center values based on the voltage output from the output register of each of the plurality of the programmed columns.

DETAILED DESCRIPTION

K-means clustering is a method that may be used for clustering data points for a variety of applications. The k-means clustering method groups or segments t data points in an n-dimensional space into a set of k clusters. In other words, k-means clustering aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean. K-means clustering is an iterative approach to classification of the data points.

The k-means clustering method may be performed in two general steps: assignment of data points to a closest cluster center, and an update of the cluster center values. One example of a k-means clustering method is known as the Lloyd's algorithm which proceeds by alternating between an assignment step and an update step.

In the assignment step, each data point is assigned to a particular k cluster center to the nearest cluster center value (also referred to as cluster means). One way to determine the closest center value to a data point is by determining the cluster center whose mean has the least squared Euclidean distance to the data point.

After the data points are assigned to their nearest cluster center, the assigned data points for a respective cluster center are then averaged together to find a new cluster center (i.e., a new cluster mean). After determining new cluster centers, then the method repeats using the new set of cluster centers in the assignment step.

The assignment step, and the update step continue until the method has converged. Convergence may be determined when the assignment of data points no longer changes. Additionally, the iterative steps may be set to a threshold or limited number of iterations. This may be necessary, if the optimum cluster center is not found, and the cluster centers begin alternating between a few points.

An example memristive crossbar array is now described for use in k-means clustering. While a particular example of a memristive crossbar array is described, other configurations of memristive crossbar arrays may be used.FIG. 1illustrates a memristive dot-product engine100, also referred to as the dot-product system, having a single vector of voltage. The dot-product engine100includes a crossbar array102including N row electrodes104and M column electrodes106. The crossbar junctions throughout the crossbar array102include a memristive element108. The dot-product engine100includes a vector input register or vector input110for applying voltages to the row electrodes104and a vector output register or vector output114for receiving output voltages resulting from current flows in the column electrodes106. Additionally, the dot-product engine100includes input registers for columns to adjust the columns conductance.

The vector input may be coupled to digital to analog convertors111to convert digital values to analog values for writing to the crossbar array102. The vector output114may include analog to digital converters115to convert analog values to digital values. The dot-product engine100also includes sense circuitry116for converting an electrical current in a column electrode106to a voltage. In an example, the sense circuitry116includes an operational amplifier118and a resistor120, which can be arranged to represent a virtual ground for read operations.

The dot-product engine100may also include other peripheral circuitry associated with crossbar arrays102used as storage devices. For example, the vector input110may include drivers connected to the row electrodes104. An address decoder can be used to select a row electrode104and activate a driver corresponding to the selected row electrode104. The driver for a selected row electrode104can drive a corresponding row electrode104with different voltages corresponding to a vector-matrix multiplication or the process of setting resistance values within the memristive elements108of the crossbar array102thereby forming a memory element of the dot-product engine. Each memory element may include a memristor and a transistor in series with one another. Similar driver and decoder circuitry may be included for the column electrodes106. Control circuitry may also be used to control application of voltages at the inputs and reading of voltages at the outputs of the dot-product engine100. Digital to analog circuitry and analog to digital circuitry may be used at the vector inputs110and at the vector output114. Input signals to the row electrodes104and column electrodes106can be either analog or digital. The peripheral circuitry above described can be fabricated using semiconductor processing techniques in the same integrated structure or semiconductor die as the crossbar array102in the above example. As described in further detail below, there are two main operations that occur during operation of the dot-product engine. The first operation is to program the memristors in the crossbar array so as to map the mathematic values in an N×M matrix to the array. In one example, only one memristor is programmed at a time during the programming operation. The second operation is the dot-product or matrix multiplication operation. In this operation, input voltages are applied and output voltages obtained, corresponding to the result of multiplying an N×M matrix by an N×1 vector. The input voltages are below the threshold of the programming voltages so the resistance values of the memristors in the array102are not changed during the matrix multiplication operation.

The dot product engine100may include analog-to-digital converters115to convert analog signals of the vector output register114to digital values. The dot product engine100may include digital-to-analog converters to convert digital values to an analog values to the column input register. The dot product engine100may include a digital-to-analog converter to convert digital values to analog values to the vector input register110.

Input to the vector input register may be a vector of voltages {Vn}. Input to the column input register may be an array of conductances {Gnm}. The vector output register may be a vector of currents {Im}. The following formula may be used to determine the vector output based on the vector input and the column input, Im=ΣnGnm·Vn.

The dot product engine100may be electronically coupled to clustering processor160. The clustering processor160may be integrally coupled to the dot product engine100and formed as a part thereof. The clustering processor160may be a separate component, such as an integrated circuit, or separate processor. The clustering processor160may be one or more central processing units (CPUs), semiconductor-based microprocessors, and/or other hardware devices suitable for retrieval and execution of instructions stored in machine-readable storage medium. The clustering processor may fetch, decode, and execute instructions, to control processes for performing k-means clustering with the crossbar array. As an alternative or in addition to retrieving, and executing instructions, the clustering processor160may include one or more electronic circuits that include electronic components for performing the functionality of one or more instructions, e.g., a Field Programmable Gate Array (FPGA) or Application Specific Integrated Circuit (ASIC). The clustering processor may include memory for storing executable instructions, and/or be couple to a separate storage medium162. The clustering processor160may be electronically coupled via electronic circuit113to DAC112to program a column of the crossbar array102. The clustering process may be electronically coupled via electronic circuit113to DAC112to apply data values as voltages to the crossbar array. The clustering processor160may be electronically coupled via electronic circuit113to ADC115to receive an output from the crossbar array102. The clustering processor160may be electrically coupled to a memory register164or cache to retrieve input vector data. The data may be static, or may be updated periodically, for example in streaming context.

The dot product system may include two modes of operation: 1) dot-product computation, and 2) programming memristor array analog values. If an array of voltage signals is applied to the rows of a crossbar via vector input110, the current measured at a column will be a weighted summation of the inputs with each input being multiplied by the conductance or ‘weight’ of the corresponding cross-point memristive device. Multiply-add operation is performed concurrently in all the layers as well within each layer of crossbar and the resulting currents are summed at the output using CMOS circuitry.

A machine-readable storage medium, such as162, may include both volatile and nonvolatile, removable and non-removable media, and may be any electronic, magnetic, optical, or other physical storage device that contains or stores executable instructions, data structures, program module, or other data accessible to clustering processor160, for example firmware, erasable programmable read-only memory (EPROM), random access memory (RAM), non-volatile random access memory (NVRAM), optical disk, solid state drive (SSD), flash memory chips, and the like. The machine-readable storage medium may be a non-transitory storage medium, where the term “non-transitory” does not encompass transitory propagating signals.

Referring now toFIG. 2, an example method200of k-means clustering is described. A k arbitrary number of data points are selected as cluster centers (block220). The number of k cluster centers selected may be based on the number of groupings desired. The k cluster centers may be randomly chosen data points to begin as the cluster centers. Each of the data points are assigned to the nearest cluster center (block230). The method then determines new cluster centers for the assigned data points. (block240). The method continues until convergence (block250).

Referring toFIG. 3, an example method300of k-means clustering with a memristor cross-bar array is described. The clustering processor160may perform a method for k-means clustering using the cross-bar array to determine Euclidean distances for data point values to k cluster centers.

A k number of cluster means is determined by the processor based on the number of data points of a vector data input, or by an input value to be used as the number of k clusters (block310). A set of d-dimensional input data having a plurality of data points is received by the system. This received input data may be stored in a memory register accessible to the processor.

The system determines an initial k arbitrary data points for the number of k clusters needed (block330). The data points may be randomly assigned as starting cluster means values. A digital based randomizer process may be used to determine random data values. The system programs the values of the k cluster means into each column of the memristor array (block340). For example, if 5 cluster means are used, each of the 5 cluster means values are programmed into the columns of the crossbar array. In this example, there would be 5 columns of the memristor array programmed with respective values for the cluster means.

Each of the k cluster means values may be a vector having multiple data elements. For example, a k cluster means value may be a vector with a set of numeric data values. Each data value of the vector may be programmed into multiple different n rows of a particular m column of the crossbar array. And each of the k cluster mean vectors, the vector values k=(k1, k2, . . . kn) may be programmed into multiple different m columns of the crossbar array. The crossbar array may be programmed according to the formula Gnm=kmnfor each cluster mean km, where n is an index value for a row of the crossbar array, and m is an index value for a column of the crossbar array. Gnmis programmed for each data element of the cluster mean vector. kmrepresents an instance of a mean vector for a cluster. For example, for a 5 dimensional space, the cluster mean vector would have 5 coeffcients or values, and the crossbar array would be programmed where G1m=km1, G2m=km2, G3m=km3, G4m=km4and G5m=km5.

The elements in each column of the memristor array are programmed as conductances. The conductance value is mapped to a possible range of numeric values. The k cluster means values are encoded or programmed into the columns of the crossbar array. In other words, a real number for the k cluster means value is mapped or translated into a conductance value in the column of the crossbar array.

An alternative method of initializing the columns with k arbitrary starting clusters is by applying random voltages to the rows, and random voltages to the columns at the same time. For example, applying random pulse sequences to the rows and columns may generate a random initial set of k cluster values. Every memristor will receive a voltage which would be the difference between its row and its column. Each column would correspondingly get programmed to a unique value. In this manner, each of the columns would be initialized with unique k cluster values.

Vector data values are then applied as applied voltages to rows of the memristor array (block350). Each data point of the vector data is applied to the memristor array as voltages.

Optionally, the system may inject noise into the memristor array by applying a voltage to an extra row of the memristor array (block360). Basically, error or noise may be introduced into the dot product calculations which may result in a different closest k cluster center to a data point being determined. Adding noise into the dot product calculations may help avoid cluster center calculations from becoming trapped in a local minimum.

The system then determines the relative distances of the data points to the k cluster means from the output column vector of the memristor array (block370). The shortest distance may be determined by the minimum Euclidean distance from a data point {d} to the k cluster centers. For example, the Euclidean distance between two points in n-dimensional space where p=(p1, p2 . . . pn) and q=(q1, q2 . . . qn) may be determined by the formula sqrt[|p|2+|q|2−2p·q]. With the crossbar array, one may calculate the 2p·q term efficiently, and for a particular point/vector |p|2is a constant term, the contribution from the cluster mean vector (for example as for q outlined above) may be handled—either by 1) adding each column's unique contribution |q|2to the measured result Im=ΣnGnm·Vnwhich is essentially the p·q term, or by 2) ensuring as programmed each cluster vector is unit normalized such that |q|2=1 for all clusters before the minimum distance cluster is determined by the program.

To determine the minimum Euclidean distance, the system identifies the maximum dot product value from the output column vector of the memristor array. The Euclidean distance is related to the negative of the dot product. Picking the max Im, of columns storing the cluster means vector kmnvalues, where Im=ΣnGnm·Vnthen determines the closest kmfor a particular data point {d}. It may be assumed that the cluster means are unit normalized in Gnmprogramming following this approach. Otherwise, |km|2may also be accounted for to determine the closest cluster.

The numeric values of the evaluated data point and the determined corresponding cluster center may be stored in a memory register. Additionally, the data may be encoded into a second crossbar array. The data points may be encoded in a row of the second crossbar array with n columns for an n-dimensional vector. Such a second crossbar array could directly drive the first crossbar array when supplying data vectors to the row electrodes of that first crossbar system. This would be accomplished by, for any desired data vector in the second crossbar array, the corresponding row electrodes of the second crossbar array would be driven with a positive voltage while all other rows would be driven with zero voltage. The output vector of the columns would thus be proportional to the desired data vector, which could drive the inputs to the first crossbar array. Additional rows or columns in the second crossbar array may be used to store the k-means cluster value that the data point is assigned to.

The system determines new k cluster means (block380). The system has now assigned data points to respective k cluster centers. The system then determines a new mean value, or new center value, by calculating a mean value for all of the data points assigned to a particular k cluster center.

The system determines whether the data points have converged to a particular cluster center means. If the data points have converged, then the method ends (block395), otherwise, block340is repeated using the new k cluster means determined in block380.

The new k cluster means values may be updated in the crossbar array using different approaches. The first approach is to program the conductances of the columns as described above to encode the new k cluster means values. In this case, the columns are programmed to the particular conductance for the respective new k cluster means values.

An approach to update the columns with the new k cluster means values is by nudging or adjusting the already programmed conductance values of a column by applying a voltage to the programmed column. The processor may calculate a delta Δ between the old k cluster means value and the new k cluster means values, Δ=km(old)−km(new). This delta may be a set of positive or negative numbers. Based on the delta values, a set of positive or negative voltages may be applied to the rows, while simultaneously grounding (applying 0 voltage) to the chosen column to “nudge” or adjust the conductance of the column to the desired conductance. All other columns in this operation would be left “floating” (no applied voltage potential) so that these conductances would not be affected. Larger voltages may move the value, for example 1 to 2 volts, whereas smaller applied voltages 0.2 volts or less may not change the conductance value. Larger positive voltages can increase the conductance, while larger negative voltages would decrease the conductance. The overall amount of the increase or decrease of the conductance is proportional to the voltage applied, or proportional to the duration of time the voltage is applied. The longer amount of time a voltage is applied, then the greater the change in conductance. A similar operation would be applied to each target column based on the corresponding delta values for that cluster mean.

FIG. 4is an example computing device400with a hardware processor402, with machine readable instructions404for performing k-means clustering with a memristor cross-bar array. As described in detail below, the machine-readable storage medium may be encoded with executable instructions410-490, for performing k-means clustering with a memristor cross-bar array.

The executable instructions include instructions for determining k number of cluster means (block410); instructions for receiving d-dimensional vector data having a plurality of data points (block420); instructions for determining k arbitrary data points as k cluster means (block430); instructions for programming the k cluster means into each column of the memristor array (block440); instructions for applying the d-dimensional vector data as applied voltages to rows of the memristor array (block450); instructions for injecting noise by applying voltage to extra row of the memristor array (block460); instructions for determining relative distances of the data points to the k cluster means from the output column vector of the memristsor array (block470); instructions for determining new k cluster means (block480); and instructions for repeating blocks440-480until convergence (block490).