模块链自动组合问题的最短路径算法

81网址：http://www.elsevier.nl/locate/entcs/volume65.htmlLastPage页面模块链的自动组合Stavros Tripakis1VERIMAG，Centre Equation，2，rue de Vignate，38610 Gi eres，France摘要我们引入了一个模块组合的问题模块被视为带有输入和输出端口的“黑兼容性关系对哪些输入端口可以连接到哪些输出端口进行建模。我们给出了一组可用模块和一个目标模块。我们希望将可用模块连接到实现目标模块的链可以给出关于每个模块可以或应该在解决方案链中出现多少副本的成本可以在模块或端口或连接上给定该算法将问题转化为图中的最短路径问题。1引言考虑下面这个熟悉的情况。用户用Latex编写了一个文档，并希望将其转换为PDF。它可以使用两个可选的转换序列来实现，每个序列都涉及一组不同的工具：(i) 用latex命令编译.tex le得到.dvi le，再用dvips编译后者得到.psle，最后用ps2pdf将后者转换成.pdf le。(ii) 使用pdflatex直接将.texle编译为.pdfle。我们希望将上述过程自动化。也就是说，用户应该能够说类似于“我有一个.texle，我想从它获得一个.pdfle”的话，系统应该找到可用的工具来执行任务。自动化解决方案与手动解决方案相比具有许多优势它使用户不必知道所有相关的工具。根 据定义，它可以自动识别，并且独立于安装在给定系统中的工具集工作。 例如，如果pdflatex是如果在某台机器上没有安装刀具链，则会自动找到替代刀具链。1 电子邮件：tripakis@imag. fr。2002年由ElsevierScienceB出版。 诉操作访问根据C CB Y-NC-N D许可证进行。82如 果可能有一个以上的解决方案，用户可以通过确定优先顺序来选择一个。例如，pdflatex通常比ps2pdf产生更好的质量文档，因此应该尽可能优先使用它。在本文中，我们提供了一个框架和算法，产生自动化的可能性和效率。在第2节中，我们介绍了我们的框架，它由一组模块组成，代表软件或硬件组件。模块有一组输入和一组输出端口：端口代表模块可以接受的不同输入和它可以产生的模块可以组成一个链，只要考虑端口之间的某种兼容关系模块组合问题是，给定一组可用模块和一个目标模块，以及实现目标的可用模块链。我们还提供了这个基本模型的扩展扩展允许表达一种解决方案对另一种解决方案的偏好，或者更一般地，解决方案的成本扩展还允许我们表达约束，例如“使用模块M至少l次”或“不使用模块M0超过u次”。我们证明了一个重要的属性，即，没有模块应该出现超过k+ 1次的解决方案，其中k=iLi，和Li是所需的下限为每个可用的模块Mi。作为该性质的特殊情况，当对于所有iii= 0（即，没有明确要求模块），则如果存在解决方案，则存在最多使用每个可用模块一次的解决方案上述性质很重要，因为它意味着可能解的空间是有限的，因此，它的搜索可以自动化。在第3节中，我们提供了一个解决模块组合问题的算法，将其转化为图 上 的 最 短 路径 问 题 。 算 法 的 最 坏 情 况 复 杂度 为 O （ （ k+ 1 ） ）（n+m）），其中n是可用模块的数量，m是兼容性关系的大小。第四节讨论相关工作。2框架在我们的框架中，我们将模块视为一个“黑盒子”，它有一组输入端口和一组输出端口。例如，输入端口p tex可以表示Latex格式（.texles），输出端口q dviDVI格式，并且模块（fpte xg;fqdvig）可以表示Latex编译器。在上面的示例中，模块只有一个输入和一个输出端口在其他情况下，它可能有不止一个：例如，toolxv可以读取.gif、.tiff、.jpg以及其他格式，并可以生成各种输出。然后，xv工具可以由模块表示（fpgif; ptif; pjpg;：g;fqgif;qtif;qjpg;：g）：83jj+1设P是所有可能的输入端口的集合，Q是所有输出端口的集合。兼容关系C P Q定义了哪些输入端口可以连接到哪些输出端口。 在上面的例子中，C可以被定义为C=f（pte x;qte x）;（pgi f;qgi f）;（pjp g;qjp g）;：g。 Cd oes不包含（p tex; q gif）这一事实意味着仅生成.gif输出的模块不能连接到只接受.tex输入的模块我们给出了一组M1，M2，M3，M4 ， M5 ， M6，M7，M8，M9，M9，M9，M10，M11，M12，M13，M14，M15，M16，M17，M19，M19，M19。 Ea chm onMi是一对M i=（P i; Q i），其中P i P和Q iQ。也就是说，一个模块由它的一组输入端口Pi和一组输出端口Qi定义。单链是序列Mi1; Mi2;：：; Mim，使得：ij2f1;：;ng，对于j=1;：;m，对于每个j= 1;：;m1，存在q2Qi和p2Pi使得（p; q）2 C.后一个条件意味着链中第j个模块的某个输出端口与第（j+1）个模块的某个输入端口兼容 在下文中，我们将使用符号M i！Mj意味着模块Mi的某个输出与Mj的某个输入兼容，即：（1）（Pi;Qi）！（Pj;Qj）9p2Pj;q2Qi：（p;q）2C：请注意，同一个模块可能在链中出现多次，而有些模块可能根本不出现还要注意，对模块规范Mi=（Pi; Qi）的理解是，从Pi中的任何输入，模块可以产生Qi中的任何输出。这正是模块链的定义模块链可以看作是目标模块的实现。更准确地说，给定一个m个目标链（Pj;Qj），j=1;：;m，并且一个目标得到m个目标（P 0; Q 0），如果P 0P1和Q0 Q m.这意味着（P 0; Q 0）可以被当作一个“真正的”模块来使用：每次（P 0; Q 0）出现在另一个链中，它都可以被实现它的链替换，而不会有任何接口问题。定义2.1[模块组合问题（MCP）]给定(a) 一组输入端口P和一组输出端口 Q，(b) 一组可用的模块A=fM1;Mng，Mi=（Pi;Qi），PiP，Qi Q， i= 1;M n，(c) 目标模M0=（ P0; Q0）， P0P、 Q0Q，(d) 相容关系CP Q，和一个多个链Mi1;：：;Mim，ij2f1;：：;ng，假设该链实现该目标。2.1以MCP为模型我们可以很容易地在上面的框架中对介绍中介绍的"\Latex-to-PDF”示例进行建模，如图1所示 有四个可用模块latex、dvips、ps2pdf、pdflatex和一个目标模块user。84pdflatex用户.tex-胶乳.dv-i.ps-.pdf-.dvi-.ps-.tex-.pdf-.tex-.pd-fFig. 1. “Latex-to-PDF”示例。每个模块具有单个输入端口和单个输出端口。 端口被标记为使得当且仅当它们具有相同的标签时两个端口是兼容的。实现用户模块的两个可能的模块链如图2所示。2.2基本模型在本节中，我们将介绍对基本模型的一些有用的扩展。这些扩展增加了模型的表达能力，而没有给算法增加任何开销，我们将在下面的部分中展示。rst扩展允许用户表达解决方案之间的首选项（通常，可能有多个解决方案，如图2所示）。第二个扩展允许定义形式的要求\模块A必须包括在解决方案链”，或\不超过k个副本的模块B可以出现在解决方案链”。.tex-胶乳.dv-idvips.ps-ps2pdf.pdf-模块链1.tex-.pdf-模块链2图二. 两个实现\Latex-to-PDF”目标的模块链。2.2.1偏好约束由于可能有一个以上的模块链实现某个目标，因此允许用户定义优先顺序是合理的。pdflatexdvipsps2pdf85解决方案，以便选择最优选的解决方案。我们通过在问题的定义中包含成本函数来将其纳入我们的框架。有多种方法来定义成本函数。一种可能性是为每个可用模块Mi指定成本c（Mi），并将链的成本定义为链中出现的所有模块的成本之和。然后，在两个链之间，最优选的一个是成本最低的。对于Latex的例子，给ps2pdf比pdflatex更高的成本可能是合理的，因为前者通常产生较低质量的输出。另一种可能性是在模块的连接上而不是单个模块上定义成本函数例如，可能已知给定模块A在连接到模块B而不是模块D时工作得更好，即使将A连接到D也是可能的。然后，对于每对模A和B，使得A！B，我们可以定义一个成本c（A; B）。第三种可能性是在端口而不是模块上定义成本函数。例如，如果在将.jpg转换为.ps时，我们可以通过位图格式或.gif格式进行转换，则可以通过将任何位图端口的成本提高到非常高的程度来隐式地禁止任何中间位图对于成本函数的任何选择，模块链M j=（Pj;Qj），j=l，m的成本可以定义如下。 如果成本被赋予m个单元，则链的成本将是和j=1;：;mc（ M j） 。 如 果给 连 接 给 定 成 本 ， 则链 的成 本 将是 和 j=1; ： ： ： ;m1c（Mj;Mj+1）。 如果给prts给定成本，则设mc（Mj;Mj+1）为Mj的所有输出端口与Mj +1的输入端口兼容的成本的最小值。然后，链的成本将是和j=1;：;m1mc（Mj;Mj+1）。一旦链的成本被定义，那么我们可以修改MCP的定义来反映这一点：我们简单地要求找到一个实现目标的最小成本链。请注意，通常可能存在多个最小成本链（例如，当所有成本都设置为0时）。2.2.2模块可用性的上下界用户可能有理由明确要求将模块包含在解决方案链中，或者明确禁止它。此外，有些模块可能是不可复制的，在某种意义上，只有一个模块（或者最多给定数量的模块）可以在链中使用。禁止一个模块是很简单的：简单地将它从可用模块集中删除。在模上设置一般的上界和/或下界也可以很容易地合并到框架中：我们可以定义一个函数fb，它对每个模M分配一个区间fb（M）=[l; u]（如果没有下界，l可以是0，如果没有上界，u可以是1然后，在MCP的定义中，增加了模块M出现在2例如，当某些模块表示硬件组件时就是这种情况860JJ在模块链中至少l次且不超过u2.3解的一个重要性质下面的性质对于限制可能解的集合是必不可少的引理2.2设A是所有可用模块的集合，并且B=fB1;：;Bkg是所需模块的多集合（即，如果模A的下界是2，则B包含A的两个副本）。如果存在一个解决方案链，那么就存在一个解决方案链使得A中没有模出现超过k +1时间在。证据不失一般性，令=A1;：;A1。设存在某个模A2A，使得A在中至少出现k+2次.也就是说，为1; A;2; A;;k+2; A;k+3，其中i是的子链，其中j ij0。因为是一个解，所以对于i =1;：;k，每一个B i出现在中。也就是说，有一个函数f：f1;：;kg！ f2;：k+2g使得Bi2f （i）. 根据鸽子洞原理，存在j2f2;：;k+2g，使得对所有的i2f1;：;kg，f（i）6=j. 现在，考虑一下新的链条=1;A;2;A;;j1;A;j+1;A;;k+2;A;k+3：即，0 已通过移除 子链A.由于j; Aj 1，我们有j0 j j j.<我们认为0是一个有效解。实际上，它尊重所有的连通性约束：在j1之后仍然有模块A，在j+1之前仍然有模块A。它还包括B中的所有模块。现在，如果A中没有出现超过k+1次的模块，0，然后我们完成了：=0的情况。 否则，我们将继续缩短0，就像我们一样。由于的初始长度是nite，并且在每次迭代中至少减少1，因此该过程最终将停止，从而产生所需的。23算法在本节中，我们将提供解决模块组合问题的算法设可用模块为M i=（P i; Q i），i = 1;：; n，并且设目标模块为M0=（P0;Q0）。 F或i=1;：;n，设fb（Mi）=[li;ui]（回想一下，这些是模块可用性的下限和上限）。不失一般性，我们可以假设对于所有i，uik+ 1，其中k= il i：的确，如果u i> k +1并且存在一个使用多于k +1个模M i拷贝的解，那么我们通过引理2.2知道，也存在一个使用至多k+ 1个模M i拷贝的解，因此，我们可以将自己限制在这组解。87该算法的第一步是建立一个图G，如图3所示G有n+2个节点。标记为M i的每个节点对应于可用模块M i。节点S（称为初始节点）和F（称为最终节点）对应于目标模块的输入和输出。G的环构造如下：对于每个可用模块M i，使得M 0！ 从S到M i有一个链接。对于每个可用模块M i，使得M i！ M 0，有一个从M i到F的链接.对于每一对可用模块Mi，Mj，i6 = j，使得Mi！ M j，从M i到M j之间有一个链接.每一个M我是P。 1.一、每一个M节点. *H.S.T.我！M1M1 JHS.T. M 1！ Mi11-P. PqP1.PP-到每个Mi节点S.. *M2H.H.从每个Mi节点。1.FHjHS.T. M0！Mi..P. PqP1.S.T.我！M0*.M.*n HjH图三. 把主控制程序转换成图表。从图G的构造方式中，很容易看出，存在解链iG具有从S到F的路径，使得该路径访问每个节点Mi至少li次且至多ui次。这样的路径可以使用深度- rst搜索（DFS）在G上找到，具有以下附加规则：一个节点不能被访问超过u i次。仅当达到F并且堆栈包含每个节点Mi至少li次时才宣布成功。上述算法的最坏情况复杂度是O（（k+1）（n+m）），其中m是兼容关系C的大小（即，G中的边数）。这是因为在DFS期间，G的节点或边不能被访问超过k值得注意的是，在没有明确要求模块的特殊情况下，即对于所有i，li= 0，最坏情况的复杂度与MCP的大小成线性关系。我我88SÆÆ一公司简介？F- -一种@一每个链路在解决方案中使用一次。--在溶液中。3.1示例3.1.1\Latex-to-PDF”示例图4展示了我们的“Latex-to-PDF”示例的转换图G显示在图的左边，两个可能的解决方案（路径）显示在右边。第一个解决方案是按顺序访问节点S、latex、dvips、ps2pdf和F的路径。第二种解决方案是访问节点S、pdflatex和F的路径。边缘上的数字1表示？Æ- -一种Dvips-什么？1F在@ps2pdf在S F@@在在pdflatexR@溶液2见图4。 解决\Latex-to-PDF\”合成问题。3.1.2一个更复杂的例子另一个例子如图5所示 有三个可用的模块，A、B和D，并且要求D在解决方案链中至少出现一次，即l D= 1。那么，满足这个约束的最短链就是A！D！A！ B.注意，在这种情况下，k= 1，因此，引理2.2的上界k + 1 = 2由出现两次的模A获得BMBBBA@@一R@SBAF-BB D图五. MCP及其解决方案（假设需要模块D的一个--胶乳-解决方@Æ893.2考虑到最优性上面讨论的算法可以容易地被修改以考虑模块、模块之间的连接或端口的成本。它需要搜索满足上面给出的约束的最短路径，而不是任何路径。最短是关于适当的度量来理解的。例如，如果MCP将成本与模块相关联，那么我们将把相应的成本分配给图G的每个节点。如果成本与模块之间的连接相关联，则我们将相应的成本分配给G的每条边。然后可以使用标准的最短路径算法来找到最优路径。4相关工作自动化软件组合并不是一个新想法。诸如make之类的工具被广泛用于自动化编译或任何其他软件转换，考虑依赖关系等。这些工具与我们的方法的主要区别是，在make中，所有替代规则（即，可能的解决方案链）必须是先验已知的并且在生成文件中硬编码。另一个缺点是，在诸如make之类的工具中，硬编码备选解决方案中的首选项并不总是容易的。我们的工作也与架构描述语言（例如，参见[1]），以及软件体系结构（例如，参见[7]）和其它组件模型（例如，见[10]）。与其关注方法论，在获得一个明确界定的问题的自动和有效的程序LEM，具有明显的实际应用。我们也一直对"轻量级”方法感兴趣。我们的框架是故意简单：例如，它不能强加全局约束的解决方案和模块没有操作语义。这种简单性使得自动化在很大程度上成为可能。Ste en et al [8，6]和Kloukinas et al [3]的工作似乎与我们的工作最接近。[8，6]提出了一个基于线性时序逻辑的框架[5，4]。它们可以表达对链中模块顺序的约束（例如，A必须出现在B）之前，然而，不清楚是否可以表达偏好约束或模块数量的界限与我们的框架的另一个不同之处是，他们感兴趣的是获得所有可能的解决方案，表示为一个图。[8，6]没有报道其合成算法的复杂性。[3]中的问题是自动生成中间件体系结构的所有可能配置。在这里，也找到了所有可能的解决方案。他们的框架不限于线性体系结构，但是，解决方案中使用的组件数量是预先确定的，并且无法表达偏好约束。与Ste en等人一样，Kloukinas等人也使用了受模型检查和形式验证技术启发的算法。90与我们相关的框架也是组件建模语言Alloy的框架，它可以在一阶逻辑中执行自动分析[2]。分析是合理的，但不完整，因为逻辑是不可判定的。我们还不知道是否有可能在Alloy框架中表达某种类型的模块组合并将其自动化本文是文[9]中工作的继续。在那里，我们提出了一个不同的框架，允许任意的架构，而不仅仅是线性的（也就是说，解决方案不是一个链，而是一个图）。我们证明了这个问题是NP完全的，并确定了可以多项式求解的特殊情况（例如，当在解决方案中必须使用的模块集合是预先已知的时）。引用[1] www.sei.cmu.edu/architecture/adl.html的网站。[2] D. Jackson.自动化一阶关系逻辑。软件工程基础，2000年。[3] C. Kloukinas和V. Issarny。 自动化中间件配置的组合。 自动化软件工程，2000年。[4] Z. Manna和A.普努埃利反应与并发系统的时序逻辑：规范。Springer-Verlag，New York，1991.[5] Z. Manna和P. Wolper。从时序逻辑规范综合通信过程。 ACM TOPLAS，1984年1月[6] T. Margaria和B.好吧元框架中自动综合的无回溯设计规划。 软件工程的基本方面，1998年。[7] M. Shaw和D.加兰软件架构：新兴学科的观点。Prentice Hall，1996年。[8] B. Ste en，T. Margaria和M.冯德贝克。 从时间约束自动综合线性过程模型：增量方法。ACM/SIGPLAN软件自动分析国际研讨会（AAS'97），1997年。[9] S. Tripakis。 自动化模块合成，2001年。 未出版的文件。[10] R. van Ommering，F.范德林登，J克莱默，J马吉。消费电子软件的考拉组件模型。IEEE计算机，2000年3月。