并行与分布式系统中的并行图匹配：并行化稳定匹配（Gale-Shapley）算法

字数 4306 2025-12-11 23:40:31

并行与分布式系统中的并行图匹配：并行化稳定匹配（Gale-Shapley）算法

题目描述

稳定匹配（Stable Matching）问题，也称为“稳定婚姻”问题，最早由 Gale 和 Shapley 提出。问题描述如下：设有两个大小相等的集合，例如求婚者（Men）集合 M 和接收者（Women）集合 W，每个求婚者对 W 中所有成员有一个严格的偏好排名列表，每个接收者对 M 中所有成员也有一个严格的偏好排名列表。目标是为每个求婚者匹配一个接收者，形成一个完美匹配（即一一对应），使得不存在任何一对“不稳定”的匹配对。所谓不稳定，是指在当前匹配之外，存在一个求婚者 m 和一个接收者 w，他们彼此更喜欢对方胜过当前的匹配伴侣。此时，m 和 w 将有动机“私奔”，破坏当前匹配的稳定性。Gale-Shapley 算法可以在 O(n²) 时间内找到这样一个稳定匹配。在并行与分布式系统中，我们希望将这一经典算法并行化，以处理大规模匹配问题（例如，大规模任务调度、资源分配、市场匹配等），提高计算效率。

解题过程

问题形式化与核心概念
- 输入：
  - 两个大小均为 n 的集合：M = {m₁, m₂, ..., mₙ}， W = {w₁, w₂, ..., wₙ}。
  - 对于每个 m ∈ M，一个关于 W 的严格全序偏好列表 prefM[m]。
  - 对于每个 w ∈ W，一个关于 M 的严格全序偏好列表 prefW[w]。
- 输出：一个完美匹配 S: M → W，使得不存在 (m, w) 满足以下条件：
  1. m 当前匹配的接收者为 S(m)。
  2. w 当前匹配的求婚者为 S'(w)（即 S⁻¹(w)）。
  3. m 在 prefM[m] 中更喜欢 w 胜过 S(m)。
  4. w 在 prefW[w] 中更喜欢 m 胜过 S'(w)。
- 核心概念：
  - 求婚/提议：算法运行过程中，未被匹配的求婚者 m 会按照其偏好列表的顺序，依次向他最喜欢的、尚未拒绝过他的接收者 w 发出求婚提议。
  - 接受/拒绝：接收者 w 收到一个求婚提议后，会比较当前求婚者 m 和她当前“暂时订婚”的对象（如果有的话）。如果 w 还没有订婚对象，她暂时接受 m 的提议，与之订婚。如果已有订婚对象 m'，则 w 会比较 m 和 m' 在其偏好列表中的位置，选择她更喜欢的那个继续订婚，并拒绝另一个。
  - 稳定性：当所有求婚者都有订婚对象，且没有新的求婚发生时，算法终止。此时形成的订婚关系集合就是一个稳定匹配。

串行 Gale-Shapley 算法回顾
让我们快速回顾串行算法，这是并行化的基础。

初始化：
    所有求婚者 m ∈ M 设为自由（未匹配）。
    所有接收者 w ∈ W 的当前伴侣设为 NULL。
    为每个求婚者 m 创建一个指针 nextProposal[m]，指向其偏好列表的第一个接收者。

While 存在自由求婚者 m do:
    令 w 为 m 偏好列表中 nextProposal[m] 指向的接收者。
    移动 nextProposal[m] 指针到下一位。
    If w 的当前伴侣为 NULL then:
        w 与 m 订婚（设置 w 的伴侣为 m，m 不再自由）。
    Else:
        令 m' 为 w 的当前伴侣。
        If w 在偏好列表中更喜欢 m 胜过 m' then:
            w 与 m' 解除婚约（m' 变为自由）。
            w 与 m 订婚（设置 w 的伴侣为 m，m 不再自由）。
        Else:
            w 拒绝 m（m 保持自由，继续下一轮循环）。
End While

关键观察：求婚过程是异步的。只要一个自由求婚者 m 是自由的，他就可以“主动”发起求婚。多个求婚者可以同时发起求婚，这为并行化提供了可能。但挑战在于协调多个求婚者对同一个接收者的求婚请求，以及确保接收者的决定（接受/拒绝）是原子性的，并且基于一致的、最新的状态。

