提高 TM 模拟器的性能

Question

我正在尝试模拟很多 2 状态、3 符号（单向磁带）图灵机。每个模拟将有不同的输入，并且将运行用于固定数量的步骤。该程序当前的瓶颈似乎是模拟器，在不停止的图灵机上占用大量内存。

任务是模拟大约 650000 个 TM，每个有大约 200 个非空白输入。我正在尝试的最大步数是 10 亿 (10**9)。

下面是我运行ning 的代码。 vector<vector<int> > TM 是一个过渡 table.

vector<int> fast_simulate(vector<vector<int> > TM, string TM_input, int steps) {
    /* Return the state reached after supplied steps */

    vector<int> tape = itotape(TM_input);

    int head = 0;
    int current_state = 0;
    int halt_state = 2;

    for(int i = 0; i < steps; i++){

        // Read from tape
        if(head >= tape.size()) {
            tape.push_back(2);
        }
        int cell = tape[head];
        int data = TM[current_state][cell];  // get transition for this state/input

        int move = data % 2;
        int write = (data % 10) % 3;
        current_state = data / 10;

        if(current_state == halt_state) {
            // This highlights the last place that is written to in the tape
            tape[head] = 4;
            vector<int> res = shorten_tape(tape);
            res.push_back(i+1);
            return res;
        }

        // Write to tape
        tape[head] = write;

        // move head
        if(move == 0) {
            if(head != 0) {
                head--;
            }
        } else {
            head++;
        }
    }

    vector<int> res {-1};
    return res;
}

vector<int> itotape(string TM_input) {
    vector<int> tape;
    for(char &c : TM_input) {
        tape.push_back(c - '0');
    }
    return tape;
}

vector<int> shorten_tape(vector<int> tape) {
    /*  Shorten the tape by removing unnecessary 2's (blanks) from the end of it.
    */
    int i = tape.size()-1;
    for(; i >= 0; --i) {
        if(tape[i] != 2) {
            tape.resize(i+1);
            return tape;
        }
    }
    return tape;
}

在性能或内存使用方面有什么地方可以改进吗？即使减少 2% 也会产生显着差异。

Answer 1

确保在整个 TM 模拟期间没有分配发生。

在程序启动时预分配一个全局数组，它对于磁带的任何状态都足够大（例如 10^8 元素）。最初将机器放在该磁带阵列的开头。维护段[0;当前机器模拟访问过的所有单元格的 R]：这使您可以避免在开始新模拟时清除整个磁带阵列。

对磁带元素使用足够的最小整数类型（例如，如果字母肯定少于 256 个字符，则使用 unsigned char）。如果字母表非常小，您甚至可以切换到位集。这减少了内存占用并提高了 cache/RAM 性能。

避免在最内层循环中使用通用整数除法（它们很慢），仅使用二的幂除法（它们会变成移位）。作为最后的优化，您可以尝试从最内层循环中删除所有分支（对此有各种巧妙的技术）。

Answer 2

改变

int move = data % 2;

到

int move = data & 1;

一个是divide，一个是bitmask，都应该在低位给0或者1。您可以随时执行此操作，只要您有 % 的 2 的幂。

您还设置了

cell = tape[head];
data = TM[current_state][cell]; 
int move = data % 2;
int write = (data % 10) % 3;
current_state = data / 10;

每一步，无论 tape[head] 是否已更改，甚至在您根本不访问这些值的分支上。仔细查看哪些分支使用哪些数据，并且只在需要时更新内容。写完之后直接看：

    if(current_state == halt_state) {
        // This highlights the last place that is written to in the tape
        tape[head] = 4;
        vector<int> res = shorten_tape(tape);
        res.push_back(i+1);
        return res;
    }

^ 此代码未引用 "move" 或 "write"，因此您可以将 "move"/"write" 的计算放在它之后，并且仅在 current_state != halt_state

另外，if 语句的真分支是优化分支。通过检查 not 暂停状态，并将暂停条件放在 else 分支中，您可以稍微改进 CPU 分支预测。

Answer 3

这是另一个使用更多算法方法的答案。

块模拟

由于您的字母表和状态数量很少，您可以通过一次处理磁带块来加速模拟。这与众所周知的 speedup theorem 有关，尽管我建议使用稍微不同的方法。

将磁带分成每块 8 个字符。每个这样的块都可以用 16 位数表示（每个字符 2 位）。现在假设机器位于块的第一个或最后一个字符处。然后其后续行为仅取决于其初始状态和块上的初始值，直到 TM 移出块（向左或向右）。我们可以预先计算所有（块值 + 状态 + 结束）组合的结果，或者可以在模拟期间懒惰地计算它们。

此方法一次可以模拟大约 8 个步骤，但如果你不走运，它每次迭代只能执行一个步骤（围绕块边界来回移动）。这是代码示例：

//R = table[s][e][V] --- outcome for TM which:
//  starts in state s
//  runs on a tape block with initial contents V
//  starts on the (e = 0: leftmost, e = 1: rightmost) char of the block
//The value R is a bitmask encoding:
//  0..15 bits: the new value of the block
//  16..17 bits: the new state
//  18 bit: TM moved to the (0: left, 1: right) of the block
//  ??encode number of steps taken??
uint32_t table[2][2][1<<16];

//contents of the tape (grouped in 8-character blocks)
uint16_t tape[...];

int pos = 0;    //index of current block
int end = 0;    //TM is currently located at (0: start, 1: end) of the block
int state = 0;  //current state
while (state != 2) {
  //take the outcome of simulation on the current block
  uint32_t res = table[state][end][tape[pos]];
  //decode it into parts
  uint16_t newValue = res & 0xFFFFU;
  int newState = (res >> 16) & 3U;
  int move = (res >> 18);
  //write new contents to the tape
  tape[pos] = newValue;
  //switch to the new state
  state = newState;
  //move to the neighboring block
  pos += (2*move-1);
  end = !move;
  //avoid getting out of tape on the left
  if (pos < 0)
      pos = 0, move = 0;
}

停机问题

评论说 TM 模拟预计要么很早就完成，要么运行所有步骤达到预定义的巨大限制。由于您要模拟许多图灵机，因此可能值得花一些时间来解决 halting problem.

第一种可以检测到的挂机是：当机器停留在同一个地方，没有远离它。让我们在模拟期间保持 TM 的 surrounding，这是距离 TM 当前位置 < 16 的字符段的值。如果你有 3 个字符，你可以用 62 位数字对周围进行编码。

为TM的每个位置维护一个散列table（我们稍后会看到，只需要31个table）。在每一步之后，将元组 (state, surrounding) 存储在当前位置的散列 table 中。现在是重要的部分：每次移动后，清除距离 TM >= 16 处的所有散列 table（实际上，只需要清除一个这样的散列 table）。在每一步之前，检查散列 table 中是否已经存在 (state, surrounding)。如果是，则机器处于无限循环中。

您还可以检测另一种类型的挂起：机器向右无限移动，但永远不会 returns 后退。为了实现这一点，您可以使用相同的 hashtables。如果 TM 位于索引为 p 的磁带的当前最后一个字符处，则不仅在 p- 中检查当前元组（状态，周围）第 hashtable，而且在 (p-1)-th，(p-2)-th，.. ., (p-15)-th hash tables。如果找到匹配项，则 TM 将无限循环向右移动。

提高 TM 模拟器的性能

Improving performance for a TM simulator

c++

performance

turing-machines

performance-testing

块模拟

停机问题