EAPSI:Facilitating cooperation between unreliable processors without direct communication

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

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.