Combinatorial algorithms in the approximate computing paradigm

Abstract

Data-intensive computing has led to the emergence of data centers with massive processor counts and main memory sizes. However, the demand for shared resources has surpassed their capacity, resulting in increased costs and limited access. Commodity hardware, although accessible, has limited computational resources. This poses a challenge when performing computationally intensive tasks with large amounts of data on systems with restricted memory. To address these issues, Approximate Computing offers a solution by allowing selective solution approximation, leading to improved resource efficiency. This dissertation focuses on the trade-off between output quality and computational resource usage in sorting and searching problems. It introduces the concept of Approximate Sorting, which aims to reduce resource usage while maintaining an accepted level of sorting quality. Quality metrics are defined to assess the ”sortedness” of approximately sorted arrays. The dissertation also proposes a general framework for incorporating approximate computing into sorting algorithms, presenting an algorithm for approximate sorting with guaranteed upper bounds. The algorithms operate under a constraint on the number of comparisons performed. The dissertation continues to explore searching algorithms, specifically binary search algorithms on approximately sorted arrays. It addresses cases where metrics are given for the input array and cases where metrics are not available. Efficient and optimal algorithms are developed for multidimensional range searches and catalog searches on approximately sorted input. The dissertation further proposes algorithms that analyze patterns in input order to optimize sorting. These algorithms identify underlying patterns and sequences, facilitating faster sorting approaches. Additionally, the dissertation discusses the growing popularity of approximate computing in the field of High-Performance Computing (HPC). It presents a novel approach to comparison-based sorting by incorporating parallel approximate computing. The dissertation also proposes algorithms for various queries on approximately sorted arrays, such as determining the rank or position of an element. The time complexity of these querying algorithms is proportional to the input metric. The dissertation concludes by emphasizing the wide range of applications for sorting and searching algorithms. In the context of packet classification in router buffers, approximate sorting offers advantages by reducing the time-consuming sorting step. By capping the number of comparisons, approximate sorting becomes a practical solution for efficiently handling the large volume of incoming packets. This dissertation contributes to the field of approximate computing by addressing resource limitations and cost issues in data-intensive computing. It provides insights into approximate sorting and searching algorithms, and their application in various domains, offering a valuable contribution to the advancement of efficient, scalable, and accessible data processing.