Automatic Design of Arbitrary-Size Approximate Sorting Networks with Error Guarantee

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F16%3APU122829" target="_blank" >RIV/00216305:26230/16:PU122829 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.fit.vutbr.cz/research/pubs/all.php?id=11175" target="_blank" >http://www.fit.vutbr.cz/research/pubs/all.php?id=11175</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/PATMOS.2016.7833691" target="_blank" >10.1109/PATMOS.2016.7833691</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Automatic Design of Arbitrary-Size Approximate Sorting Networks with Error Guarantee

Popis výsledku v původním jazyce

Despite the fact that hardware sorters offer great performance, they become expensive as the number of inputs increases. In order to address the problem of high-performance and power-efficient computing, we propose a scalable method for construction of power-efficient sorting networks suitable for hardware implementation. The proposed approach exploits the error resilience which is present in many real-world applications such as digital signal processing, biological computing and large-scale scientific computing. The method is based on recursive construction of large sorting networks using smaller instances of approximate sorting networks. The design process is tunable and enables to achieve desired tradeoffs between the accuracy and power consumption or implementation cost. A search-based design method is used to obtain approximate sorting networks. To measure and analyze the accuracy of approximate networks, three data-independent quality metrics are proposed. Namely, guarantee of error probability, worst-case error and error distribution are discussed. A significant improvement in the implementation cost and power consumption was obtained. For example, 20% reduction in power consumption was achieved by introducing a small error in 256-input sorter. The difference in rank is proved to be not worse than 2 with probability at least 99%. In addition to that, it is guaranteed that the worst-case difference is equal to 6.

Název v anglickém jazyce

Automatic Design of Arbitrary-Size Approximate Sorting Networks with Error Guarantee

Popis výsledku anglicky

Despite the fact that hardware sorters offer great performance, they become expensive as the number of inputs increases. In order to address the problem of high-performance and power-efficient computing, we propose a scalable method for construction of power-efficient sorting networks suitable for hardware implementation. The proposed approach exploits the error resilience which is present in many real-world applications such as digital signal processing, biological computing and large-scale scientific computing. The method is based on recursive construction of large sorting networks using smaller instances of approximate sorting networks. The design process is tunable and enables to achieve desired tradeoffs between the accuracy and power consumption or implementation cost. A search-based design method is used to obtain approximate sorting networks. To measure and analyze the accuracy of approximate networks, three data-independent quality metrics are proposed. Namely, guarantee of error probability, worst-case error and error distribution are discussed. A significant improvement in the implementation cost and power consumption was obtained. For example, 20% reduction in power consumption was achieved by introducing a small error in 256-input sorter. The difference in rank is proved to be not worse than 2 with probability at least 99%. In addition to that, it is guaranteed that the worst-case difference is equal to 6.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA16-17538S" target="_blank" >GA16-17538S: Přibližná ekvivalence pro aproximativní počítání</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Power and Timing Modeling, Optimization and Simulation (PATMOS), 2016 26rd International Workshop on

ISBN

978-1-5090-0733-2

ISSN

—

e-ISSN

—

Počet stran výsledku

8

Strana od-do

221-228

Název nakladatele

Institute of Electrical and Electronics Engineers

Místo vydání

Bremen

Místo konání akce

Bremen

Datum konání akce

20. 9. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000401809900038