TY - JOUR
T1 - A high-performance bidirectional architecture for the quasi-comparison-free sorting algorithm
AU - Chen, Wei Ting
AU - Chen, Ren Der
AU - Chen, Pei Yin
AU - Hsiao, Yu Che
N1 - Funding Information:
Manuscript received June 26, 2020; revised October 6, 2020 and December 2, 2020; accepted December 29, 2020. Date of publication January 14, 2021; date of current version March 8, 2021. This work was supported in part by the NOVATEK Fellowship and in part by the Ministry of Science and Technology of Taiwan under Grant MOST 109-2622-8-006-018-TA. This article was recommended by Associate Editor J.-Y. Kim. (Corresponding author: Pei-Yin Chen.) Wei-Ting Chen, Pei-Yin Chen, and Yu-Che Hsiao are with the Digital Integrated Circuit Design Laboratory, Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan 70101, Taiwan (e-mail: [email protected]).
Publisher Copyright:
© 2004-2012 IEEE.
PY - 2021/4
Y1 - 2021/4
N2 - This paper proposes a high-performance bidirectional architecture for the quasi-comparison-free sorting algorithm. Our architecture improves the performance of the conventional unidirectional architecture by reducing the total number of sorting cycles via bidirectional sorting along with two auxiliary methods. Bidirectional sorting allows the sorting tasks to be conducted concurrently in the high-and low-index parts of our architecture. The first auxiliary method is boundary finding, which shortens the range for index searching by finding the boundaries of the range. The second auxiliary method is queue storing, which stores each useful index in a queue in advance to reduce the number of miss cycles during index searching. The performance of our architecture highly depends on the distribution of input data. For each set of input data to be sorted, five Gaussian distributions of the input data and four standard derivations for each distribution were adopted in our experiments. The results show that at the expense of some additional area cost, the number of sorting cycles and the energy consumption are significantly reduced by our method.
AB - This paper proposes a high-performance bidirectional architecture for the quasi-comparison-free sorting algorithm. Our architecture improves the performance of the conventional unidirectional architecture by reducing the total number of sorting cycles via bidirectional sorting along with two auxiliary methods. Bidirectional sorting allows the sorting tasks to be conducted concurrently in the high-and low-index parts of our architecture. The first auxiliary method is boundary finding, which shortens the range for index searching by finding the boundaries of the range. The second auxiliary method is queue storing, which stores each useful index in a queue in advance to reduce the number of miss cycles during index searching. The performance of our architecture highly depends on the distribution of input data. For each set of input data to be sorted, five Gaussian distributions of the input data and four standard derivations for each distribution were adopted in our experiments. The results show that at the expense of some additional area cost, the number of sorting cycles and the energy consumption are significantly reduced by our method.
UR - http://www.scopus.com/inward/record.url?scp=85099733813&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85099733813&partnerID=8YFLogxK
U2 - 10.1109/TCSI.2020.3048955
DO - 10.1109/TCSI.2020.3048955
M3 - Article
AN - SCOPUS:85099733813
SN - 1549-8328
VL - 68
SP - 1493
EP - 1506
JO - IEEE Transactions on Circuits and Systems I: Regular Papers
JF - IEEE Transactions on Circuits and Systems I: Regular Papers
IS - 4
M1 - 9324938
ER -