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 four 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.

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.

Fourth, what kind of loop is the program executing? Two types can be distinguished:

• Plain loop. The program is stuck in a single loop, which itself does not contain other loops. All examples shown so far are of this type.
• Nested loop. The program is stuck in a loop that itself contains one or more loops. The number of iterations that each inner-loop executes must be constant across each iteration of the outer-loop for the hang to be periodic. Figure 7 and 8 show examples of periodic hangs with nested loops.

The periodic hang in Figure 10 is quite complex. Figure 10 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.

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.

Detection

The detector for Periodic Hangs with plain loops 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.

Detection of Periodic Hangs with nested loops is very similar. It uses the same analysis but runs when:

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