计算机指令设计
计算机指令设计
摘要
计算机已经成为现代社会发展不可取代的有利助手，而计算机控制更是遍及各领域。因而对计算机指令控制部件并达到最优的研究具有深远的意义。本文主要关于在计算机控制方面，对计算机指令控制计算机部件的问题作了具体的分析，对于使得所有部件得到控制的最少指令集合和所有部件得到控制的总长度最小的指令集合，分别建立了相应的整数线性规划模型。
对于模型的求解,我们用lingo软件同时计算出结果。对所设计算法的复杂性，主要是从算法的时间复杂性和空间复杂性两方面进行分析。
关键字：计算机指令最优控制线性规划时间复杂性 lingo
一、问题重述
在计算机控制过程中，一条计算机指令往往可以控制几个计算机部件，反过来，一个部件一般由几条指令控制。一个基本问题是，在指令集合里寻找最少的指令，使得所有的部件得到控制；另一个问题是，当给定每条指令的长度时,在指令集合里，寻找最长度最少的若干指令，使得他们可以控制全部部件。
对于上面的两个问题，建立如下两个数学模型：
1. 建立使得所有部件得到控制的最少指令集合；
2. 建立使得所有部件得到控制的总长度最小的指令集合。
再给出指令控制的部件和指令的长度后如附表-1所示，用所建立的数学模型对附表-1所列的数据求出结果。
3．设计模型的求解算法，用附表-1中所列的数据给出求解结果；
4. 分析所设计的算法的复杂性和计算得到的结果。
二、问题分析
由于一条计算机指令往往可以控制几个计算机部件，反过来，一个部件一般有几条指令控制，这两个都是线性规划问题且约束条件相同，只是目标函数不同。
对于问题一：建立使得所有的部件得到控制的指令集合里的最少的指令模型。我们利用整数线性规划模型，找出所求优化问题的目标函数和约束条件，并确保一个部件至少有1条指令控制，同时利用软件计算得出所有部件得到控制的最少指令的集合。为使所有部件得到控制的指令的总长度的最小长度，仍然建立整数线性规划模型，依然要保证一个部件至少有1条指令控制，再用软件计算得出所有部件得到控制的指令的总长度的最小长度。
对于问题二：对于模型1和模型2求解，我们用的是Lingo软件同时进行求解。
对于问题三：主要是从时间复杂度和空间复杂度两方面对算法的复杂度进行分析。
三、模型假设
1) 假设每个指令都正常控制相应的部件。
2) 假设每个部件都能被指令集合中一条或多条指令控制。
3) 假设每条指令在运行过程中不发生逻辑错误, 且每个部件均工作正常。
4)在指令控制部件的过程中只考虑指令和部件的对应性, 而不考虑计算机指令
控制过程中其他的关系和问题。
四、符号的定义及说明
符号定义及说明
x第i条指令是否被使用
i
a第i个部件是否被第j条指令控制
ij
l第j条指令的长度
i
m部件的总个数
n指令的总条数
F所用指令的总条数
1
F所用部件的总个数
2
这里只给出主要符号的意义，其他符号将在文中给出，在此不再一一赘述。
五、模型的建立及求解
5.1 建立使得所有的部件得到控制的最少指令集合
此问的目的是为了在指令集合中寻找条数最少的指令, 使所有的计算机部件得到控制。变量i x 为0- 1 变量, i x 表示是否使用第i 条指令, 如果使用第i 条指令, 则其对应的i x = 1, 否则i x = 0 。 所使用指令的总条数可表示为1F , 因此目标函数为:
Min: ∑==
n
i i
x
F 1
1（1）
约束条件：
1）ij a 表示第j 个部件和第i 条指令的关系, 如果第j 个部件能被第i 条指令控制
ij
a = 1, 否则ij a = 0 .
2）用i n
i ij x a ∑=1
表示第j 个部件是否得到指令集合中一条或多条指令控制，则
11
≥∑=i n
i ij
x a
表示第j 个部件得到指令集合中至少一条指令的控制.即：
11
≥∑=i n
i ij
x a
，j =1，2，3... m
（2）
由此，建立了如下的数学模型：
Min: ∑==
n
i i
x
F 1
1??
???
??
??
=≥====∑=n i i ij ij ij i i m j x a a or a x or x t s 1
,...2,1(,11010..）（3）
5.2 建立使得所有部件得到控制的总长度最小的指令集合
首先我们引入一组变量,,...,21m l l l 其中i l 表示第i 条指令的长度. 问题二的目的是为了在指令集合中寻求总长度最小的若干指令, 使所有的计算机部件得到控制. 根据对问题一的分析可知, 问题二同属整数线性规划问题, 并得相似模型为:
Min: i
n
i i
x l F ∑==
1
2
??
???
??
??=≥====∑=n i i ij ij ij i i m j x a a or a x or x t s 1
),...2,1(,11010.. （4）
5.3 建立求解算法的模型 用lingo 软件实现：
根据附表一所列数据利用lingo 软件求得一组最优解为x1=1,x2=1,x3=1,x4=1,x5=1,x6=1,x7=1,x8=1,x9=1,x10=1,x12=1,x13=1:, 目标
函数min:∑==
n
i i
x F 1
1=12。
即能控制所有部件, 且所用指令条数最少的一组指令为: 1,2,3,4,5,6,7,8,9,10,11,13,共12 条指令。
根据附表一所列数据利用lingo 软件求得一组最优解为:x1=1,x2=1,x3=1,x4=1,x5=1,x6=1,x7=1,x8=1,x9=1,x10=1,x13=1,x14=1;
目标函数min: j n
j j
x l
F ∑==
1
2=406。
即能控制所有部件, 且所用指令长度总和最小的一组指令为 1，2,3 ，4, 5 ，6, 7，8,9,10 ，13,14. 共12 条指令, 总长406。 5.4 算法的复杂度分析
Lingo 求解本题的复杂性分析如下：
虽然模型的约束及变量个数影响其计算速度，但此模型用Lingo 编程，在优化编程方面，Lingo 的计算机的运行时间短，所以效率最高。
六、 结果分析
七、模型的评价和与推广
我们建立的模型对计算机指令优化控制问题作了细致的分析，并且提出了模型的几种算法，而且还进行实例的计算求解，最后还用了lingo 数学软件检验了
结果的正确性．总的来讲本模型可以适用于其他的相似问题，而且单纯形法的算法快捷，整数规划明确简单。但是由于我们采用的算法有局限性，所以在问题有多组最优解的时候，我们只能求到一组，不过经过检验，所得的结果还是令人满意的。
八、参考文献
[1]钱颂迪，运筹学[M]，北京: 清华大学出版社，1990。
[2]西北工业应用数学系，线性代数[M],西安：西北工业出版社，1998。
[3]何建坤,实用线性规划及计算机程序[M]，北京: 清华大学出版社，1985。
[4]刘卫国， Matlab程序设计和应用[M]，北京：高等教育出版社，2002。