International Business Machines Corporation

Peng Zhao

Alexandre E Eichenberger

Peng Wu

Roch Georges Archambault

Yaoqing Gao

Raul Esteban Silvera

Kai-Ting Amy Wang

Shimin Cui

Stephen Curial

Guansong Zhang

Liangxiao Hu

Amy K Wang

Amy Kai-Ting Wang

George Chochia

Amy (k T) Wang

Embodiments of the present invention provide a method, system and computer program product for the data splitting of recursive data structures. In one embodiment of the invention, a method for data splitting recursive data structures can be provided. The method can include identifying data objects of a recursive data structure type, such as a linked list, within source code, the recursive data structure type defining multiple different data fields. The method further can include grouping the data objects into some memory pool units, each of which can contain the same number of data objects. Each memory pool unit can be seen as an array of data objects. The method can include data splitting, which could be maximal array splitting in each different memory pool unit. Finally, the method can include three different approaches, including field padding, field padding and field splitting, to handle irregular field sizes in the data structure.

Data splitting for recursive data structures

A compiler method for exploiting data value locality for computation reuse. When a code region having single entry and exit points and in which a potential computation reuse opportunity exists is identified during runtime, a helper thread is created separate from the master thread. One of the helper thread and master thread performs a computation specified in the code region, and the other of the helper thread and master thread looks up a value of the computation previously executed and stored in a lookup table. If the value of the computation previously executed is located in the lookup table, the other thread retrieves the value from the table, and ignores the computation performed by the thread. If the value of the computation is not located, the other thread obtains a result of the computation performed by the thread and stores the result in the lookup table for future computation reuse.

Compiler method of exploiting data value locality for computation reuse

A method for analyzing data reordering operations in Single Issue Multiple Data source code and generating executable code therefrom is provided. Input is received. One or more data reordering operations in the input are identified and each data reordering operation in the input is abstracted into a corresponding virtual shuffle operation so that each virtual shuffle operation forms part of an expression tree. One or more virtual shuffle trees are collapsed by combining virtual shuffle operations within at least one of the one or more virtual shuffle trees to form one or more combined virtual shuffle operations, wherein each virtual shuffle tree is a subtree of the expression tree that only contains virtual shuffle operations. Then code is generated for the one or more combined virtual shuffle operations.

Analyze and reduce number of data reordering operations in SIMD code

A computer implemented method, apparatus, and computer usable program code for compiling source code for performing a complex operation followed by a complex reduction operation. A method is determined for generating executable code for performing the complex operation and the complex reduction operation. Executable code is generated for computing sub-products, reducing the sub-products to intermediate results, and summing the intermediate results to generate a final result in response to a determination that a reduced single instruction multiple data method is appropriate.

Code generation for complex arithmetic reduction for architectures lacking cross data-path support

A computer implemented method for facilitating debugging of source code. The source code is scanned to identify a candidate region. A procedure control descriptor is generated, wherein the procedure control descriptor corresponds to the candidate region. The procedure control descriptor identifies, for the candidate region, a condition which, if true at runtime means that the candidate region can be specialized. Responsive to a determination during compile time that satisfaction of at least one condition will be known only at runtime, the procedure control descriptor is used to specialize the candidate region at compile time to create a first version of the candidate region for execution in a case where the condition is true and a second version of the candidate region for execution in a case where the condition is false, and further generate code to correctly select one of the first region and the second region at runtime.

Procedure control descriptor-based code specialization for context sensitive memory disambiguation

A target operation in a normalized target loop, susceptible of vectorization and which may, after compilation into a vectorized form, seek to operate on data in nonconsecutive physical memory, is identified in source code. Hardware instructions are inserted into executable code generated from the source code, directing a system that will run the executable code to create a representation of the data in consecutive physical memory. A vector loop containing the target operation is replaced, in the executable code, with a function call to a vector library to call a vector function that will operate on the representation to generate a result identical to output expected from executing the vector loop containing the target operation. On execution, a representation of data residing in nonconsecutive physical memory is created in consecutive physical memory, and the vectorized target operation is applied to the representation to process the data.

Sparse vectorization without hardware gather/scatter

A computer program product is provided for extracting SIMD parallelism. The computer program product includes instructions for providing a stream of input code comprising basic blocks; identifying pairs of statements that are semi-isomorphic with respect to each other within a basic block; iteratively combining into packs, pairs of statements that are semi-isomorphic with respect to each other, and combining packs into combined packs; collecting packs whose statements can be scheduled together for processing; and generating SIMD instructions for each pack to provide for extracting the SIMD parallelism..

Method to exploit superword-level parallelism using semi-isomorphic packing

A method for implementing shadow versioning to improve data dependence analysis for instruction scheduling in compiling code, and to identify loops within the code to be compiled, for each loop initializing a dependence a matrix, for each loop shadow identifying symbols that are accessed by the loop, examining dependencies, storing, comparing and classifying the dependence vectors, generating new shadow symbols, replacing the old shadow symbols with the new shadow symbols, generating alias relationships between the newly created shadow symbols, scheduling instructions and compiling the code.

Implementing shadow versioning to improve data dependence analysis for instruction scheduling

A method for generating code, including identifying at least one portion of source code that is simdizable and has a dependence, analyzing the dependence for characteristics, based upon the characteristics, selecting a transformation from a predefined group of transformations, applying the transformation to the at least one portion to generate SIMD code for the at least one portion.

Generating optimized SIMD code in the presence of data dependences

A computer implemented method, system and computer program product for automatically generating SIMD code. The method begins by analyzing data to be accessed by a targeted loop including at least one statement, where each statement has at least one memory reference, to determine if memory accesses are safe. If memory accesses are safe, the targeted loop is simdized. If not safe, it is determined if a scheme can be applied in which safety need not be guaranteed. If such a scheme can be applied, the targeted loop is simdized according to the scheme. If such a scheme cannot be applied, it is determined if padding is appropriate. If padding is appropriate, the data is padded and the targeted loop is simdized. If padding is not appropriate, non-simdized code is generated based on the targeted loop for handling boundary conditions, the targeted loop is simdized and combined with the non-simdized code.

Efficient generation of SIMD code in presence of multi-threading and other false sharing conditions and in machines having memory protection support

A method and system for generating efficient versioned codes for single instruction multiple data units whose memory systems have alignment constraints. The system creates multiple versions of codes based on relative alignments of the data streams involved in the computation. The system also analyzes characteristics of relative alignments (e.g. compile-time or runtime) to determine whether code versioning is beneficial based on a cost model.

Growing community of inventors

North York, Canada

Peng Zhao