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 上的模拟历史可能会被损坏。 这需要复杂的“回滚”协议来纠正错误的计算。 这两种模拟方法都会在算法执行过程中导致时间范围的演变和波动。该研究将利用 PI 和合作者最近发现的非平衡表面生长现象与保守方案的波动时间范围演变之间的新颖联系。 随着可用于计算科学和工程问题的计算机节点数量增加到数千，必须解决底层算法的可扩展性问题。 这些问题包括算法渐近扩展的程度（在无限数量处理器的限制下）以及它们如何接近渐近极限。 最近，PI 研究了这样的情况：每个 PE 在规则格子拓扑上连接到其最近邻居的 PE，并且每个 PE 如果不提​​前时间，则无需执行额外的计算。 这接近算法可扩展性的“最坏情况”场景。 然而，结果表明，非空闲 PE 的分数是有限的，并且在无限多个 PE 的渐近极限中远离零。 因此，随着问题规模和 PE 数量的增加，该算法是可扩展的。用于获得 PDES 这些结果的 PI 和合作者的方法是非平衡界面/表面物理的强大机制，特别是有限尺寸缩放和通用性，应用于波动的时间范围。 本研究旨在扩展此类调查。 特别是，通常应用于物理表面的有限尺寸缩放、普适性、重整化群、粗粒度和平均场方法将应用于 PDES 模拟过程中出现的简单模型时间表面和实际时间表面在科学和工程领域。 根据时间范围的“形态”特性，PI 将设计和开发同时优化模拟速度和数据管理的算法。 该研究是计算机科学、非平衡表面物理学和复杂系统研究之间的跨学科研究。 它将有助于可扩展的大规模并行算法的工程和微调，而实际实现将有助于理解大型异步系统中的协作行为。 这笔赠款还特别重视年轻科学家的教育和培训。%%%***