defined on the vertex processor. The vertex processor is able to adjust the position of the vertex, which allows the programmer to control where information is deposited on the grid. Other extensions are also possible, such as controlling how large an area the vertex affects. The fragment processor cannot perform a direct scatter operation because the location of each fragment on the grid is fixed at the time of the fragment's creation and cannot be altered by the programmer. However, a logical scatter operation may sometimes be recast or implemented with another gather step. A scatter implementation would first emit both an output value and an output address. An immediately following gather operation uses address comparisons to see whether the output value maps to the current output slot. In dedicated compute kernels, scatter can be performed by indexed writes. Gather Gather is the reverse of scatter. After scatter reorders elements according to a map, gather can restore the order of the elements according to the map scatter used. In dedicated compute kernels, gather may be performed by indexed reads. In other shaders, it is performed with texture-lookups. Sort The sort operation transforms an unordered set of elements into an ordered set of elements. The most common implementation on GPUs is using radix sort for integer and floating point data and coarse-grained merge sort and fine-grained sorting networks for general comparable data. Search The search operation allows the programmer to find a given element within the stream, or possibly find neighbors of a specified element. The GPU is not used to speed up the search for an individual element, but instead is used to run multiple searches in parallel. Mostly the search method used is binary search on sorted elements. Data structures A variety of data structures can be represented on the GPU: Dense arrays Sparse matrices (sparse array) static or dynamic Adaptive structures (union type) Applications The following are some of the areas where GPUs have been used for general purpose computing: Automatic parallelization Physical based simulation and physics engines (usually based on Newtonian physics models) Conway's Game of Life, cloth simulation, fluid incompressible flow by solution of Euler equations (fluid dynamics) or Navier–Stokes equations Statistical physics Ising model Lattice gauge theory Segmentation 2D and 3D Level set methods CT reconstruction Fast Fourier transform GPU learning machine learning and data mining computations, e.g., with software BIDMach k-nearest neighbor algorithm Fuzzy