IEEE Consumer Electronics Magazine - May/June 2022 - 89

Figure 2. (a) Structure of the dual CAS cell. (b)
Structure of BSN and OESN. (c) Architecture of
DPSN to sort four input records using OESN network.
previous techniques. Hence, we claim ULPSorter
is suitable for embedded applications.
RELATED WORK
Najafi et al.10 have proposed an innovative
sorting method using a unary processing
method. The unary processing effectively
reduces the number of resources utilized in a
sorting network. This method encodes every
input data as a stream of 0/1 b. The comparator
unit of the unary sorter includes only one AND
date and one OR gate.
H-Sort15 is proposed to overcome the main
limitation of the basic unary sorter. In the original
unary sort, the performance is declined
sharply by increasing the data-width of the input
records. H-sort overcomes this issue by utilizing
the parallelization technique.
Sklyarov and Skliarova18 utilize two sequentially
reusable vertical lines of comparators in
even-odd transition networks to sort input
records with less resource consumption. They
show that in their proposed sorting network, a
pipeline can be constructed in the form of
increasing the number of vertical lines to have
tradeoff between the performance and resource
consumption. This technique is called reusable
sorting network (RSN)18 in our article to use it in
the " Experimental Results and Analysis " section.
We introduced the real-time hardware sorter
(RTHS)4 based on the multidimensional sorting
network (MDSN) algorithm that is able to sort a
2-D matrix of input records. In conventional sorting
networks, increasing the number of pipeline
stages (i.e., improving the operating frequency)
leads to more resource consumption. RTHS
overcomes this issue by utilizing smaller sorting
networks as basic building blocks. In
May/June 2022
comparison to RTHS,4 we proposed a basic
3D-Sorter in the work by Norollah et al.17 to
reduce required resources for an area and
power constrained application. Now, in comparisonto3D-Sorter,17
we introduce a novel
ultralow power sorter in this article to reduce
required resources and power consumption
more significant than 3D-Sorter17 and previous
state-of-the-art techniques.
ULP-SORTER ARCHITECTURE
Principle of MDSA
The MDSA4 converts a one-dimensional input
array into an n-dimensional matrix (denoted as
nD-MDSA); then, it sorts the records of the
matrix. A large array is effectively converted into
several smaller arrays in the shape of a matrix,
in parallel, by this algorithm. We have discussed
the detailed description of 3D-MDSA in the work
by Norollah et al.17
The MDSA algorithm has following five main
advantages that motivate us to use it in ULPSorter.
1)
The minimum and maximum records are
obtained with just two phases in 3D-MDSA.
2) MDSA assists us to transfer input array
records to 3-D matrix in order to improve the
parallel processing.
3) MDSA reduces the size of the bitonic sorter.
4) MDSA simplifies the hardware implementation
algorithm.
5) MDSA reduces the needed resources in comparison
with other high-performance
methods.
Dual Compare-and-Swap (CAS) Cell
A CAS cell is the smallest component of a
sorter than encompasses of a W=2 bit comparator
and 2W 2:1 multiplexers. Two W-bit
records are given to a CAS cell, and then, the
larger and smaller records are sent to the output
lines of the CAS cell either in the ascending or
descending order. In the MDSA structure, changing
the format of sorting from ascending to
descending, and vice versa is necessary. Hence,
a dual CAS cell should have an ability to change
the sorting order. Figure 2(a) shows the structure
of a dual CAS cell. When the " Direction "
89
IEEE Consumer Electronics Magazine - May/June 2022

Table of Contents for the Digital Edition of IEEE Consumer Electronics Magazine - May/June 2022
