Browse Prior Art Database

Method and Apparatus to reduce branches and conditions in code using auxiliary arrays.

IP.com Disclosure Number: IPCOM000247417D
Publication Date: 2016-Sep-06
Document File: 23 page(s) / 78K

Publishing Venue

The IP.com Prior Art Database

Abstract

The proposed paper describes a method in which a simple auxillary array can be used to halve the number of branches and in some conditions, even completely remove the branches occurring in clipping operations. A clipping operation is made up of a pair of if-conditions that do a boundary check of a variable with a minimum and maximum value with the intention of setting it's value to an integer that lies within the range of [minimum, maximum]. Such operations are prevalent in image processing and molecular dynamics code.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 01 of 23

Method and Apparatus to reduce branches and conditions in code using auxiliary arrays.


1. Introduction

Clipping operations (clipping values of parameters) occur very frequently in application domains such as computer graphics, digital signal processing and particle physics. In such applications, the value of a parameter is supposed to be within a range, the most common range being [min..max], where min(minimum) can be anywhere between 0 and a positive integer value and max(maximum) is a positive integer value, much greater than min. If the variable value falls beyond the range, the application specific algorithm cannot semantically process it. Hence the algorithm modifies the value to ensure that it falls within the range. This process is known as clipping.

A most common example is in the field of image processing where area of the screen has a pre-determined value. Pixel co-ordinates are visible only if they fall within the screen area. And only those pixels that are visible or fall within the purview of the screen area get to be processed. In graphics applications, most often, min takes on a non-zero positive value.

Another application domain where parameters are often clipped is particle physics where particles are arranged in 2D (two dimensional) or 3D (three dimensional) structures and are processed. One such example is a random number generator modeled on particle physics known as multidimensional wandering particles or MDWP[3]. This random number generator produces random numbers based on particle movement in a n-dimensional hypercube. Clipping is a common procedure used in the algorithm wherein the resultant co-ordinates of the particles owing to their movement causes them to wrap around the hypercube sides. In such applications, min is usually zero.

Usually, a clip operation involves two if-conditions corresponding to the two boundary checks (minimum and maximum) on the parameter value and if required, modifies it to ensure that the parameter falls within the range [min..max]. Generally the clip operation falls in the hot path and is executed repeatedly leading to a high number of branches and condition checks in program execution which needs to be optimized for better performance.

In general, a clipping operation looks like the following-

__________________________________________________

If(var cond1 min) var=alpha;
If(var cond2 max) var=beta;

Fig 1: Example of a clipping operation

__________________________________________________

1


Page 02 of 23

cond1 and cond2 can be any of the following pairs as shown in Table 1 below that can occur in an example such as Fig 1 .

Table 1: Pairs of conditional operators that normally occur in clipping operations

Cond1 < < == == <= <=

>= > >= > == ==

The presence of branches in code hurt application performance in superscalar RISC (Reduced Instruction Set Computing) processors. These processors work on a pipeline model which is fed with a stream of instructions obtained by the instruc...