Method, system, and product for performing uniformly fine-grain data parallel computing

#The present invention relates to parallel computing. More particularly, the present invention relates to a method, computer system and computer program product for performing uniformly fine-grain data parallel computing of, for example, regression clustering.

#Computing power of Central Processing Units (CPU) has dramatically increased in the last few decades, supported by both miniaturization and increasing clock frequencies. More and more electronic gates are being packed onto the same area of a silicon die as miniaturization advances. More hardware supported parallel computing, pipelining for example, has further increased the computing power of CPUs.

#Frequency increases have sped up CPUs even more directly and linearly. But the long predicted physical limit of the miniaturization process seems to have finally been reached recently, so that increasing the frequency appears to be no longer feasible due to the accompanied non-linear increase of power consumption, even though miniaturization still continues today. This situation has forced the industry to go toward packing multiple CPU cores onto the same silicon die without increasing clock frequency. Parallel computing has emerged from an optional computational architecture for supercomputing into the mainstream choice for general computing, and this will likely continue in the future. As a result of this fundamental computing architecture change, algorithm design, data structure design, and programming strategies are all facing new challenges.

#The subject matter regarded as the invention is particularly pointed out and distinctly claimed in the concluding portion of the specification. The invention, however, both as to organization and method of operation, together with objects, features, and advantages thereof, may best be understood by reference to the following detailed description when read with the accompanying drawings. It should be noted that the figures are given as examples only and in no way limit the scope of the invention. Like components are denoted by like reference numerals.

#FIG. 1 illustrates a computing system of mixed computing architecture, according to embodiments of the present invention;

#FIG. 2 illustrates assignment of work to thread blocks running in parallel, according to embodiments of the present invention; and

#Graphics Processing Units (GPUs) have employed multicore parallel computing, even longer than CPUs have, due to the parallel nature of graphics computations. Some efforts have been made to use GPUs' special architecture for more general purpose numerical computing; however, such efforts have achieved limited results and the task was very difficult until recently. It was difficult to program general purpose numerical algorithms on GPUs because of their specialized architecture for graphics processing—numerical computations had to be shaped into “graphics operations” before they could be programmed through the graphics programming interface. In the last few years, however, GPUs developed rapidly from a special graphics processing unit into General Purpose uniform multicore computing devices (called “GP-GPU”), which has made the mapping of general purpose numerical computing tasks onto the new GPU architecture much easier. An augmented C-language interface, NVIDIA's CUDA, is also available now for programming GPUs. These advances have made general purpose computing on GPUs practical for general programmers without knowledge of the graphics programming interface. The benefits of using a GP-GPU for numerical processing over CPU multicores are significant savings on both the hardware cost and power consumption per GFLOPS (Giga Floating point Operations Per Second). Measured by the number of floating point operations per second, GPUs' performance shown a significantly faster increase in the last few years than CPUs. With hundreds of light-weight multiple-data and multiple-thread processors, a GPU offers much more computational power for general purpose computing at both lower capital equipment cost and lower power consumption.

#According to embodiments of the present invention, uniformly fine-grain data parallel computing may be performed on a computing device which comprises a mixed computing architecture (hereinafter “mixed computing architecture”), which may include, for example, at least one central processing unit (CPU) and at least one uniformly fine-grain data parallel computing device, such as, for example, a graphics processing unit (GPU) or a general purpose graphics processing unit (GP-GPU). “Uniformly fine-grain data parallelism” means that the size of each data partition dk in D is the same (uniform), the tasks to be performed on them are the same, and each task can access the data partition needed for its computation in as few memory-access cycles as possible. Uniformity of the size of dk helps (but does not necessarily guarantee) design a common procedure p for all threads so that the execution of these threads is truly synchronized without wasting cycles.

#According to embodiments of the present invention, a method is disclosed which includes computing, using at least one uniformly fine-grain data parallel computing unit, a mean-square error regression within a regression clustering algorithm. The mean-square error regression is represented in the form of at least one summation of a vector-vector multiplication.