并行化策略：多进程/多线程模型
我们考虑在共享内存多核系统或多处理器集群（通过消息传递）上并行化。核心思想是让多个自由求婚者并行地执行求婚步骤。这可以显著减少“轮次”（串行算法中求婚者依次求婚的次数），尤其是在早期阶段，许多求婚者可以同时行动。

主要步骤：

a. 数据划分与初始化
* 将求婚者集合 M 划分成 p 个大小大致相等的子集 M₁, M₂, ..., M_p，其中 p 是处理器/线程的数量。
* 每个处理器/线程 P_i 负责其分配到的求婚者子集 M_i 的求婚过程。
* 维护全局（或分布式共享）的数据结构：
* husband[w]: 存储接收者 w 的当前伴侣（初始为 NULL）。
* nextProposal[m]: 每个求婚者 m 下一次要求婚的接收者在偏好列表中的索引（初始化为 0）。
* 维护一个全局的“自由求婚者列表”或队列，用于跟踪哪些求婚者当前是自由的。在并行环境中，这通常需要并发控制。

b. 并行求婚循环
每个处理器 P_i 在其负责的 M_i 中，循环执行以下操作，直到全局没有自由求婚者为止（或所有求婚者都已匹配）：
1. 选择一个自由求婚者：P_i 从 M_i 的自由求婚者集合中（或从一个本地工作队列）取出一个求婚者 m。这需要避免多个处理器处理同一个求婚者。通常使用本地的任务队列可以减少争用。
2. 读取偏好并锁定：P_i 读取 m 的下一个求婚对象 w = prefM[m][nextProposal[m]]。然后，它尝试获取接收者 w 的“锁”（或使用原子操作）。这是确保原子性决策的关键。如果锁已被其他处理器持有，P_i 可能需要等待或尝试处理另一个自由求婚者。
3. 处理求婚：
* 一旦获取了 w 的锁，P_i 读取 w 的当前伴侣 currentHusband = husband[w]。
* 如果 currentHusband 为 NULL，则 w 接受 m 的求婚。设置 husband[w] = m，将 m 标记为“已订婚”（从自由列表中移除），递增 nextProposal[m]。
* 如果 currentHusband 不为 NULL，则 P_i 需要查阅 w 的偏好列表 prefW[w]，比较 m 和 currentHusband。
* 如果 w 更喜欢 m，则 w 与 currentHusband 解除婚约（将 currentHusband 重新标记为自由，并可能放回某个处理器的工作队列），然后 w 与 m 订婚（更新 husband[w] = m，m 标记为已订婚）。
* 否则，w 拒绝 m。m 保持自由，P_i 递增 nextProposal[m]，m 将被放回 P_i 的自由求婚者列表，等待下一轮尝试向偏好列表中的下一个接收者求婚。
4. 释放锁：处理完成后，P_i 释放 w 的锁。
5. 处理被拒绝的求婚者：如果 m 在本轮被拒绝，并且其 nextProposal[m] 还未到达列表末尾，则 P_i 将 m 重新加入本地的自由求婚者工作列表。如果 nextProposal[m] 已到末尾，意味着 m 已向所有接收者求婚并被拒绝（在严格的偏好假设下，这不会发生，但算法实现中可以作为终止条件之一）。
6. 终止检测：需要一个全局终止检测机制。当所有处理器的本地自由求婚者列表都为空，并且没有正在进行的求婚操作时，算法终止。这可以通过一个全局计数器（活跃求婚者数量）结合屏障同步来实现。当计数器为零时，所有处理器退出循环。
关键问题与优化
a. 锁的粒度与争用：
* 为每个接收者 w 设置一个锁是最直接的。但在高并发下，对热门接收者（排名靠前的）的锁争用会很激烈。优化策略包括：
* 退避与重试：当一个处理器未能获取锁时，不忙等，而是暂时处理另一个自由求婚者。
* 细粒度锁：如果数据结构更复杂，可能需要更细粒度的锁。但在基本算法中，每个接收者一个锁通常足够。

b. 数据结构一致性：
* husband[w] 的更新必须在持有 w 的锁的情况下进行，以保证原子性和可见性。
* 每个求婚者的 nextProposal[m] 只需要被其所属的处理器访问，因此不需要锁。但被拒绝后放回自由列表时，需要确保处理器能看到最新的状态。

c. 负载均衡：
* 初始时，每个处理器分配到等量的求婚者。但随着算法进行，一些求婚者可能很快被匹配，而另一些可能需要多次尝试。使用工作窃取（Work Stealing）可以改善负载均衡：当一个处理器耗尽其本地自由求婚者队列时，它可以从其他处理器的队列中“窃取”一些求婚者来处理。

