题目分析

本题要求设计一个用于 MalnaRISC 处理器的排序程序，该处理器只支持 CMPSWP R_i R_j 指令，该指令比较两个寄存器的值并在需要时交换。关键特性是：同一行中的多个指令可以并行执行，只要它们涉及的寄存器互不相同。

关键观察

$1$. 指令特性：

CMPSWP 是唯一的指令类型

同一行内指令必须涉及不同的寄存器（互不冲突）

可以理解为并行比较交换操作

$2$. 问题本质： 我们需要设计一个排序网络（Sorting Network），其中：

每个阶段（行）包含多个可并行执行的比较器

比较器是比较两个元素并在需要时交换的比较交换单元

目标是使用尽可能少的阶段数（行数）

$3$. 已知最优结构： 对于排序网络，已知的较优结构包括：

双调排序器（Bitonic Sorter）

奇偶归并网络（Odd-Even Merging Network）

希尔伯特排序网络

算法思路

1. 基于双调排序的并行网络 代码实现了双调排序网络的变体，这是一种高效的并行排序算法：

将输入序列构建成双调序列

递归地对双调序列进行排序

2. 递归分治策略 对于大小为 $n$ 的数组：

如果 $n$ 是 $2$ 的幂，使用标准的双调排序网络

如果 $n$ 不是 $2$ 的幂，填充到最近的 $2$ 的幂，执行排序，然后移除多余的部分

3. 并行阶段组织 每个阶段（代码中的一行）包含多个可并行执行的 CMPSWP 操作：

同一阶段内，所有比较操作涉及的寄存器对互不重叠

阶段之间是串行的，前一阶段完成后才能执行下一阶段

算法步骤

$1$. 双调排序网络构建：

对于大小为 $n$ 的数组（$n$ 是 $2$ 的幂）：

for k = 1, 2, 4, ..., n/2:  # 双调序列构建
    for j = k, k/2, ..., 1:  # 双调合并
        for i = 0 to n-1:
            if (i & j == 0) and (i & (2k) == 0):
                compare_swap(i, i+j)

$2$. 并行化优化：

将内层循环中所有可以并行执行的比较操作放在同一阶段：

对每个 $i$，如果操作不冲突（寄存器不重复），可以放在同一行

使用位运算判断哪些操作可以并行

$3$. 非 2 的幂处理：

如果 $n$ 不是 $2$ 的幂：

设 $m = 2^{\lceil \log_2 n \rceil}$（大于等于 $n$ 的最小 $2$ 的幂）

对 $m$ 个元素执行双调排序

从结果中移除涉及虚拟元素（索引 $\ge n$）的比较操作

正确性证明

$1$. 双调排序的正确性： 双调排序是经典的排序网络算法，已被证明能够正确排序任意输入序列。

$2$. 并行执行的合法性： 代码确保同一阶段内的所有比较操作：

涉及的寄存器索引对互不相同

没有寄存器在同一阶段内出现两次 这满足了 MalnaRISC 的并行执行约束。

$3$. 非 2 的幂的处理： 填充虚拟元素不会影响实际元素的最终排序结果，因为：

虚拟元素值视为无穷大（或按需处理）

移除涉及虚拟元素的操作后，剩余操作仍构成有效的排序网络

复杂度分析

时间/空间复杂度（对于输出）

• 阶段数：$O(\log^2 n)$

• 总比较操作数：$O(n \log^2 n)$

• 代码行数：$O(\log^2 n)$

实际运行

在 MalnaRISC 上：

• 每阶段（行）的指令并行执行

• 总执行时间与阶段数成正比

• 这是理论上的较优排序网络

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<vector<pii>> R;
    auto solve = [&](int n, int d = 0) {
        for (int w = 0; w < __lg(n); w++) {
            vector<vector<pii>> V(w + 1);
            auto bs = [&](int l, int r)->void{
                for (int k = __lg(r - l + 1) - 1, c = 1; ~k; k--, c++) {
                    vector<bool> b(r - l + 1);

                    for (int i = l; i <= r; i++)
                        if (!b[i - l])
                            b[i - l] = b[i - l + (1 << k)] = true, V[c].emplace_back(i + d, i + (1 << k) + d);
                }
            };

            for (int l = 0; l < n; l++) {
                int r = l + (1 << w + 1) - 1, m = l + r >> 1;

                for (int i = m, j = m + 1; i >= l; i--, j++)
                    V[0].emplace_back(i + d, j + d);

                bs(l, m), bs(m + 1, r), l = r;
            }

            R.insert(R.end(), V.begin(), V.end());
        }
    };

    if (__builtin_popcount(n) == 1)
        solve(n);
    else {
        solve(1 << __lg(n) + 1);
        vector<vector<pii>> R2;

        for (int i = 0; i < R.size(); i++) {
            vector<pii> v;

            for (auto [x, y] : R[i])
                if (x < n && y < n)
                    v.emplace_back(x, y);

            if (!v.empty())
                R2.emplace_back(v);
        }

        R = move(R2);
    }

    cout << R.size() << endl;

    for (auto &v : R) {
        for (auto [x, y] : v)
            cout << "CMPSWP R" << x + 1 << " R" << y + 1 << ' ';

        cout << '\n';
    }

    return 0;
}