使用MPI并行化进行奇偶排序的实践方法
最编程
2024-07-22 13:45:14
...
奇偶排序
odd-even-sort, using MPI
代码在 https://github.com/thkkk/odd-even-sort
使用 MPI 实现奇偶排序算法, 并且 MPI 进程 只能向其相邻进程发送消息
nprocs
是进程数。 每个进程拥有独立的一块数据 data[0 ~ block_len-1]
,组合起来为整个待排序的数组。
方法
每个阶段排序之后不进行check
此前,在每个阶段的奇偶排序进行完之后,都会进行一次进程之间的信息传递,以判断排序是否完成,这个过程要进行约\(3*nprocs\)次的send/recv。现在的优化是:总共只进行nprocs轮排序,不再进行check。这样的话,即使是目前在最小编号进程中的元素,而它值较大,本应排序到最大编号进程中,也可以在nprocs轮中排到正确的位置。
这样之后,大约有几十ms的优化。
进程之间互相传递数据,然后进行优化后的归并
在一个排序阶段中,相邻进程块互相发送自己的全部数据,之后在每个块内部将两个块的数据进行归并,但是只保留最小/最大的block_len个元素,将其拷贝到自己的data上。这样可以省掉一半的归并时间。
这样之后大约有100+ms的优化。
进程之间发送全部数据之前,先发送端点处的数据
进程之间发送全部数据之前,先发送端点处的数据,判断左边进程中的最大元素是否小于等于右边进程中的最小元素,如果是,那么无需进行后续数据的发送和归并。
这样之后大约有几十ms的优化。
代码
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <mpi.h>
#include <cmath>
#include "worker.h"
using namespace std;
bool is_edge(int rank, bool odd_or_even, bool last_rank){
if (odd_or_even == 0){
return (rank & 1) == 0 && last_rank;
}
else{
return rank == 0 || ((rank & 1) == 1 && last_rank);
}
}
void merge_left(float *A, int nA, float *B, int nB, float *C){ //make sure C[nA-1] is available
float *p1 = A, *A_end = A + nA, *p2 = B, *B_end = B + nB, *p = C, *C_end = C + nA;
while( p != C_end && p1 != A_end && p2 != B_end)
*(p++) = ((*p1) <= (*p2)) ? *(p1++) : *(p2++);
while( p != C_end )
*(p++) = *(p1++);
}
void merge_right(float *A, int nA, float *B, int nB, float *C){
float *p1 = A + nA , *p2 = B + nB , *p = C + nB;
while( p != C && p1 != A && p2 != B )
*(--p) = (*(p1-1) >= *(p2-1)) ? *(--p1) : *(--p2);
while( p != C )
*(--p) = *(--p2);
}
void Worker::sort() {
//data[0, block_len)
if (out_of_range) return ;
std::sort(data, data + block_len);
//先把当前进程数据排好序
if (nprocs == 1) return ;
bool odd_or_even = 0; // = 0: even; = 1: odd;
float *cp_data = new float [block_len];
float *adj_data = new float [ceiling(n, nprocs)];
int limit = nprocs;
while(limit--){
if(is_edge(rank, odd_or_even, last_rank)){
//边界情况,没有与其他进程存在于同一个进程块内
}
else if((rank & 1) == odd_or_even){ //receive info
size_t adj_block_len = std::min(block_len, n - (rank + 1) * block_len);
MPI_Request request[2];
MPI_Isend(data + block_len - 1, 1, MPI_FLOAT, rank + 1, 0, MPI_COMM_WORLD, &request[0]);
MPI_Irecv(adj_data, 1, MPI_FLOAT, rank + 1, 1, MPI_COMM_WORLD, &request[1]);
MPI_Wait(&request[0], MPI_STATUS_IGNORE);
MPI_Wait(&request[1], MPI_STATUS_IGNORE); //发送端点数据
if(data [block_len - 1] > adj_data[0]) {
//此时两块之间存在未排好序的数据,需要排序
MPI_Sendrecv(data, block_len, MPI_FLOAT, rank + 1, 0,
adj_data, adj_block_len, MPI_FLOAT, rank + 1, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
//互相交换数据
// merge
merge_left(data, (int)block_len, adj_data, (int)adj_block_len, cp_data);
//进行归并排序,取前block_len个数据返回到cp_data中
memcpy(data, cp_data, block_len * sizeof(float)); //拷贝回data
}
}
else if ((rank & 1) == !odd_or_even){ //send info
size_t adj_block_len = ceiling(n, nprocs);
MPI_Request request[2];
MPI_Isend(data, 1, MPI_FLOAT, rank - 1, 1, MPI_COMM_WORLD, &request[1]);
MPI_Irecv(adj_data + adj_block_len - 1, 1, MPI_FLOAT, rank
- 1, 0, MPI_COMM_WORLD, &request[0]);
MPI_Wait(&request[1], MPI_STATUS_IGNORE);
MPI_Wait(&request[0], MPI_STATUS_IGNORE);
//发送端点数据
if (adj_data[adj_block_len - 1] > data[0]){
//此时两块之间存在未排好序的数据,需要排序
MPI_Sendrecv(data, block_len, MPI_FLOAT, rank - 1, 1,
adj_data, adj_block_len, MPI_FLOAT, rank - 1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
//互相交换数据
// merge
merge_right(adj_data, (int)adj_block_len, data, (int)block_len, cp_data);
//进行归并排序,取前block_len个数据返回到cp_data中
memcpy(data, cp_data, block_len * sizeof(float)); //拷贝回data
}
}
odd_or_even ^= 1;
}
delete[] cp_data;
delete[] adj_data;
}
实验数据
n | N\(\times\) P | 耗时(ms) | 相对单进程的加速比 |
---|---|---|---|
100000000 | 1$\times$1 | 12728.326000 | 1 |
100000000 | 1$\times$2 | 6754.229000 | 1.884 |
100000000 | 1$\times$4 | 3559.514000 | 3.576 |
100000000 | 1$\times$8 | 2007.818000 | 6.339 |
100000000 | 1$\times$16 | 1340.771000 | 9.493 |
100000000 | 2$\times$16 | 870.302000 | 14.625 |
上一篇: 如何轻松上手使用PDF文件处理工具指南
推荐阅读
-
使用MPI并行化进行奇偶排序的实践方法
-
[姿势估计] 实践记录:使用 Dlib 和 mediapipe 进行人脸姿势估计 - 本文重点介绍方法 2):方法 1:基于深度学习的方法:。 基于深度学习的方法:基于深度学习的方法利用深度学习模型,如卷积神经网络(CNN)或递归神经网络(RNN),直接从人脸图像中学习姿势估计。这些方法能够学习更复杂的特征表征,并在大规模数据集上取得优异的性能。方法二:基于二维校准信息估计三维姿态信息(计算机视觉 PnP 问题)。 特征点定位:人脸姿态估计的第一步是通过特征点定位来检测和定位人脸的关键点,如眼睛、鼻子和嘴巴。这些关键点提供了人脸的局部结构信息,可用于后续的姿势估计。 旋转表示:常见的旋转表示方法包括欧拉角和旋转矩阵。欧拉角通过三个旋转角度(通常是俯仰、偏航和滚动)描述头部的旋转姿态。旋转矩阵是一个 3x3 矩阵,表示头部从一个坐标系到另一个坐标系的变换。 三维模型重建:根据特征点的定位结果,三维人脸模型可用于姿势估计。通过将人脸的二维图像映射到三维模型上,可以估算出人脸的旋转和平移信息。这就需要建立人脸的三维模型,然后通过优化方法将模型与特征点对齐,从而获得姿势估计结果。 特征点定位 特征点定位是用于检测人脸关键部位的五官基础部分,还有其他更多的特征点表示方法,大家可以参考我上一篇文章中介绍的特征点检测方案实践:人脸校正二次定位操作来解决人脸校正的问题,客户在检测关键点的代码上略有修改,坐标转换部分客户见上图 def get_face_info(image). img_copy = image.copy image.flags.writeable = False image = cv2.cvtColor(image, cv2.COLOR_BGR2RGB) results = face_detection.process(image) # 在图像上绘制人脸检测注释。 image.flags.writeable = True image = cv2.cvtColor(image, cv2.COLOR_RGB2BGR) box_info, facial = None, None if results.detections: for detection in results. for detection in results.detections: mp_drawing.Drawing.detection = 无 mp_drawing.draw_detection(image, detection) 面部 = detection.location_data.relative_keypoints 返回面部 在上述代码中,返回的数据是五官(6 个关键点的坐标),这是用 mediapipe 库实现的,下面我们可以尝试用另一个库:dlib 来实现。 使用 dlib 使用 Dlib 库在 Python 中实现人脸关键点检测的步骤如下: 确保已安装 Dlib 库,可使用以下命令: pip install dlib 导入必要的库: 加载 Dlib 的人脸检测器和关键点检测器模型: 读取图像并将其灰度化: 使用人脸检测器检测图像中的人脸: 对检测到的人脸进行遍历,并使用关键点检测器检测人脸关键点: 显示绘制了关键点的图像: 以下代码将参数 landmarks_part 添加到要返回的关键点坐标中。
-
41 个下载免费 3D 模型的最佳网站-使用说明:使用权限可能因型号而异。因此,在下载文件之前,请仔细检查每个下载页面上的许可证和使用权限。 17. Clara.io Clara.io 是一个创建 3D 内容的全球平台,也是一个培养新 3D 艺术家的社区。Clara.io 提供+100,000个免费的3D模型,包括OBJ,Blend,STL,FBX,DAE,Babylon.JS,Three.JS格式,用于 Clara.io,Unity 3D,Blender,Sketchup,Cinema 4D,3DS Max和Maya。 使用说明:免费,标准和专业帐户仅供个人使用,如果您需要将 clara.io 用于商业用途,请与销售团队联系。 18. 3DExport 3DExport是一个市场,您可以在其中购买和销售用于CG项目的3D模型,3D打印模型和纹理。它提供15 +不同的3D格式供下载,如3DS MAX(.max),Cinema4D(.c4d),Maya(.mb,.ma),Lightwave(.lwo),Softimage(.xsi),Wavefront OBJ(.obj),Autodesk FBX(.fbx)等。它还提供15种不同的语言! 使用说明:免费下载仅供个人和非商业用途。 19. 3D Warehouse 3D Warehouse是一个开放的库,允许用户共享和下载SketchUp 3D模型,用于建筑,设计,施工和娱乐!任何人都可以免费制作,修改和重新上传内容到3D仓库,您可以找到任何您能想到的东西,如家具,电子产品,室内产品等。 使用说明:3D Warehouse中的所有模型都是免费的,因此任何人都可以下载文件以用于SketchUp甚至其他软件,如AutoCAD,Revit和ArchiCAD。 20. CadNav.com CadNav是CGI平面设计师和CAD / CAM / CAE工程师的在线3D模型库,我们提供超过50000 +免费3D模型和CAD模型下载。在CadNav网站上,您可以下载高质量的多边形网格3D模型,3D CAD实体对象,纹理,Vray材料,3D作品,CAD图纸等。 使用说明:免费下载仅供个人和非商业用途。 21. All3dfree.net 就像网站名称一样,它提供免费的3D模型,还包括Vray材料,CAD块,2d和3d纹理集合,无需注册即可免费下载。它是不断更新的,因此您可以查找或请求3DS,MAX,C4D,skp,OBJ,FBX,MTL等格式的模型。 使用说明:所有资源均不允许用于商业用途,否则您将承担责任。 22. Hum3D 自2005年以来,Hum3D帮助来自3多个国家的80D艺术家节省3D建模时间,并制作逼真的3D模型,用于电影,视频游戏,AR应用程序和可视化。所有模型均由首席3D艺术家进行验证,他们检查其是否符合专业要求和最新的3D建模标准。 使用说明:免费下载仅供个人和非商业用途。 23. Artist-3D.com 艺术家-3D 库存的免费 3D 模型下载按通用类别排序。它为人体解剖学、汽车、家具、火箭、卫星等模型提供 AutoDesk 3DS Max 格式。您还可以在浏览他们的网站时找到教程和类似类型的建模。 使用说明:使用权限可能因型号而异。因此,在下载文件之前,请仔细检查每个下载页面上的许可证和使用权限。 24. Free the models 就像本网站的标题一样,它为3d应用程序和3d游戏引擎提供免费的内容模型。您可以为您的任何项目找到许多有趣且有用的模型!它提供3ds,wavefront,bryce,poser,lightwave,md2和unity3d格式的模型。还有一个很棒的纹理集合,可以在您最喜欢的建模和渲染程序中使用。 使用说明:您从这里下载的所有内容都可以免费使用,除非它不能包含在另一个免费的网络或CD收藏中,也不能单独出售。否则,您可以在商业游戏,3D应用程序或渲染作品中使用它。您不必提供信用,但如果您这样做,那就太好了。 25. Resources.blogscopia 本网站由一家名为Scopia的公司创建。他们制作3D图像和视频,您可以找到许多为CGI工作的信息架构设计的模型,所有这些都可以在现实生活中使用。您可以免费下载它们,但是,如果您想一次下载它们,您可以支付 3 到 9 欧元。 使用说明:您可以免费下载模型部分的所有文件。每个压缩文件都包含您也可以在此处找到的许可证。基本上,您可以对文件执行任何操作。唯一的限制是不归属于Scopia的重新分发。 26.ambientCG 1000+公共领域PBR材料适合所有人!环境CG是使用许多不同的方法和资产类型创建的,例如照片纹理(PBR),贴花(PBR),图集(PBR),照片纹理(普通),物质存档(SBSAR),雕刻画笔,3D模型和地形。您可以在所有项目中*使用它们! 使用说明:在 ambientCG 上提供下载的所有 PBR 材料、画笔、照片和 3D 模型均根据知识共享 CC0 1.0 通用许可提供。您可以复制、修改、分发和执行作品,即使是出于商业目的,也无需征得许可。信用将不胜感激。 不要满足于平庸的大理石纹理 - 立即使用我们的免费PBR大理石纹理升级您的3D设计。 27.Pixar One Twenty Eight 这是一个提供官方动画行业经典纹理的网站:皮克斯,创建于 1993 年,该纹理库包括 128 个重复纹理,现在免费提供。 它包含您来到的纹理,包括砖块和动物毛皮。肯定会有一些你可以使用的东西。 使用说明:皮克斯动画工作室的《Pixar One Twenty Eight》根据知识共享署名4.0国际许可协议进行许可。即使出于商业目的,您也可以重新混合、调整和构建您的作品,只要您以相同的条款对新创作进行信用和许可。 访问数以千计的免费纹理并提升您的设计游戏 - 立即开始下载! 28. 3DXO 即使有近 620 个免费贴纸可供下载,3DXO 也不是最大的资源,但它的内容非常有用,不需要注册。无论是简单的墙壁或地板,还是一些奇怪的小东西,您都需要的纹理都可以在此网站上看到。 使用说明:使用权限可能因型号而异。因此,在下载文件之前,请仔细检查每个下载页面上的许可证和使用权限。 29. 3DModelsCC0 3DModelsCC0 与其他产品的不同之处在于它包含超过 250+ 个高质量 3D 模型,并且本网站上的所有内容都是免费的,完全是公共领域!使用我们的模型时无需信用或归属! 使用说明:为每个人提供完全免费的公共领域内容。 30.Sketch up texture club Sketchup Texture Club是一个非营利性的教育和信息门户网站,由3D社区的图像促进协会管理,特别强调面向学生和建筑和室内设计专业人士的可视化和渲染技术,以及所有正在学习3D可视化的人。 使用说明:您无需支付版税或使用费。纹理可以免费下载和使用。不允许将纹理作为竞争产品出售或重新分发,即使图像被修改也是如此。 31. FlippedNormals FlippedNormal 是一个提供计算机图形和 3D 资产的市场,您可以找到许多用于雕刻、建模、纹理、概念艺术、3D 模型、游戏资产或课程的高级资产! 使用说明:使用权限可能因型号而异。因此,在下载文件之前,请仔细检查每个下载页面上的许可证和使用权限。 32. NASA 3D NASA 3D网站是一个在线门户,提供与太空和各种NASA任务相关的大量三维模型和模拟。该网站是用户友好的,并提供有关每个型号的详细信息。该网站允许用户探索和下载几种不同格式的模型,包括 OBJ、STL 和 FBX,只需单击下载按钮即可。 使用说明: 要下载模型,只需单击模型页面上的下载按钮并选择所需的格式。 33. 3DAGOGO (Astroprint) 3DAGOGO 是一个提供广泛 3D 模型的网站,包括角色、车辆和建筑物。3DAGOGO 的独特功能之一是它专注于适合 3D 打印的模型,使其成为希望创建物理原型或模型的设计师的绝佳资源。要使用 3DAGOGO,设计师只需在网站上搜索他们正在寻找的模型类型,然后下载 STL 格式的文件。 使用说明: 要使用 3DAGOGO,只需搜索所需的 3D 模型类型并下载 STL 格式的文件。根据需要自定义模型,并确保在将其用于商业目的之前检查使用权限。 34. FreeCAD FreeCAD是一款了不起的3D建模软件,可让您在计算机上创建令人难以置信的3D设计。该软件可免费下载和使用,它提供了广泛的工具和功能,可用于创建用于各种目的的3D模型。 该网站易于浏览,您可以找到开始使用FreeCAD的所有必要信息。此外,该网站还提供一系列教程和指南,可帮助您了解 3D 建模的来龙去脉。 使用说明: 要下载模型,请访问网站并从库中选择所需的模型。该网站还提供了一系列使用该软件的教程和指南。 35. Pinshape Pinshape是一个提供一系列3D打印模型的网站。网站上提供的型号质量很高,因此您可以确保您的最终印刷产品看起来很棒。该网站提供了广泛的模型,包括从家居用品到小雕像和珠宝的所有物品。 但这还不是Pinshape所能提供的全部!该网站还允许用户上传和共享自己的3D模型。这意味着您不仅可以下载出色的模型,还可以通过分享自己的设计为社区做出贡献。此外,Pinshape 提供了一系列自定义选项,因此您可以调整和调整模型以满足您的特定需求。 使用说明: 要下载模型,请在网站上创建一个帐户,搜索所需的模型,然后单击下载按钮。该网站还为每种型号提供了一系列定制选项。 36.Yeggi Yeggi 提供了大量免费的 3D 模型,您可以下载各种格式的模型,例如 STL、OBJ 和 FBX。该网站易于使用,您可以按关键字、类别或特定网站搜索模型。 Yeggi 对于任何寻找 3D 模型的人来说都是一个很好的资源。它提供了大量的模型集合,从日常物品到复杂的机械,以及介于两者之间的一切。该网站的收藏量在不断增长,每天都有新的型号增加。 使用说明: 要下载模型,请在网站上搜索所需的模型,然后单击下载按钮。该网站还提供指向托管模型的原始网站的链接。 37. Open3DModel 来自开放3D模型的图像 Open3DModel具有各种类别的模型,包括建筑,车辆和角色。无论您需要建筑物,汽车还是人的3D模型,都可以在此网站上找到。 该网站易于浏览,您可以按类别或关键字搜索模型。每个模型都附带预览图像和详细信息,例如文件格式、大小和多边形数量。此信息可以帮助您选择适合您需求的模型。 使用说明: 要下载模型,请访问网站,从库中选择所需的模型,然后单击下载按钮。 使用最好的 3D 资产管理工具简化您的 3D 制作流程。立即试用它们,将您的 3D 项目提升到一个新的水平! 38. 3DExport 对于那些为其 3D 设计项目寻找 3D 模型、纹理和其他资源的人来说,该平台是一个很好的资源。该网站有大量模型可供选择,包括 3D 打印对象、游戏资产等。用户可以按类别、文件格式或价格范围浏览,以找到适合其项目的完美资源。此外,3DExport 还提供一系列教程和其他 3D 资源,以帮助用户提高技能并创建更令人印象深刻的设计。 使用说明: 要使用 3DExport,只需创建一个帐户并浏览可用型号。您可以按类别、格式和价格进行搜索,以找到所需的型号。找到喜欢的模型后,只需下载它并开始在您的项目中使用它。 39.Blend Swap Blend Swap是一个社区驱动的市场,提供与Blender软件兼容的各种免费3D模型。该平台允许用户共享和下载模型、纹理和其他资产,以便在他们的项目中使用。 使用说明: 创建免费帐户后,您可以浏览社区上传的大量3D模型。当您找到要使用的一个时,只需下载它并将其导入您选择的 3D 软件即可。 40. 3DShook 3DShook 是一个高级 3D 模型市场,提供一系列用于建筑、游戏等各个行业的高质量模型。该平台提供基于订阅的模型,具有不同的定价计划,允许用户访问一系列模型。 使用说明: 注册免费帐户后,只需浏览3D模型库,选择您喜欢的模型,然后以您需要的格式下载它们。 41. Smithsonian X 3D 史密森尼 X 3D 对于正在寻找历史文物和文物的高质量 3D 模型的设计师来说,这是一个独特的资源。该平台提供了大量3D模型,这些模型是根据史密森尼博物馆和研究中心中的真实物体扫描创建的。 使用说明: