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

approximate computing sorting networks genetic programming

 Přestože hardwarové řadicí obvody jsou velmi výkonné, jejich plocha na čipu výrazně roste s přibývajícím počtem vstupů. V práci je představena škálovatelná metoda konstrukce řadicích sítí, která umožňuje vytvářet výkonné a nízkopříkonově implementace. Navržený přístup využívá toho, že řada běžných aplikací toleruje drobné chyby na výstupu. Metoda je založena na  rekurzivní konstrukci velkých sítí s využitím malých instancí přibližných řadicích sítí. Tento proces je konfigurovatelný a umožňuje  získat vyvážený poměr mezi příkonem a přesností. Pro analýzu  přesnosti řadicích sítí jsme navrhli tři metriky umožňující exaktně stanovit chybu nezávislé na rozložení vstupních dat. Pomocí navržené metody byly získány implementace pro ASIC a FPGA obvody, které zabírají méně plochy na čipu a spotřebovávají méně energie. Například 20% redukce příkonu byla získána povolením malé chyby v 256-vstupé řadičce. Odchylka byla maximálně 2 pozice v 99 % případů. Navíc bylo prokázáno, že maximální odchylka byla o 6 pozic.