tag

#bitonic-sort

6 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

GPU Bitonic Sort

GPU Bitonic Sort GPU bitonic sort is a GPU implementation of bitonic sort. It uses a fixed compare and exchange pattern that fits SIMD style execution well. The algorithm performs more comparisons than quicksort or merge sort, but its memory access and control flow are regular. This makes it useful for small to medium arrays, block local sorting, graphics workloads, and GPU kernels where predictable execution is more important than...
algorithms sorting gpu bitonic-sort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Bitonic Sorting Network

Bitonic Sorting Network A bitonic sorting network is a fixed sequence of compare and exchange operations that sorts a fixed number of elements. It is based on the idea of repeatedly building bitonic sequences and merging them. A bitonic sequence increases and then decreases, or can be rotated into that shape. The network first creates bitonic sequences of small size, then merges them into larger sorted sequences until the full...
algorithms sorting sorting-network bitonic-sort
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Bitonic Sort

Bitonic Sort Bitonic sort is a comparison sorting algorithm based on bitonic sequences. It is important because its compare and swap pattern is fixed, which makes it suitable for parallel hardware and sorting networks. A bitonic sequence first increases and then decreases, or can be rotated into that form. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1] $$...
algorithms sorting bitonic-sort sorting-network
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

SIMD Bitonic Sort

SIMD Bitonic Sort SIMD bitonic sort sorts a small fixed number of elements using vector registers. It maps a bitonic sorting network onto SIMD lanes, replacing scalar compare and exchange with vector min and max operations plus lane shuffles. The schedule is fixed. No branches depend on data. This property fits SIMD execution where all lanes execute the same instruction. Problem Given a vector of $W$ elements held in SIMD...
algorithms sorting simd bitonic-sort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Parallel Bitonic Sort

Parallel Bitonic Sort Parallel bitonic sort is a sorting network based algorithm. It sorts by repeatedly forming bitonic sequences and then merging them into sorted order. A bitonic sequence first increases and then decreases, or can be rotated into that shape. The algorithm works especially well on parallel hardware because the compare and exchange pattern is regular and independent of the input values. Problem Given an array $A$ of size...
algorithms sorting parallel bitonic-sort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Bitonic Sort on Hypercube

Bitonic Sort on Hypercube Bitonic sort on a hypercube maps the bitonic sorting network onto processors connected as a hypercube. Each processor communicates with neighbors that differ in one binary address bit. The fixed communication pattern matches the regular compare and exchange stages of bitonic sort. This model is useful for parallel sorting theory and for systems whose communication topology resembles a hypercube. Problem Given $n$ keys distributed across $p...
algorithms sorting parallel distributed hypercube bitonic-sort