Document Actions
ACMChina – DL Pearls from China, March 2009
ACMChina – DL Pearls from China, March 2009
- Natural algorithms
-
ACM -SIAM Symposium on Discrete Algorithms
Pages: 422-431
Year of Publication: 2009
Author: Bernard Chazelle
Abstract Translated by: 俞纬
Abstract:
该篇论文给出了给出自组织的复杂系统可以用算法方法研究的证据。通常情况下，自组织的复杂系统通常都是用物理学和控制论等方法来进行研究的。该文章使 用理论计算机的工具，解决了理论环境学中的一个古老的问题：计算鸟群位置时的收敛问题。该文证明了，如果要收敛到一个稳定的状态，那么2^2^...^n 的模拟次数是必须的。这里，幂的高度是鸟的数目的线形函数，而n为鸟的数目。并且，出人意料的，我们证明了这个界是对于这个模型来说是固有而无法改进的。 这个令人惊奇的结果证明了用算法方法来解决生物动力学系统问题的可能性，这被称为“自然算法”。
- Topic：Relays, base stations, and meshes: enhancing mobile networks with infrastructure
-
Proceedings of the 14th ACM international conference on Mobile computing and networking
Pages: 81-91
Year of Publication: 2008
ISBN:978-1-60558-096-8
Authors: Nilanjan Banerjee, Mark D. Corner, Don Towsley, and Brian N. Levine
Abstract Translated by: 文浩
Abstract:
无线移动网络固有地存在间断的连接和高延迟。部署路由支持的基础架构（包括基站、Mesh节点和中继节点），虽然可以提高网络性能，但其成本和性能之 间的权衡关系却并不清晰。本文通过部署一个大规模的车用网络，研究了不同的架构部署方式。研究结果表明了每种部署方式各具一定优势。由于这些实验结论只适 用与具有相似特征（网络规模、无线技术、移动特征）的网络，作者进一步提出了一个精确的分析模型以提供理论支持。
根据本文的实验部署和理论分析，作者得到了两点关于基础架构部署的重要结论：1.如果增加x个基站能使得车用网络的数据包平均延迟降低一半，那么达到 同样的效果需要2x mesh节点或者5x中继节点。考虑部署基站的成本，选择部署mesh节点或中继节点经济上更为可行；2.我们观察到即使只部署少量的基础架构也优于依靠 大量的移动节点来完成路由中继，从而避免采用网络分割容忍的路由方式。
- MPIWiz: subgroup reproducible replay of mpi applications
-
Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming
Pages: 251-260
Year of Publication: 2009
ISBN:978-1-60558-397-6
Authors: Ruini Xue, Xuezheng Liu, Ming Wu, Zhenyu Guo, Wenguang Chen, Weimin Zheng, Zheng Zhang, Geoffrey Voelker
Abstract Translated by:薛瑞尼
Abstract:
消息传递接口（Message Passing Interface，MPI）是分布式计算环境中实现粗粒度并行编程的事实标准。然而，MPI程序内在的不确定性（non-determinism）和计 算规模使得调试MPI程序非常困难。许多MPI重播工具使用数据重播（data-replay）或者顺序重播（order-replay）确定性地重播 MPI程序来辅助调试。然而每种方法都存在不足：数据重播记录所有消息内容可能产生大量日志，顺序产生日志很小但重播时需要启动所有进程。这些不足使得基 于确定性重播的调试技术未能在MPI程序的开发过程中广泛使用。
本文提出了分组再现重播（Subgroup Reproducible Replay，SRR），一种混合的确定性重播技术，融合了数据重播了顺序重播的优点同时避免了二者的不足。SRR将MPI程序的所有进程分成不同小组， 组间通信采用数据重播，组内通信采用顺序重播。这样，SRR可以充分利用程序中存在的通信局部性。在重播时，程序员可以重播独立的每个小组。SRR由于不 记录组间通信减小了日志量，同时通过控制分组规模降低了重播时的资源需求。用户可以利用这种灵活性在MPI程序中自由地实时确定性重播。
MPIWiz是基于上述观点实现的一个原型系统。这个原型系统支持对应用程序函数和系统调用的动态插装，用户程序无需代码修改和重新链接就可以处理 MPI程序和系统调用中的不确定性函数。实验结果显示与数据重播相比，MPIWiz的日志规模最大可以减少3/4。与正常执行时间相比，日志记录运行时间 开销约为27%，重播可以在53%的时间内完成。