k Nearest Neighbor Classification Coprocessor with Weighted Clock-Mapping-Based Searching

Fengwei AN; Lei CHEN; Toshinobu AKAZAWA; Shogo YAMASAKI; Hans Jürgen MATTAUSCH

doi:10.1587/transele.E99.C.397

k Nearest Neighbor Classification Coprocessor with Weighted Clock-Mapping-Based Searching

Fengwei AN, Lei CHEN, Toshinobu AKAZAWA, Shogo YAMASAKI, Hans Jürgen MATTAUSCH

Full Text Views

0

Share
Cite this

Summary :

Nearest-neighbor-search classifiers are attractive but they have high intrinsic computational demands which limit their practical application. In this paper, we propose a coprocessor for k (k with k≥1) nearest neighbor (kNN) classification in which squared Euclidean distances (SEDs) are mapped into the clock domain for realizing high search speed and energy efficiency. The minimal SED searching is carried out by weighted frequency dividers that drastically reduce the normally exponential increase of the worst-case search-clock number with the bit width of vector components to only a linear increase. This also results in low power dissipation and high area-efficiency in comparison to the traditional method using large numbers of adders and comparators. The kNN classifier determines the class of an unknown input sample with a majority decision among the k nearest reference samples. The required majority-decision circuit is integrated with the clock-mapping-based minimal-SED searching architecture and proceeds with the classification immediately after identification of each of the k nearest references. A test chip in 180 nm CMOS technology, which can process 8 dimensions of 32 reference vectors in parallel, achieves low power dissipation of 40.32 mW (at 51.21 MHz clock frequency and 1.8 V supply voltage). Significantly, the distance search circuit consumes only 5.99 mW. Feature vectors with different dimensionality up to 2048 dimensions can be handled by the designed coprocessor due to a dimension extension circuit, enabling large flexibility for usage in different application.

Publication: IEICE TRANSACTIONS on Electronics Vol.E99-C No.3 pp.397-403

Publication Date: 2016/03/01

Publicized

Online ISSN: 1745-1353

DOI: 10.1587/transele.E99.C.397

Type of Manuscript: PAPER

Category: Electronic Circuits

Authors

Fengwei AN
  Hiroshima Unversity
Lei CHEN
  Hiroshima Unversity
Toshinobu AKAZAWA
  Hiroshima Unversity
Shogo YAMASAKI
  Hiroshima Unversity
Hans Jürgen MATTAUSCH
  Hiroshima Unversity

Keyword

k nearest neighbor classifier, minimal Euclidean distance search, clock-mapping concept, weighted frequency dividers, majority circuit

Cite this

Copy

Fengwei AN, Lei CHEN, Toshinobu AKAZAWA, Shogo YAMASAKI, Hans Jürgen MATTAUSCH, "k Nearest Neighbor Classification Coprocessor with Weighted Clock-Mapping-Based Searching" in IEICE TRANSACTIONS on Electronics, vol. E99-C, no. 3, pp. 397-403, March 2016, doi: 10.1587/transele.E99.C.397.
Abstract: Nearest-neighbor-search classifiers are attractive but they have high intrinsic computational demands which limit their practical application. In this paper, we propose a coprocessor for k (k with k≥1) nearest neighbor (kNN) classification in which squared Euclidean distances (SEDs) are mapped into the clock domain for realizing high search speed and energy efficiency. The minimal SED searching is carried out by weighted frequency dividers that drastically reduce the normally exponential increase of the worst-case search-clock number with the bit width of vector components to only a linear increase. This also results in low power dissipation and high area-efficiency in comparison to the traditional method using large numbers of adders and comparators. The kNN classifier determines the class of an unknown input sample with a majority decision among the k nearest reference samples. The required majority-decision circuit is integrated with the clock-mapping-based minimal-SED searching architecture and proceeds with the classification immediately after identification of each of the k nearest references. A test chip in 180 nm CMOS technology, which can process 8 dimensions of 32 reference vectors in parallel, achieves low power dissipation of 40.32 mW (at 51.21 MHz clock frequency and 1.8 V supply voltage). Significantly, the distance search circuit consumes only 5.99 mW. Feature vectors with different dimensionality up to 2048 dimensions can be handled by the designed coprocessor due to a dimension extension circuit, enabling large flexibility for usage in different application.
URL: https://globals.ieice.org/en_transactions/electronics/10.1587/transele.E99.C.397/_p

