Cray Research, Inc.

Douglas M Pase

Janet M Eberhart

Thomas A MacDonald

Eric Carl Fromm

Randal Steven Passint

Steven M Oberlin

Frank R Barriuso

David J Sielaff

Gary W Elsesser

Dave Wagner

Division system and method support a hardware division address centrifuge to provide a flexible addressing scheme, and thus facilitates the reorganization and redistribution of data between remote and local memory blocks in a distributed memory massively parallel processing system. A flexible addressing scheme supports data organizations which can vary widely, depending on the processing task. Different data organizations in memory are supported by a PE internal address having certain bits designated as the target PE number and the remaining bits designating the offset within that PE's local memory. The PE and offset bits are distributed throughout the PE internal address to achieve various data distributions throughout memory. When a transfer occurs, the PE number bits and offset bits are separated via the centrifuge under control of a software-supplied mask. The centrifuge supports scatter-gather as well as constant-stride capabilities and is easily adaptable by the user to fit a wide variety of processing tasks.

Array address and loop alignment calculations

An efficient integer-division-by-an-constant method and apparatus. This integer-division-by-an-constant is useful in calculations which must be performed often and/or quickly, and where the denominator is fixed for the calculations, such as address calculations in massively parallel, distributed memory processor systems. Also described is a method and apparatus using the integer-division-by-an-constant method and apparatus, which facilitates removing power-of two restrictions on the reorganization and redistribution of data between remote and local memory blocks in a massively parallel, distributed-memory processing system. The flexible addressing scheme provided supports data organizations which vary widely depending on the processing task. In particular, a plurality of processing elements (PEs) operating in parallel within a subset of all the PEs in a massively parallel processor system, may simultaneously operate on an array data structure, the array data structure having an arbitrary size and shape. Different data organizations in memory are supported by a processing element (PE) internal array address having certain index ranges designated as the target PE number and the areas within those index ranges designating the offset within that PE's local memory. The index ranges and areas are distributed throughout the PE internal array address to achieve various data distributions throughout memory.

Method and apparatus for removing power-of-two restrictions on

A system and address method for extracting a PE number and offset from an array index. According to one aspect of the present invention, a processing element number is assigned to each processing element, a local memory address is assigned to each memory location and a linearized index is assigned to each array element in an array. The processing element number of the processing element in which a particular array element is stored is computed as a function of a linearized index associated with the array element and a distribution specification associated with the array. In addition, a local memory address associated with the array element is computed as a function of the linearized index and the distribution specification.

System and method of addressing distributed memory within a massively

A method of setting array boundaries in order to simplify addressing across processor elements in a distributed memory system having global addressing. Each dimension of an array is examined to determine a lower bound, a declared upper bound and an implicit upper bound. The lower bound and the declared upper bound in each dimension are used to set limits for operations on array elements while the implicit upper bound calculated from the lower bound and the declared upper bound is used in calculating the location (processor element and offset) of a particular array element.

Method for the dynamic allocation of array sizes in a multiprocessor

A method of managing distributed memory in which a local memory is partitioned into a shared heap segment, a shared stack segment, a private heap segment and a private stack segment. One of the segments starts at a fixed address and grows upward. A second segment starts at a fixed address and grows downward. A third segment starts at a relocatable segment wall and grows downward and a fourth segment starts at a relocatable segment wall and grows upward.

Method of managing distributed memory within a massively parallel

A method of synchronizing accesses to shared data in a multiprocessing system having an atomic swap capability. A distinguished lock value is defined. A processor which wishes to access a shared data memory location performs an atomic swap of the lock value to the shared data memory location. If the data received from the atomic swap is equivalent to the lock value the processor knows that the memory location has been locked by another processor. The processor then repeats the atomic swap at intervals until data is received which is not equivalent to the lock value. The processor operates on the data and then performs a write to the shared data memory location to replace the lock value with the updated data. In an alternate embodiment, in situations where a unique lock value cannot be defined, an array is created to store lock values associated with particular shared data memory locations. A processor seeking access to a shared data memory location performs atomic swaps of the lock value to the lock array to determine access to a shared data memory location.

Growing community of inventors

Burnsville, MN, United States of America

Douglas M Pase