Taming Control Divergence in GPUs through Control Flow Linearization

Branch divergence is a very commonly occurring performance problem in GPGPU in which the execution of diverging branches is serialized to execute only one control flow path at a time. Existing hardware mechanism to reconverge threads using a stack causes duplicate execution of code for unstructured control flow graphs. Also the stack mechanism cannot effectively utilize the available parallelism among diverging branches. Further, the amount of nested divergence allowed is also limited by depth of the branch divergence stack. In this paper we propose a simple and elegant transformation to handle all of the above mentioned problems. The transformation converts an unstructured CFG to a structured CFG without duplicating user code. It incurs only a linear increase in the number of basic blocks and also the number of instructions. Our solution linearizes the CFG using a predicate variable. This mechanism reconverges the divergent threads as early as possible. It also reduces the depth of the reconvergence stack. The available parallelism in nested branches can be effectively extracted by scheduling the basic blocks to reduce the effect of stalls due to memory accesses. It can also increase execution efficiency of nested loops with different trip counts for different threads. We implemented the proposed transformation at PTX level using the Ocelot compiler infrastructure. We evaluated the technique using various benchmarks to show that it can be effective in handling the performance problem due to divergence in unstructured CFGs.

Coupled deformation-flow analysis for methane hydrate production by depressurized wells

A formulation for coupled flow-deformation analysis of methane-hydrate extraction problems is presented. By assuming that the hydrate does not flow, a two phase flow formulation is considered, based on Darcy's law and capillary pressure relation. The formulation is implemented in the finite difference code FLAC. The code was used to investigate the stability of a methane extraction well by depressurizing the well. © 2005 Taylor & Francis Group, London.

Electroosmotic flow analysis of a branched U-turn nanofluidic device.

In this paper, we present the analysis of electroosmotic flow in a branched -turn nanofluidic device, which we developed for detection and sorting of single molecules. The device, where the channel depth is only 150 nm, is designed to optically detect fluorescence from a volume as small as 270 attolitres (al) with a common wide-field fluorescent setup. We use distilled water as the liquid, in which we dilute 110 nm fluorescent beads employed as tracer-particles. Quantitative imaging is used to characterize the pathlines and velocity distribution of the electroosmotic flow in the device. Due to the device's complex geometry, the electroosmotic flow cannot be solved analytically. Therefore we use numerical flow simulation to model our device. Our results show that the deviation between measured and simulated data can be explained by the measured Brownian motion of the tracer-particles, which was not incorporated in the simulation.

Wave dispersion and power flow analysis of an infinite aerofoil-shaped beam

Classic flutter analysis models an aerofoil as a two degree-of-freedom rigid body supported by linear and torsional springs, which represent the bending and torsional stiffness of the aerofoil section. In this classic flutter model, no energy transfer or dissipation can occur in the span-wise direction of the aerofoil section. However, as the aspect ratio of an aerofoil section increases, this span-wise energy transfer - in the form of travelling waves - becomes important to the overall system dynamics. This paper extends the classic flutter model to include travelling waves in the span-wise direction. Namely, wave dispersion and power flow analysis of an infinite, aerofoil-shaped beam, subject to bending, torsion, tension and a constant wind excitation, is used to investigate the overall system stability. Examples of potential applications for these high aspect ratio aerofoil sections include high-altitude balloon tethers, towed cables, offshore risers and mooring lines.