Determinism in Real-Time Applications

An algorithm exhibits determinism when the time to execute the algorithm is predictable and repeatable given any valid input set. Executing a deterministic algorithm takes a predetermined amount of time within a prescribed variance.

Determinism is a product of both the algorithm and the system on which it executes. Real-time systems, such as the LabVIEW Real-Time Module, provide the foundation for you to deterministically execute algorithms. However, determinism is not guaranteed without resource management in any real-time system that has dynamically controlled resources. Resource contention—the inability of a process to access needed resources immediately during execution—destroys determinism. Examples of resource contention in a vision application include the following:

• Parallel processes that use the same image
• Vision algorithms that allocate memory, even for internal workspace, from the systems memory manager

Resource contention is just one example of how to destroy determinism. Determinism also can be destroyed by the nature of some algorithms, by adding file I/O, or by networking. Refer to the LabVIEW Help for a discussion on determinism and programming deterministic applications.

Determinism versus Time-Bounded Execution

Due to the complexity of vision algorithms and the dramatic variance in their input sets (mostly images), determinism, as defined in the previous section, is not attainable. For example, to be deterministic, a pattern matching routine would have to produce results in the same amount of time for any template on any image regardless of content or size.

However, one of the most important characteristics of determinism, limiting execution time, is achievable as long as a final result is not expected for any given time limit. The deterministic condition requires both a lower and upper bound on execution time. Algorithms designed to support execution caps are referred to as time-bounded. When time is exceeded, these algorithms return with a timeout error.

For certain vision algorithms, the execution time has relatively small jitter if the input sets are similar. For instance, pattern matching produces results in roughly the same time when searching for the same pattern in images with common content. Therefore, many vision applications already contain components that have consistent execution times. Running the application on the LabVIEW Real-Time Module enhances the time reliability. Unfortunately, this execution behavior is dependant on the commonality of the input sets. In many applications, the input sets are common enough that you can safely predict the execution time by running the application over a large, representative set of example images. In some cases, however, getting a representative set of example images may be difficult, or a bounded execution time may be particularly important. Herein lies the need for time-bounded algorithms.

Time-Bounded Execution

As with determinism, time-bounded behavior is controlled by both the algorithm and the environment in which it executes. For this reason, some vision algorithms are not candidates for time bounding. For example, algorithms whose execution time varies widely between similar images are not productive under time constraints. This includes operations, such as skeleton, separation, and segmentation, whose execution time can vary dramatically with slight changes in the input image. This makes choosing a time limit for such operations difficult. However, many vision algorithms are adaptable to time limits when the appropriate timed environment is established.

When using NI Vision with the LabVIEW Real-Time Module, the timed environment is best described in terms of the following process flow:

1. Initialize the timed environment.
2. Prepare resources.
3. Perform time-bounded vision operations.
4. Close the timed environment

Initializing the Timed Environment

You must initialize the timed environment to manage resource allocation. While the LabVIEW Real-Time Module manages all of the resources used by the vision application, some resources must be allocated dynamically, which leaves the possibility for resource contention. For example, if a vision algorithm needs to allocate memory for internal workspace, it may contend with another piece in LabVIEW for access to the memory manager. This could cause it to lose priority to another execution thread. To alleviate this problem, pre-allocate resources during initialization for internal algorithm workspace and the timing mechanism. Use the IMAQ Initialize Timed Execution VI to preallocate memory used by the NI Vision algorithms.

Use the IMAQ Initialize Timed Execution VI to initialize the environment. Because resource requirements differ among vision applications, you can change the amount of memory reserved using the Reserved Memory Size control. If the reserved resources are exhausted during execution, a special out-of-memory error message is generated. If you receive this error, increase the amount of resource memory to meet the needs of your processing.

The resources you reserve at initialization are not used until the timing mechanism is started. These resources are intended for use in internal processing that is not exposed in the LabVIEW environment. For objects that are exposed in LabVIEW, always preallocate resources before entering the time-bounded portion of your code. For example, preallocate destination images using the IMAQ Create and IMAQ SetImageSize VIs before entering time-bounded code.

Preparing Resources

Allocate any resource whose exact size you know before the time limit is started. This encourages optimal use of the reserved resources and provides maximum flexibility.

System resources allocated before timed execution are available at any time. Reserved resources allocated inside the time-bounded portion of your code are not guaranteed to be available outside the timed environment. Therefore, you should preallocate as much as possible before entering the time-bounded portion of your code. When time-bounded execution begins, changes to system resources by NI Vision algorithms, such as resizing an existing image, generate an error.

Images can be created only in system resources. In addition, special image changes performed by learning a pattern, calibrating an image, or adding an overlay also require system resources. This is primarily because they have to exist outside the timed environment. These operations are prohibited during time-bounded execution.

Performing Time-Bounded Vision Operations

To limit the execution time of a block of vision operations, make the following modifications:

• Isolate the portion of code to time-bound in an independent VI.
• Set the independent VI’s execution priority to time-critical so that lower priority processes do not interrupt the timed execution. Refer to the for information about program architecture.
• Turn off automated error handling so that dialog boxes are not generated when an error occurs.
• Replace all Vision VIs in the time-bounded operation with their time-bounded counterparts located in Preallocated.llb. Using a Vision VI that is not time-bounded generates a run-time error if the time limit is set. Replacing the VIs ensures that Vision algorithms do not request resources from the system while running.
• Call the IMAQ Start Timed Execution VI at the beginning of the vision block to initiate the time limit. Use the IMAQ Stop Timed Execution VI to turn off the time limit at the end of the Vision block. Connect the error output from the IMAQ Start Timed Execution VI to the Vision VIs in sequential order ending with the IMAQ Stop Timed Execution VI. When time expires and the processing is not complete, the Vision VI executing at that moment generates a special timeout error. The error cluster propagates the timeout condition reducing overall execution jitter. Attempting to start an additional time limit results in an error.

For vision algorithms working with images, serialized processing is crucial because an image may be shared among multiple vision routines running in parallel. When changes to the image are required, the image is blocked from access until the updates are completed. This is another form of resource contention that invalidates time constraints. If the error cluster is passed between VIs sequentially, this type of conflict is avoided. Use the error cluster to sequence your VIs and one loop in the code to avoid time constraint conflicts.

All non-vision processing during time-bounded execution is not constrained by the timing mechanism, increasing the jitter of the overall execution. Consequently, limit non-vision processing during time-bounded execution. In particular, eliminate any operation in the LabVIEW Real-Time Module requesting resources because these operations nullify the time limit. For example, do not build or resize arrays to sizes determined at run-time if a time limit is active. However, you can perform such operations as reading elements from an array. Other operations, such as file I/O, serial I/O, and networking, are inherently non-deterministic and should be avoided in the time-critical portion of your application. Refer to the LabVIEW Real-Time Module documentation to determine which routines can execute deterministically.

Because some non-vision processing may be required during timed execution, use the IMAQ Check Timed Execution VI periodically to see if time has expired. Determine how frequently you need to check for expired time based on the complexity of the non-vision process and the required jitter.

Closing the Timed Environment

When time-bounded execution is no longer needed, call the IMAQ Uninitialize Timed Execution VI to release the resources reserved at initialization. When the environment is uninitialized, calls to the IMAQ Start Timed Execution VI produce an error.