Archive

Archive for March, 2011

Google Summer Of Code 2011 编译器项目介绍

March 27th, 2011 2 comments

Google Summer Of Code 2011(被墙) 正在进行中,将会在明天开始接受学生提交proposal,截止时间是四月八号。
今年共有四个编译器项目被Google接受。LLVM和GCC没有悬念的出现在了开源项目名单中。过去几年这两个组织接受的学生数量都在5~7个之间,今年可能也不会有太大变化。除了LLVM和GCC之外,还有Jikes RVM和Jato VM两个Java虚拟机/编译器项目,这两个项目也是GSoC的“老项目”。其中Jikes RVM比较成熟,是编译器领域研究论文广泛使用的实现平台。Jato VM是一款尚在开发中的Java JIT,目前的版本号是0.2。
过去几年均有中国学生参与了GCC或LLVM的GSoC项目,希望今年也可以再接再厉。不过目前GSoC的主页在大陆地区无法打开,为高校学生参与开源项目制造了不少人为障碍。

附带上这几个组织的Idea List:

GCC:http://gcc.gnu.org/wiki/SummerOfCode

LLVM:http://llvm.org/OpenProjects.html

Jikes RVM:http://jikesrvm.org/Google+Summer+of+Code+2011

Jato VM:http://www.jatovm.org/projects.html

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

 

伯克利、UIUC、斯坦福三所大学并行计算研究介绍

March 7th, 2011 No comments

本文是这篇论文( PDF)的笔记:

“Ubiquitous Parallel Computing from Berkeley, Illinois and Stanford“

 

导论

 

过去几十年处理器的性能一直遵循着摩尔定律增长,现有的软件可以在不改变代码的情况下提升性能。

但是这种趋势在几年前停止了。能耗限制使得处理器时钟频率无法继续提高,处理器厂商开始通过在一个芯片上放置多个核心来提升性能。现在只有支持并行化的应用才能享受到硬件性能提升带来的好处了。
这种变化对于服务器而言不是问题,(因为)可以通过大量的任务级并行来提高系统的吞吐量。问题是那些运行在客户端/移动设备上的应用,需要做算法上的改动支持并行化。
由此带来的问题有:

  1. 那种要求增加更多功能(性能)的、令人激动的新型客户端应用 会出现吗?
  2. 这类应用会(反过来)促进并行化么?
  3. 我们能开发出来一个编程环境,让大多数程序员(轻松的)开发并行代码么?
  4. 多核架构和运行其上的应用能够在未来十年内适应几百个核心的规模么?

我们相信以上所有的问题,答案都是肯定的。而及时的解决方案需要加速将研究创想推广到产业界中。
三所实验室的观点相同之处在于:都在针对特定类别的应用进行并行化,而不是沿用过去的方法研究“未来的未知的程序”;都集中于能够scale到上百个核心的客户端/移动设备上的应用;都认为单一的解决方案是不现实的;假设开发团队由计算机专家和领域专家混合组成。
三所实验室的观点差异之处在于:并行编程模式(pattern)在并行软件架构上的角色;针对的编程环境;并行代码的生成方式;并行化的架构支持方式;并行架构的验证(evaluate)方式。

 

ParLab at Berkeley

Patterns and Frameworks

大多数人设想的并行编程环境的设计目标是提供给当今的经过常规训练的程序员使用,而ParLab的设计目标是提供给“明天的程序员”——掌握一点计算机技能的领域专家使用。计算机专家和领域专家组成混合团队开发并行应用。
ParLab相信架构(Architecture)是并行程序设计的关键,框架(Framework)是架构实现高效的关键。ParLab用设计模式和一种模式语言作为框架的基础,程序通过设计模式层次化的构建,在不破坏模式的前提下进行定制(customization)。
ParLab构想的框架分为高、低两个层次:productivity层和efficiency层。前者面向领域专家,后者面向计算机专家。

SEJITS