Copy

@ARTICLE{e99-c_3_397,
author={Fengwei AN, Lei CHEN, Toshinobu AKAZAWA, Shogo YAMASAKI, Hans Jürgen MATTAUSCH, },
journal={IEICE TRANSACTIONS on Electronics},
title={k Nearest Neighbor Classification Coprocessor with Weighted Clock-Mapping-Based Searching},
year={2016},
volume={E99-C},
number={3},
pages={397-403},
abstract={Nearest-neighbor-search classifiers are attractive but they have high intrinsic computational demands which limit their practical application. In this paper, we propose a coprocessor for k (k with k≥1) nearest neighbor (kNN) classification in which squared Euclidean distances (SEDs) are mapped into the clock domain for realizing high search speed and energy efficiency. The minimal SED searching is carried out by weighted frequency dividers that drastically reduce the normally exponential increase of the worst-case search-clock number with the bit width of vector components to only a linear increase. This also results in low power dissipation and high area-efficiency in comparison to the traditional method using large numbers of adders and comparators. The kNN classifier determines the class of an unknown input sample with a majority decision among the k nearest reference samples. The required majority-decision circuit is integrated with the clock-mapping-based minimal-SED searching architecture and proceeds with the classification immediately after identification of each of the k nearest references. A test chip in 180 nm CMOS technology, which can process 8 dimensions of 32 reference vectors in parallel, achieves low power dissipation of 40.32 mW (at 51.21 MHz clock frequency and 1.8 V supply voltage). Significantly, the distance search circuit consumes only 5.99 mW. Feature vectors with different dimensionality up to 2048 dimensions can be handled by the designed coprocessor due to a dimension extension circuit, enabling large flexibility for usage in different application.},
keywords={},
doi={10.1587/transele.E99.C.397},
ISSN={1745-1353},
month={March},}

Copy

TY - JOUR
TI - k Nearest Neighbor Classification Coprocessor with Weighted Clock-Mapping-Based Searching
T2 - IEICE TRANSACTIONS on Electronics
SP - 397
EP - 403
AU - Fengwei AN
AU - Lei CHEN
AU - Toshinobu AKAZAWA
AU - Shogo YAMASAKI
AU - Hans Jürgen MATTAUSCH
PY - 2016
DO - 10.1587/transele.E99.C.397
JO - IEICE TRANSACTIONS on Electronics
SN - 1745-1353
VL - E99-C
IS - 3
JA - IEICE TRANSACTIONS on Electronics
Y1 - March 2016
AB - Nearest-neighbor-search classifiers are attractive but they have high intrinsic computational demands which limit their practical application. In this paper, we propose a coprocessor for k (k with k≥1) nearest neighbor (kNN) classification in which squared Euclidean distances (SEDs) are mapped into the clock domain for realizing high search speed and energy efficiency. The minimal SED searching is carried out by weighted frequency dividers that drastically reduce the normally exponential increase of the worst-case search-clock number with the bit width of vector components to only a linear increase. This also results in low power dissipation and high area-efficiency in comparison to the traditional method using large numbers of adders and comparators. The kNN classifier determines the class of an unknown input sample with a majority decision among the k nearest reference samples. The required majority-decision circuit is integrated with the clock-mapping-based minimal-SED searching architecture and proceeds with the classification immediately after identification of each of the k nearest references. A test chip in 180 nm CMOS technology, which can process 8 dimensions of 32 reference vectors in parallel, achieves low power dissipation of 40.32 mW (at 51.21 MHz clock frequency and 1.8 V supply voltage). Significantly, the distance search circuit consumes only 5.99 mW. Feature vectors with different dimensionality up to 2048 dimensions can be handled by the designed coprocessor due to a dimension extension circuit, enabling large flexibility for usage in different application.
ER -