ITR/AP(MPS): Non-Equilibrium Surface Growth and the Scalability of Parallel Discrete-Event Simulations for Large Asynchronous Systems

ITR/AP(MPS)：大型异步系统的非平衡表面生长和并行离散事件仿真的可扩展性

• 批准号: 0113049
• 负责人: Gyorgy Korniss
• 金额: $ 45万
• 依托单位: Rensselaer Polytechnic Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-15 至 2005-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0113049&HistoricalAwards=false
• 关键词: ITR; AP; MPS; Non; Equilibrium

This award is the result of a proposal submitted to the Information Technology Research initiative. Modeling and simulation of the evolution of natural and artificial complex systems are of fundamental importance in both sciences and engineering. In a large class of systems, the underlying dynamic is asynchronous, the "updates" in the local "configurations" of the system are discrete events in continuous time. Examples of such systems include magnetization dynamics in condensed matter, the evolution of financial markets, call arrivals in cellular communication networks, and the spread of emerging diseases and epidemics.To design and develop faithful and scalable parallel algorithms to simulate the evolution of large asynchronous systems is one of the most challenging areas in parallel computing. The ultimate goal of this proposal is to better understand how the scalability of Parallel Discrete-Event Simulation (PDES) algorithms can be enhanced, to program and run PDES simulations for a few chosen applications in science and engineering, and to educate junior researchers to allow them to prepare for careers at the interface between basic sciences and information technology. These types of PDES can be applied to an extremely wide spectrum of computational problems in science, engineering, manufacturing, biology, and economics.PDES use the concept of local random simulated time as well as a synchronization scheme. The parallel algorithm must concurrently advance the local simulated times of each subsystem carried by a processing element (PE), without violating causality. In a "conservative" PDES scheme, only those PE's which are guaranteed not to violate causality attempt the updates and increment their local time. The rest of the PE's must idle. In the "optimistic" approach the PE's do not have to idle, but since causality is not guaranteed at every update, the simulated history on certain PE's can become corrupted. This requires a complex "rollback" protocol to correct erroneous computation. Both simulation approaches lead to an evolving and fluctuating time horizon during algorithm execution.The research will exploit a novel connection recently discovered by the PI's and collaborators between non-equilibrium surface growth phenomena and the evolution of the fluctuating time horizon of conservative schemes. As the number of computer nodes available to a computational science and engineering problem increases to many thousands, questions of scalability of the underlying algorithms must be answered. These questions include both how well the algorithms scale asymptotically (in the limit of an infinite number of processors) and how they approach the asymptotic limit. Recently the PI's studied the case where each PE is connected to its nearest-neighbor PE's on regular lattice topologies, and each PE has no additional computation to perform if it is not advancing time. This is close to a "worst-case" scenario for scalability of the algorithm. Nevertheless, it was shown that the fraction of non-idling PE's is finite and bounded away from zero in the asymptotic limit of infinitely many PE's. Hence the algorithm is scalable as the problem size and number of PE's increase.The methodology of the PI's and collaborators used to obtain these results for PDES is the powerful machinery of non-equilibrium interface/surface physics, notably finite-size scaling and universality, applied to the fluctuating time horizon. This research aims to extend this type of investigation. In particular, the methods of finite-size scaling, universality, renormalization group, coarse-graining, and mean-field approaches that are commonly applied to physical surfaces will be applied to both simple model time surfaces and realistic time surfaces that arise during PDES simulations in science and engineering. Based on the "morphological" properties of the time horizon, the PI's will design and develop algorithms that optimize simulation speed and data management at the same time. The research is interdisciplinary at the border between computer science, non-equilibrium surface physics, and the study of complex systems. It will contribute to the engineering and fine-tuning of scalable massively parallel algorithms, while actual implementations will help to understand cooperative behavior in large asynchronous systems. This grant also puts special emphasis on the education and training of young scientists.%%%***

该奖项是提交给信息技术研究倡议的提案的结果。 自然和人工复杂系统演化的建模和仿真在科学和工程中具有根本的重要性。 在一个大类的系统中，潜在的动态是异步的，系统的本地“配置”中的“更新”是连续时间中的离散事件。 这类系统的例子包括凝聚态物质中的磁化动力学、金融市场的演化、蜂窝通信网络中的呼叫到达以及新兴疾病和流行病的传播。设计和开发忠实的和可扩展的并行算法来模拟大型异步系统的演化是并行计算中最具挑战性的领域之一。 该提案的最终目标是更好地了解并行离散事件仿真（PDES）算法的可扩展性如何得到增强，为科学和工程中的一些选定应用程序编程和运行PDES仿真，并教育初级研究人员，使他们能够为基础科学和信息技术之间的接口职业生涯做好准备。 这些类型的PDES可以应用于科学，工程，制造，生物学和经济学中非常广泛的计算问题。PDES使用本地随机模拟时间的概念以及同步方案。 并行算法必须同时推进由处理元件（PE）承载的每个子系统的局部模拟时间，而不违反因果关系。 在一个“保守”的PDES方案中，只有那些保证不违反因果关系的PE尝试更新并增加它们的本地时间。 其余的PE必须闲置。 在“乐观”方法中，PE不必空闲，但是由于在每次更新时都不能保证因果关系，因此某些PE上的模拟历史可能会损坏。 这需要一个复杂的“回滚”协议来纠正错误的计算。 这两种模拟方法导致一个不断发展和波动的时间范围在algorithmexecution.The研究将利用一个新的连接最近发现的PI的和合作者之间的非平衡表面生长现象和保守方案的波动时间范围的演变。 随着计算科学和工程问题的计算机节点数量增加到数千个，底层算法的可扩展性问题必须得到回答。 这些问题包括算法的渐近扩展性（在无限数量处理器的限制下）以及它们如何接近渐近极限。 最近PI研究了每个PE在规则格拓扑上连接到其最近邻居PE的情况，并且如果每个PE不推进时间，则每个PE没有额外的计算要执行。 这接近于算法可扩展性的“最坏情况”场景。 然而，它表明，非空闲PE的分数是有限的，并有界远离零的渐近极限无穷多个PE的。 因此，该算法是可扩展的问题的大小和数量的PE的increasing.The方法的PI的和合作者用来获得这些结果的PDES是强大的机械非平衡界面/表面物理，特别是有限大小的缩放和普遍性，适用于波动的时间范围。 这项研究旨在扩大这种类型的调查。 特别是，通常应用于物理表面的有限尺寸标度，普适性，重整化群，粗粒化和平均场方法的方法将被应用于简单的模型时间表面和在科学和工程中的PDES模拟过程中出现的现实时间表面。 基于时间范围的“形态学”属性，PI将设计和开发同时优化仿真速度和数据管理的算法。 该研究是计算机科学，非平衡表面物理学和复杂系统研究之间的跨学科。 它将有助于工程和可扩展的大规模并行算法的微调，而实际的实现将有助于理解大型异步系统中的合作行为。 该补助金还特别重视青年科学家的教育和培训。%*