d. 终止检测：
* 实现一个高效的、非集中式的终止检测机制是关键。一种常见方法是使用“信数”或“扩散-积累”协议。简单实现中，可以定期进行全局屏障同步，检查是否所有处理器的本地队列为空且没有活跃的求婚操作。但这会增加开销。更高效的方法可以是让每个处理器维护一个本地状态（活跃/空闲），并通过消息传递（在分布式内存中）或共享变量（在共享内存中）传播状态变化，以检测全局终止。
算法复杂度分析
- 正确性：并行算法本质上模拟了串行Gale-Shapley算法的执行顺序。由于每个接收者对同时到达的多个求婚请求，通过锁保证了其决策是串行化的（即每次只处理一个请求，并基于最新的 husband[w] 做出决定），因此最终得到的匹配与串行算法产生的结果是相同的（具体来说，是求婚者最优的稳定匹配）。稳定性证明与串行算法相同。
- 时间：最坏情况下，每个求婚者最多求婚 n 次，总共 O(n²) 次求婚操作。在理想并行情况下，如果每次迭代都有 p 个处理器并行处理求婚，且无争用，时间复杂度可降至 O(n²/p)。然而，锁争用、负载不均衡和通信开销会降低实际加速比。平均情况下，算法收敛很快，许多求婚者在几次尝试后即被匹配。
- 空间：O(n²) 存储偏好列表，O(n) 存储状态（husband, nextProposal, 锁等）。
扩展与讨论
- 分布式内存版本：在消息传递接口（MPI）环境下，求婚者和接收者可以分布在不同节点。求婚请求、接受/拒绝消息需要通过消息传递。此时，锁机制被节点间的消息协调所替代。每个接收者进程负责处理发送给它的求婚消息，并原子地更新状态、发送回复。终止检测需要使用分布式协议。
- 非完全图/偏好列表不完整：算法可以推广到求婚者和接收者数量不等，或偏好列表不完整（某些配对不允许）的情况。并行化策略基本不变。
- 应用：除了经典的“婚姻匹配”，该算法广泛应用于全国住院医师匹配计划、学校招生、任务分配、无线网络中的信道分配等场景。在这些大规模应用中，并行化至关重要。

总结

并行化稳定匹配（Gale-Shapley）算法的核心在于利用其固有的异步特性：多个自由求婚者可以同时发起求婚。通过为每个接收者引入锁来保证其决策的原子性，并辅以高效的任务分配、负载均衡和终止检测机制，可以实现一个高效的并行算法。该算法是“并行化经典串行算法”的一个典型案例，展示了如何在保持算法逻辑不变的前提下，通过并发控制和任务分解来利用多核或分布式计算资源。

