最优指令控制的设计

《最优指令控制的设计》由会员分享，可在线阅读，更多相关《最优指令控制的设计（19页珍藏版）》请在金锄头文库上搜索。

1、最优化计算机指令控制设计摘要本文为了使计算机指令控制最优，建立了解决最优控制的整数规划模型。问题1，通过分析题意知，此问目标是求出使得所有部件得到控制的最少指令集合，约束为使各部件至少得到一次控制，建立了0-1整数规划模型，运用lingo软件求得最少的指令集合是2，4，7，11，12，17，18，19，20，28，29，30，31，共13条指令。问题2，此问目标变为求出使得所有部件得到控制的总长度最短的指令集合，约束条件与问题1相同，同样的建立0-1整数规划模型，运用lingo软件求得总长度最小的指令集合是1，3，4，5，6，7，10，14，17，19，21，22，23，24，总长度为360。

2、问题3，首先介绍了单纯形法和穷举法，再根据这两种算法的原理运用Matlab软件来求解问题，得到的最优解同问题1和问题2。问题4，对所设计算法的时间复杂度和空间复杂度以及对计算所得结果进行了分析。关键词：计算机指令 优化控制 0-1整数规划 单纯形算法 穷举法一问题的重述在计算机控制过程中，一条计算机指令往往可以控制几个计算机部件，反过来，一个部件一般有几条指令控制。一个基本的问题是，在指令集合里寻找最少的指令，使得所有的部件得到控制；另一个问题是，当给定每条指令的长度时，在指令集合里，寻找总长度最小的若干指令，使得他们可以控制全部部件。对于上面两个问题，建立如下两个数学模型：1、 建立使得所有

3、部件得到控制的最少指令集合；2、 建立是所有部件得到控制的总长度最小的指令集合；再给出指令控制的部件和指令的长度后如表1所示，用所建立的数学模型对表1所列的数据求出结果。3、 设计模型的求解算法，用表1中所示的数据给出求解结果；4、 分析所设计算法的复杂性和计算所得到的结果。表1指令控制的部件和指令的长度指令指令所控制的部件指令的长度指令指令所控制的部件指令的长度14，8，20，31，44151913，23，26，392628，19，22，29，3780207，12，40，412232，16，34，33，320302112，16，19，28，352647，11，35，3012226，2327，

4、451955，13，18，2172333，37，40，411761，7，9，23，2519243，17，19，362273，5，6，14，24322516，33，44，451087，20，21，32，35122613，19，24，253099，15，20，4545272，3，5，882106，10，39，42，4336284，7，9，12，4373111，11，21，34，38572916，17，20，3266122，4，18，22，37783028，33，34，3655136，17，25，36653110，23，25，27241422，33，34，3853321，5，44，4546152，1

5、0，20，37343311，15，18，4337169，24，29，3948347，14，22，36771715，18，29，3146353，15，25，3991842，44，4，4532二问题的分析2.1 对问题1的分析问题1中，目标是求出使得所有部件得到控制的最少指令集合。为了实现这个目标，设置了两个0-1变量，第一个控制每个指令用与不用，第二个控制该指令是否控制各个部件，约束为使各部件至少得到一次控制。此问属于典型的整数规划模型，故此可以设立0-1变量，建立0-1整数规划模型。2.2 对问题2的分析问题2相对问题1而言，只是目标有所变化，其实质是一样的，同样可以设立0-1变量，建立0-1

6、整数规划模型。2.3 对问题3的分析问题3要求我们设计模型的求解算法，最后再求出结果。对于一般的0-1整数规划模型，有很多算法可以实现，常见的有：分支定界法，穷举法，贪婪算法，单纯形法和遗传算法。故此，本模型就可采用其中几种不同算法对模型进行分析求解。2.4 对问题4的分析问题4要求我们分析所设计算法的复杂性和计算所得到的结果，复杂性分析是多方面的，要从时间和空间以及适应性等角度去分析。三模型的假设和符号的说明3.1 模型的假设1.假设每个部件都能被指令集合中一条或多条指令控制；2.假设每条指令在运行时都不发生逻辑错误,且每个部件均正常工作；3.假设控制同一部件的指令间无优先关系；4.假设一条

7、指令控制多个部件时无优先关系；5.在指令控制部件的过程中我们只考虑指令和部件的对应性,而不考虑计算机指令控制过程中的延迟性等问题。3.2 符号的说明符号表示意义第i条指令是否使用第i条指令是否控制第j个部件m表示指令总数n表示部件总数F表示使用指令的总数L表示使用指令的总长度四模型的准备4.1 线性规划线性规划问题：求多变量线性函数在线性约束条件下的最优值。线性规划的一般形式：线性规划问题的标准形式：任意线性规划问题可化为标准形式。具体如下：1.目标函数标准化 2.约束条件标准化假设约束条件中有不等式约束或引入新变量（称为松弛变量），则以上两式等价于以下两式：3.自由变量标准化若变量无约束，可

