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

Created by W.Langdon from gp-bibliography.bib Revision:1.3872

  author =       "Vojtech Mrazek and Zdenek Vasicek",
  title =        "Automatic Design of Arbitrary-Size Approximate Sorting
                 Networks with Error Guarantee",
  booktitle =    "International Workshop on Power And Timing Modeling,
                 Optimization and Simulation",
  year =         "2016",
  editor =       "Ricardo Reis and Aida Todri-Sanial",
  address =      "Bremen, Germany",
  month =        sep # " 21-23",
  keywords =     "genetic algorithms, genetic programming, cartesian
                 genetic programming, approximate computing, sorting
  URL =          "",
  size =         "8 pages",
  abstract =     "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 analyse 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, 20percent
                 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 99percent. In addition to
                 that, it is guaranteed that the worst-case difference
                 is equal to 6.",
  notes =        "


Genetic Programming entries for Vojtech Mrazek Zdenek Vasicek