Use of Carry Chain Logic and Design System Extensions to Construct Significantly Faster and Larger Single-Stage N-Sorters and N-Filters
The authors’ recently published design system for the creation of single-stage N-sorter/N-filter sorting devices, which were implemented using a particular example hardware block, is here expanded and applied to a second hardware type, FPGA carry chain logic. Although several researchers...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2022-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9843991/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841554021681201152 |
|---|---|
| author | Robert B. Kent Marios S. Pattichis |
| author_facet | Robert B. Kent Marios S. Pattichis |
| author_sort | Robert B. Kent |
| collection | DOAJ |
| description | The authors’ recently published design system for the creation of single-stage N-sorter/N-filter sorting devices, which were implemented using a particular example hardware block, is here expanded and applied to a second hardware type, FPGA carry chain logic. Although several researchers have published applications which use FPGA carry chain logic, most do not use carry chain logic as is done here, and none of the applications target sorting devices. Prior to the introduction of the single-stage N-sorter/N-filter design system, the fastest state-of-the-art hardware devices which sorted more than 2 input values were multistage sorting networks, in which the sorting process is performed by one or more 2-sorters and 2-max/2-min filters, operating in each sequential stage. Using the authors’ original design system, single-stage N-sorters and N-filters were shown to be faster than the fastest comparable sorting networks when sorting 3 to 9 inputs. Here, product term splitting and a new Sum-of-Products output multiplexer equation are added to the design system, and this expanded design system is then implemented in carry chain logic to build faster and larger N-sorters, and much larger and still fast N-max/N-min filters. The new carry chain N-sorters are implemented in the FPGA used in the Amazon AWS EC2 F1 instance, which is one of the two example FPGAs utilized in the previous publication. A carry chain logic 16-sorter, not practical when using the original hardware block, has a speedup of 4.61 relative to the fastest 16-network. An example of the new, very large single-stage carry chain N-max filters is the 125-max <inline-formula> <tex-math notation="LaTeX">$5\times 5\times 5$ </tex-math></inline-formula> CNN video max pooling filter, which operates in only 2.075 nS. A 2-stage 1024-max network, using single-stage 32-max carry chain filters, has a speedup of 2.85 versus the existing state-of-the-art 10-stage network of 2-max filters. |
| format | Article |
| id | doaj-art-2ecd49baf9284f12bfcc969d0c8de8e0 |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2022-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-2ecd49baf9284f12bfcc969d0c8de8e02025-01-09T00:00:37ZengIEEEIEEE Access2169-35362022-01-0110796897970210.1109/ACCESS.2022.31945389843991Use of Carry Chain Logic and Design System Extensions to Construct Significantly Faster and Larger Single-Stage N-Sorters and N-FiltersRobert B. Kent0https://orcid.org/0000-0002-1189-4295Marios S. Pattichis1https://orcid.org/0000-0002-1574-1827Department of Electrical and Computer Engineering, The University of New Mexico, Albuquerque, NM, USADepartment of Electrical and Computer Engineering, The University of New Mexico, Albuquerque, NM, USAThe authors’ recently published design system for the creation of single-stage N-sorter/N-filter sorting devices, which were implemented using a particular example hardware block, is here expanded and applied to a second hardware type, FPGA carry chain logic. Although several researchers have published applications which use FPGA carry chain logic, most do not use carry chain logic as is done here, and none of the applications target sorting devices. Prior to the introduction of the single-stage N-sorter/N-filter design system, the fastest state-of-the-art hardware devices which sorted more than 2 input values were multistage sorting networks, in which the sorting process is performed by one or more 2-sorters and 2-max/2-min filters, operating in each sequential stage. Using the authors’ original design system, single-stage N-sorters and N-filters were shown to be faster than the fastest comparable sorting networks when sorting 3 to 9 inputs. Here, product term splitting and a new Sum-of-Products output multiplexer equation are added to the design system, and this expanded design system is then implemented in carry chain logic to build faster and larger N-sorters, and much larger and still fast N-max/N-min filters. The new carry chain N-sorters are implemented in the FPGA used in the Amazon AWS EC2 F1 instance, which is one of the two example FPGAs utilized in the previous publication. A carry chain logic 16-sorter, not practical when using the original hardware block, has a speedup of 4.61 relative to the fastest 16-network. An example of the new, very large single-stage carry chain N-max filters is the 125-max <inline-formula> <tex-math notation="LaTeX">$5\times 5\times 5$ </tex-math></inline-formula> CNN video max pooling filter, which operates in only 2.075 nS. A 2-stage 1024-max network, using single-stage 32-max carry chain filters, has a speedup of 2.85 versus the existing state-of-the-art 10-stage network of 2-max filters.https://ieeexplore.ieee.org/document/9843991/Field programmable gate arraysFPGAsortingsorting networksvideo max pooling |
| spellingShingle | Robert B. Kent Marios S. Pattichis Use of Carry Chain Logic and Design System Extensions to Construct Significantly Faster and Larger Single-Stage N-Sorters and N-Filters IEEE Access Field programmable gate arrays FPGA sorting sorting networks video max pooling |
| title | Use of Carry Chain Logic and Design System Extensions to Construct Significantly Faster and Larger Single-Stage N-Sorters and N-Filters |
| title_full | Use of Carry Chain Logic and Design System Extensions to Construct Significantly Faster and Larger Single-Stage N-Sorters and N-Filters |
| title_fullStr | Use of Carry Chain Logic and Design System Extensions to Construct Significantly Faster and Larger Single-Stage N-Sorters and N-Filters |
| title_full_unstemmed | Use of Carry Chain Logic and Design System Extensions to Construct Significantly Faster and Larger Single-Stage N-Sorters and N-Filters |
| title_short | Use of Carry Chain Logic and Design System Extensions to Construct Significantly Faster and Larger Single-Stage N-Sorters and N-Filters |
| title_sort | use of carry chain logic and design system extensions to construct significantly faster and larger single stage n sorters and n filters |
| topic | Field programmable gate arrays FPGA sorting sorting networks video max pooling |
| url | https://ieeexplore.ieee.org/document/9843991/ |
| work_keys_str_mv | AT robertbkent useofcarrychainlogicanddesignsystemextensionstoconstructsignificantlyfasterandlargersinglestagensortersandnfilters AT mariosspattichis useofcarrychainlogicanddesignsystemextensionstoconstructsignificantlyfasterandlargersinglestagensortersandnfilters |