algorithm - 优化(并行化)我的 "virtual machine"模型的执行

Question

假设我有一个简单的“虚拟机”模型，它以下列格式之一保存指令队列:

• unary_opcode, in_address, out_address
• binary_opcode、in1_address、in2_address、out_address

其中所有地址都是存储单元数组的整数。

是否有任何著名的算法可以分析指令序列并尝试尽可能多地并行化指令，而无需:

1. 从顺序执行中产生不同的结果。
2. 数据竞赛。

Answer 1

如果指令 A 在列表中的指令 B 之前，并且 ((B 读取 A 的写入之一) OR (B 和 A 具有相同的写入地址) OR (B 写入 A 的读取之一))，则添加一个定向从 B 到 A 的边。请注意，此图是一个 DAG，因为指令是按特定顺序排列的。

现在将一条指令的“层”计算为:没有出边的指令是第 1 层。只有到第 N 层及以下的出边的指令是第 N+1 层。显然，如果一条指令有一条到另一条指令的传出边，而另一条指令的层未知，请不要给它赋值!有一个简单的递归例程用于从每​​条指令分配像 DFS 一样工作的层。

现在第 i 层的指令可以在周期 i 上运行(但不会更早)，这是最优的。

如果并行机能够抑制来自早期指令的写入，则可能会做得更好(在这种情况下可以删除写入-写入冲突边缘)。我的确切意思是，当给定一批要并行执行的指令时，如果其中一些指令具有相同的写入地址，则机器确定性地写回批处理中最后一条指令的结果以写入该地址(而不是具有未指定的行为，或者不确定地写回写入该地址的批处理中的 -some- 指令的结果)。