EAPSI:Facilitating cooperation between unreliable processors without direct communication

现代高性能计算机有许多不同的处理器，它们必须协同工作才能完成传入的任务。这些处理器不能有效地通信，可能以不同的速度运行，并且可能在没有警告的情况下发生故障。这项研究将实现一种新方法，允许多个不可靠的处理器在不直接相互通信的情况下完成任务。处理器不知道任务何时到达，必须在任务到来时处理它们。在这种情况下划分工作是高性能计算的一项基本任务，这项研究有可能提高实际系统的性能。这项工作将在新加坡国立大学与Seth Gilbert教授合作进行，他是该方法的发明者之一，将为这项研究的实施提供宝贵的帮助。这种数据结构，即动态待办事项树，是异步处理器和在线任务的第一个任务映射数据结构，它实现了理论上的保证（在最优的log3 m范围内，其中m是并发任务的最大数量）。我们的目标是验证动态待办事项树也实现了良好的实际性能。将此数据结构与当前的技术状态进行比较，希望能显示出显著的改进。这些结果可能对问题的限制较少的版本（即任务是脱机的）以及其他类似的任务（如互斥和分布式时钟）具有更广泛的含义。该奖项由美国国家科学基金会与新加坡国家研究基金会共同资助。

Modern high-performance computers have many different processors that must work together to complete incoming tasks. These processors cannot communicate efficiently, may run at different speeds, and can break down without warning. This research will implement a new method that allows multiple, unreliable processors to complete tasks without communicating with each other directly. The processors have no prior knowledge of when the tasks will arrive, and must handle them as they come. Dividing work in this setting is a fundamental task in high-performance computing, and this research has the potential to improve performance of real systems. This work will be conducted at the National University of Singapore in collaboration with Professor Seth Gilbert, one of the inventors of this method that will provide invaluable assistance in implementation of this research. This data structure, the dynamic to-do tree, is the first task mapping data structure for asynchronous processors and online tasks that achieves theoretical guarantees (within log3 m of optimal where m is the maximum number of concurrent tasks). The goal will be to verify that the dynamic to-do tree also achieves good practical performance. This data structure will be compared with the current state of the art, hopefully showing a significant improvement. These results may have broader implications for less restricted versions of the problem (i.e. the tasks are given offline) and to other similar tasks such as mutual exclusion and distributed clocks. This NSF EAPSI award is funded in collaboration with the National Research Foundation of Singapore.