周知编译原理龙书阐述的基本块指令调度算法，它所使用的空的资源预约表RTD与每个指令的资源预约表RT，可以看作二维矩阵，行表示时钟周期、列表示cpu资源，其定位的元素值1表示占用/预约，0表示空闲/非预约。前者是随周期递增而动态扩大的矩阵，后者是固定尺寸(维数)的矩阵（指令花费周期与每周期预约资源皆已知）。在调度时，按带优先级比如关键路径的拓扑排序基本块内的指令，顺序选取一条指令Inst，计算每前驱发射周期加延迟的结果tmp，取所有tmp的最大值tmax作为Inst的发射周期，再判断处理器资源是否可用，即RTD和RT作
与运算，得到一个新矩阵RTN，若RTN为
全零矩阵则tmax为Inst的最终发射周期，否则递增tmax再做矩阵与运算，直至得到全零矩阵。最后更新RTD，即RTD与RT作
或运算结果存于RTD。重复上述过程直到基本块末尾。
综上不难看出，如果一个基本块很大比如有1000条指令，平均每指令花2个周期，则RTD需要2000个条目，若一条目即矩阵每行占用32字节（256种资源数），则总量约64k。当然这对于现代内存体量来说不算什么，但可以有更好的节省内存的做法：RTD尺寸其实可以相对固定，其上限为基本块中耗费周期最多指令的周期的一个大于1常数因子倍（为兼顾指令并行性），这样一来就要增加当指令完成时（当前指令发射周期大于前一条的终止周期时复位前一条指令的RTD）从发射周期处复位RTD即作一个矩阵反运算的操作，其它步骤对应的矩阵与、矩阵或运算的操作保留不变。另由于RTD固定了尺寸，因此发射周期递增后要取模
【备注】以上是我针对简单机器模型（每种资源数量仅一个，比如整数运算单元1个，内存访问单元1个，浮点运算单元1个）用布尔矩阵作的优化。如果是复杂的超标量机器即每种资源数有多个，那么只需修改如下：布尔矩阵换成整数矩阵；新增一个机器资源可用总数整数矩阵RDA（单列资源数同值），布尔矩阵与运算换成加法并与RDA比较，若大于RDA则递增tmax；布尔矩阵或运算换成加法；布尔矩阵反运算换成减法，RTD减RT存于RTD
posted @
2023-09-23 12:14 春秋十二月 阅读(335) |
评论 (0) |
编辑 收藏曾因朋友问到监控，致使我探究了kretprobe的实现，想到编译中的尾调用优化，作个小结
1. kretprobe_trampoline_holder该跳转函数无参是必须的或说最好的通用设计，因为替换返回地址是非正常程序流程，即被探测函数的调用者无感知，不存在为跳转函数准备入参。若要设计传参且只读，则不会破坏被探测函数调用者的上下文，但跳转函数内部流程怎么用参数是个问题，这需要一种约定
2. 跳转函数为调用trampoline_handler准备入参，即在栈上构造一个（不完整的）pt_regs，再把它地址即栈顶赋给rdi，rdi是x86_64上传入第一参数使用的寄存器，同时预留一个栈单元存放原返回地址（为什么要预留？因为被探测函数返回时，其调用者存放返回地址的栈空间被释放了，所以得在跳转函数内造一个）。由于trampoline_handler内调到用户自定义handler而传入pt_regs，因此自定义handler内要注意最好别改动pt_regs，否则会破坏被探测函数调用者的上下文
posted @
2023-09-13 02:26 春秋十二月 阅读(302) |
评论 (0) |
编辑 收藏有理数域的本原多项式与有限域的本原多项式定义不同，前者不要求不可约（由高斯引理知两个本原多项式的乘积还是本原），后者则必须不可约（确保生成的有限域其每个元素有逆元）。aes基于有限域F{0,1}设计，故使用的模8次多项式不可约
P(x)=x^8+x^4+x^3+x+1，但不是本原多项式，因为它的阶是51而非255。有限域次数为8的本原多项式有16个、不可约多项式有30个（由莫比乌斯反演推出），具体多项式影响s盒与列混合操作的实现。不可约加之0的逆元规定为0，保证正确加解密。若0的逆元规定为非0比如x，则导致x有两个逆元，便违反了逆元唯一性，除非s盒不用有限域设计。逆元等于其自身的非0元素只有1，原因可类比模素数二次剩余的求解
posted @
2023-09-13 02:00 春秋十二月 阅读(348) |
评论 (0) |
编辑 收藏1. 若DFA D是用子集构造法从NFA N构造出来的，则L(D)=L(N)
2. 一个语言L被某个DFA接受，当且仅当被某个NFA接受
3. 一个语言L被某个£-NFA接受，当且仅当被某个DFA接受
4. 若对于某个DFA A，L=L(A)，则存在一个正则表达式R使得L=L(R)
5. 每一个用正则表达式定义的语言也可用有穷自动机定义
6. 若通过填表算法不能区分两个状态，则它们是等价的
7. DFA的状态等价性是传递的
8. 若对于DFA每个状态q及与q等价的所有状态组成块，则不同的状态块形成状态集合的划分。也就是说，每个状态恰好属于一个块，同一块中的所有成员都是等价的，从不同块中选择的状态对都不是等价的
9. 根据等价状态划分算法最小化DFA D得到的DFA M是唯一的。也就是说，不存在其它等价于D的DFA N，其状态数比M少
----------------------------------------------------------------------------------------
10. 对于正则表达式，空集是并运算的单位元、连接运算的零元，空串是连接运算的单位元
11. 若L和M都是正则语言，则L和M的并、交、差也是
12. 若L是字母表T上的正则语言，则~L=T*—L也是
13. 若L是正则语言，则L的反转也是
14. 若L是字母表T上的正则语言，h是T上的一个同态，则h(L)也是正则的
15. 若h是字母表A到字母表T的同态，且L是T上的正则语言，则逆同态h^-1(L)也是正则的
posted @
2023-09-09 08:11 春秋十二月 阅读(1093) |
评论 (0) |
编辑 收藏1. 空性：对于R，若给定形式是自动机比如£-NFA，则等价于判定能否从初始状态到达接受状态，这需计算可达状态集合，若任一接受状态在里面，则为非空，否则为空。耗时不超过O(n^2)，n为自动机的状态数。若给定形式是正则表达式，则可先转为£-NFA，再计算可达状态集合，如此增多转化时间O(s)，s为正则表达式的长度。也可不转为自动机，直接根据基础归纳规则用递推法判定，耗时为O(s)。 对于CFL，等价于判定开始符号是否为产生的，若是则非空，否则为空。如直接用产生变元的基础归纳法计算，那耗时O(n^2)，n为文法G的规模，接近变元的个数。一个改进的算法实现，预先建立以变元为索引的数组、每个变元的链接（产生式内链接、产生式间链接），则耗时O(n)
2. 成员性：设串w的长度为n。对于R，等价于判定自动机能否接受w，若给定形式是DFA，则耗时O(n)。若给定形式是NFA，则耗时O(n*s^2)，s为状态数，如NFA有£转移，那需先计算它的闭包，耗时增多O(s^2)，可见总耗时还是O(n*s^2)。若给定形式是正则表达式，则先转为NFA，耗时增多O(r)，r为表达式的长度。 对于CFL，等价于判定从文法G的开始符号S能否推导出w，一般用CYK算法构造产生式三角表，再查看S是否属于表的顶点集合，若属于则能推导出w，否则不能，耗时为O(n^3)
posted @
2023-09-09 08:09 春秋十二月 阅读(64) |
评论 (0) |
编辑 收藏因为一个整数p，若检测为合数，这永远是真命题；而检测为素数，这命题只以较大概率成立。 可构造一种NP检测算法，步骤如下：
1. 猜测p（位长度n）的因子列表｛p1,p2,…pi｝，这是非确定的，每个分支耗时O(n)
2. 验证p1*p2*…pi？=p-1，耗时不超过O(n^2)
3. 若各因子乘积等于p-1，则用当前算法递归验证每个因子都是素数
4. 随机选择p最小剩余系内的一个数x，计算x^((p-1)/q) （q遍历上述列表经过步骤3验证过的素因子）是否都不同余于1模p，若是则必有x^(p-1)同余于1模p，则由指数整除p的欧拉数及费马小定理，知p为素数，考虑到有少量的合数也满足费马小定理，故需多次选择x重复验证，选择个数最多为log(p)
分析：本算法涉及的数论定理——设p是奇素数，p-1的所有素因子是q1,q2,…qs，那么g为原根的充要条件是，g^((p-1)/qj)不同余1模p，j=1,2…,s
结论：第3步可以看成递归调用树，每个顶点为待检测整数，其每个子结点为一个因子，则最多n层，每层至多耗时O(n^4)，所以每个路径即检测p是否素数的非确定任一分支中，总耗时O(n^5)。 2002年，印度科学家发现素检测确定性多项式时间算法，于是从NP前进到了P
posted @
2023-09-09 08:07 春秋十二月 阅读(652) |
评论 (0) |
编辑 收藏为什么命题逻辑有效性是可判定的，而谓词逻辑有效性是不可判定的？
因为命题逻辑由有限个合式公式及原子命题构成，且原子命题的取值只有真、假两种，简单的判定方法是真值表穷举，其复杂度为指数级：2^N，N为原子命题数量。快速的方法是先转成合取范式（输入是由否定、而且、或者、蕴含四种连接词构成的语法正确的命题逻辑公式，经过对公式结构归纳作蕴含释放、否定原子、分配律变换三步处理，同时运用DAG优化：共享终止即叶子结点、删除冗余的测试结点、删除重复的有相同子图结构的内部结点，输出等价最小的合取范式），再检测合取范式的有效性（检查所有子句，若每个子句包含至少一个原子及其否定形式，则有效，否则因为存在一种真值指派使其为假而导致整个合取范式无效），其复杂度为多项式级：N*logN+N，N为公式长度。谓词逻辑基于命题逻辑扩展，添加了变元、函数、量词“所有”与“存在”，如果量词没有约束变元范围即定义域无限，那么函数值域也是无限的，另外可能引入的自由变元不受限制，这导致了解空间是无限的，所以不存在通用算法去判定任意谓词逻辑公式是否有效，具体证明可以用pcp归约，即构造一组特定的谓词逻辑公式，它是有效的当且仅当pcp实例有解，又已知pcp是不可判定的，故该特定谓词逻辑有效性是不可判定的，由于任意包括特定，所以谓词逻辑有效性是不可判定的
posted @
2023-09-09 08:05 春秋十二月 阅读(62) |
评论 (0) |
编辑 收藏设程序片段S=if C then S1 else S2，S1和S2可以是由赋值、条件、循环构成的复杂语句，S不为当前程序最后语句或某个循环主体最后语句，则S对应的流图生成的深度优先生成树T有3条树边，有S1的出口数+S2出口数-1条交叉边。为什么是3条树边？C到S1、C到S2、S1或S2到S3（S3是S后继结点，下同）。为什么交叉边数是S1出口数+S2出口数-1？因为流图中S1出口及S2出口到S3的边，在生成T的过程中，只有1个出口比S3先访问，这对应形成1条树边，访问S3后再访问其它出口，这对应形成其它出口到S3的交叉边，注意这里没有前向边，因为较晚访问的出口在T中不可能是S3的祖先。如果把S改为if C then S1，情况会怎样？结果取决于生成T的过程中先访问S3还是S1。若先访问S3，则有树边2条：C到S3、C到S1，交叉边数等于S1的出口数：S1的每个出口到S3各一条边，没有前向边。若先访问S2，则有树边1条：C到S2，前向边1条：C到S3，交叉边数等于S1出口数-1。
总结此类问题分析的基本思路是对程序控制结构先构建流图，再构建深度优先生成树，辨别其中的前向边、交叉边、后退边
posted @
2023-09-07 06:50 春秋十二月 阅读(53) |
评论 (0) |
编辑 收藏1.闭包记录分配：若逃逸分析能识别哪些闭包记录在创建它们的函数中是出口不活跃的，则这些闭包记录可分配在栈帧中（不再是堆中）
2.内联扩展：由于小函数较多，因此内联可以免去调用开销而提高性能，对于递归函数，需先用循环前置头转换再内联，如果是尾递归函数，可先使用尾调用优化删除递归。如果一个函数的所有调用都被内联扩展，并且该函数没有作为参数传递或其它方式被引用，那么可以删除这个函数本身即函数定义。内联扩展可以继续作用于扩展后的函数体，只要存在函数调用，这也叫层叠式内联
3.循环不变量参数外提：递归函数经过循环前置头转换后，若每次递归调用头函数，传入的某些参数值总不变，则可以将它们从函数参数中删除，函数体中的每次使用出现用序曲函数对应的参数名替换
4.解开嵌套的let：将嵌套的多层let中的代码合并为一个let中的代码，in中的代码不变
5.避免代码膨胀：由于内联复制函数体，通常使程序体积变大，且层叠式内联可无限扩展下去，因此为避免代码膨胀，有如下启发式策略对内联进行控制
a) 只内联执行很频繁的函数调用，可根据静态估计比如循环嵌套深度、迭代次数，或根据执行剖面分析反馈，计算函数的执行频率
b) 内联很小的函数，其函数体不会比直接调用多出较多指令
c) 内联只调用一次的函数，然后删除原来的函数定义
posted @
2023-09-07 06:47 春秋十二月 阅读(48) |
评论 (0) |
编辑 收藏1. 整数r>s>0，(r, s)=1，2∤r+s，x=r^2-s^2, y=2rs, z=r^2+s^2，求证(x, y)=1，(y, z)=1
证明：由2∤r+s（r与s必一奇一偶）知2∤r-s，故2∤r^2-s^2，以及2∤(r+s)(r+s)。又1=(r, s)=(r+s, r)=(r+s, s)=(r+s, rs)。同理得1=(r, s)=(r-s, rs)，故1=((r+s)(r-s), rs)=(r^2-s^2, rs)，又1=(2, r^2-s^2)，故(r^2-s^2, 2rs)=1，即(x, y)=1。(y, z)=(2rs, r^2+s^2)=(2rs, r^2+s^2+2rs)=(2rs, (r+s)(r+s))=(rs, (r+s)(r+s))=(rs, r+s)=(r, r+s)=(r, s)=1
注：用最大公约数定义、整除性质、反证法，也可以得出(x, y)=1，(y, z)=1。本法则直接从最大公约数定理推导
2. u^2+3v^2=2p不可能成立，u、v为整数，p为奇素数
证明：u^2+3v^2=2p => u^2+v^2=2(p-v^2) => 2|u^2+v^2=(u+v)^2-2uv => 2|(u+v)^2 => 2|u+v。得出这个中间结论，再由它可得4|2(u+v)|2v(u+v)=2v^2+2uv，以及4|(u+v)^2=u^2+v^2+2uv，故得4|u^2+3v^2+4uv，继得4|u^2+3v^2=2p，即2|p，所以矛盾，证毕
3. 若四个正整数y1*x2=y2*x1，(x1,y1)=(x2,y2)=1，则x1=x2，y1=y2
证明：由y1*x2=y2*x1可得x1|y1*x2，又因(x1,y1)=1，故x1|x2；另得x2|y2*x1，又因(x2,y2)=1，故x2|x1；终得x1=x2，y1=y2
4. 假设2∤z，z^3=x^2+3y^2有解且满足(x, y)=1，其通解形式为x=a^3-9ab^2，y=3a^2b-3b^2，a、b满足z=a^2+3b^2，求证(-3/p)=1，p是z的任一素因子；(a, 3b)=1
证明：先论证中间结论3∤z，p>3且(p, xy)=1。若3|z，则3|x^2+3y^2=>3|x^2=>3|x=>9|x^2，另有9|x^2+3y^2=>9|3y^2=>3|y^2=>3|y，这与(x, y)=1矛盾，故3∤z。又2∤z，得p>3，由此若p|x，则p|3y^2得p|y，或若p|y，则p|x^2得p|x，都与(x, y)=1矛盾，故(p, xy)=1。
再论证勒让德符号(-3/p)=1。由以上中间结论得等价形式x^2+3y^2=(Z^3p^2)p，及p∤x^2、p∤y^2，推得1=(x^2/p)=(-3y^2/p)=(-3/p)。
最后论证(a, 3b)=1。假设2|z，则2|a^2+b^2=(a+b)^2-2ab或(a-b)^2+2ab =>2|a+b, 2|a-b。因题设是2∤z，故2∤a+b, 2∤a-b，由此推得2∤a^2-b^2, 4∤a^2-b^2，进而8∤a^2-b^2，即(8, a^2-b^2)=1。由1=(x, y)=(a^3-9ab^2, 3a^2b-3b^2)=(a(a^2-9b^2), 3b(a^2-b^2))。又(a^2-9b^2, a^2-b^2)=(8b^2, a^2-b^2)=(b^2, b^2-a^2)=(b^2, a^2)=(a, b)^2，于是令a^2-9b^2=(a, b)^2*A, a^2-b^2=(a, b)^2*B，则得1=(x, y)=(a, b)^2*(aA, 3bB)，故(a, 3b)=1
5. 已知2∤u+w，3∤u，(u, w)=1，求证(2u, u^2+3w^2)=1
证明：2∤u+w=>2∤u^2+w^2=>2∤u^2+3w^2，即(2, u^2+3w^2)=1。
由3∤u，(u, w)=1得(u, 3w)=(u, 3w^2)=(u, u^2+3w^2)=1。
综上两式结果得(2u, u^2+3w^2)=1
6. 已知(3v, w)=1，2∤3v+w，求证(18v, 3v^2+w^2)=1
证明：(3v, w)=1=>(3v, w^2)=(3v, 3v^2+w^2)=1。
(3v, w)=1=>(3, w)=1=>(3, w^2)=(3, 3v^2+w^2)=1。2∤3v+w=>2∤v+w=>2∤v^2+w^2=>2∤3v^2+w^2，即(2, 3v^2+w^2)=1。
综上三式结果得(18v, 3v^2+w^2)=1
###############################
从1、5和6问题的证明过程可得，如果一个数由两个或多个因子相乘，那么求证是否互素可以逐一求每个因子与另一个数是否都互素
posted @
2023-09-07 06:43 春秋十二月 阅读(596) |
评论 (0) |
编辑 收藏