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.%%%***

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