为了获得的目的图卢兹大学博士学位发布人：图卢兹国立理工学院（INP Toulouse）学科或专业：网络、电信、系统和体系结构提交人和支持人：内斯林·巴达奇2016年5月27日星期五标题：机载模块化航空电子系统的时间分配博士学校：图卢兹数学、计算机科学、电信（MITT）研究单位：图卢兹计算机科学研究所（I.R.I.T.）论文主任：M.克里斯蒂安·弗拉布尔M.让·吕克·沙尔巴格报告员：M. Alexandre Caminada，贝尔福蒙贝利亚尔大学技术学院M.艾曼纽·格罗洛恩斯玛·波蒂埃评审团成员：M. Emmanuel Grolleau，ENSMA POITIERS，总裁M. Benoit Viaud，艺术家，成员M. CHRISTIAN FRABOUL，INP TOULOUSE，成员M. JEAN LUC SCHARBARG，INP TOULOUSE，成员KATIA JAFFRES RUNSER女士，INP TOULOUSE，成员谢谢你首先，我要感谢我的论文导师Christian Fraboul，以及我的导师Jean-Luc Scharbarg和KatiaJaffres-Runser，没有他们，我感谢他们的耐心、热情和信任。我非常感谢ISAE-ENSMA教授和普瓦捷LIAS成员Emmanuel Grolleau，我还要感谢ArtalTechnologies航空业务部门负责人Benoît Viaud同意我对他们在论文答辩后的讨论中提出的建设性意见和观点表示感谢。感谢Katia和Emmanuel在她的博士论文期间感谢亚明的讨论，让我从哲学的角度来我要感谢再次感谢你们两个的好心情和效率-能力。一个想法的所有成员的IRT团队和所有的人，我分享了咖啡，膳食，笑声，小和大的夜晚和宝贵的时刻：伊曼纽尔，Andès-Luc，让蒂安，朱利安，Riadh，Béatrice;我的同志和现在的朋友JB，雷诺，克莱门特，阿齐兹，艾米莉我要感谢图卢兹的居民，感谢他们的梦之队，感谢他们的好心情，感谢他们在湖边散步，感谢他们在阳光下的酒吧聚会：Christophe，Yvan，Adrien，Emilie，Marj，Sandra，Pierre，Magalie，Ren，Thomas，Ed。感谢"室友"，他们在我读博士的时候照顾我，还有一份全职工作。你知道如何让我快乐与圣Nectaire，自制面包，国王的膳食，所有美丽的时刻和坚定不移的支持。我非常感谢你。一个特别的想法芭芭拉，我的bb，我的chtimi为她的爱和她的黄金友谊。J’espère 致我一生的朋友萨那、卡苏、阿梅尔、马内尔、纳西巴、胡达。你们是最棒的!最后，我必须衷心感谢我的家人，特别是我的父母，感谢他们的支持和鼓励，以及我的兄弟萨米、雷达和贾利尔，他们推动了我的前进。我0. 谢谢你。并支持我的选择。我的小姐姐塔拉和露露。最后，我最后一次感谢你，查理。如果没有你敏锐的眼光和批判性的判断力，这份手稿就不会是现在的样子但最重要的是，在这些年的劳动中，你陪伴着我，使我能够自由地献身于我欠你太多了，谢谢ii.摘要在过去的十年里，实时嵌入式系统已经从集中式架构发展这一发展使得通过使用分布式计算器（或处理模块）以及通过定义标准化的通信和服务接口来引入更多的功能成为可能本文以基于ARINC 653和ARINC 651标准的集成模块化航空电子设备（IMA）为例向模块化体系结构的转变引入了新的设计挑战，主要与满足应用程序的时间限制有关这些时间限制是为了确保部署在这些模块化系统上的应用程序正常运行例如，通过定义分布在远程计算机上的两个应用程序之间允许的最大通信延迟，可以模块化系统的设计模块化系统的规模和复杂性不断增加，这就要求实施在本文中，我们主要关注给定计算器上的功能分布，我们确定了分布式嵌入式功能的执行周期，这些功能被描述为通信分区，保证了应用程序的时间限制，并提供了高度的系统可扩展性我们的方法考虑到了电子通信网络的可变（但有限）穿越时间。本文的第一个贡献是将IMA模块化系统的集成问题重新表述从在检查时间约束的所有时间分配中，我们执行多标准搜索，该搜索联合优化计算负载的标准。通信的时间和时间裕度这两个标准的定义是本文的第二个贡献是提出了两种适用于我们问题的多准则搜索启发式。解决这个问题是困难的，因为有效时间分配的数量因此，大量的允许时间分配不允许在没有适当工具的帮助下提取最令人满意的解决方案。在这项工作中，我们建议对于这两种算法，问题的基数通过在每个模块处的局部优化阶段来减小局部优化的第一步我们表明，对于大型系统，这两种启发式都应用于IMA系统的简化示例 这些解决方案清楚地显示了所需的计算器负载可扩展性和网络中的裕度特征本文的最后一个贡献是对帕累托最优解进行了详细的分析。该分析突出了不同类别的帕累托最优解，每个类别代表负载和网络边缘之间的不同折衷了解这些解决方案类别后，摘要从实时嵌入式系统体系结构到模块化体系结构的演变通过使用分布式计算机和通信接口以及标准化服务引入了更多的功能。本论文的重点是ARINC 653和ARINC 664标准第7部分中标准化的集成模块化航空电子架构（IMA）。在其他方面，这一发展引入了新的设计挑战，即为此类系统的适当功能应用强制性的定时约束。模块化系统的设计是一个有约束条件的集成问题，它涉及一些困难的问题（设计、空间和时间资源分配）。这些困难为可扩展集成和设计工具的实现提供了这些工具的设计是本文的目的。我们主要感兴趣的是将定时资源分配给全球分布式系统。特别是，我们确定了分布式嵌入式函数的执行时间，以确保应用程序的定时限制，并提供高度的系统可扩展性，给定仪表上的航空电子函数的分布。我们的方法考虑了通信网络的时间上界可变性本文的第一个贡献是将IMA系统的集成问题表述为具有时间约束的多准则优化问题。对于将航空电子功能分发到计算机，IMA分区的执行周期是为了确保传输数据的新鲜度和不丢失在满足时间限制的所有临时分配中，我们执行多标准搜索，以优化计算机负载和网络中的时间裕度。这两个标准有助于将来扩展所提议的体系结构。本文的第二个贡献是提出了两种适合我们问题的多准则搜索启发式。请注意，有效临时分配的数量随其上托管的模块和分区的数量呈指数增长我们提供了两种多准则优化算法：（i）EXHAUST，最优穷尽搜索算法，（ii）TABOO，一种基于Tabu元启发式的近似算法。对于这两种算法，问题的基数通过每个模块的局部优化阶段来减小，这是由两个所选优化度量的线性使得可能的这第一个局部优化步骤有助于使用EXHAUST解决中等大小的问题以达到最优。我们证明，对于大型系统，TABOO算法是一个非常好的候选算法，因为它在合理的时间内提取出令人满意的解，同时测试了有限数量的有效分配。这两个启发式应用于IMA系统示例。对得到的解的分析使我们能够强调两种算法得到的帕累托最优解的质量它们具有可扩展性、并发负载最小化和网络裕度最大化的预期特征。我们的最新贡献在于对使用EXHAUST和TABOO获得的权衡解决方案进行了详细分析该分析强调了系统负载和网络裕度之间具有不同折衷的帕累托最优解的不同类别这些解决方案的知识允许系统集成商从提供搜索标准和网络负载裕度之间的折衷的解决方案类中选择解决方案vii目录谢谢你我摘要iii.摘要V目录七图表十一图片列表十三1一般简介12工业和科学背景52.1实时嵌入式系统的模块化. ... ... ... ... ... ... ... ...... ... ...62.1.1模块化航空电子架构：IMA。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...82.1.1.1功能级别和逻辑通信IMA-ARINC 65392.1.1.2IMA-ARINC 653系统级。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...122.2IMA模块化系统的设计... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...162.3模块化体系结构的时间验证... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...192.3.1端到端功能约束和时间表。... ... ... ... ... ... ... ... ... ... ... ...192.3.2分区的排序。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...202.3.3实时调度的属性。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...2.3.4具有严格非抢先周期的实时关键系统中的调度。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...21222.4评估端到端通信延迟。... ... ... ... ... ... ... ... ... ... ... ... ...262.4.1通信延迟的上限。... ... ... ... ... ... ... ... ... ... ... ...262.4.2最坏情况下的确切通信延迟。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...272.5模块化体系结构集成的辅助方法... ... ... ... ... ... ... ... ... ... ...272.5.1主要方27viii法... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...2.5.2相关工作说明。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...28ix2.6L’allocation temporelle : un problème d’optimisation multicritère2.7结论323IMA 35中时间分配问题的公式化3.1IMA 36系统的建模3.1.1CPM 37的型号3.1.2分区模型3.1.3通信模型373.1.4所研究示例的应用参数3.2端到端时间表分析383.2.1端到端功能延迟393.2.2端到端通信延迟403.3问题的表述423.3.1问题的变量423.3.2实时应用程序约束423.3.2.1对数据新鲜度的约束3.3.2.2对更新453.3.2.3实时全局约束473.3.2.4说明性示例483.3.3IMA48的系统限制3.3.3.1目标分区期间的协调493.3.3.2有效调度的构建3.4时间分配的离散公式3.5结论554用于评估时间分配的度量4.1介绍性示例574.1.1模块充电M1594.1.2目标分区的通信裕度P2594.2基本指标614.2.1模块M A 62的充电4.2.2目标分区的通信裕度624.2.3一个模块的通信裕度4.2.4s1和s2的基本指标比较644.3全球系统654.3.1为IMA 65系统充电4.3.1.1IMA系统中模块的平均负载......................................................................654.3.1.2IMA 65系统的最大负载4.3.2全球网络指标664.3.2.1全局网络利润的平均值..............................................................................66材料表x材料表4.3.2.2整体最差情况网络边缘..............................................................................674.3.2.3拟议指标的应用674.4结论695IMA 71中时间分配的多目标优化5.1多目标优化问题5.1.1解决方案和变量725.1.2指标的选择725.1.2.1本地指标的选择735.1.2.2全球指标的选择735.1.3多准则优化735.1.4多目标时间分配问题的公式化5.2建议的多目标启发式775.3模块78中的局部优化步骤5.3.1用模块79求帕累托最优解的算法5.3.2考虑MAF的相似性815.4全局优化：EXHAUST82算法5.5全局优化：多准则TABOO82算法5.5.1禁忌研究835.5.2TABOO 84启发式的工作原理5.6结论876建议启发式的验证896.1测试架构896.1.1示例1：15 CPM906.1.2示例2：20 CPM906.2Pareto 90前沿分析工具6.2.1世代距离916.2.2等效类6.3局部优化的有效性6.4最优帕累托前沿95的分析6.4.1等效类的分析6.4.2同一等价类的解的分析6.4.3不同最优帕累托986.5升级到6.5.1示例1：搜索TABOO1016.5.2TABOO105的10次迭代解分析6.5.3TABOO停止标准6.5.4示例2：搜索TABOO1106.6结论1157结论和展望1177.1结论1177.2前景119来文清单121xi参考书目123xii材料表图表2.1功能级别和逻辑通信IMA-ARINC65392.2周期性和严格周期性任务（Liu和Layland模型 [1]）2.3采样和排队模式122.4IMA-ARINC系统级653132.5MAF 13的插图.........................................................................................................................2.6VL 15的操作.............................................................................................................................2.7体系结构示例...........................................................................................................................2.8空客A380上的分布式IMA架构2.9IMA 17模块化系统的主要设计步骤......................................................................................2.10 端到端功能延迟2.11 两级调度2.12 AUTOSAR可运行对象放置的最小加载算法[2]252.13 [ 2 ] 26中LL算法的排序示例..................................................................................................2.14 使用ScatterD工具的优化过程................................................................................................2.15 IMA的时间分配方法。...........................................................................................................333.1具有4个CPM的IMA架构示例................................................................................................3.2端到端功能和通信延迟3.3通信中违反新鲜度参数3.4财产的申请1443.5通信中的更新覆盖3.6财产的申请2463.7一种构造具有谐波周期的MAP的算法模块513.8最少加载53的MAF中的分区排序算法3.9MAF 53的序列示例.................................................................................................................3.10 两种可能的时间4.1具有4个CPM的IMA架构示例................................................................................................4.2S1和S2中的可用插槽xii图表4.3计算通信的裕度δ.....................................................................................................................4.4目的地期间的利润4.5分区P263的度量σ24.6时间分配的候选解决方案。最好的妥协是红色695.1优势解（点）和非优势解（叉）755.2帕累托76等级分配算法...........................................................................................................5.3Tabou 85多目标启发式算法...................................................................................................6.1在不减少类似MAF的情况下评估具有局部优化的解-示例1946.2使用局部优化评估解决方案，减少类似的MAF956.3具有降低的MAF的最佳帕累托前沿和不具有降低的MAF的最佳帕累托前沿-实施例1966.4FPT解决方案在等效类中.........................................................................................................6.53类最优帕累托等价的比较.....................................................................................................6.6对例1中禁忌搜索的10次迭代的解进行评估。1026.7对例1中禁忌搜索的76次迭代的解的评估。1036.8对例1103中禁忌搜索的300次迭代的解的评估6.9最优解类：穷尽搜索和禁忌搜索300次迭代-示例11046.10 与最坏情况前线的比较1056.11 TABOO算法106的10次迭代的等价类.................................................................................6.12 3个最优帕累托等价类之间的比较.......................................................................................6.13 EXHAUST和TABOO中过采样的比较1076.14 TABOO 300次迭代中实际前端大小的演变-示例11086.15 解的评估和最优帕累托解的表示;例2中的EX- HAUST 1116.16 对例2中禁忌搜索的10次迭代的解进行评估。1126.17 对例2113中禁忌搜索的100次迭代的解的评估6.18 对例2113中禁忌搜索的300次迭代的解决方案进行评估6.19 最优解类：穷尽搜索和禁忌搜索300次迭代-示例2114xiii图片列表3.1源分区的应用程序设置源分区3.2示例38中分区的执行时间.......................................................................................................3.3网络延迟的限制3.4通信新鲜度参数3.5对目标分区的周期的约束3.6图3.9的顺序图4.1E2Ew，以M1为目标的通信的新鲜度参数和裕度（T2，T3，T4）=（40， 40，20）614.2E2Ew，以M1为目标的通信的新鲜度参数和裕度（T2，T3，T4）=（30， 30，30）614.3基本指标4.4全球指标6.1实施例1的参数和组件.............................................................................................................6.2实施例2的参数和组分.............................................................................................................6.3EXHAUST算法的局部优化和相似性简化性能....................................................................6.4通过多目标详尽搜索的一些最优解-示例1976.5TABOO在不同迭代中的性能-示例11046.6TABOO（10次迭代）和EXHAUST的平均过采样度示例11076.7通过多目标禁忌搜索的一些最优解-示例2115xiv表的列表xv1一般简介嵌入式系统越来越多地采用所谓的模块化架构它们由一组通过实时网络相互连接的计算机组成这种模块化架构允许嵌入式系统的扩展。事实上，旧的联合体系结构不允许添加越来越多的新功能。它们也不允许以 这减少了本论文的重点是基于ARINC 653和ARINC 664第7部分标准的一体化模块化航空电子系统（IMA）。考虑到这一点，它基于硬件体系结构的标准化和共享一个计算机的应用程序的健壮分区L’application est donc vue comme un ensemble de partitions logicielles 这种类型模块化机载架构代表了航空电子（或汽车）系统的重大发展，但代价是增加了复杂性这些系统至关重要，它们的时间验证对于确保用户安全至关重要为此，必须开发支持此类系统设计的方法，以在开发阶段可靠地正如我们将看到的，模块化系统的设计一个主要的困难是这些模块化系统的异步性质计算机在操作中不同步因此，我们不能使用公共时钟进行时间验证1.一般性介绍2系统的孔隙率这种异步性有助于另一方面，它使系统的验证变得复杂，而系统的验证对于所有可能的发射和偏移场景都必须是可靠的目前，关键嵌入式系统的设计依赖于 这些专家拥有有限的工具来帮助配置嵌入式应用程序的运行时间，以集成复杂的系统。模块化航空电子系统由大约100个计算单元组成，这些计算单元交换大约1000个流。计算和通信资源的共享使得计算所支持的函数的时间属性变得复杂因此，资源共享要求在选择适当的集成策略时考虑整个系统。所有这些都必须考虑到组成应用程序的功能的执行约束这些限制使得很难保证系统对未来发展的容忍度：在更改或添加新功能或硬件的情况下这些重新配置是必要的，以确保数据的一致性，并满足通过网络执行功能和交换的实时约束一些研究工作已经解决了实时体系结构的规模和集成问题。这项工作将该问题作为空间分配和分布式调度问题来解决在这些工作中，如果分配优化了集成商所期望的一个或多个性能标准（通常，计算器的负载被最小化，等等），则选择分配这些解决方案是复杂的，在本文中，我们建议不将设计表述为空间分配问题，而是将其表述为时间分配问题，空间分配问题可以由输入/输出单元的强位置约束来我们将采用可能不满足系统实时约束的第一解决方案，而不是在所有可能的系统中寻找最终系统。然后，我们将尝试修改该解的时间特性（这里是函数的周期性），以满足实时约束并提出接近最优的解研究的目的L’objectif de la présente thèse est l’aide à l’intégration des architectures temps réel avec laprise我们指出，通过端到端，我们感兴趣的是从传感器（向致动器启动数据源函数）约束通常涉及刺激和反应之间的响应时间IMA航空电子架构是本论文工作的研究案例，其中考虑了计算机上分区的空间分配已经完成我们的方法31.一般性介绍允许通过选择确保整个系统的正确实时行为的时间参数来细化所提出的尺寸调整方法为集成商提供了在L’objectif est de dimensionner le système de façonà éviter从分区在计算器上的空间分配开始我们将考虑端到端时间约束的时间分配问题表述在这个优化问题论文工作的计划和贡献这份手稿分为六章，首先讨论了这篇论文的科学背景，然后详细介绍了所提出的贡献第2章：工业和科学背景。 我们介绍了IMA航空电子设备的模块化架构。在回顾了基本原理之后，我们描述了设计这样一个系统的不同阶段我们介绍了嵌入式功能的空间分配的标准方法通过定义延迟和端到端约束，我们可以进一步提出分配选择对时间性能的影响问题最后，阐述了本文的不同目标。随后，本章回顾了最新技术水平的主要工作我们确定了最适合IMA模块化系统集成问题的解决方案的特征然后，我们总结了手稿其余部分中提出的研究的贡献第三章：IMA中时间分配问题的公式化。本文的第一个贡献是将积分问题表述这个问题被表示为一个组合优化问题，
我的内容管理
展开