并行与分布式系统中的并行图匹配：并行化稳定匹配（Gale-Shapley）算法题目描述稳定匹配（Stable Matching）问题，也称为“稳定婚姻”问题，最早由 Gale 和 Shapley 提出。问题描述如下：设有两个大小相等的集合，例如求婚者（Men）集合 M 和接收者（Women）集合 W，每个求婚者对 W 中所有成员有一个严格的偏好排名列表，每个接收者对 M 中所有成员也有一个严格的偏好排名列表。目标是为每个求婚者匹配一个接收者，形成一个完美匹配（即一一对应），使得不存在任何一对“不稳定”的匹配对。所谓不稳定，是指在当前匹配之外，存在一个求婚者 m 和一个接收者 w，他们彼此更喜欢对方胜过当前的匹配伴侣。此时，m 和 w 将有动机“私奔”，破坏当前匹配的稳定性。Gale-Shapley 算法可以在 O(n²) 时间内找到这样一个稳定匹配。在并行与分布式系统中，我们希望将这一经典算法并行化，以处理大规模匹配问题（例如，大规模任务调度、资源分配、市场匹配等），提高计算效率。解题过程问题形式化与核心概念输入：两个大小均为 n 的集合：M = {m₁, m₂, ..., mₙ}， W = {w₁, w₂, ..., wₙ}。对于每个 m ∈ M，一个关于 W 的严格全序偏好列表 prefM[m] 。对于每个 w ∈ W，一个关于 M 的严格全序偏好列表 prefW[w] 。输出：一个完美匹配 S: M → W，使得不存在 (m, w) 满足以下条件： m 当前匹配的接收者为 S(m)。 w 当前匹配的求婚者为 S'(w)（即 S⁻¹(w)）。 m 在 prefM[m] 中更喜欢 w 胜过 S(m)。 w 在 prefW[w] 中更喜欢 m 胜过 S'(w)。核心概念：求婚/提议：算法运行过程中，未被匹配的求婚者 m 会按照其偏好列表的顺序，依次向他最喜欢的、尚未拒绝过他的接收者 w 发出求婚提议。接受/拒绝：接收者 w 收到一个求婚提议后，会比较当前求婚者 m 和她当前“暂时订婚”的对象（如果有的话）。如果 w 还没有订婚对象，她暂时接受 m 的提议，与之订婚。如果已有订婚对象 m'，则 w 会比较 m 和 m' 在其偏好列表中的位置，选择她更喜欢的那个继续订婚，并拒绝另一个。稳定性：当所有求婚者都有订婚对象，且没有新的求婚发生时，算法终止。此时形成的订婚关系集合就是一个稳定匹配。串行 Gale-Shapley 算法回顾让我们快速回顾串行算法，这是并行化的基础。关键观察：求婚过程是异步的。只要一个自由求婚者 m 是自由的，他就可以“主动”发起求婚。多个求婚者可以同时发起求婚，这为并行化提供了可能。但挑战在于协调多个求婚者对同一个接收者的求婚请求，以及确保接收者的决定（接受/拒绝）是原子性的，并且基于一致的、最新的状态。并行化策略：多进程/多线程模型我们考虑在共享内存多核系统或多处理器集群（通过消息传递）上并行化。核心思想是让多个自由求婚者并行地执行求婚步骤。这可以显著减少“轮次”（串行算法中求婚者依次求婚的次数），尤其是在早期阶段，许多求婚者可以同时行动。主要步骤： a. 数据划分与初始化 * 将求婚者集合 M 划分成 p 个大小大致相等的子集 M₁, M₂, ..., M_ p，其中 p 是处理器/线程的数量。 * 每个处理器/线程 P_ i 负责其分配到的求婚者子集 M_ i 的求婚过程。 * 维护全局（或分布式共享）的数据结构： * husband[w] : 存储接收者 w 的当前伴侣（初始为 NULL）。 * nextProposal[m] : 每个求婚者 m 下一次要求婚的接收者在偏好列表中的索引（初始化为 0）。 * 维护一个全局的“自由求婚者列表”或队列，用于跟踪哪些求婚者当前是自由的。在并行环境中，这通常需要并发控制。 b. 并行求婚循环每个处理器 P_ i 在其负责的 M_ i 中，循环执行以下操作，直到全局没有自由求婚者为止（或所有求婚者都已匹配）： 1. 选择一个自由求婚者：P_ i 从 M_ i 的自由求婚者集合中（或从一个本地工作队列）取出一个求婚者 m。这需要避免多个处理器处理同一个求婚者。通常使用本地的任务队列可以减少争用。 2. 读取偏好并锁定：P_ i 读取 m 的下一个求婚对象 w = prefM[m][nextProposal[m]] 。然后，它尝试获取接收者 w 的“锁”（或使用原子操作）。这是确保原子性决策的关键。如果锁已被其他处理器持有，P_ i 可能需要等待或尝试处理另一个自由求婚者。 3. 处理求婚： * 一旦获取了 w 的锁，P_ i 读取 w 的当前伴侣 currentHusband = husband[w] 。 * 如果 currentHusband 为 NULL，则 w 接受 m 的求婚。设置 husband[w] = m ，将 m 标记为“已订婚”（从自由列表中移除），递增 nextProposal[m] 。 * 如果 currentHusband 不为 NULL，则 P_ i 需要查阅 w 的偏好列表 prefW[w] ，比较 m 和 currentHusband 。 * 如果 w 更喜欢 m，则 w 与 currentHusband 解除婚约（将 currentHusband 重新标记为自由，并可能放回某个处理器的工作队列），然后 w 与 m 订婚（更新 husband[w] = m ，m 标记为已订婚）。 * 否则，w 拒绝 m。m 保持自由，P_ i 递增 nextProposal[m] ，m 将被放回 P_ i 的自由求婚者列表，等待下一轮尝试向偏好列表中的下一个接收者求婚。 4. 释放锁：处理完成后，P_ i 释放 w 的锁。 5. 处理被拒绝的求婚者：如果 m 在本轮被拒绝，并且其 nextProposal[m] 还未到达列表末尾，则 P_ i 将 m 重新加入本地的自由求婚者工作列表。如果 nextProposal[m] 已到末尾，意味着 m 已向所有接收者求婚并被拒绝（在严格的偏好假设下，这不会发生，但算法实现中可以作为终止条件之一）。 6. 终止检测：需要一个全局终止检测机制。当所有处理器的本地自由求婚者列表都为空，并且没有正在进行的求婚操作时，算法终止。这可以通过一个全局计数器（活跃求婚者数量）结合屏障同步来实现。当计数器为零时，所有处理器退出循环。关键问题与优化 a. 锁的粒度与争用： * 为每个接收者 w 设置一个锁是最直接的。但在高并发下，对热门接收者（排名靠前的）的锁争用会很激烈。优化策略包括： * 退避与重试：当一个处理器未能获取锁时，不忙等，而是暂时处理另一个自由求婚者。 * 细粒度锁：如果数据结构更复杂，可能需要更细粒度的锁。但在基本算法中，每个接收者一个锁通常足够。 b. 数据结构一致性： * husband[w] 的更新必须在持有 w 的锁的情况下进行，以保证原子性和可见性。 * 每个求婚者的 nextProposal[m] 只需要被其所属的处理器访问，因此不需要锁。但被拒绝后放回自由列表时，需要确保处理器能看到最新的状态。 c. 负载均衡： * 初始时，每个处理器分配到等量的求婚者。但随着算法进行，一些求婚者可能很快被匹配，而另一些可能需要多次尝试。使用工作窃取（Work Stealing）可以改善负载均衡：当一个处理器耗尽其本地自由求婚者队列时，它可以从其他处理器的队列中“窃取”一些求婚者来处理。 d. 终止检测： * 实现一个高效的、非集中式的终止检测机制是关键。一种常见方法是使用“信数”或“扩散-积累”协议。简单实现中，可以定期进行全局屏障同步，检查是否所有处理器的本地队列为空且没有活跃的求婚操作。但这会增加开销。更高效的方法可以是让每个处理器维护一个本地状态（活跃/空闲），并通过消息传递（在分布式内存中）或共享变量（在共享内存中）传播状态变化，以检测全局终止。算法复杂度分析正确性：并行算法本质上模拟了串行Gale-Shapley算法的执行顺序。由于每个接收者对同时到达的多个求婚请求，通过锁保证了其决策是串行化的（即每次只处理一个请求，并基于最新的 husband[w] 做出决定），因此最终得到的匹配与串行算法产生的结果是相同的（具体来说，是求婚者最优的稳定匹配）。稳定性证明与串行算法相同。时间：最坏情况下，每个求婚者最多求婚 n 次，总共 O(n²) 次求婚操作。在理想并行情况下，如果每次迭代都有 p 个处理器并行处理求婚，且无争用，时间复杂度可降至 O(n²/p)。然而，锁争用、负载不均衡和通信开销会降低实际加速比。平均情况下，算法收敛很快，许多求婚者在几次尝试后即被匹配。空间：O(n²) 存储偏好列表，O(n) 存储状态（ husband , nextProposal , 锁等）。扩展与讨论分布式内存版本：在消息传递接口（MPI）环境下，求婚者和接收者可以分布在不同节点。求婚请求、接受/拒绝消息需要通过消息传递。此时，锁机制被节点间的消息协调所替代。每个接收者进程负责处理发送给它的求婚消息，并原子地更新状态、发送回复。终止检测需要使用分布式协议。非完全图/偏好列表不完整：算法可以推广到求婚者和接收者数量不等，或偏好列表不完整（某些配对不允许）的情况。并行化策略基本不变。应用：除了经典的“婚姻匹配”，该算法广泛应用于全国住院医师匹配计划、学校招生、任务分配、无线网络中的信道分配等场景。在这些大规模应用中，并行化至关重要。总结并行化稳定匹配（Gale-Shapley）算法的核心在于利用其固有的异步特性：多个自由求婚者可以同时发起求婚。通过为每个接收者引入锁来保证其决策的原子性，并辅以高效的任务分配、负载均衡和终止检测机制，可以实现一个高效的并行算法。该算法是“并行化经典串行算法”的一个典型案例，展示了如何在保持算法逻辑不变的前提下，通过并发控制和任务分解来利用多核或分布式计算资源。