Error Analysis of the Square Root Operation for the Purpose of Precision Tuning: a Case Study on K-means

Abstract : In this paper, we propose an analytical approach to study the impact of floating point (FLP) precision variation on the square root operation, in terms of computational accuracy and performance gain. We estimate the round-off error resulting from reduced precision. We also inspect the Newton Raphson algorithm used to approximate the square root in order to bound the error caused by algorithmic deviation. Consequently, the implementation of the square root can be optimized by fittingly adjusting its number of iterations with respect to any given FLP precision specification, without the need for long simulation times. We evaluate our error analysis of the square root operation as part of approximating a classic data clustering algorithm known as K-means, for the purpose of reducing its energy footprint. We compare the resulting inexact K-means to its exact counterpart, in the context of color quantization, in terms of energy gain and quality of the output. The experimental results show that energy savings could be achieved without penalizing the quality of the output (e.g., up to 41.87% of energy gain for an output quality, measured using structural similarity, within a range of [0.95,1]).
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-02183945
Contributor : Olivier Sentieys <>
Submitted on : Monday, July 15, 2019 - 5:00:12 PM
Last modification on : Wednesday, January 8, 2020 - 11:48:55 AM

File

ASAP_kmeans_final.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02183945, version 1

Citation

Oumaima Matoussi, Yves Durand, Olivier Sentieys, Anca Molnos. Error Analysis of the Square Root Operation for the Purpose of Precision Tuning: a Case Study on K-means. ASAP 2019 - 30th IEEE International Conference on Application-specific Systems, Architectures and Processors, Jul 2019, New York, United States. pp.1-8. ⟨hal-02183945⟩

Share

Metrics

Record views

296

Files downloads

585