1

问题：我想使用所谓的两相锁定概念同时计算一些方程。

我的方法：创建一个数组，将实时更新每个变量的值。我有点卡在我应该创建线程的方式上，在算法上应用互斥锁/信号量以并发执行。

输入（当然，我会建立一个更大的方程组来测试并发程序的效率）

2
3 6
&0 = &0 + 4 + 3
&1 = &0 - &1 + 2 + 5
&0 = &1 + 3

输入说明：

第一行是未知数。（&0 和 &1 是未知数）第二行是它们各自的初始值。（&0 等于 3，&1 等于 6） 下一行是方程式。

输出

&0 = 14
&1 = 11

在我实现方程的结构下方（可以吗？可以改进吗？）

struct X{
    int id; // the calculated variable
    int sum; // the sum of every constants
    std::string eq; // the row as a string
    std::unordered_map<int, int> unknowns; // store all the unknowns and counts them
    X(std::string);
    void parsing(); // parse eq to get id, sum and unknowns
    void updating(); // update the value of id on a global array when all the unknowns are available
};
4

1 回答 1

0

1. 在分配之间建立依赖关系图

我认为您的目标是尽可能多地并行计算分配，同时获得相同的结果，就好像您一个接一个地按顺序计算分配一样。为了确定可以并行完成的工作，我建议在您的赋值表达式之间构建一个依赖关系图。

从最后一个赋值开始：参与赋值的任何变量意味着要计算它，我们需要计算对所涉及的变量进行修改的最后一个赋值。用你给出的例子：

&0 = 3                // A0 (variable initialization)
&1 = 6                // A1 (variable initialization)
&0 = &0 + 4 + 3       // A2
&1 = &0 - &1 + 2 + 5  // A3
&0 = &1 + 3           // A4

依赖项是：

A4 <-- A3         (To compute A4, you need to compute A3 before)
A3 <-- A2 and A1  (To compute A3, you need to compute A2 for the value of &0 and A1 for &1)
A2 <-- A0
A1 <-- no dependency
A0 <-- no dependency

2.递归计算依赖关系

免责声明：我对 C++ 中锁和线程的使用不是很熟悉。但我想我可以给出一个通用的方法。

现在您已经确定了依赖关系是什么，您可以尝试计算它们。我可以为线程过程建议这种简单的方法：

computeAssignment(Assignment * as) {
  if (as is not computed) {
    lock Assignment as
    for each dependency of as {
      spawn a thread running computeAssignment(dependency) // Recursion occurs here
    }
    wait for all the threads spawned in the for loop to finish
    compute the result of this assignment
    unlock Assignment as
  }
  return result of as
}

当一个线程开始检查分配给它的分配时，它首先检查它是否是之前计算过的。如果未计算分配，则必须以使第一个线程进行此检查阻止访问所有其他线程的方式完成此检查。

当第一个线程忙于生成线程以计算依赖关系并计算分配结果时，其他线程在第一次检查时被阻塞。当第一个线程最终解锁分配时，所有等待的线程都将看到计算结果。

要开始计算，您应该为您拥有的每个变量生成其中一个线程，并为它们提供修改变量作为参数的最后一个赋值。在您的示例中，这将是 2 个线程，从分配 A4（最后修改 &0）和 A3（最后修改 &1）开始。

于 2020-06-10T02:41:34.830 回答