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

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

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