熊英飞-算法合成——自动应用算法模式合成高效程序.pdf

1、算法合成自动应用算法模式合成高效程序熊英飞 北京大学演讲嘉宾熊英飞北京大学副教授熊英飞于2009年从日本东京大学获得博士学位，2009-2011年在加拿大滑铁卢大学工作，2012年加入北京大学，现任新体制长聘副教授。熊英飞的研究兴趣是程序设计语言和软件工程，特别是程序合成、修复和分析。他提出了理论和方法降低程序编写和缺陷修复的代价。比如，基于差别的双向变换框架是最广泛使用的双向变换框架之一，概率和逻辑结合的程序合成框架玲珑框架将程序修复的正确率从此前不到40%提升到80%以上。他的工作也被工业界采用，比如新一代Linux内核配置项目、燕云DaaS系统、华为公司等。他获得CCF-IEEE CS青

2、年科学家奖、MODELS十年最有影响力论文奖，5次获得ACM SIGSOFT/IEEE TCSE杰出论文奖。他是SATE18的程序委员会联合主席，也在PLDI、ICSE、FSE等会议担任PC。知乎问题课程名点赞数算法数据结构47大学语文23马克思主义12汇编语言5体系结构1算法为什么难：示例 最大子段和问题:输入一个整数的列表，求列表上连续一段的最大和。1,-2,3,-2,3 4 穷举算法非常容易实现 算法复杂度为(3)能否应用算法课的知识来进行优化？算法为什么难：示例 算法课教了一系列算法设计模式，尝试应用分治 算法复杂度:(/),m:处理器个数 应用算法设计模式并不容易 分治：把原问题分解

3、成规模更小的问题 对具体问题并没有给出分解方法，需要程序员的智慧 分治后的程序长度、理解难度均远超原来的程序研究目标：自动应用算法模式应用分治降低难度：算法设计是困难耗时的步骤节省成本：会算法的程序员需要更高人力成本同一时间、同一地点、同一公司、同一部门的两个招聘岗位提高质量：算法优化是缺陷来源 SeL4:著名经验证操作系统内核 第一阶段：采用Haskell的算法设计 验证导致500+修改 第二阶段：采用C的系统实现 验证导致50+修改优化前程序简洁、优雅、模块化优化后程序冗长、繁杂、破坏边界提升效率：自动优化程序目前的编译优化技术只能进行局部小替换，通常很难显著降低程序复杂度。自动应用算法模

4、式有望对程序进行整体大幅优化。常见编译优化技术大型语言模型是否解决这个问题？Can you optimize this program as a parallel program using D&C?The expected time complexity is O(n/p),where n is the length of the input list x,and p is the number of CPU cores.mss=-INF for i in range(len(x):for j in range(i,len(x):mss=min(mss,sum(xi:j+1)return m

5、ssmin而不是max北京大学目前成果 两类算法设计模式的自动应用方法分治类问题arXiv:2202.12193分治（并行化）、增量计算、流算法、线段树、最长子段问题等动态规划问题OOPSLA23根据不同的算法设计模式实例化成不同的合成工具 例：列表上的()分治算法的合成工具输入：一个程序，从列表产生输出可以用任意编程语言、任意算法编写也可从形式化需求自动导出输出：一个列表上的分治程序和输入程序等价算法复杂度是()，其中为CPU的数量传统求解方法：程序演算 通过一系列程序变换半自动得到优化后的程序 但算法设计往往需要“根据具体问题设计关键模块”这样的操作 通用程序变换规则难以完成问题特定的设计

6、 因此，程序演算保持半自动求解14方法概览分治/并行化增量计算单通道/流算法线段树提升问题Lifting Problem求解算法AutoLifter规约基于搜索的归纳程序合成求解动态规划MPF和LOF合成问题求解算法SynMem手动应用分治算法 第二小问题：输入整数列表 查找列表中的第二小的元素 输入程序 时间复杂度:O(nlogn)目标：采用分治优化程序 得到O(n/m)并行程序return sorted(xs)l手动应用分治算法 分三步应用分治:1.将输入列表分成两份+2.在两份列表上分别递归计算sndmin3.合并结果得到原列表上的结果 但是，这样的合并操作是不存在的1,3,52,4,6