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 it executes the same sequence of instructions.

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.

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

Detection

The detector for Periodic Hangs runs when:

  • the run summary is inside a loop, and
  • the loop executed its last instruction

It then analyzes the loop. If the loop is not yet fully bootstrapped, it waits until it has. Once it is fully bootstrapped, it classifies the loop as hanging when it is clear that none of the Anytime exit conditions will be met. This is a straightforward check.

For stationary loops it requires checking a single data value per exit condition.

For travelling loops it requires checking all data values that the loop will consume. Although this can be an infinite set, the number of non-zero data values is always finite, and it only has to check a subset of those. Next to that, it checks that none of the already consumed values will cause the loop to break at an Anytime exit.