Sorting operations are considered to be a significant part of any computer system and are widely used in many applications. In applications where sorting has to be efficiently accomplished (i.e., inO(1) time) on small-sized entries, hardware accelerators, such as ASICs, FPGAs, or GPUs, are used to speed up the sorting operations. In the literature, the bitonic sort algorithm (or variants thereof) is still considered to be the most commonly used approach in many hardware sort implementations for decades. However, the time complexity of the bitonic sort isO((log(n))2) for sortingnelements, which does not satisfy the constant-time constraint we demand for our setting. In this paper, we proposecompetition-style sorting networks(CSNs), a framework for designing hardware-based competition-style class of sorting networks that captures all forms of two-stage sorting networks where the first stage (competition) consists of pairwise comparisons and the second stage (evaluation) ranks the entries and sorts them. To illustrate the utility of this framework, we develop and test one instance of this design, called the Competition Sort Algorithm (CSA), which has a time complexity ofO(1), and specifically, one clock cycle. We implemented and tested CSA on both an Intel Cyclone V FPGA and the NVIDIA Quadro T1000 GPU then measured itsgain, which combines the trade-offs between the relative speedup and the relative area increase, against the bitonic sort. Our results show that the CSA achieves a significant gain of up to 11.01× on the FPGA and a relative speedup of up to 3.32× on the GPU. We also compare the area, power, and latency of CSA with the bitonic sort algorithm on the FPGA.

Modern microprocessors contain several special function units (SFUs) such as specialized arithmetic units, cryptographic processors, etc. In recent times, applications such as cloud computing, web-based search engines, and network applications are widely used, and place new demands on the microprocessor. Hashing is a key algorithm that is extensively used in such applications. Hashing can reduce the complexity of search and lookup from O(N) to O(N/n), where n bins are used. Hashing is typically performed in software. Thus, implementing a hardware-based hash unit on a modern microprocessor would potentially increase performance significantly. In this article, we propose a novel hardware hash unit (HU) design for use in modern microprocessors, at the microarchitecture level and at the circuit level. First, we present the design of the HU at the microarchitecture level. We simulate the HU to compare its performance with a software-based hash implementation. We demonstrate a significant speedup (up to 15×) for the HU. Furthermore, the performance scales elegantly with increasing database size and application diversity, without increasing the hardware cost. Second, we present the circuit design of the HU for use in modern microprocessors, using a 45nm technology. Our proposed hardware hash unit is based on the use of a content-addressable memory (CAM) to implement each bin of the hash table. We simulate the HU circuit and compare it with a traditional CAM design. We demonstrate an average power reduction of 5.48× using the HU over the traditional CAM. Also, we show that the HU can operate at a maximum frequency of 1.39 GHz (after accounting for process, voltage and temperature (PVT) variations and accounting for wiring parasitics). Furthermore, we present the delay, power and area trade-offs of the HU design with varying hash table sizes.