8、引入两个新变量，令=-，故以下我们只考虑标准形式，也可以用矩阵形式表示为一般要求，4.2 单纯形法定理一：1、线性规划问题的可行域是一个凸多边形；2、线性规划问题如果存在最优解，则最优解必在可行域的顶点处达到。可行域的顶点称为基本可行解。基本思想：从可行域的一个顶点（基本可行解）出发，转换到另一个顶点，并且使函数值逐步减小，有限步后可得到最优解。五模型的建立5.1 问题1 模型的建立第一问目标是求出使得所有部件得到控制的最少指令集合。为了实现这个目标，设置了两个0-1变量，第一个控制每个指令用与不用，第二个控制该指令是否控制各个部件，约束为使各部件至少得到一次控制。设置变量，令其中，m,n分别

9、表示指令总数和部件总数。目标函数： （F表示使用指令的总数）约束条件：用表示第条指令与第个部件的关系，如果第个部件能被第条指令控制，则=1，否则=0。易知表示第个部件是否得到指令集合中的一条或多条指令的控制，当1时，表示第个部件得到指令集合中至少一条指令的控制。所以，可得到该问题的于约束条件为： 矩阵形式为：综上所述，对问题一建立数学模型I：5.2 问题2 模型的建立第二问模型建立和第一问类似，只是目标变为求出使得所有部件得到控制的总长度最短的指令集合。为了实现这个目标，也设置了两个0-1变量，第一个控制每个指令用与不用，第二个控制该指令是否控制各个部件，约束为使各部件至少得到一次控制。设置变

10、量，令其中，分别表示指令总数和部件总数。使 表示各个指令的长度，则目标函数为： （L表示使用指令的总长度）约束条件：用表示第条指令与第个部件的关系，如果第个部件能被第条指令控制，则=1，否则=0。易知表示第个部件是否得到指令集合中的一条或多条指令的控制，当1时，表示第个部件得到指令集合中至少一条指令的控制。所以，可得到该问题的于约束条件为：矩阵形式为： 综上所述，对问题二建立数学模型II：六算法的设计和模型的求解根据题目表1-1中的数据，我们利用之前建立的问题1模型和问题2模型求解得使所有部件得到的控制的最小指令集合和总长度最少的指令集合。6.1算法的设计6.1.1 第一种算法：单纯形法单纯形

11、法是线性规划问题的一般解法，其基本思想是寻找一个基的可行解(极点)，便可以通过有限步的迭代找到问题的最优解。求解问题1用单纯形的二阶段法：第一阶段：第一步将数学模型的线性规划转化为单纯形法的标准形式(由于原始问题全部由“”约束条件构成因此还需添加人工变量和剩余变量)本问题约束矩阵M=（A，l，K)，其中A是系数矩阵，l和K分别是m阶单位矩阵，Z表示人工变量的和。辅助目标函数：将其转化为求最大值问题：同样目标函数转化约束方程组为：第二步检验各非基变量的检验系数，本题如果都成立则基可行解已是最优解解计算结束；否则转为下一步。第三步以辅助目标函数为判断依据进行迭代选取辅助目标函数中具有非负系选取辅助

12、目标函数中具有非负系数的非基变量(假设是)，作为进人下一个基本可行解的进基变量，然后转入下面介绍的第四步如果此时所有系数均为非负，就得到辅助目标函数的最优解假如此时的辅助目标函数值为零，并且所有人工变量均不在基内，这就得到了原始问题的一个基本可行解，然后就转入第二阶段计算；如果此时辅助目标函数值不为零，则人工变量至少还有一个仍留在基内取非零的正值，那么原始问题就没有可行解，则停止运算，转至第六步第四步由进基变量，满足为出基变量。第五步以为主元进行迭代，把基变量转化为非基变量，重复一到五直到得到结果。第六步如果没有可行解则根据题意设x都为1。第二阶段：去掉辅助目标函数所在的行和列，然后以原目标函

13、数代替第一阶段的辅助目标函数作为判断依据，进行单纯形法迭代运算步骤同第一阶段中第一至五步相类似(注意将第二步中j的范围定为到)，直到得到原线性规划问题的最优解2求解问题2的算法根据模型的相似性只需将求解问题1中的目标函数改为：即可，算法与求解问题1的相同6.1.2 第二种算法：穷举法穷举法可以解决这种线性规划问题。第一步 建立循序的约束条件，根据模型I可知：第二步 通过运行得到的满足条件的指令结果，即得到了所以的可以控制所有部件的指令集合。我们再根据目标函数所要要求的，在这些结果，我们分别定义不同的目标函数，找到最少的指令条数集合和总长度最短的指令集合。6.1.3 第三种算法：lingo求解我

14、们已经建立了模型I和模型II，可以直接通过lingo软件来解决问题，只要输入目标函数和约束条件，就可以得到结果。6.2 对问题1模型的求解6.2.1 数据的分析由于模型的要求，对表1进行重新排列，改变表1按照指令排布，转为用部件为变量排布，这就是下面的表2：表2 每个部件指令相对应的控制指令说明部件控制部件的指令部件控制部件的指令16，11，32247，16，2623，12，15，27256，13，26，31，3537，24，27，35261941，12，18，282722，3155，7，27，322821，3167，10，13，22292，16，1774，6，8，20，28，28，3430481,2,27311，1796,9,16,28323，8，291010,15,31333，14，23，25，30114,11,33343，11，14，33，1220,21,2