Content deleted Content added
→Sorting: Somewhat of a description how this works in terms of a hardware arrangement. |
|||
Line 100:
[[Bubble sort]] is also an example of 1D systolic computation,<ref>C.L. Britton, Jr., M.N. Ericson, and D.W. Bouldin, "A Virtual Zero-Time, Monolithic Systolic Sorting Array", 1989 https://www.osti.gov/servlets/purl/6004774</ref> although it applies N-1 passes for an array of size N. Each pass systolically moves the maximum element of a subsequence towards its final ___location in the sorted result.
If one is willing to use N/2 processing elements (PE) each with a comparator and two registers, elements arranged in a stack-like fashion, an array (or stream) of size N can thus be sorted in 2N time by pushing its elements in while on every level of the systolic stack the maximum of the pair of elements stored in each PE is pushed further down. And after all the elements are pushed in, the process is reversed with the minimum element in each PE being popped out (or "pushed up"), resulting in the stream of elements coming out sorted in ascending order.<ref>M. H. Alsuwaiyel, *Parallel Algorithms*, World Scientific, 2022, Sec. 9.5 "An On-chip Bubble Sorter" (in Ch. 9 "Systolic Computation").</ref>
==Implementations==
| |||