众包和预测分析：实现实用和可重复的自动调优

众调：通过众包和预测分析阿卜杜勒·瓦希德·梅蒙引用此版本：阿卜杜勒·瓦希德·梅蒙众调：通过众包和预测分析实现实用和可重复的自动调优。人工智能UniversitéParis Saclay（COmUE），2016.法语NNT：2016SACLV037。电话：01395556HAL Id：tel-01395556https://theses.hal.science/tel-013955562016年11月10日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire编号：2016SACLV037《医生的故事》DEL’U“UECOLE DOCTORALE N ° 580Sciences et technologies de l'information et de la communicationParM.阿卜杜勒·瓦希德·梅蒙众调：通过众包和预测分析Thèse présentée et soutenue à Versailles，le 17 Juin2016：评审团组成：巴图·丹尼斯先生巴图·丹尼斯先生巴斯托·塞德里克先生Bordeaux Universeur ， BordeauxUniverseur，斯特拉斯堡CASTRO Pablo de Oliveira凡尔赛大学会议硕士HEYDEMANN Karine Mauettre de conféécement，Université Pierre et Marie Curie MonsieurJALBY William Mesquerseur，Université de Versailles法国cTuning基金会FURSIN Grigori Chercheur先生特别报告员特别报告员Co-directeur de thèse巴黎-萨克雷大学Espace Technologique/Immeuble DiscoveryRoute de标题：Crowdtuning：Auto-tuning Pragmatique et Reproductible via Crowdsourcing et AnalysesPrédictivesMots clés：réglage automatique de compilateur，gestion des connaissances，reproductibilitédes ex-périmentations，l'optimization du programme par crowdsourcing，automatique，partagede code et des données简历： Leréglagedesexistiquesd'optimisation de compilateurpour de multiple ciblesouimplémentationsd'unemêmearchitectureestdevenu.此外，这个问题是一个普遍的问题，它是一种特殊的现象，而且没有必要重复。Enfin，des erreurs dechoix de paramétrage d'Escheristiques sontfréquentes en raison du grand nombre depossibilités d'optimization et des interactionscomplex entre tous les composants matériels etlogiciels. La prise en compte de multipleexigences，comme la performance，laconsommation d'énergie，la taille de code，la fiabilité et le cobalt，peut aussi nécessiter lagestion de plusieurs solutions candidates.Lacompilation itérative avec profil d'exécution（profiling feedback），le réglageautomatique（auto tuning）et l'apartissageautomatique ont montré un grand potentiel pourrésoudre ces problèmes.例如，我们的avonsutilisés avec succès pour concevoir le premiercompilateur qui utilizing l'optimizationautomatique de code.Il s'agit du compilateurMilepost GCC，whiadopted automatiquementles meilleures optimisations pour plusieursprogrammes，donnéeset architectures en sebasant sur les caractéristiques statiques etdynamiques duprogrammes.Malheureusement，son utilisationen pratique，a été très limitée par le tempsd'estissage très long et le manque debenchmarks et de données représeniès.此外，“黑色木材”的处理模式不能代表与程序或架构的特性和最佳优化相关的因素。在这一点上，我们提出了一种新的方法论和一种新的基于集体思维（cM）的外部系统目标是使不同的基准、入门者、汇编者、外部人员和其他对象共同参与，使参与性的贡献 正式 化和 便利 化。 Une constrainte est lareproductibilitédesexperimentationspourl'ensemble des utilisaplisaplets et platformes.Notre cadre de travail open-source et notredépôt（repository）public permettent de rendreleréglageautomatiqueetl'apartissaged'optimisations practicable.此外，cM还允许社区验证结果、参与者和模型，以便进行预防 。 cMpermetaussidefournirdesinformations utiles pour l'amélioration et lapersonnalisationdesmodulesderéglageautomatique et d'automissage ainsi que pourl'amélioration des modèles de prévision etl'identification des éléments manquants.通过对劳动干部的分析和评价，我们提出了一个有效的、孤立的、有助于提高模型预测精度的主要特征的协同因素的识别方法。同时，自动化规则的正式化和复杂性的降低技术标准的永久性。Ceci permet de se contenterd'unensembleminimald'optimisationspertinentes ainsi que de benchmarks et dedonnées我们将在欧盟FP6里程碑项目中以及与意法半导体合作的HiPEAC阶段中，收集大量实验结果、基准测试结果和入口数据，请访问http://c-mind.org巴黎-萨克雷大学Espace Technologique/Immeuble DiscoveryRoute deCrowdtuning：通过众包和预测分析实现实用和可复制的自动调整关键词：编译器自动调优，知识管理，可重复的实验，众包程序优化，机器学习，代码和数据共享由于大量的可用设计和优化选择、所有软件和硬件组件之间的复杂交互以及对性能、功耗、尺寸、可靠性和成本的多个严格要求，针对快速发展的硬件调整通用编译器优化算法或优化软件已经变得不可容忍地复杂、特别、耗时且容易出错。迭代反馈导向编译、自动调优和机器学习等技术在解决上述问题方面表现出很大的潜力。例如，我们成功地使用它们来启用世界上第一个基于机器学习的自调优编译器Milepost GCC，该编译器基于静态和动态程序功能自动学习跨多个程序、数据集和架构的最佳优化。遗憾的是，由于培训时间很长，缺乏具有代表性的基准和数据集，其实际使用非常有限。此外，“黑盒”机器学习模型本身无法全面了解特征和最佳优化之间的相关性。在这篇论文中，我们提出了第一个知识方法和框架，称为集体思维（cM），让社区共享各种基准，数据集，编译器，工具和其他工件，同时在许多用户（平台）之间以可重复的方式进行我们的开源框架和公共优化存储库有助于实现自动调优和机器学习。此外，cM让社区验证优化结果，共享意外的运行时行为或模型错误预测，提供有用的改进反馈，自定义常见的自动调整和学习模块，改进预测模型并找到缺失的功能。我们对所提出的框架的分析和评估表明，它可以有效地暴露，隔离和协作识别有助于模型预测准确性的关键特征。与此同时，自动调优和机器学习的形式化使我们能够持续应用标准的复杂性降低技术，以留下最小的一组有影响力的优化和相关功能，以及真正具有代表性的基准和数据集。我们在http://c-mind.org上发布了大部分实验结果、基准测试和数据集，同时在欧盟FP6MILEPOST项目和意法半导体HiPEAC实习期间vii献给我的家人和朋友出版物ix[1] GrigoriFursin、Yuriy Kashnikov、Abdul Wahid Memon、Zbigniew Chamski、OlivierTemam、Mircea Namolaru、Elad Yom-Tov、Bilha Mendelson、Ayal Zaks、Eric Courtois 、Francois Bodin 、 Phil Barnard、 Elton Ashton、 Edwin Bonilla 、John Thomson、Christo-pher Williams和Michael F. P.Milepost gcc：支持机器学习的自调优编译器International Journal of Parallel Programming，39：296-327，2011. 10.1007/s10766-010-0161-2。[2] Grigori Fursin ， Abdul Wahid Memon ， Christophe Guillon ， and AntonLokhmotov.集体思维，第二部分：走向性能和成本意识软件工程作为一门自然科学。arXiv预印本arXiv：1506.06256，第18届并行计算计算机国际研讨会（CPC[3] 阿卜杜勒·瓦希德·梅蒙和格里戈里·富尔辛。众调：使用预测建模和众包将自动调优系统化 。 在 PARCO 小 型 研 讨 会 上 ， 关 于 “Ap-application Autotuning for HPC（Architectures）”，慕尼黑，德国，2013年9月。共享的人工产物所有与集体思维实验有关的基准、数据集和工具都已在c-mind.org/repo上共享，供社区验证。确认xi首先，我感谢博士的科学和技术支持Grigori Fursin成功地完成了这篇论文。在我的整个研究工作中，他一直非常友好和合作。 他在优化编译器、机器学习、自动调优软件和实验再现性领域的丰富专业知识从一开始就成为我灵感的源泉。他的不断支持和协调总是让我在正确的道路上我的博士。 我祝愿他的职业生涯一切顺利。我感谢教授。感谢我的论文指导威廉·杰尔比在科学和管理上的支持。 他礼貌的态度和合作对我来说是一个巨大的鼓励。我要感谢巴勃罗·德·奥利维拉、克里斯托夫·吉隆、乌马尔·阿里·汗、克里斯-蒂安·贝尔廷、伊万·鲁克斯、尤里·卡什尼科夫和阿卜杜勒-哈吉·马祖兹，感谢他们在我的研究工作和论文撰写过程中给予我技术和道义上的支持 他们一直是我的好朋友和导师在我的博士学位。我也非常感谢HEC1，巴基斯坦授予我硕士学位，导致博士奖学金和HiPEAC2为我提供研究资助，在法国意法半导体进行研究，从2013年8月至12最后，我感谢我的父母，家人和朋友在我博士期间不断的精神支持。我希望我能告诉他们我有多爱他们。1高等教育委员会2欧洲高性能和嵌入式架构与编译卓越网络内容xiii1介绍11.1介绍11.2动机81.3合作研究和实验91.4集体思维：合作实验101.5现实生活中的激励示例131.6研究目标181.7论文贡献191.8论文组织202背景. 232.1一.导言. 232.2基础知识232.3优化编译器252.3.1优化转换252.4迭代编译（自动调优）292.5用于调优编译器优化的机器学习312.5.1决策树322.5.2K-最近邻（KNN）332.5.3支持向量机（SVM）2.6实验crowdsouring2.7摘要363自动调谐滤波373.1一.导言. 373.2实验装置373.2.1第37章3.2.2优化383.2.3平台39XIV内容3.2.4基准和实验393.2.5集体优化数据库403.3多目标经验迭代优化403.4摘要474MILEPOST GCC：通过机器学习494.1导言.494.1.1里程碑自适应优化框架504.1.2Milepost GCC和交互式编译接口514.1.3静态程序功能534.2使用机器学习预测优化遍数544.2.1概率机器学习模型574.2.2Transductive机器学习模型604.3生产应用的现实优化场景614.4摘要645使用Collective Mind65实现众包编译器自动调优5.1一、导言. 655.2集体思维方法655.2.1跨学科协作方法5.3Collective Mind基础设施和存储库675.3.1数据和参数描述和分类705.3.2OpenME接口用于细粒度分析、调优和调整。735.4工具和库的多个版本共存745.5摘要756众包特征学习和模型改进6.1一、导言. 776.2公共研究设想和实验管道6.2.1验证编译器自动调优（迭代编译）796.2.2验证机器学习（分类和预测建模）806.3学习数据集特征以启用自适应软件856.4摘要887结论和今后的工作. 88A 生殖实验93A.1 Grid5000框架93内容xv内容A.1.1Grid5000上的实验设置94A.2 共享人工制品以实现再现性96A.2.1Flags剪枝96A.3 使用移动设备的众包自动调谐98Bibliography参考书目99图目录xvii1.1传统计算机工程与 我们的合作平台...............................................................................111.2使用Hopfield神经网络的模式识别、图像滤波和字符降噪的概念示例141.3我们在神经网络研究中使用的各种硬件，软件，开发工具和优化的一小部分161.4逐步和手动制作的建议作为决策树的示例，为我们的神经网络提供最佳性能和成本182.1编译器操作的阶段242.2mc.codelet的CFG272.3通过启用和禁用各种转换实现的加速上述默认情况下，在-O3处启用列出的转换。............................................................292.4反馈指导的迭代编译302.5决策树-falign-functions优化332.6使用KNN算法进行342.7支持向量机3.1优化标志及其参数的演变383.2使用迭代编译的最大执行时间加速413.3迭代编译期间的加速比分布423.4迭代编译期间AMD平台上的加速比分布443.5优化案例的代码大小改进和编译时间加速453.6使用具有均匀随机分布的迭代编译获得95%的可用加速所需的迭代次数454.1开放式框架可自动调优程序并改进默认优化算法514.2GCC交互式编译接口：a）原始GCC，b）里程碑GCC使用ICI和插件52XVIII图目录4.3为给定程序获得最佳性能的优化比较554.4基于静态程序特征的所有程序的欧几里德距离584.5AMD和Intel59上的迭代编译加速4.6ARC上迭代编译的加速（i）随机搜索策略，以及（ii）里程碑特征学习模型614.7为ARC学习的决策树的顶层。...............................................................................624.8执行时间加速（a）、代码大小改进（b）和编译Intel63上BerkeleyDB的时间加速比（c）5.1对集体思维框架和知识库的高层次描述（cM）685.2概念性地描述了当前的特设实验715.3基于事件和插件的OpenME接口746.1总结所提出的合作方法和实际的buildbot。786.2众包优化时执行时间与代码大小的变化图像角点检测应用80的步骤6.3覆盖共享代码和数据集样本的几种不同的优化组合826.4自动检测相关特征以预测优化聚类846.5在社区的帮助下检测缺失的数据集特征866.6意外行为有助于识别和共享缺失的功能。........................................................................866.7从cM插件组装的性能和成本感知自调优软件的概念。...............................................87表的列表xix3.1 Milepost GCC标志的最佳组合，以改善执行时间，代码大小和编译时间464.1Milepost GCC V2.1中当前可用的静态程序功能列表566.1GCC中一些性能最好的优化标志组合。816.2使用具有完全交叉验证的优化SVM时的预测精度分别来自以前和目前的工作83