Archive

Archive for the ‘Research’ Category

如何写一篇没有节操的计算机科学论文

November 30th, 2012 No comments

本文是对这篇论文[1]内容的介绍。

做编译性能优化的同学,免不了要面对Benchmark这个东西。一个idea实现出来,Benchmark上跑一跑,如果性能提升了百分之几,那就是莫大的宽慰,可以写论文了。不过大多数的时候,性能提升是看人品的事情,性能下降的反而居多。这个时候,不要慌,不要愁,把链接次序改一改,多添加几个环境变量,见证奇迹的时刻到了:看看是不是性能的对比就不一样了?多试几次,最多会有5%~10%的性能改变,有时高有时低。这时,没有节操的你,就可以跳出对你最有利的链接次序和环境设置,放在自己的论文里面了。

开个玩笑。你肯定不是没有节操的人,但是严谨的你需要阅读一下Todd Mytkowicz等人的论文,防止自己在实验环节出现“Measurement Bias”错误。计算机发展到现在已经变得非常复杂,各种看起来微不足道的因素都有可能影响到你的性能测试结果。只有在实验的时候充分的考虑到这些可能的因素并积极的避免,才可能会让自己的实验结果更加的可信。

原论文的摘要:

This paper presents a surprising result: changing a seemingly innocuous aspect of an experimental setup can cause a systems researcher to draw wrong conclusions from an experiment. What appears to be an innocuous aspect in the experimental setup may in fact introduce a significant bias in an evaluation. This phenomenon is called measurement bias in the natural and social sciences.

Our results demonstrate that measurement bias is significant and commonplace in computer system evaluation. By significant we mean that measurement bias can lead to a performance analysis that either over-states an effect or even yields an incorrect conclusion. By commonplace we mean that measurement bias occurs in all architectures that we tried (Pentium 4, Core 2, and m5 O3CPU), both compilers that we tried (gcc and Intel’s C compiler), and most of the SPEC CPU2006 C programs. Thus, we cannot ignore measurement bias. Nevertheless, in a literature survey of 133 recent papers from ASPLOS, PACT, PLDI, and CGO, we determined that none of the papers with experimental results adequately consider measurement bias.

Inspired by similar problems and their solutions in other sciences, we describe and demonstrate two methods, one for detecting (causal analysis) and one for avoiding (setup randomization) measurement bias.

[1]: Producing wrong data without doing anything obviously wrong

附:标题抄袭了果壳/mihir0的这篇文章:

要显著,不要节操——如何写一篇节操丧尽的心理学论文

摘录:充满幽默感的论文摘要

November 30th, 2012 No comments

原文见这里

Using code examples in professional software development is like teenage sex. Those who say they do it all the time are probably lying. Although it is natural, those who do it feel guilty. Finally, once they start doing it, they are often not too concerned with safety, they discover that it is going to take a while to get really good at it, and they realize they will have to come up with a bunch of new ways of doing it before they really figure it all out.

OCCP 2013: Call for Papers

October 22nd, 2012 No comments

一个新的 Workshop,做事务内存方向的同学可以关注下。

—————————————————————-

CALL FOR PAPERS

OCCP 2013

1st Workshop on Optimistic Cooperation in Concurrent Programming

Rome, Italy, March 16th, 2013
(collocated with ETAPS 2013)

http://www.scss.tcd.ie/Vasileios.Koutavas/occp-workshop/
—————————————————————-

* DESCRIPTION

Optimistic concurrency has long been accepted as a convenient method for programming systems where there is contention for resources. Traditionally in database systems and more recently in software transactional memory systems, optimistic concurrency is realized in the form of transactions, which the programmer can assume run isolated from their environment, thereby alleviating the need for explicit programming of locking schemes.

Recent research on concurrent programming models have lead to the realization in both academia and industry that optimistic concurrency can also be advantageous in programming systems where concurrent processes need to cooperate to perform a desired task. In such systems transactional isolation needs to be abandoned.  This brings forward numerous challenges in 1) the design and implementation of such systems, 2) the invention of appropriate programming language support for optimistic process cooperation, 3) the semantics, theory and verification of these systems.

This workshop aims to bring together researchers and practitioners from academia and industry who work on aspects of optimistic process cooperation. It also aims to connect the different research communities pertinent to this field. These include the programming language community, the systems community and the concurrent calculi community.