类似Python、Ruby的高生产力语言具有很高的生产率,但是执行效率不如高效率语言如C/C++/Java。现有的一种提高执行效率的方法是利用高生产力语言的延迟绑定特性,如果被调用的函数有相应的高效率语言编译好的模块实现,那么运行时环境就会使用编译好的高效率代码模块替代相应的函数;如果没有,则进行解释执行。
JVM和.NET都提供了类似的JIT功能,本项目的区别在于不会JIT整个高生产力语言,仅仅是对有对应高效率语言的代码生成器的部分进行JIT。
这样做的好处是领域专家和计算机专家可以更加有效的合作。领域专家专注与高生产力语言部分,计算机专家进行的并行化优化可以在运行时环境中直接替换掉原先的解释代码。
Copperhead是这个思想的一个例子。
项目的目标是针对图像处理应用的并行化提供支持。

Platforms and Applictions of 2020

未来的程序必然同时是跟移动客户端和云计算相关的。
浏览器中运行的客户端程序很多,所以浏览器的并行化也是关注焦点之一。
移动客户端和云计算都要考虑响应速度和功耗。
接下来使用了一个移动互联网应用来说明。这个应用叫“name whisperer”,运行在手机上,给走向你的人拍一张照片,传到云中进行分析,得到这个人的名字,通过手机上的扬声器说出这个人的名字。

Object Recognition Systems

将图像处理领域的算法进行并行化,利用GPU将原来4.2分钟的运行时间优化到1.8秒,提升了140倍。

Performance Measurement and Autotuning

原先对软件隐藏底层平台细节的做法已经不适应生产力发展了。现在需要一种新的接口,将硬件信息暴露给软件。This perspective suggests architectures with transparent performance and energy consumption and Standard Hardware Operation Trackers (SHOT).
ParLab认为自动性能调优是也重要的研究领域。

The Architecture and OS of 2020

我们预测2020年的芯片将会包含几百个核心,采用“hardware tile”的方式进行组织。每一个“tile”包含一个用于顺序代码ILP的处理器和一堆用于DLP的计算单元(GPU)。“tile”组成的阵列支持TLP。内存系统将是cache和scatchpads的混合系统。
运行于此类硬件之上的操作系统,也将会有大的变化,尤其是进程的调度方式。OS kernel会在“hardware tiles”进行粗粒度的调度(“Partitions”),而更细致的调度交给用户层来完成。

Par Lab Today

识别和使用了一些“软件模式”,应用在了视觉、音乐、医疗、语音、浏览器领域。
两个SEJITS原型和autotuner。
64-core tiles的FPGA模型,SHOT原型。
Tessellation OS原型,Lithe原型。

 

UPCRC–Illinois

在应用方面,关注于3D Web和human-centered interfaces。关注程序语言、编译器、运行时系统,致力于提供一个简单的并行编程模型。目前关注的硬件架构是上百个核心的共享内存系统。

Applications

3D Web将带来大量激动人心的新应用,同时这些应用对于算法的效率要求很高。为此我们设计开发了新的并行算法,以期达到更好的性能。在图像处理、视频领域设计的并行算法速度提高了1~2个数量级。
设计了ParKD等执行并行环境的数据结构来支持并行化。
我们也在研究并行浏览器。

Programming Environment

首先定义和区分了“concurrent”和“parallel”的概念,并指出多核带来的改变跟”concurrency“没有关系,影响的是”parallel programming“。
针对普通的并行编程的需求,我们致力于提供一种编程环境support simple parallelism with languages that are deterministic by default and concurrency safe。
基于Java的Deterministic Parallel Java(DPJ)提供了比较强的确定性,并提供了交互式的分析移植工具,以及代码检查工具。
对于共享库这样的高级并行需求,我们相信性能调优需要在一个编译分析和代码开发紧密结合的环境中进行。通过允许在代码中添加注解来知道编译器优化执行优化,使得在编译器中精细的调整GPU/多核CPU平台的参数成为可能。另外我们还使用autotuning技术来支持高级并行化要求。
SIMD模型最适合并行库和串行代码的集成。我们在Hierarchical Tiled Arrays(HTA)上的工作显示不仅在数组/循环上有很好的性能,在很多复杂应用中也有很好的潜力。

Architecture

关注的焦点在cache coherence protocols,提出了Bulk Architecture、DeNovo architecture、Rigel architecture三种不同的架构来探索cache coherence protocols。

 

The Stanford University Pervasive Parallelism Laboratory

