1

我正在尝试通过 C++ 多线程解决网络流问题。

给定一个网络（所有节点都通过弧连接，每条弧连接2个且只有2个结束节点，一个是输入节点，另一个是输出节点，每个节点可以有多个输入弧和输出弧），每个节点需要做一些计算，然后将计算结果数据交换到其连接的输入和输出节点。

多个节点可以组合成一个任务，由一个线程运行。这样就可以将整个网络的计算工作量划分为多个任务。所有这些任务都被推送到一个 boost 线程池中，以便所有线程可以同时运行这些任务。

但是，如果一个节点（在一个线程任务中）需要与另一个节点（在另一个线程任务中）进行数据交换，就会出现同步问题。数据接收方需要等待数据发送方的数据缓冲区中可用的数据。

我的程序需要对网络进行分区，以便尽可能均匀地分配每个线程的任务工作负载。如果所有线程共享一个大数据缓冲区结构，程序并行性不好，因为临界区太大。即使数据结构的一部分（对它们有用）已可用于读取或写入，某些线程也必须等待解锁的一大数据缓冲区结构。

例如，one-large 数据缓冲区结构具有以下缓冲区单元：cell1、cell2、cell3、cell4。

当线程 1 尝试写入单元格 1 时，它必须锁定整个数据缓冲区结构，以便线程 2 无法读取或写入单元格 2，依此类推。

因此，我想根据线程号将一个大数据缓冲区结构分解为多个不同的数据单元，以便每个单元保存一个线程任务所需的数据。

例如，如果我们有 2 个线程，我们创建 2 个数据单元，分别保存 4 个线程所需的数据。如果我们有 4 个线程，我们将创建 4 个数据单元，分别保存 4 个线程所需的数据。等等。

我的问题是：

(1) 如何设计数据单元？你可以看到它的大小是基于线程数的。

(2) 如何减少同步开销？临界区很小，但如果节点间数据交换频率很高，则获取和释放互斥锁的开销可能会很高。

(3)当一个节点的计算完成并且数据被写入它的单元格时，如何通知数据接收节点，使得通知消息只被运行接收节点计算任务的等待线程接收。所有其他不相关的节点和线程不受影响。

该程序对时间非常敏感，应该非常严格地控制消息交换的延迟并尽可能减少。

非常感谢任何帮助。

谢谢

4

1 回答 1

0

我认为处理这个问题的常用方法是在线程之间建立一个消息传递基础设施。

每个线程都有一个消息队列。在您的示例中，假设节点 N1 分配给线程 1，节点 N2 分配给线程 2，并且 N1 和 N2 之间有一条边。然后，当线程 1 完成 N1 计算时，它会向线程 2 发送一条消息：

“向节点 N2 发送输入”

要将消息发送到线程，您只需锁定该线程的消息队列并附加您的消息。您使用一个互斥锁和两个条件变量（queue_not_empty_condition 和 queue_not_full_condition）来实现有界队列。当一个线程想要等待新的工作时，它只是在它的消息队列上休眠。

为了减少同步开销，您可能需要一种将多条消息放入队列（“批量发送”）的方法，同时只锁定互斥锁一次。然后在一个线程内循环看起来像这样：

if (I can do work without communicating with other threads)
    do that work
else
    send all pending messages (in batches to each destination thread)
    wait on my input queue and pop the messages off in a batch

不过，消息的“批处理”可能会以复杂的方式与有界队列交互。没有免费的午餐。

于 2011-09-25T05:03:49.787 回答