Low Cost Sorting Network Circuits using Unary Processing

IP Status: US Patent Issued: 11,475,288

Applications

• All applications of sorting such as data mining, databases, ATM and communication switching, scientific computing, scheduling, artificial intelligence and robotics, image, video and signal processing.

Technology Overview

This technology proposes a novel area- and power-efficient approach for hardware implementation of sorting network circuits based on unary processing. Sorting is a common task in a wide range of applications from signal and image processing to switching systems. For applications that require high performance, sorting is often performed in hardware. Hardware cost and power consumption are the dominant concerns. The usual approach is to wire up a network of compare-and-swap units in a configuration called a Batcher (or Bitonic) network. In the proposed implementation, input data is encoded as unary serial bit-streams, with values represented by the fraction of 1’s in a stream of 0’s and 1’s. Synthesis results of complete sorting networks show up to 92% area and power saving compared to the conventional binary implementations, however, the latency increases. To mitigate the increased latency, this technology uses a novel time-encoding of data. The result is a low-cost, energy-efficient implementation with only a slight accuracy loss.

Phase of Development

TRL: 3-4
Theoretical foundation developed, synthesis results of pipelined and non-pipelined completely sorting networks for 8, 16, 32, 64, 128, and 256 data inputs have validated the idea.

Desired Partnerships

This technology is now available for:

• License
• Sponsored research
• Co-development

Please contact our office to share your business’ needs and learn more.

Researchers

• Marc Riedel Associate Professor, Department of Electrical and Computer Engineering
• Kia Bazargan Associate Professor, Department of Electrical and Computer Engineering