The PPL Approach to Parallelism

我们认为异构架构是未来的趋势(也是现在的现实),而这将导致写并行程序更加困难。我们认为唯一的出路就是提供面向领域的并行语言和编程环境。为此我们的并行环境分成了3个层次:最上层是DSL层,一个领域对应一个领域专属语言;第二层是DSL Infrastructure层,包含一个领域嵌入式语言(Scala)和一个公共并行运行时环境(Delite);最下层是(异构)的硬件体系结构。
每个层次的具体介绍略。

 

参考文献

 

[1]Catanzaro et al.,Ubiquitous Parallel Computing from Berkeley, Illinois, and Stanford,IEEE Micro,2010

Pidgin加密插件介绍

March 1st, 2011 No comments

PidginUnix/Linux下使用最多的IM客户端,支持MSNGTalk、飞信1等几十种协议。Pidgin同时也是一个开放应用程序框架,允许用户开发自己的插件。本文介绍在Pidgin官网列出的几款通信加密插件,并分析其安全性和易用性。

Pidgin-paranoia

Pidgin-paranoia基于一次一密乱码本的加密原理。假设你和朋友各自有一本一模一样的小本子,里面写的是一串随机字符序列。当你要发信息给朋友的时候,就将信息(明文)按照顺序与小本子中的随机字符进行异或操作,这就加密成了密文。你的朋友收到密文之后根据小本子将密文再次进行异或操作,便还原了明文。之后你和朋友将乱码本上“用过”的字符序列撕掉,下次加密/解密的时候使用新的随机字符序列。如果乱码本的随机字符序列足够长,那么理论上一次一密乱码本是无法破解的。

一次一密乱码本原理上完美,使用上却有几个问题。第一个问题就是乱码本属于对称加密,你和朋友需要共享乱码本。如果安全的与朋友共享乱码本而不被他人监听获取,是对称密码的主要的问题。Pidgin-paranoia官方页面给出的一个方案是“拷贝到U盘里面,然后(寄)给你的朋友

对称加密的第二个问题是如果你有N个朋友,那么你就需要N个密码本。如果这些朋友相互之间通信,那么就需要N*N个不同的密码本。朋友一多,乱码本管理就麻烦起来。

通信的安全性只依赖于乱码本的安全性,乱码本是明文保存在硬盘里的,进而安全性依赖于你和朋友的电脑的安全性。如果你的电脑被入侵,被盗窃,被别人扣留,那么对方就可以得到密码本,继而得以知道你和朋友聊天的所有内容。

另外,Pidgin-paranoia没有认证功能,无法确定和你聊天的是否就是你的朋友,中间人可以伪造消息。

Pidgin-paranoia目前的最新版本是0.4.0

Pidgin-GPG

PGP是久经考验的邮件加密工具/协议,而GPGPGPGNU实现。Pidgin-GPG实现了GPG的功能,从而(理论上)可以达到和GPG一样的安全性。

Pidgin-Encryption

Pidgin-Encryption的设计考虑了安全性和易用性的折中问题,设计时参考了SSH的风格。Pidgin-Encryption为每一个帐号新建一个公钥/私钥对。当你与朋友聊天时,Pidgin-Encryption会将你的公钥发送给对方,同时接收对方的公钥并保存起来。相互有了对方的公钥之后便可以进行加密聊天了。下一次聊天时Pidgin-Encryption会先比对对方发送的公钥和上次接受的公钥是否一致,如果不一致将提示你进行确认,以防止中间人攻击。

Pidgin-Encryption最大的特点就是易用,安装并开启了之后,不需要额外的设置就可以直接使用。Pidgin-Encryption使用MozillaNSS库,提供加密和认证两个功能。缺点是其安全性也依赖于私钥的安全性,而私钥是明文保存的,如果你的电脑被入侵,被盗窃,被别人扣留,那么对方就可以得到私钥,继而可能破译你和朋友聊天的所有内容。

周期性的删除并重新生成自己的公钥/私钥对可以在一定程度上避免以往的聊天内容被破译。

Pidgin-OTR

 

Pidgin-OTR是四款插件中最年轻的一款插件,采用Ian Goldberg等人专门为IM聊天设计的安全协议,其对IM通信安全的角度和目标也和之前的几款插件不同。

