Archive

Archive for the ‘编译’ Category

CUDA开源

December 16th, 2011 No comments

NV宣布CUDA开源了,又多了一个研究平台。
估计很快会有很多优化被移植到上面去,相关论文井喷一下。
以前有消息说NV的编译器是基于Open64的,现在要公布的是LLVM的。难道有两套?

Clang/LLVM距离完全编译FreeBSD还有五个字节

March 7th, 2011 No comments

估计FreeBSD会慢慢舍弃GCC了。

Roman Divacky发送至 llvmdev

In FreeBSD, we aim for replacing gcc with clang. We can compile all of the
base system except the loader which does not fit within the hardware
limits (7680 bytes).
Currently (r127066) clang/llvm is missing the target by 5 bytes. Thus
it’s 5 bytes from us being able to compile all of FreeBSD with clang (and
replace gcc with clang).

There’s #6627 (http://llvm.org/bugs/show_bug.cgi?id=6627) that if fixed
would get us well over the limit (by saving ~30 bytes).

Can someone please help us and fix this bug? thank you!

roman
_______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

 

Phase Analysis 简介

March 1st, 2011 No comments

程序在运行的时候,其行为不是完全随机的,而是呈现一定的规律性(稳定性)。可以按照程序的性能变化将程序的运行时间分成不同的intervals(时间间隔),性能上相似的intervals的集合称为phase(阶段)。掌握程序的phase信息对于程序的性能模拟、在线优化等都有帮助。本文介绍Phase Analysis的基本概念、分类、应用领域、以及分析算法。

导言:什么是program phase?

程序在运行的时候,其行为不是完全随机的,而是呈现一定的规律性(稳定性)。例如一个程序,它运行期间的cache缺页率可能如下图所示(横轴表示时间,竖轴表示缺页率):

cache miss rate

通过对示例图可以看到,cache miss随着程序的运行,一段时间内的cache miss数量相似的,随后短暂剧烈变化,之后在一段时间内“相似”。如果把程序执行的时间分割成一段段小的时间间隔(interval),根据每个interval中cache miss的情况可以将这些interval按照“相似度”划分成不同的集合,称这样的集合为phase[1]。掌握了程序的phase信息之后,可以在不同phase使用不同的在线优化/优化参数,帮助指令模拟程序减少模拟时间等。

使用program phase分析,有几个问题需要考虑。首先是phase这个概念的具体定义是什么?不同的研究者使用的方法和研究的目的不同,给出的定义也是各有差异的;其次是如何将程序运行的过程进行分割?早期研究选用固定时间间隔(fix-length interval)的分割方法,后期有研究者提出了变长时间间隔(var-length interval)和“长时间间隔”(long-length interval)的概念;第三是使用何种评价函数来评估interval,并按照相似度进行分类?有从程序代码本身进行评价的,从运行时的硬件计数器进行评价的,也有从程序运行的轨迹(trace)或profile进行评价的;第四是离线(offline)识别还是在线(online)识别?第五是要求识别(detection)还是预测(prediction)phase的变化?

问题定义与数学抽象

关于program phase的定义,不同的研究者给出的定义不尽相同。Sherwood 等[1]将phase定义为“具有相似行为的大小固定的interval的集合“(We define a phase as a set of intervals (or slices in time) within a program’s execution that have similar behavior, regardless of temporal adjacency. );Hind等[2]将phase检测问题抽象为在抽象成一个长字符串的execution profile上的相似子串切分问题,进行了形式化的建模,并指出粒度(granularity)和相似度(similarity)是phase detection问题的两个最重要参数;Gu等[3]将其定义为“从某种抽样角度相似的行为的序列”(a phase is sequence of similar actions, as seen from a particular sampling perspective.),并提出interval的大小不应该是固定的。本文选用 Sherwood[1]的观点。

Phase Analysis的应用

Gu等研究者例举了以下应用[3]:

  • Program understanding and debugging:用于程序理解和调试。
  • Reducing simulation and profiling workload:降低模拟器的时间开销,减少profiling的overhead。
  • System reconfiguration:为可配置硬件/系统提供帮助,主要是嵌入式系统和移动设备。
  • Adaptive optimizations:JVM、.NET这样的托管环境是phase analysis技术最为活跃的使用领域。

Phase的划分方法

研究者尝试了很多不同种类的评估标准,从纯软件的代码结构分析到纯硬件的事件计数器。Gu等将评估方法分成以下几类[3]:

  • High level software data:使用类似过程体、函数调用图之类的代码信息。Sherwood等[1]使用的“Basic Block Vector”即属于这一类。
  • low level software data:利用指令片段等低级信息。
  • mixed software/simulated hardware data:使用代码信息的同时,使用硬件模拟器模拟运行以获得相应的数据。
  • simulated hardware data:使用硬件模拟器模拟运行得到程序运行的性能数据。
  • real hardware data:使用真实的硬件事件计数器信息。

phase analysis算法按照获取数据的时间可以大致分成online和offline两大类。Online phase analysis在程序运行的时候动态的识别或预测phase的变化,一般不需要代码相关的信息,根据硬件数据分析,硬件数据可以是真实硬件的数据也可以是在模拟器中运行的数据。Offline phase analysis则可以是完全不需要程序的运行数据(纯代码分析方法),或者是将程序运行若干次得到的profile进行分析。[3]

Phase Analysis的研究现状

Phase analysis的论文在2002~2004年的时候发表的比较多[1][2][4][5][6],之后每年大约十篇左右,每年在程序语言和编译技术的顶级会议上会有一到两篇phase analysis相关的论文(包括应用)。主要的研究团队有McGill大学的Dayong Gu和Clark Verbrugge、加利福尼亚大学圣芭芭拉分校Timothy Sherwood和Brad Calder等。

Bibliography

1: Sherwood, T. and Perelman, E. and Hamerly, G. and Sair, S. and Calder, B., Discovering and exploiting program phases, 2004

2: Hind, M.J. and Rajan, V.T. and Sweeney, P.F., Phase shift detection: A problem classification, 2003

3: Gu, Dayong and Verbrugge, Clark, A Survey of Phase Analysis: Techniques, Evaluation and Applications, 2006

4: Dhodapkar, A.S. and Smith, J.E., Comparing program phase detection techniques, 2003

5: Sherwood, T. and Perelman, E. and Calder, B., Basic block distribution analysis to find periodic behavior and simulation points in applications, 2002

6: Sherwood, T. and Sair, S. and Calder, B., Phase tracking and prediction, 2003

 

LLVM 2.8 发布

October 10th, 2010 2 comments

LLVM团队在这个月5号的时候发布了LLVM 2.8。新的版本引入了LLDB等工具,Clang和MC也有了不小的进步。可惜的是MIPS的Backend还是处于实验阶段,没有支持64 bit。希望在LLVM 3.0的时候可以支持MIPS64——如果支持龙芯3就更好了——恩,我在白日梦。

LLVM的Release Notes在这里

GCC Internals 4.5.x 中文版

September 25th, 2010 2 comments

GCC Internals是描述GCC内部结构的手册,有GCC团队维护。目前官方只有英文版提供。

Eric Fisher做了一个4.4的中文版,目前4.5的分支以及trunk都在翻译中。
目前项目托管在google code上:
http://code.google.com/p/gccint-zh/
有兴趣的同学可以co出来看看。

提取方法:
svn checkout http://gccint-zh.googlecode.com/svn/trunk/ gccint-zh-read-only
我负责的4.5分支:
svn checkout http://gccint-zh.googlecode.com/svn/branches/gcc-4.5.0/ gccint-4.5.0