高性能体系结构中高效连通组件标记算法

用于高性能体系结构的高效连通组件标记算法引用此版本：劳伦特·卡巴莱。用于高性能体系结构的高效相关组件标记算法。计算机视觉和模式识别[cs.CV]。巴黎萨克雷大学（COmUE），2016年。法语。NNT：2016年SACLS299。电话：01597903HAL ID：电话：01597903https://theses.hal.science/tel-01597903提交日期：2018年HAL是一个多学科的开放存取档案馆，用于存放和传播科学研究论文，无论它们是否被公开。论文可以来自法国或国外的教学和研究机构，也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaireNNT：2016年SACLS299医生的论文从UN第580号博士学校信息与通信科学与技术博士专业：计算机科学通过M. 我们的卡巴莱用于高性能架构的高效连通分量标记算法的研究论文于2016年9月28日在伊维特河畔吉夫发表并答辩评审团组成：M.S. CONCHONM.D. 我是BLRI南巴黎大学教授（评审团主席）LRI南巴黎大学名誉教授（考官）M.L. LacaSS agne教授（论文主任）大学巴黎6号，LIP6A女士。金额RTM.O. 发送IEYSM.S. 我的儿子格勒诺布尔大学GIPSA实验室教授（报告员）ENSSAT/IRISA Lannion教授（考官）斯图加特大学教授（考官）M.H. TalBOT教授（报告员）巴黎ESIEE，A2SI1谢谢你这篇论文对我来说是一个个人的成就，因此，在将近40岁的时候，那些允许我在良好的条件下到达并支持这项工作的人的名单首先，如果没有我的论文导师莱昂内尔·拉卡萨涅先生对我的信任，一切都是不可能的。2011年5月25日，当他接到一个奇怪的电话，有人想做一篇迟来的论文时，他也在场在像我这样的职业生涯中下注从来都不是一件容易的事，他表现出了完美的承诺，一种伟大的教育意识，使我成为一名计算机电子学家，最后是一种敏锐的细节感，这使我的工作具有了非常感谢你莱昂内尔!J’exprime ma profonde gratitude à madame Annick Montanvert et monsieur Hugues Talbot pouravoir我要非常热烈地感谢Sylvain CONCHON先生同意担任论文评审团主席，以及Daniel Étiemble先生、Olivier Sentieys先生和Sven SIMON先生（Danke!）我很我想再次感谢Daniel Étiemble先生在我的整个工作过程中对我的善意、恳求、信任和总是明智的科学和句法建议：与您一起工作是一次难忘的经历。当然，如果没有巴黎中央学院（第一个）和中央高等教育学院（第二个）的参与，这一切都是无论是同事和朋友（Céline、Pascale、Marc、Paolo、Frédéric）的鼓励，还是JohnCagnol先生和Lionel Gabet先生的不懈支持，他们使我能够调整我的部门，认真开展我的研究工作，当然还有整个LISA团队（Didier、Hanane、Malika、Philippe），他们承担了很多责任，继续成功地我还要感谢特别感谢斯蒂芬妮，感谢她的效率和幽默感，感谢她经常帮助我理解（和克服）论文的行政复杂性在这四年里，我的家人我的母亲米歇尔和我的父亲勒内（他15年前离开了我们），除了他们的爱，他们我的兄弟杰罗姆，我亲爱的嫂子拉蒂西亚和我的侄子和侄女（约汉，劳拉，诺亚）为他们的生活乐趣我的妻子克里斯汀，她是勇气，善良和倾听的化身，能够承担别人的担忧，仍然微笑。我不能用几句话来概括我欠你的一切，所以一个词就足够了：一切。2谢谢你现在让你的梦想成真，我会在你身边我的两个太阳，玛农和蒂图安，对他们来说，"论文"这个词一定意味着缺席，我希望你们一生都记住，你们的父亲是和你们一起走到这一步的，也是因为你们，最后，我的朋友们（Nue我是我们所有相遇的总和，尽管这些年我可能很遥远，但3目录感谢1目录8图14列表表17列表算法列表20导言21CH APITRE 1二进制图像的相关分量标记的基础知识1.1用于关联组件标记的拓扑概念1.1.1 数字拓扑301.1.2 铺设301.1.3 网格301.1.4 连接性301.1.5 图像的路径方向1.1.6 邻居311.2从相关组件到1.2.1 相关组件321.2.2 二进制图像的相关组件标记的结构。341.2.3 第一直觉351.2.4 相关组件中的标签类别1.3图的数据结构和操作371.3.1 对偶连通图/邻接矩阵1.3.2 传递闭包371.3.3 Floyd-Warshall算法381.3.4 扎根森林391.3.5 等效表表示1.3.6 联合查找算法401.4先锋算法421.4.1 罗森菲尔德·普法尔茨421.4.2 HaralickShapiro44岁1.4.3 Lumia ShapiroZuniga472941.4.4 RonseDevijver49材料表41.5算法和体系结构491.5.1 相关分量标记算法的拓扑学稀疏和密集501.5.2 算术强度的问题1.5.3 其他标签511.6相关成分分析511.6.1 相关组件的描述符1.6.2 描述符的计算521.7结论52第二章相关组件中的顺序标记算法的最新技术水平2.1导言532.2建立2.2.1 图像测试542.2.2 图像大小542.2.3 指标552.2.4 随机图像的再现性552.2.5 密度562.2.6 粒度572.3数据集特征分析582.3.1 数据集参数对标签数量的影响2.3.2 来自SIDBA和SIDBA4602.4算法改进612.4.1 决策树612.4.2 等效性管理：铃木632.4.3 压缩路径642.4.4 RCM642.4.5 HCS：一种基于状态机的算法2.4.6HCS2652.4.7 AREMSP662.4.8 格拉纳662.4.9 LSL：光速标签672.5描述符的计算722.6结论73CH APITRE 3序列标记算法的性能和3.1导言753.2一组参考算法的构成3.2.1 Rosenfeld家族的变体763.2.2 HCS2系列的变体783.2.3 铃木79系列的变体5375材料表53.2.4 后续实验81材料表63.3数据集参考算法的对抗813.3.1 对密度的行为813.3.2 关于粒度的行为813.3.3 结果与SIDBA82图像的比较3.3.4 关于参考算法的一般行为的结论数据集833.4中间步骤在相关组成部分中对整体标签性能的贡献3.4.1 随机图像的结果843.4.2 SIDBA84的图像结果3.4.3 相关成分标签的结论3.5相关成分分析863.5.1 随机图像的结果873.5.2 SIDBA88的图像结果3.5.3 第89章3.6中间阶段在构成相关组成部分分析总体绩效中所占份额3.6.1 随机图像的结果893.6.2 SIDBA89的图像结果3.6.3 结论913.791代体系结构的性能演变3.8结论92CH APITRE 4多核架构的相关组件标签4.1导言934.2多核94的数据切片4.2.1 原则944.2.2 数据结构954.2.3 标签和相关成分分析的情况4.3以前在相关组件中并行化标签的工作4.3.1 现代建筑通才作品1004.3.2 其他架构的工作4.4并行光速标签：适用于多核102的LSL4.4.1 一般原则1024.4.2 切割成条1024.4.3 标签4.4.4 金字塔合并1044.4.5 融合带1044.5PLSL104的实施4.5.1 ICMP和替代方案的使用4.5.2 描述符1054.6PLSL105的性能评估4.6.1 统一模型1054.6.2 指标1064.7结论10693材料表7××107131CH APITRE 5Archite多核框架上并行相关分量分析算法的性能5.1导言1075.2台式机-4核1085.2.1 随机图像的结果1085.2.2 SIDBA4110图像的结果5.2.3 中间步骤的份额1115.2.4 办公机器111的结论5.3工作站- 2个12核1135.3.1 随机图像的结果1135.3.2 SIDBA4115图像的结果5.3.3 中间步骤的份额1165.3.4 工作站119的结论5.4计算服务器- 4 15个内核1195.4.1 随机图像的结果1195.4.2 SIDBA41215.4.3 中间步骤的份额1235.5数据大小和活动内核数量的综合影响1265.6结论128CH APITRE 6用于非常高核数架构的迭代相关组件标记算法6.1导言1316.2非递归迭代算法：MPAR EP1326.2.1 原则1326.2.2 传播速度1336.2.3 第135章6.3MPAR FB + PID + OMP+ AT1356.3.1 MPAR F：递归前向1366.3.2 MPARFB：通过前后扫描（向前向后）的递归算法1366.3.3 MPAR FB + MID：使用矢量指令1376.3.4 MPAR FB + PID+ OMP1386.3.5 MPAR FB + MID + OMP + AT：切片和激活表6.3.6 MPAR FB + PID + OMP + AT+ MAX1416.3.7 实施1416.4WARP142级6.4.1 原则1426.4.2 图形结构1426.4.3 相关子组件和子图1436.4.4 WARP算法0：传递闭包1446.4.5 WARP：到达144个来源材料表81616.4.6 来源的竞争1476.4.7 WARP联盟：WARP +有效联盟机制6.4.8 WARPCPU1506.4.9 WARPGPU1526.5结论160第七章并行迭代算法的性能7.1导言1617.2MPAR算法和高核架构1617.2.1 测量基础设施1617.2.2 测试程序1627.2.3 低C/BW比1637.2.4 高C/BW比1657.2.5 最大传播效率与最小传播效率1657.2.6 对密度的行为1667.2.7 瓷砖切割行为1667.2.8 适用于具有大量内核的机器的前景7.2.9 MPAR168算法的结论7.3GPU169上的WARP算法7.3.1 测量基础设施1697.3.2 测试程序1697.3.3 WARP GPU和Maxwell170一代7.3.4 随机图像1707.3.5 不同内核在整体性能组成中的份额1717.3.6 SIDBA41727.3.7 GPU一代的影响1727.3.8 对图像大小的依赖性7.3.9 考虑传输1747.3.10 WARP GPU175类算法的结论7.4结论175结论和研究177参考文献179189CHA A附件A.1 算法189A.1.1 罗森菲尔德普法尔茨189A.1.2 HaralickShapiro190A.1.3 Lumia ShapiroZuniga191A.1.4 RCM：一个错误的好主意193材料表9A.1.5 塞尔科194材料表10××A.2 并行算法在IVB2上的性能12195A.3 并行算法在IVB上的性能4 15197A.4 WARP：延迟199×>数字列表1.1基于正多边形的平面路面301.2相应的网格301.3二维图像的连通性表示1.4扫描方向321.5将像素的邻接分解1.6将像素的邻接分解1.7相关组件中的标签数据结构1.8直接算法的掩码361.9对偶连通图/邻接矩阵1.10 图及其传递闭包381.11 根树示例1.12 有向图中的对偶图/邻接矩阵1.13 对偶图/等效表1.14 合并两个定向树411.15 罗森菲尔德的面具421.16 Rosenfeld：标签流程的关键步骤1.17 Haralick面具1.18 Haralick：第一次通过-直接扫描451.19 Haralick：第一次通过-反向扫描461.20 Haralick- 第二次传球和稳定461.21 Lumia47的面具1.22 Lumia算法的步骤1.23 Lumia算法的步骤1.24 第49段的代表性1.25 相关组件中标记的存储器拓扑1.26 Rosenfeld掩模51的附加标签生成器形状1.27 相关组件描述符的提取522.1度量和对图像大小N2和处理器频率的依赖性..................................................................2.2g= 1、g= 4和g= 16以及平均cpp时，cpp随密度的变化在2.3对于g粒度，密度为35%的随机图像1、2、4、8、16，图像大小为1024 1024572.4相关成分数量（na）、临时标签数量（ne）和附加标签数量（ns = n-na）的变化证据根据粒度582.5在增加颗粒时创建新的附加标签拉里592.6相关组成部分规模变化的证据2.7标准图像DataBAse602.8每像素的相关分量和附加标签的密度材料表129图列表10>×>>××××>×××××奏效×2.9决策树，p是要标记为61的当前像素2.10 考虑当前像素62的决策树2.11 随机图像：加载和测试每个像素的平均次数没有决策树和有决策时间表622.12 SIDBA数据库：每个像素的平均加载和测试次数（无和使用决策632.13 使用Suzuki表管理类之间的联合的原理2.14 RCM64的特定掩模2.15 HCS65的特殊面罩2.16 RCM65的特定面罩2.17 使用AREMSP 66的树木组合2.18 Grana67专用面罩的构造2.19 LSL：相对表和段682.20 LSL：基于相对标签的等效性构建3.1Rosenfeld系列变体：对于大小为1024、粒度为g{1，4，16}的图像，以cpp表示;对于内核上的粒度，以cppd表示Skylake773.2HCS2系列变体：对于大小为1024、粒度为g{1，4，16}的图像，性能以cpp表示，cppd作为粒度的函数Skylake78的心脏3.3铃木系列变体：1024 1024图像以cpp表示和粒度g{1，4，16}和cppd，作为Skylake80内核上粒度的函数3.4直接参考算法：cpp用于1024和1024大小的图像粒度g{1，4，16}和平均cpp作为Skylake82内核上粒度的函数3.5直接参考算法：平均cpp和变异性（cppmax和cppmin）Skylake83内核上的SIDBA数据库3.6随机图像的总cpp组成与密度（%）的关系尺寸1024 1024，Skylake85芯上的g = 13.7随机图像的总cpp组成与密度（%）的关系尺寸1024 1024和g= 4，适用于Skylake85内核3.8随机图像的总cpp组成与密度（%）的关系尺寸1024 1024和g= 16在Skylake85芯上3.9相关分量分析：大小为1024 1024、粒度为g{1，4，16}的图像的cpp以及Skylake87内核上粒度的平均cpp3.10 相关分量分析：Skylake883.11 相关分量分析：平均cpp和变异性（cppmax和cppmin）Skylake88内核上的SIDBA数据库3.12 相关成分分析：总体CPP组成与密度的关系（%）对于Skylake90内核上大小为1024、1024和g = 1的随机图像3.13 相关成分分析：总体CPP组成与密度的关系（%）对于Skylake90内核上大小为1024、1024和g = 4的随机图像3.14 相关成分分析：总体CPP组成与密度的关系Skylake90内核上大小为1024、1024和g = 16的随机图像的百分比3.15 相关分量分析：参考算法的平均cpp从Conroe（2006年）到Skylake（2015年）的7种架构的SIDBA数据库924.1趋势线来自免费午餐是软件竞争的根本性转变[100]（2009年更新94图列表11××××××××××4.2内核上的并行化954.32个线程的基本块切片示例：像素、行、切片具有先验排序或通过堆栈954.4锁的原理964.5两个螺纹的最大切割尺寸974.6罗森菲尔德面具974.7标签图像的水平条带4.8用两个标签计数器合并两个条带4.9波段合并：掩码和相应的决策树994.10 频带联合的调度示例4.11 Niknam等人的垂直条带切割1014.12 标签图像的水平条带化5.1多核并行化：用于2048× 2048图像大小和粒度的cpp作为SKL1×4108机器4个内核上粒度的函数的g奏效{1，4，16}和cpp d5.2相关分量分析：LSLRLE的cpp与最小值的比值对于粒度g=1（红色），SKL机器14上的像素算法的cpp，g=4（绿色）和g=16（蓝色）1095.3多核并行化：基于SIDBA4数据库的SKL1 41104内核上的平均cpp和可变性（cpp max和cpp min）5.4多核并行化：4个计算机内核上大小为2048 2048且g= 1的随机映像的全局cpp与密度（%）的组合SKL1 41125.5多核并行化：4个计算机内核上大小为2048 2048且g= 4的随机映像的全局cpp与密度（%）的组合SKL1 41125.6多核并行化：对于4个机器内核上大小为2048×2048且g= 16的随机帧，SKL1×41125.7多核并行化：用于2048× 2048图像大小和粒度的cpp在IVB2×12113的5.8多核并行化：对于大小为4096×4096（左）和8192×8192（右）的映像，cpp d作为24个IVB25.9相关分量分析：LSLRLE的cpp与最小值的比值对于粒度g=1（红色），在机器IVB2 12上的像素算法的cpp，g=4（绿色）和g=16（蓝色）1155.10 多核并行化：基于SIDBA4数据库的24个IVB 2内核的平均cpp和可变性（cppmax和cppmin）121155.11 多核并行化：24个计算机内核中大小为2048 2048且g= 1的随机映像的全局cpp与密度（%）的组合IVB2 121175.12 多核并行化：24个机器内核中大小为2048×2048且g= 4的随机帧的IVB2×12117图列表12××××××××××××××××××←→××5.13 多核并行化：24个计算机内核上大小为2048 2048且g= 16的随机映像的全局cpp与密度（%）的组合IVB2 121175.14 多核并行化：大小为4096、4096、g=1（顶部）、g=4（中间）和g= 16的随机图像的全局cpp组成与密度（%）（底部）在机器IVB2 12118的24个核心上5.15 多核并行化：大小为8192×8192且g=1（顶部）、g=4（中间）和g= 16的随机图像的（下）在机器IVB2×12118的24个内核上5.16 多核并行化：用于2048× 2048图像大小和粒度的cpp在60个IVB4 15120核上，g奏效于{1，4，16}和cpp d，取决于粒度5.17 多核并行化：对于大小为4096、4096（左）和8192、8192（右）的映像，cpp d作为60个IVB4 15内核上粒度的函数1225.18 相关分量分析：LSLRLE的cpp与最小值的比值对于粒度g=1（红色），在机器IVB4 15上的像素算法的cpp，g=4（绿色）和g=16（蓝色）1225.19 多核并行化：基于SIDBA4数据库的60个IVB 4内核的平均cpp和可变性（cppmax和cppmin）151225.20 多核并行化：60个计算机内核中大小为2048 2048且g= 1的随机映像的全局cpp与密度（%）的组合IVB4 151245.21 多核并行化：60个计算机内核中大小为2048 2048且g= 4的随机映像的全局cpp与密度（%）的组合IVB4 151245.22 多核并行化：60个计算机内核中大小为2048 2048且g= 16的随机映像的全局cpp与密度（%）的组合IVB4 151245.23 多核并行化：大小为4096、4096、g=1（顶部）、g=4（中间）和g= 16的随机图像的全局cpp组成与密度（%）（底部）在机器IVB的60个核心上4 151255.24 多核并行化：总cpp的组成与密度（%）对于大小为8192×8192且g=1（顶部）、g=4（中间）和g= 16的随机图像5.25（下）在机器IVB4×15125的60个核心上cpp作为机器上粒度为{1，4，16}的图像大小的函数IVB4×15，具有15、30、45或60个活动核心1286.1MPAREP：de l’image (E)6.2MPAREP：最小传播掩模e5min+（e1，. ... ... （9）........... 1336.3传播速度：5帧5满，需要5次传播迭代以6.4传播速度：在5 -5螺旋的情况下，传播的13次这是确保稳定性所必需的6.5由于扫描方向引起的传播速度不对称1366.6在直接和反向通道中将标签传播6.7稳定MPAR EP算法（红色）、MPAR F算法（绿色）和MPAR FB算法的标签图像所需的迭代次数，用于图像大小为128×128，取决于密度137