Ian Goldberg等人认为在IM上的“秘密”谈话应该和两个人在单独房间中谈话一样“秘密”,满足以下的特点(假设这两个人叫AliceBob):

  1. Alice能够确认自己在和Bob谈话,反之亦然。
  2. 房间只有他们俩,除非实现安装了窃听器,或者AliceBob)自己说出来,没有人知道他们的谈话内容。
  3. 即使AliceBob的谈话内容透露出来,她也不能证明这些话确实是Bob说的,反之亦然。

其中特点1是属于认证(Authentication)要求;特点2在网络上无法满足(任何路由节点都可以窃听),需要用加密来保证;特点3 Pidgin-EncryptionPidgin-GPG都无法满足。Pidgin-OTR根据以上的场景,在保密性和认证功能的基础上提出了另外两个设计目标:

  1. Perfect Forward Secrecy:即使获取了BobAlice的电脑,知道了所有的私钥、公钥、密码,截获了过去所有的数据包,也无法破译AliceBob过去的通信内容。
  2. Repudiable AuthenticationBob知道自己在和Alice通信,但是无法向第三人证明信息就是Alice发送的。

在实现上,Pidgin-OTR使用了短生命期密钥和消息认证吗机制来达到上述的两个设计目标。大致的协议过程如下:

  1. 通过经典的Diffie-Hellman密钥交换过程交换公钥,得到一个共享的密钥SS
  2. 密钥SS进行散列处理,得到通信需要的对称加密密钥EKMAC密钥MK,加密通道建立完成;
  3. 用第二组公钥再次使用Diffie-Hellman交换过程,得到第二个共享的密钥SS’
  4. 密钥SS’进行散列处理,得到通信需要的加密密码EK’MAC密码MK’
  5. 丢弃SSEK,将MK随后续数据报文发送出去,握手完成。

这个设计如何保证Perfect Forward SecrecyRepudiable Authentication

  1. Perfect Forward SecrecyPidgin-OTR在每次会话建立的时候生成临时的公钥/私钥对,并在会话结束时删除。由于AliceBob)的私钥只存在于AliceBob)的电脑中,一旦删除便可做到彻底无法恢复。这就保证了即使窃取了AliceBob)的电脑,或是在其中装了后门,也无法知晓之前AliceBob的通信内容。
  2. Repudiable Authentication:首先通信内容是采用的对称加密方式,这就使得Bob无法证明加密信息是自己生成的还是Alice生成的;其次步骤5的时候将MK发送出去,使得窃听者可以伪造基于密钥SS的数据包。由于AliceBob已经采用了基于SS’的密钥,所以无法欺骗AliceBob,但是另一方面,AliceBob就可以以此抵赖自己发送过的数据包。

其它通信安全问题

除了使用以上各种加密插件之外,以下问题也会对你和朋友的通信安全有影响:

  1. Pidgin聊天记录。默认是开启的,而Pidgin-Encryption等插件都是是默认保存解密后的明文。如果你的电脑被别人访问,对方可以直接看到你的聊天记录。加密聊天的时候最好选择“不记录本次会话”,或者干脆关闭聊天记录功能。
  2. 木马/后门/Rootkit/按键记录器。如果你是“重要人物”,那么小心你的电脑上可能会被黑客安装这些东西。这意味着你的私钥会被窃取,继而通信的安全性就不存在了。定期杀毒、经常更换私钥都无法彻底避免。用LiveCDLiveUSB来启动可以彻底避免这个问题。
  3. 站在背后的人/摄像头。他能看到你看到的内容,即所有聊天内容。
  4. 不要在网吧使用。理由是网管和GA局都可以看到你的屏幕。

参考链接

pidgin-paranoia主页:http://pidgin-paranoia.sourceforge.net/

pidgin-GPG主页:https://github.com/segler-alex/Pidgin-GPG/wiki

pidgin-encryption主页:http://pidgin-encrypt.sf.net/

pidgin-OTR主页:http://www.cypherpunks.ca/otr/

pidgin主页:http://pidgin.im/

1通过openfetion移植到Pidgin实现。

 

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