# parallel-bitonic-sort

**Repository Path**: prefer2023/parallel-bitonic-sort

## Basic Information

- **Project Name**: parallel-bitonic-sort
- **Description**: 并行双调排序
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-06-19
- **Last Updated**: 2026-06-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Parallel Bitonic Sort

基于MPI的并行Bitonic排序算法实现，包含优化版本。

## 文件说明

| 文件 | 说明 |
|------|------|
| `bitonic_sort.c` | 基线版本 - 正确的MPI并行Bitonic Sort |
| `bitonic_sort_advanced.c` | 优化版本 - OpenMP并行 + 双缓冲指针交换 |
| `Makefile` | 编译脚本 |
| `OPTIMIZATIONS.md` | 详细优化记录 |
| `第6题 Parallel Bitonic Sort.md` | 原始PDF提取内容 |
| `第6题 Parallel Bitonic Sort_CN.md` | 中文翻译版本 |

## 编译与运行

### 环境要求

- MPI实现（OpenMPI, MPICH等）
- C编译器（gcc）
- OpenMP（优化版本需要）

### 编译

```bash
# 编译所有版本
make all

# 仅编译基线版本
make bitonic_sort

# 仅编译优化版本
make bitonic_sort_advanced
```

### 运行基线版本

```bash
# 运行基线版本（语法: mpirun -np <进程数> ./bitonic_sort [每进程数据量]）
mpirun --allow-run-as-root --oversubscribe -np 4 ./bitonic_sort 250000
```

### 运行优化版本

```bash
# 运行优化版本（需设置OpenMP线程数）
OMP_NUM_THREADS=4 mpirun --allow-run-as-root --oversubscribe -np 4 ./bitonic_sort_advanced 250000
```

参数说明：
- 进程数必须是2的幂次方
- 每进程数据量默认为1,000,000
- 总数据量 = 每进程数据量 × 进程数（自动计算）

## 算法原理

### Bitonic序列

一个序列 $a = (a_1, a_2, ..., a_p)$ 是Bitonic序列，当且仅当：

- $a_1 \leq a_2 \leq ... \leq a_k \geq ... \geq a_p$，其中 $1 < k < p$（先递增后递减）
- $a_1 \geq a_2 \geq ... \leq ... \leq a_p$，其中 $1 < k < p$（先递减后递增）
- 序列可以分成两部分，交换后满足上述两种情况之一

### Bitonic排序过程

1. **构建Bitonic序列**：从相邻的数对开始，通过compare-and-exchange操作形成递增和递减序列对
2. **合并**：将相邻的序列对合并成更大的Bitonic序列
3. **最终排序**：在最后一步，将单个Bitonic序列排序为完全有序序列

### 并行实现（MPI）

每个处理器负责 $N/P$ 个元素，算法流程：

```
输入: 处理器数量 P, 数据长度 N
1. 每个处理器生成 N/P 个随机数
2. 本地排序（qsort或bitonic sort）
3. 并行Bitonic合并网络:
   for k = 2, 4, 8, ..., P:
     for j = k/2, k/4, ..., 1:
       partner = rank XOR j
       与partner交换数据
       合并两个有序序列
       根据方向保留前半部分或后半部分
```

### 方向判定

在Bitonic合并的每一步中：
- 如果 `rank` 的第 $\log_2(k)$ 位为0：该组按升序排列
- 如果 `rank` 的第 $\log_2(k)$ 位为1：该组按降序排列

对于每个比较步骤：
- `rank < partner`：升序组保留较小元素，降序组保留较大元素
- `rank > partner`：升序组保留较大元素，降序组保留较小元素

### 时间复杂度

当 $P = n$（处理器数等于数据量）：
$$T_{par}^{bitonic} = \sum_{i=1}^{\log n} i = \frac{\log n(\log n + 1)}{2} = O(\log^2 n)$$

当 $P \ll n$（处理器数远小于数据量）：
$$T_{par}^{bitonic} = \frac{N}{P}(\log N + \log^2 P)$$


## 优化说明

优化版本 (`bitonic_sort_advanced.c`) 包含以下优化：

1. **OpenMP并行本地排序** - 使用Bitonic Sort网络代替qsort，支持OpenMP并行化
2. **优化的Merge函数** - 直接合并并保留所需半部分，减少内存拷贝
3. **智能排序策略** - 根据数组大小自动选择qsort或并行Bitonic Sort
4. **编译器优化** - 使用-O3、-march=native等高级优化标志
5. **双缓冲指针交换** - 使用两个缓冲区并通过指针交换避免所有memcpy

详见 `OPTIMIZATIONS.md`。