9 Emerging Hardware Technologies for IoT Data Processing
463
• Forming New Clusters: The bank controller forms new partitions by reading the
data points from the data subarrays and comparing them with the centroids (2).
The index of the closest centroid to every data point is used as the new cluster
label for these data and will be written to the label array (3). This is accomplished
through a set of serial comparators at the bank controller. As the data points are
read out, the serial comparator determines the index of the closest centroid to the
data.
• Computing Medians: The centroid of each cluster must be recomputed by
applying the bit-serial median algorithm to all the elements of every cluster. This
requires the bank controller to keep track of the cluster members at all time. The
label array uses the same structure as the data array to carry out the required book
keeping for all of the data points. At the beginning of every median computation,
the label arrays are searched for matching entries using the cluster labels one
after another (4). The outcome of every search operation is the matching lines
in the label subarray connected to a row selector unit to determine the I and P
values for the data array (5). Next, the median bits are computed by iteratively
performing the vertical majority vote computation followed by the horizontal
minority propagation (6). The median bits are streamed to the bank controller for
updating the centroids as they are serially computed by the MISC arrays (7). This
process ends after a certain number of iterations defined by the software. One
other possibility for ending the program is to stop the process if all of the newly
computed centroids are the same as the old ones. In other words, the computation
is repeated until convergence is reached.
9.5.5.4 MISC Data Representation
MISC needs to represent the data points in a fixed-point positive format due to the
limits of the bit-serial median algorithm on negative or real numbers. The software
performs all the necessary data conversion and preprocessing for clustering real
numbers and negative values prior to loading the data points into the MISC chips.
Clustering Real Numbers MISC converts the real valued numbers to fixed-point
data prior to clustering. A 64-bit fixed-point format achieves virtually the same
results obtained with a double-precision IEEE floating point format for a wide range
of applications and datasets. However, for more sensitive applications, MISC is
flexible enough to compute the medians of wider bit representations by increasing
the number of vertical majority vote computation and applying minimal changes
to the control logic. Figure 9.27 shows an example clustering tasks for five real
valued numbers. A preprocessing step is considered to convert floating point to the
fixed point. The input floating point data are scaled by a factor of 2 3 . Then, the bit
serial median algorithm is used to compute the median. Finally, the median value is
identified.
Handling Negative Numbers The median computation by the bit-serial median
algorithm assumes that the input data are positive integers. This may not be
463
• Forming New Clusters: The bank controller forms new partitions by reading the
data points from the data subarrays and comparing them with the centroids (2).
The index of the closest centroid to every data point is used as the new cluster
label for these data and will be written to the label array (3). This is accomplished
through a set of serial comparators at the bank controller. As the data points are
read out, the serial comparator determines the index of the closest centroid to the
data.
• Computing Medians: The centroid of each cluster must be recomputed by
applying the bit-serial median algorithm to all the elements of every cluster. This
requires the bank controller to keep track of the cluster members at all time. The
label array uses the same structure as the data array to carry out the required book
keeping for all of the data points. At the beginning of every median computation,
the label arrays are searched for matching entries using the cluster labels one
after another (4). The outcome of every search operation is the matching lines
in the label subarray connected to a row selector unit to determine the I and P
values for the data array (5). Next, the median bits are computed by iteratively
performing the vertical majority vote computation followed by the horizontal
minority propagation (6). The median bits are streamed to the bank controller for
updating the centroids as they are serially computed by the MISC arrays (7). This
process ends after a certain number of iterations defined by the software. One
other possibility for ending the program is to stop the process if all of the newly
computed centroids are the same as the old ones. In other words, the computation
is repeated until convergence is reached.
9.5.5.4 MISC Data Representation
MISC needs to represent the data points in a fixed-point positive format due to the
limits of the bit-serial median algorithm on negative or real numbers. The software
performs all the necessary data conversion and preprocessing for clustering real
numbers and negative values prior to loading the data points into the MISC chips.
Clustering Real Numbers MISC converts the real valued numbers to fixed-point
data prior to clustering. A 64-bit fixed-point format achieves virtually the same
results obtained with a double-precision IEEE floating point format for a wide range
of applications and datasets. However, for more sensitive applications, MISC is
flexible enough to compute the medians of wider bit representations by increasing
the number of vertical majority vote computation and applying minimal changes
to the control logic. Figure 9.27 shows an example clustering tasks for five real
valued numbers. A preprocessing step is considered to convert floating point to the
fixed point. The input floating point data are scaled by a factor of 2 3 . Then, the bit
serial median algorithm is used to compute the median. Finally, the median value is
identified.
Handling Negative Numbers The median computation by the bit-serial median
algorithm assumes that the input data are positive integers. This may not be