* SCOPE

Topics of interest include, but are not limited to:

– Programming language support for optimistic process cooperation.
– Semantics and theory of optimistic process cooperation.
– Compilation techniques and runtime systems.
– Calculi for modelling optimistic process cooperation in concurrent and distributed computing.
– Use of optimistic cooperation in the modelling of service-oriented and biological systems.
– Reversible computation.
– Static analysis and verification of systems employing optimistic process cooperation.
– Programming idioms for optimistic process cooperation.
– Applications where optimistic process cooperation can provide a significant benefit to the programmer.
– Experience reports of existing systems and prototypes employing forms of optimistic cooperation.

* INVITED SPEAKERS

– Suresh Jagannathan (Purdue University)
– Victor Luchangco (Oracle Labs)

* TUTORIALS

– Matthew Fluet  (Rochester Institute of Technology)  Transactional Events
– Vasileios Koutavas  (Trinity College Dublin)  Theory of Optimistic Cooperation

* PAPER SUBMISSION AND PUBLICATION

Submitted papers should contain previously unpublished complete work, work in progress, or experience reports. Submissions should be in PDF format, prepared using the EPTCS style (http://style.eptcs.org/), and should be from 7 to 15 pages long, including references. Papers must be submitted through the Easychair page of the workshop: http://www.easychair.org/conferences/?conf=occp2013

Accepted papers will be distributed in electronic preliminary proceedings at the workshop. Subsequently, selected papers will be invited for publication in a post-workshop refereed proceedings in Electronic Proceedings in Theoretical Computer Science.

* DATES

Abstract submission deadline:  17 December 2012
Paper submission deadline:  21 December 2012
Notification:  18 January 2013
Camera ready deadline:  22 February 2013

* ORGANISERS

Nick Benton  (Mircosoft Research)
Matthew Fluet  (Rochester Institute of Technology)
Matthew Hennessy  (Trinity College Dublin)
Vasileios Koutavas  (Trinity College Dublin)
Jens Palsberg  (UCLA)

[新闻]中国科大的研究团队中了POPL,内地第一篇,一作梁红瑾

October 10th, 2011 No comments

转自http://news.ustc.edu.cn/xwbl/201110/t20111009_120986.html

我校研究论文被POPL录用 为大陆研究机构首篇被录用论文
2011-10-09
日前,中科大-耶鲁高可信软件联合研究中心梁红瑾、冯新宇和付明的论文“一种用于验证并发程序变换的基于依赖-保证的模拟关系”(A Rely-Guarantee-Based Simulation for Verifying Concurrent Program Transformations)被第39届编程语言原理国际会议(ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages,简称POPL)录用。此前,中国大陆尚无任何单位以第一作者单位的身份在POPL上发表过论文,中国科大是第一个以第一单位在POPL上发表论文的高校和科研院所。

POPL是编程语言领域历史最久、水平最高的国际会议,它是讨论编程语言和编程系统最新突破的最主要论坛,内容涵盖编程语言的理论、编程语言的设计、编译器技术、程序分析、程序验证、可信软件等众多研究领域。国际期刊和会议的各种分区方法都把POPL放在该领域的最高区域中。

论文第一作者梁红瑾是中国科大计算机科学与技术学院博士一年级学生,她与冯新宇教授等的论文提出了一种验证并发程序变换的一般方法,首次将并发程序逻辑中的依赖-保证条件(rely-guarantee conditions)引入到传统的程序模拟关系(simulation)中,成功地解决了对验证提供模块化支持的难题,并将这种方法应用于编译优化、并发数据结构的实现和并发垃圾收集等算法的正确性验证。审稿人对论文的贡献给予了充分肯定,他们分别指出:“我感到这篇文章很吸引人。结合模拟关系与依赖-保证推理的想法看起来很不错,而且我在别处都没有见过……这项工作能提供一种漂亮的统一理论,用于验证并发程序变换。”“并发系统的精化问题的研究非常具有挑战性,这篇文章则向这个领域迈出了很好的一步。”“一个能够同时支持运行时系统验证和编译器验证的逻辑将非常有用。这篇文章展示了这样一个逻辑,并且看起来是一种非常普适的、自然的方法。”

作为联合研究中心的研究进入国际一流水平的又一体现是,联合研究中心邵中教授(我校大师讲席教授)和冯新宇教授被介绍国际新兴技术的期刊列为国际上从事新兴技术“防崩溃代码”(Crash-Proof Code)的主要研究人员。防崩溃代码是美国麻省理工学院主办的、颇具影响力的Technology Review杂志(中文版名字为《科技创业》)今年第6期评选出的2011年度十大新兴技术之一。这项技术是指用逻辑推理的方法来进行程序验证,以构造高可信的安全攸关软件。《科技创业》主要介绍了澳大利亚国家信息与通信技术研究中心(NICTA)2009年完成的对可以实际应用的操作系统内核seL4的验证。《科技创业》在有关这项技术的报导中提到,从事这方面研究的还有我校冯新宇教授、微软Redmond研究院Chris Hawblitzel研究员和耶鲁大学邵中教授。

NICTA的研发主要展示验证大型系统软件的可行性。他们验证了seL4的大部分代码,但由于相关理论和技术的欠缺,不得不放弃对一些最底层的关键代码的验证,包括底层部分C代码和600行汇编代码,因而可靠性保证尚不够彻底。邵中教授和冯新宇教授的研究则主要针对系统软件验证中的关键理论和技术。他们带领联合研究中心的研究人员等在2008年也验证了一个小的实验性的操作系统内核以展示相关理论和技术上的突破。虽然该内核比seL4小得多,但得益于他们提出的“开放式验证框架理论”的方法学、硬件中断验证技术和汇编程序验证技术,内核的所有代码都得到了验证。

中科大-耶鲁高可信软件联合研究中心成立于2008年10月,以我校计算机学院软件安全实验室的力量为主体,耶鲁大学邵中教授主持的Flint小组给予技术支持和研究合作。双方的合作研究始于2004年,根据研究领域和研究队伍的特点,当初就把目标设定为建设领域内国际一流的研究中心。经历以耶鲁为主合作发表、以我方为主合作发表和我方能够独自发表国际一流水平论文这样几个阶段,联合研究中心已经奠定了坚实的研究基础,形成了以海外引进的冯新宇教授为学术带头人的研究团队。

(计算机学院)

[笔记]Transparent Virtualization of Graphics Processing Units

September 25th, 2011 No comments

一个月之前 Dr. Pavan Balaji 做的一个报告,介绍他正在做的GPU虚拟化的工作。(报告的介绍在这里

问题的背景是目前使用GPU进行计算的案例越来越多,工作站一般使用一块或者几块显卡,高性能中心使用数量巨大的GPU进行加速计算。如果遇到显卡坏了需要更换,或者添加了新的显卡的时候,就需要将应用停止下来,然后重新开始。进一步的,如果应用所在的主机上没有特定的显卡,那么应用就无法进行计算了(或者使用模拟的方法,但是效率很低)。

Dr. Pavan Balaji 给出的解决方法是将GPU虚拟化,做成一个“GPU云服务”的形式(又是云计算)。通过一个运行时环境,将一个网络中的可用的GPU都集中起来管理,统一分配和调度,能够解决上述的两个问题。对于物理显卡维护的问题,云服务环境可以将分配在待拆卸显卡上的计算分流到别的GPU上去;当有新的GPU插进来时再自动的分配计算。如果本机没有可用的GPU,就通过网络将计算发给另外一台或多台主机的闲置GPU上进行计算。

这个方案最大的好处就是方便,但是要应用起来,第一个问题就是通用性。如果重新设计了一套GPU接口,需要程序修改之后才能使用,推广难度就会很大。而最大的挑战是性能。因为在CPU和GPU之间多添加了一个虚拟化层,甚至有时候需要通过网络传送数据,overhead 是相当可观的。

Balaji 重用了 OpenCL 的接口规范,重新实现了 OpenCL 的 runtime,从而解决了第一个问题。使用 OpenCL 接口的程序可以不需要任何修改就运行在虚拟化的GPU上。性能问题,Balaji做的工作主要是在函数的通信优化上,通过缓存函数参数、将小函数调用打包成一个大的数据包再发送等方法降低开销。对于local(本机上)的GPU,这个方法得到的效果还不错。而对于remote(别的主机上)的GPU,使用MPI作为下层实现,数据甩来甩去,优化的效果估计不会太乐观,空间估计也不会太大。