程序综合与编译

程序综合(synthesis)和程序编译(compilation)常常会被混淆。我们大多数人熟知的是编译,比如将C++代码编译为x86汇编;而在FPGA中我们更多会采用综合一词,比如高层次综合、逻辑综合、物理综合等等。两者工作似乎都是将一种语言翻译为另一种语言,但事实上仔细分析一下还是有很多区别。

粗略地来讲,编译器仅仅做了一个翻译的功能,即高级语言只是描述了要做什么(what)任务(传统的C/C++/Java等编程语言大多是命令式编程);而综合器做的事情则更多,它还需要去探索怎么(how)去执行这个任务,涉及到程序的改写。

区别两者一个很重要的特征在于有无搜索(search)的过程。编译器通常是将一个预定义的调度(schedule)进行转换,而综合器则是根据程序的描述找到一个最优的调度来满足需求。不过事实上,很多现代的编译器都已经具备有自动优化(autotuning)的功能,比如TVM,因此编译与综合的界限其实在逐渐模糊。

另外,程序综合也很像机器学习。仔细思考一下现在的机器学习,其实也是一个程序到程序的映射,或者说我们一开始写的就是元程序(metaprogram)。大多机器学习算法都包括训练(training)和推断(inference)两个过程,训练实际上就是读入源程序然后进行优化/综合的过程,把其中未确定的参数给确定下来,进而得到最终的程序/模型;而推断则是利用训练好的确定的程序运行得到结果。

February 1, 2020 - 程序综合与编译

如上图,红叉是传统编译确定性的写法,你写什么就得到什么程序;而红叉之外的是搜索空间,满足你的spec可能有非常多程序,都落在灰圈中,而要在灰圈的程序中找到最好的一个,这是综合。

那么到底什么是程序综合?

Program Synthes is correspond to a class of techniques that are able to generate a program from a collection of artifacts that establish semantic and syntactic requirements for the generated code.1

用更加通俗易懂的话来说,我现在要盖房子,综合器只告诉你一个设计图纸/目标,至于怎么盖你自己想;而编译器会十分细致入微,告诉你第一步先造地基,第二步往上盖,第三步怎样怎样。

现在的程序综合研究主要关注以下几个方面:

  • 从高层描述中自动生成算法
  • 将综合技术应用在广泛的问题上面,比如Excel的自动填充[FlashFill]、代码自动打分等
  • 逆向工程,低层实现转为高层等价表示,如将Java转为SQL

而高层次综合(HLS)同样是给出是什么(what),然后综合器告知应该怎么做。HLS和传统编译的区别可见该文

像TVM、Halide、GraphIt、Taichi这些新生代的DSL,他们正是将综合的概念融入编译,分离出算法和调度(schedule)。

算法对应的即传统的编译,而调度正是所谓的spec,是可以探索的,是可以交由综合器自由发挥的。

这也解释了为什么现在编译和综合的概念越来越模糊,因为编译更多融入了综合的概念,而综合也在往编译方面发展。

我们现在已经是软件2.0时代,而有种说法是我们已经进入到编译3.0时代2,如今的编译器加入了搜索的元素(启发式/机器学习都可以),使得编译出来的程序性能更高,也更大程度解放程序员疯狂调参的过程。

总的来说,“条条大路通罗马”,综合器告诉你最好的一条,编译器只让你走其中一条。

参考资料

  1. Armando Solar-Lezama (MIT), Introduction to Program Synthesis - Lecture 1, 2018 
  2. 编译1.0实现汇编到高级编程语言的抽象,这是我们现在本科编译原理教的东西,语法分析、词法分析、代码生成等等都是上个世纪编译器刚出来时的产物。编译2.0分离出编译器的前中后三个部分,诞生出了LLVM,前端接各种语言,有成熟的parser;中端做平台无关优化;后端做平台特定优化和codegen。衍生出的高级编译原理、静态程序分析等都是这个世纪初的成果。 

以上是 程序综合与编译 的全部内容, 来源链接: utcz.com/a/128190.html

回到顶部