Data compression is a key aspect of computing applications such as online search engines, cloud computing and big data computing. In recent times, with the increasing popularity of remote and cloud-based computation, compression is becoming more important. Reducing the size of a data object in this context would not only reduce the transfer time, but also the amount of data transferred. The key figures of merit of a data compression scheme are its compression ratio and its compression, decompression and search (lookup) speeds. Traditional compression techniques achieve high compression ratios, but require decompression before a lookup can be performed, thus increasing the lookup time. In this paper, we propose an incremental compression technique for plain-text data objects (PIC), that uses variable length encoding to compress data. The dictionary of possible words is sorted based on the statistical frequency of the words, and the words are encoded using the variable length code-words. Words that are not in the dictionary are handled as well. The driving motivation of our technique is to perform significantly faster lookups without the need to decompress the compressed data object. PIC also facilitates string operations (such as concatenation, insertion, deletion and lookup-and-replacement) on compressed text without the need of decompression. In this manner, these string operations are incrementally compressed, resulting in greatly improved efficiency. We implement our technique in C++, and compare PIC with industry standard tools like lz4, gzip and bzip2 in terms of compression ratio, lookup speed, and lookup-and-replace time. PIC is about 8.84×, 100.17× and 174.25× faster as compared to lz4, gzip and bzip2, respectively, when the data is looked-up, and restored into a compressed format. A lookup-and-replace operation on a PIC-compressed file is shown to be 2.83× faster than a plain-text file. We formally prove that our method does not produce any false positive or false negative results during a lookup, and also prove that PIC is amenable to file concatenation. We have also implemented a parallel version of PIC. Compression, decompression and search times are 2.24×, 1.51× and 5× faster when eight threads are used instead of one. We also demonstrate that the parallel version of PIC scales better compared to commonly available tools for parallel compression. PIC opens the possibility of performing all string manipulations on a PIC-compressed file, yielding about 2× compression over plain text, and 1-2 orders of magnitude faster operations than traditional compression schemes.

Modern microprocessors contain several Special Function Units (SFUs) such as specialized arithmetic units, cryptographic processors, etc. In recent times, applications such as cloud computing, web-based search engines, and network applications are widely used, and place new demands on the microprocessor. Hashing is a key algorithm that is extensively used in such applications. Hashing is typically performed in software. Thus, implementing a hardware-based hash unit on a modern microprocessor would potentially increase performance significantly. In this paper, we present the circuit design for a hardware hash unit (HU) for modern microprocessors, using a 45nm technology. Our proposed hardware hash unit is based on the use of a CAM to implement each bin of the hash function. We simulate the HU circuit and compare it with a traditional CAM design. We demonstrate an average power reduction of 5.48x using the HU over the traditional CAM. Also, we show that the HU can operate at a maximum frequency of 1.39 GHz (after accounting for process, voltage and temperature (PVT) variations and accounting for wiring parasitics). Furthermore, we present the delay, power and area trade-offs of the HU design with varying hash table sizes.

In recent times, applications like web-based search, antivirus scanners, cloud computing, social media applications, and network applications are extremely common. The hash table is a heavily used data structure in such applications. Modern microprocessors have several special function units (SFUs) such as a floating point unit, a memory management unit, and a cryptography unit. However, hashing is typically performed in software, which reduces the performance of such applications. In this paper, we propose an FPGA-based implementation of a hash unit (a hash function and a hash table) in an FPGA. The FPGA-based hash unit is implemented as a coprocessor for a CPU. The CPU and the FPGA communicate through a PCI Express (PCIe) interface. The hash table in our hash unit is implemented as a content-addressable memory (CAM), to enhance the speed of hash operations. The hash unit (HU) coprocessor is tested in the context of virus checking application, when the hashing operation only requires membership checks. Our HU can be used in other hashing applications as well; we use virus checking as a representative application. Hashing operations are performed in a batch on the FPGA, to provide better utilization of the PCIe bus. We demonstrate a significant performance of up to 7.3× for our FPGAbased hash unit implementation compared to a software-based hashing implementation. This speedup is for the entire virus checking application (not just the hash lookup portion of the virus checking application).

Historically, microprocessor instructions were designed in order to obtain high performance on integer and floating point computations. Today's applications, however, demand high performance for cloud computing, web-based search engines, network applications, and social media tasks. Such software applications involve an extensive use of hashing in their computation. Hashing can reduce the complexity of search and lookup from O(n) to O(n/k), where k bins are used. In modern microprocessors hashing is done in software. In this paper, we propose a novel hardware hash unit design for use in modern microprocessors. We present the design of the Hash Unit (HU) at the micro-architecture level. We simulate the new HU to compare its performance with a software-based hash implementation. We demonstrate a significant speed-up (up to 12×) for the HU. Furthermore, the performance scales elegantly with increasing database size and application diversity, without increasing the hardware cost.