Little Man 计算机程序输出 1，延迟 5 秒

Question

假设一个小人电脑程序需要1微秒来执行一条指令。我需要编写一个 LMC 程序，它接受 0 到 10（含）之间的输入，并在延迟那么多秒后产生一个 1 的输出。

例如，输入 5 将在五秒后产生输出 1。延迟不需要完美，但必须精确到 0.01% 或 100 微秒以内。我怎样才能做到这一点？

Answer 1

您需要创建循环来消磨时间。您需要一个大约需要 1 秒才能执行的代码块，然后重复执行与输入的数字相对应的该块。所以挑战在于设计需要 1 秒执行的代码。

让我们循环尝试一下：

       LDA start
loop   STA count
       LDA count
       SUB one
       BRP loop

       ; ...other code...

one    DAT 1
start  DAT 999
count  DAT

这个循环将有 1000 次迭代。每次迭代有 4 条指令，因此 1000 次迭代需要 4000µs。我们可以稍微加强代码以使循环有更多指令，但我们离 1 秒还差得很远，所以我们最好使用第二个循环来重复执行上面的代码。外循环需要迭代大约 250 次，因为 250*4000 = 一百万，即 1 秒。

所以我们会：

       LDA start2
loop2  STA count2

; here starts the code we used earlier
       LDA start3
loop3  STA count3
       LDA count3
       SUB one
       BRP loop3
; end of the code we used earlier

       LDA count2
       SUB one
       BRP loop2
       
       ; ... other code

one    DAT 1
start2 DAT 249
start3 DAT 999
count2 DAT
count3 DAT

如果我们对执行的指令数进行精确计算，那么我们得出：

内循环执行4*1000条指令
外循环在内循环之前有 2 条指令，在内循环之后有 3 条指令，因此总共有 5 条指令的“开销”。
总计 250*(5+4000) 条指令，即 1001250。

这有点太多了（因为开销）：偏差大约是 0.1%，所以我们需要稍微调整一下数字。

但是让我们首先通过实现执行上述代码的外部循环来完成程序，该循环执行输入中指定的次数：

       INP
       BRZ output ; output immediately!
       SUB one

; a new outer loop: 
loop1  STA count1

; start of what we already had:
       LDA start2
       
loop2  STA count2
       LDA start3

loop3  STA count3
       LDA count3
       SUB one
       BRP loop3

       LDA count2
       SUB one
       BRP loop2
; end of what we already had

       LDA count1
       SUB one
       BRP loop1

output LDA one
       OUT
       HLT

one    DAT 1
start2 DAT 249
start3 DAT 999
count1 DAT
count2 DAT
count3 DAT

请注意，我们添加的外部循环也有其开销...如果我们在该计数中包含 LDA start2，则同样有 5 条指令开销。

loop1 的一次迭代因此需要 5 + 1001250 = 1001255。

最后，现在让我们调整 start2 和 start3 值，使我们更接近 1000000。在电子表格中玩一对数字，你会发现你接近 start2 = 541 用于 542 次迭代，start3 = 459 用于 460 次迭代（您可以使用其他有趣的对，结果相似）。

在 loop3 的一次迭代中执行的指令：4
在loop2的一次迭代中执行的指令：5 + (460*4) = 1845
在loop1的一次迭代中执行的指令：5 + (542*1845) = 999995

因此我们还需要 5 条指令才能达到完美的秒数。这很简单...只需在 loop1 的开销中重复几次指令即可。所以我们最终得到这个：

       INP
       BRZ output ; output immediately!
       SUB one

; a new outer loop: 
loop1  STA count1

       LDA start2
       LDA start2 ; dummy instructions to spend 5µs more...
       LDA start2 ; ...
       LDA start2 ; ...
       LDA start2 ; ...
       LDA start2 ; ...
       
loop2  STA count2
       LDA start3

loop3  STA count3
       LDA count3
       SUB one
       BRP loop3

       LDA count2
       SUB one
       BRP loop2

       LDA count1
       SUB one
       BRP loop1

output LDA one
       OUT
       HLT

one    DAT 1
start2 DAT 541 ; the two magic numbers
start3 DAT 459 ; ...
count1 DAT
count2 DAT
count3 DAT

我们还没有谈到在 loop1 的外部执行的开销。这包括 BRZ、SUB（如果输入非零）和 output 部分中的两条指令（LDA 和 OUT），因此 3- 4µs.

这意味着我们对以下每个输入都有以下延迟：

input | µs from INP to OUT
------+-------------------
    0 |        3
    1 |  1000004
    2 |  2000004
  ... | ...
    9 |  9000004
   10 | 10000004

您甚至可以通过在外循环的最后一次迭代中跳过 4 条虚拟指令来摆脱那些额外的 4 毫秒。所以改变这个：

loop1  STA count1

       LDA start2
       LDA start2 ; dummy instructions to spend 5µs more...
       LDA start2 ; ...
       LDA start2 ; ...
       LDA start2 ; ...
       LDA start2 ; ...

对此：

loop1  STA count1

       BRZ skip   ; this branches only in the last iteration
       LDA start2 ; dummy instructions to spend 4µs more...
       LDA start2 ; ...
       LDA start2 ; ...
       LDA start2 ; ...
skip   LDA start2

所以现在计时是准确的，除了输入为0的情况。没有办法花费少于3条指令来处理那种情况（零检测，加载1，并输出它）。

Little Man 计算机程序输出 1，延迟 5 秒

Little Man Computer Program to output 1 with delay of 5 seconds

delay

little-man-computer