Neural algorithmic reasoners are parallel processors. Teaching them
sequential algorithms contradicts this nature, rendering a significant share of
their computations redundant. Parallel algorithms however may exploit their
full computational power, therefore requiring fewer layers to be executed. This
drastically reduces training times, as we observe when comparing parallel
implementations of searching, sorting and finding strongly connected components
to their sequential counterparts on the CLRS framework. Additionally, parallel
versions achieve strongly superior predictive performance in most cases.

神经算法推理器是并行处理器，教给它们顺序算法与其本质相悖，导致他们的大部分计算无效。与之相对，平行算法可以充分利用它们的计算能力，因此执行所需的层数较少。这大大减少了训练时间，比较了在 CLRS 框架上搜索、排序和查找强连通分量的平行实现与顺序实现，观察到这一点。此外，平行版本在大多数情况下实现了明显更好的预测性能。

并行算法与神经执行对齐

Parallel Algorithms Align with Neural Execution

In this paper we address the problem of designing an interruptible system in
a setting in which $n$ problem instances, all equally important, must be solved
concurrently. The system involves scheduling executions of contract algorithms
(which offer a trade-off between allowable computation time and quality of the
solution) in m identical parallel processors. When an interruption occurs, the
system must report a solution to each of the $n$ problem instances. The quality
of this output is then compared to the best-possible algorithm that has
foreknowledge of the interruption time and must, likewise, produce solutions to
all $n$ problem instances. This extends the well-studied setting in which only
one problem instance is queried at interruption time.
In this work we first introduce new measures for evaluating the performance
of interruptible systems in this setting. In particular, we propose the
deficiency of a schedule as a performance measure that meets the requirements
of the problem at hand. We then present a schedule whose performance we prove
that is within a small factor from optimal in the general, multiprocessor
setting. We also show several lower bounds on the deficiency of schedules on a
single processor. More precisely, we prove a general lower bound of (n+1)/n, an
improved lower bound for the two-problem setting (n=2), and a tight lower bound
for the class of round-robin schedules. Our techniques can also yield a
simpler, alternative proof of the main result of [Bernstein et al, IJCAI 2003]
concerning the performance of cyclic schedules in multiprocessor environments.

设计并行处理的可中断系统，采用合同算法进行调度，并提出新的性能评价指标，证明在一般的多处理器环境中存在一种调度算法，其性能接近最优，同时找到了单处理器的若干种最小系统缺陷下界的限制。