Periodic Hangs

This page classifies 2LBB programs that are trapped in a hang cycle where the Program Pointer (PP) traverses the same path each time. These hangs are called Periodic as each cycle requires the same amount of execution steps.

Features

There are different types of Periodic Hangs. They can be classified considering the following three features.

First, does the data change while the program is in the periodic loop? Three types can be distinguished:

  • Constant. The data does not change at all. An example is shown in Figure 1.
  • Oscillating. The data changes within a loop, but the changes cancel each other out. There is no effective change between consecutive cycles. An example is shown in Figure 2.
  • Changing. One or more data values change between consecutive cycles. A simple example is shown in Figure 3.

Second, how often is each instruction visited within each loop? Two types can be distinguished:

  • Uniform. Each instruction is executed equally often. The hangs in Figure 1 to 3 are all of this type.
  • Non-uniform. Some instructions are carried out more frequently than others. The program in Figure 4 is of this type.
Figure 1. No data change
Figure 2. Oscillating data change
Figure 3. Inter-loop data change
Figure 4. Non-uniform execution

Third, does the data pointer (DP) move? Three types can be distinguished:

  • Stationary. DP does not move at all. Examples are the hangs shown earlier in Figure 1, 2, and 3.
  • Sentry Go. DP paces back and forth within a loop, but these movements cancel each other out. There is no effective movement between subsequent loops. An example is shown in Figure 5.
  • Travelling. DP moves one or more steps between subsequent loops. This generates an infinite data sequence. Figure 6 shows a simple example.

Figure 5. Sentry Go DP movement
Figure 6. Travelling DP movement

Awareness of these features is required to be able to reliably detect all periodic hangs. If, for example, the detection algorithm assumes that each instruction is executed once every cycle, it will not detect Non-Uniform Periodic Hangs. The algorithm should also not assume that each cycle the same values are changed, as it will then not be able to detect Travelling Periodic Hangs.

Periodic hangs can become quite complex. Figure 7 shows a fairly complex Periodic Hang on a 5×5 grid. Figure 8 shows an even more complex Periodic Hang on a 6×6 grid. It takes 410 steps before the program enters the periodic loop. The hang period is 82 steps. It generates the following data sequence: ... -2 4 2 -2 4 2 -1 3 2 -2 3 1 -1 3 2 0. Every period it extends the sequence with three cells. Inside the periodic loop DP visits the last nine values, leaving -2 4 2 in its wake.

My search program is able to detect all the hangs shown on this page.

Figure 7. A Non-Uniform, Changing, Travelling Periodic Hang
Figure 8. A hang with period 82