IEICE TRANSACTIONS on Electronics
k Nearest Neighbor Classification Coprocessor with Weighted Clock-Mapping-Based Searching
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
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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://global.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 -
English
