c++ - 在 C++ 中使用 OpenMP 并行化算法
问题描述
我的问题是这样的:
我想用 C++ 中的蚁群优化算法来解决 TSP。现在我已经实现了一个迭代解决这个问题的算法。
例如:我生成了 500 只蚂蚁——它们一个接一个地找到自己的路线。每只蚂蚁直到前一只蚂蚁完成后才开始。
现在我想并行化整个事情——我考虑过使用 OpenMP。
所以我的第一个问题是:我可以生成大量同时工作的线程(蚂蚁数量> 500)吗?
我已经尝试了一些东西。这是我的 main.cpp 中的代码:
#pragma omp parallel for
for (auto ant = antarmy.begin(); ant != antarmy.end(); ++ant) {
#pragma omp ordered
if (ant->getIterations() < ITERATIONSMAX) {
ant->setNumber(currentAntNumber);
currentAntNumber++;
ant->antRoute();
}
}
这是我的 Ant 类中“关键”的代码,因为每个 Ant 读取和写入同一个矩阵(信息素矩阵):
void Ant::antRoute()
{
this->route.setCity(0, this->getStartIndex());
int nextCity = this->getNextCity(this->getStartIndex());
this->routedistance += this->data->distanceMatrix[this->getStartIndex()][nextCity];
int tempCity;
int i = 2;
this->setProbability(nextCity);
this->setVisited(nextCity);
this->route.setCity(1, nextCity);
updatePheromone(this->getStartIndex(), nextCity, routedistance, 0);
while (this->getVisitedCount() < datacitycount) {
tempCity = nextCity;
nextCity = this->getNextCity(nextCity);
this->setProbability(nextCity);
this->setVisited(nextCity);
this->route.setCity(i, nextCity);
this->routedistance += this->data->distanceMatrix[tempCity][nextCity];
updatePheromone(tempCity, nextCity, routedistance, 0);
i++;
}
this->routedistance += this->data->distanceMatrix[nextCity][this->getStartIndex()];
// updatePheromone(-1, -1, -1, 1);
ShortestDistance(this->routedistance);
this->iterationsshortestpath++;
}
void Ant::updatePheromone(int i, int j, double distance, bool reduce)
{
#pragma omp critical(pheromone)
if (reduce == 1) {
for (int x = 0; x < datacitycount; x++) {
for (int y = 0; y < datacitycount; y++) {
if (REDUCE * this->data->pheromoneMatrix[x][y] < 0)
this->data->pheromoneMatrix[x][y] = 0.0;
else
this->data->pheromoneMatrix[x][y] -= REDUCE * this->data->pheromoneMatrix[x][y];
}
}
}
else {
double currentpheromone = this->data->pheromoneMatrix[i][j];
double updatedpheromone = (1 - PHEROMONEREDUCTION)*currentpheromone + (PHEROMONEDEPOSIT / distance);
if (updatedpheromone < 0.0) {
this->data->pheromoneMatrix[i][j] = 0;
this->data->pheromoneMatrix[j][i] = 0;
}
else {
this->data->pheromoneMatrix[i][j] = updatedpheromone;
this->data->pheromoneMatrix[j][i] = updatedpheromone;
}
}
}
因此,由于某些原因,omp 并行 for 循环不会在这些基于范围的循环上工作。所以这是我的第二个问题——如果你们对如何完成基于范围的循环的代码有任何建议,我很高兴。
谢谢你的帮助
解决方案
所以我的第一个问题是:我可以生成大量同时工作的线程(蚂蚁数量> 500)吗?
在 OpenMP 中,您通常不应该关心有多少线程处于活动状态,而是确保通过工作共享结构(例如omp for
或)公开足够的并行工作omp task
。因此,虽然您可能有一个包含 500 次迭代的循环,但您的程序可以在一个线程和 500 个线程(或更多,但它们只是空闲)之间的任何线程上运行。这与其他并行化方法不同,例如您必须管理所有线程及其功能的 pthreads。
现在您的示例使用ordered
不正确。仅当循环体的一小部分需要按顺序执行时,Ordered 才有用。即便如此,它也可能对性能造成很大的问题。ordered
如果你想在里面使用,你还需要声明一个循环ordered
。另请参阅这个出色的答案。
你不应该使用有序。相反,请确保蚂蚁number
事先知道那里,编写代码使得它们不需要数字,或者至少数字的顺序对蚂蚁来说无关紧要。在后一种情况下,您可以使用omp atomic capture
.
至于对共享数据的访问。尽量避免它。添加omp critical
是获得正确并行程序的第一步,但通常会导致性能问题。衡量您的并行效率,使用并行性能分析工具来确定您是否属于这种情况。然后您可以使用原子数据访问或减少(每个线程都有自己的数据,只有在主要工作完成后,来自所有线程的数据才会合并)。
推荐阅读
- java - Visual Studio Code:Java 应用程序和远程调试
- c# - 如何在本地使用 Azure ServiceBus
- matlab - 在Matlab中以双倍的单元格数组X值绘制数据时间
- python - 卷积双线性插值
- android - 尝试使用 RecyclerView 时出错 - 为什么?
- sql - 尝试将表单提交到数据库时出错
- xml - 如何在 PowerShell 中自动创建 XML 的新元素?
- angular - 错误参考错误:“ng build”时“未定义缓冲区”
- java - 为什么 ResponseEntity 正文返回 null?
- audio - 无法从视频文件中添加额外的音频 - 错误输出文件 #0 不包含任何流