US 8,146,067 B2Granted

Efficient data reorganization to satisfy data alignment constraints

AssigneeInternational Business Machines Corporation

InventorsAlexandre E. Eichenberger, John Kevin Patrick O'Brien, Peng Wu

Life of this patent

Estimating the term…

Loading patent…

Abstract

Vectorizing misaligned references in compiled code for SIMD architectures that support only aligned loads and stores is presented. In the framework presented herein, a loop is first simdized as if the memory unit imposes no alignment constraints. The compiler then inserts data reorganization operations to satisfy the actual alignment requirement of the hardware. Finally, the code generation algorithm generates SIMD codes based on the data reorganization graph, addressing realistic issues such as runtime alignments, unknown loop bounds, residue iteration counts, and multiple statements with arbitrary alignment combinations. Beyond generating a valid simdization, a preferred embodiment further improves the quality of the generated codes. Four stream-shift placement policies are disclosed, which minimize the number of data reorganization generated by the alignment handling.

Claims9

Dependent claims

A computer program product comprising a computer-storage medium having stored thereon:

means for identifying a loop iterating over a plurality of continuous streams of memory in a stride-one fashion;
means for generating a vectorized representation of the loop for a single instruction multiple datapath architecture, wherein the vectorized representation ignores misalignments among the plurality of continuous streams of memory;
means for developing the vectorized representation into a data reorganization graph representation of the loop, wherein the data reorganization graph representation includes stream-shifting operations that adjust alignment of at least one of the plurality of continuous streams of memory so as to satisfy a data alignment constraint of the computer, the stream-shifting operations applied to the data reorganization graph according to a simdization policy that includes shifting a subset of the plurality of continuous streams of memory to a dominant stream offset in the data reorganization graph, the dominant stream offset being a stream offset that occurs most often among input operands;
and
means for generating object code from the data reorganization graph.

2 more elements

An information-handling system, comprising:

at least one processor;
one or more data storage units accessible by the at least one processor;
and
functional descriptive material contained within the data storage units that, when executed by the at least one processor, directs the at least one processor to perform actions of:
identifying a loop iterating over a plurality of continuous streams of memory in a stride-one fashion;
generating a vectorized representation of the loop for a single instruction multiple datapath architecture, wherein the vectorized representation ignores misalignments among the plurality of continuous streams of memory;
developing the vectorized representation into a data reorganization graph representation of the loop, wherein the data reorganization graph representation includes stream-shifting operations that adjust alignment of at least one of the plurality of continuous streams of memory so as to satisfy a data alignment constraint of the computer, the stream-shifting operations applied to the data reorganization graph according to a simdization policy that includes shifting a subset of the plurality of continuous streams of memory to a dominant stream offset in the data reorganization graph, the dominant stream offset being a stream offset that occurs most often among input operands;
and
generating object code from the data reorganization graph.

6 more elements

Dependencies are inferred from the claim text.