RTHS

KO | EN

gitlite — search

#javascript #python #hacktoberfest #react #ai #typescript #llm #go #golang #android #machine-learning #rust #deep-learning #linux

★ 20 Open GitHub ↗

Real-Time Hardware Sorter, Using A Multi-Dimensional Sorting Algorithm

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# RTHS - Real Time Hardware Sorter

Welcome to the RTHS, hardware description of Real Time Hardware Sorter.

## Description

We have developed a groundbreaking multi-dimensional sorting algorithm and accompanying FPGA-based architecture that significantly reduces the required resources and increases memory efficiency. This method has minimal negative impact on execution time in the FPGA chip, even as the number of input records increases. As such, our solution presents a viable alternative to other sorting techniques.

In addition to its primary use case, our proposed method can also be applied in two other areas. Firstly, it can be utilized to implement Min/Max queues, allowing for the quick identification of minimum and maximum records. Secondly, it can be used to find the largest and smallest records in big data stream processing. Through the sorting process, our method provides continuous access to the largest and smallest records at any given time.

The RTHS hardware sorter utilizes a multidimensional sorting algorithm that combines parallel and pipeline processing to achieve optimal performance and low execution time. To begin the sorting process, the input records are grouped based on their values in different dimensions. These groups are then sorted in parallel, and their results are merged to produce the final sorted output. Furthermore, the RTHS design incorporates several optimizations to enhance performance, such as using hardware-friendly data structures and implementing a dynamic allocation scheme for intermediate storage. These optimizations result in a highly efficient and cost-effective hardware sorter that is ideal for real-time applications.

This project provides a simplified hardware description of the sorter, based on the RTHS design. It is capable of sorting up to 16 input records, organized in a 4 x 4 matrix. **Please note that this project is intended for academic use only.**

**If you use RTHS design in your research, we would appreciate the following citation in any publications to which it has contributed:**

A. Norollah, D. Derafshi, H. Beitollahi and M. Fazeli, "RTHS: A Low-Cost High-Performance Real-Time Hardware Sorter, Using a Multidimensional Sorting Algorithm," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems.
doi: [10.1109/TVLSI.2019.2912554](https://doi.org/10.1109/TVLSI.2019.2912554)

> Get in touch with me by [a.norollah.official@gmail.com](mailto:a.norollah.official@gmail.com)

## Application

The parameters that determine the width of the data and the number of records can be adjusted using the "N" and "W" parameters, which can range from 16 to 256 and 16 to 128 bits, respectively. These values can be modified based on the resources available on the target FPGA chip, and can be found in the top module of the design.

However, it should be noted that changing the "N" parameter will alter the structure of the Bitonic Sorting Network (BSN), necessitating an upgrade to this component as well.

The sorting process employed by this hardware is similar to the multidimensional sorting algorithm described in our paper. We have provided the necessary hardware modules to implement this algorithm, some of which are listed in the table below:

| Files                | Description                                                                   | Documentation                                      |
| -------------------- | ----------------------------------------------------------------------------- | -------------------------------------------------- |
| 0_REG.v              | the registers required in each layer in all design                            | [0_REG.md](Doc/0_REG.md)                           |
| 1_Comparator.v       | comparator                                                                    | [1_Comparator.md](Doc/1_Comparator.md)             |
| 1_BitonicNetwork.v   | 4-input records BSN                                                           | [1_BitonicNetwork.md](Doc/1_BitonicNetwork.md)     |
| 1_BitonicPreStage.v  | prestage of BSN                                                               | [1_BitonicPreStage.md](Doc/1_BitonicPreStage.md)   |
| 1_BitonicPosStage1.v | posstage of BSN, level 1                                                      | [1_BitonicPosStage1.md](Doc/1_BitonicPosStage1.md) |
| 1_BitonicPosStage2.v | posstage of BSN, level 2                                                      | [1_BitonicPosStage2.md](Doc/1_BitonicPosStage2.md) |
| 1_BitonicPosStage3.v | posstage of BSN, level 3                                                      | [1_BitonicPosStage3.md](Doc/1_BitonicPosStage3.md) |
| 2_a_sorter.v         | the Real-Time Hardware Sorter (RTHS) design for sorting 4 x 4 matrix records. | [2_a_sorter.md](Doc/2_a_sorter.md)                 |
| 2_b_switch.v         | the implicit switch design                                                    | [2_b_switch.md](Doc/2_b_switch.md)                 |
| 2_c_Controller.v     | the control unit                                                              | [2_c_Controller.md](Doc/2_c_Controller.md)         |
| TB_BitonicNetwork.v  | testbench for BSN                                                             | [TB_BitonicNetwork.md](Doc/TB_BitonicNetwork.md)   |
| TB_Sorter.v          | testbench for the RTHS design                                                 | [TB_Sorter.md](Doc/TB_Sorter.md)                   |
| Input.hex            | 16 test records with 16 data width                                            | -                                                  |

## Documentation

Comprehensive documentation for each module is available in the [`Doc/`](Doc/) directory:

- **[Register Module](Doc/0_REG.md)** - Basic register bank with async reset
- **[Comparator](Doc/1_Comparator.md)** - Fundamental sorting element
- **[Bitonic Network](Doc/1_BitonicNetwork.md)** - Complete bitonic sorting network
- **[Bitonic Pre-Stage](Doc/1_BitonicPreStage.md)** - Butterfly pattern comparator stage
- **[Bitonic Post-Stage 1](Doc/1_BitonicPosStage1.md)** - 2-element sorting stage
- **[Bitonic Post-Stage 2](Doc/1_BitonicPosStage2.md)** - 4-element sorting stage
- **[Bitonic Post-Stage 3](Doc/1_BitonicPosStage3.md)** - 8-element sorting stage
- **[Main Sorter](Doc/2_a_sorter.md)** - Top-level multi-dimensional sorter
- **[Switch Module](Doc/2_b_switch.md)** - Matrix transpose operation
- **[Control Unit](Doc/2_c_Controller.md)** - State machine for sorting sequence
- **[Bitonic Network Testbench](Doc/TB_BitonicNetwork.md)** - Testbench for BSN
- **[Sorter Testbench](Doc/TB_Sorter.md)** - Comprehensive testbench with file I/O

Each documentation file includes:

- Module overview and interface
- Detailed functionality description
- Usage examples
- Implementation details
- Related modules and relationships
- Performance characteristics

## Other properties

Category: Sorting Network (SN)

Language: Verilog

Development status: Stable

Manual: Included

Additional info: Design done, FPGA proven

License: GPL

RTHS

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README