1

假设一个小人计算机程序需要 1 微秒来执行一条指令。我需要编写一个 LMC 程序，该程序接受 0 到 10（含）之间的输入，并产生一个 1 的输出，但延迟了这么多秒。

例如，输入 5 将在 5 秒后产生输出 1。延迟不必是完美的，但必须在 0.01% 或 100 µsec 内准确。我怎样才能做到这一点？

4

1 回答 1

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 = 459460 次迭代（还有其他有趣的对您可以使用，结果相似）。

  • 在一次迭代中执行的指令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，并输出它）。

于 2020-11-23T19:54:23.060 回答