International Business Machines Corporation

Jaime Humberto Moreno

Ravi Nair

Malcolm Scott Ware

Hans Mikael Jacobson

Bruce Martin Fleischer

Thomas Winters Fox

Jude A Rivers

Richard Edward Matick

James Allan Kahle

John-David Wellman

Mayan Moudgill

Sameh W Asaad

Daniel Arthur Prener

David Arnold Luick

Fredy Daniel Neeser

Victor V Zyuban

Erik Richter Altman

Philip Braun Winterfield

Mahmut K Ebcioglu

Pradeep Kumar Dubey

Gabriel Mauricio Silberman

Charles Marshall Barton

Vinodh R Cuppu

Mavan Moudgill

Embodiments relate to loading and storing of data. An aspect includes a method for transferring data in an active memory device that includes memory and a processing element. An instruction is fetched and decoded for execution by the processing element. Based on determining that the instruction is a gather instruction, the processing element determines a plurality of source addresses in the memory from which to gather data elements and a destination address in the memory. One or more gathered data elements are transferred from the source addresses to contiguous locations in the memory starting at the destination address. Based on determining that the instruction is a scatter instruction, a source address in the memory from which to read data elements at contiguous locations and one or more destination addresses in the memory to store the data elements at non-contiguous locations are determined, and the data elements are transferred.

Active memory device gather, scatter, and filter

Embodiments relate to packed loading and storing of data. An aspect includes a system for packed loading and storing of distributed data. The system includes memory and a processing element configured to communicate with the memory. The processing element is configured to perform a method including fetching and decoding an instruction for execution by the processing element. A plurality of individually addressable data elements is gathered from non-contiguous locations in the memory which are narrower than a nominal width of register file elements in the processing element based on the instruction. The processing element packs and loads the data elements into register file elements of a register file entry based on the instruction, such that at least two of the data elements gathered from the non-contiguous locations in the memory are packed and loaded into a single register file element of the register file entry.

Gather/scatter of multiple data elements with packed loading/storing into /from a register file entry

Embodiments relate to packed loading and storing of data. An aspect includes a method for packed loading and storing of data distributed in a system that includes memory and a processing element. The method includes fetching and decoding an instruction for execution by the processing element. The processing element gathers a plurality of individually addressable data elements from non-contiguous locations in the memory which are narrower than a nominal width of register file elements in the processing element based on the instruction. The data elements are packed and loaded into register file elements of a register file entry by the processing element based on the instruction, such that at least two of the data elements gathered from the non-contiguous locations in the memory are packed and loaded into a single register file element of the register file entry.

Gather/scatter of multiple data elements with packed loading/storing into/from a register file entry

Embodiments relate to tree traversal in a memory device. An aspect includes a method for tree traversal in a memory device. The method includes receiving a pointer to a tree structure within memory of the memory device. An evaluation condition is received to identify a desired node of the tree structure. The tree structure is traversed to identify the desired node. Data is returned from the desired node meeting the evaluation condition.

Tree traversal in a memory device

According to one embodiment of the present invention, a method for operating a memory device that includes memory and a processing element includes receiving, in the processing element, a command from a requestor, loading, in the processing element, a program based on the command, the program comprising a load instruction loaded from a first memory location in the memory, and performing, by the processing element, the program, the performing including loading data in the processing element from a second memory location in the memory. The method also includes generating, by the processing element, a virtual address of the second memory location based on the load instruction and translating, by the processing element, the virtual address into a real address.

Active buffered memory

Methods and apparatus allowing a choice of Least Frequently Used (LFU) or Most Frequently Used (MFU) cache line replacement are disclosed. The methods and apparatus determine new state information for at least two given cache lines of a number of cache lines in a cache, the new state information based at least in part on prior state information for the at least two given cache lines. Additionally, when an access miss occurs in one of the at least two given lines, the methods and apparatus (1) select either LFU or MFU replacement criteria, and (2) replace one of the at least two given cache lines based on the new state information and the selected replacement criteria. Additionally, a cache for replacing MFU cache lines is disclosed. The cache additionally comprises MFU circuitry (1) adapted to produce new state information for the at least two given cache lines in response to an access to one of the at least two given cache lines, and (2) when a cache miss occurs in one of the at least two given cache lines, adapted to determine, based on the new state information, which of the at least two given cache lines is the most frequently used cache line.

Cache line replacement techniques allowing choice of LFU or MFU cache line replacement

Cache with selective least frequently used or most frequently used cache line replacement

A system for instruction memory storage and processing in a computing device having a processor, the system is based on backwards branch control information and comprises a dynamic loop buffer (DLB) which is a tagless array of data organized as a direct-mapped structure; a DLB controller having a primary memory unit partitioned into a plurality of banks for controlling the state of the instruction memory system and accepting a program counter address as an input, the DLB controller outputs distinct signals. The system further comprises an address register located in the memory of the computing device, it is a staging register for the program counter address and an instruction fetch process that takes two cycles of the processor clock; and a bank select unit for serving as a program counter address decoder to accept the program counter address and to output a bank enable signal for selecting a bank in a primary memory unit, and a decoded address for access within the selected bank.

System and method for instruction memory storage and processing based on backwards branch control information

A multi-port register file may be selectively bypassed such that any element in a result vector is bypassed to the same index of an input vector of a succeeding operation when the element is requested in the succeeding operation in the same index as it was generated. Alternatively, the results to be placed in a register file may be bypassed to a succeeding operation when the N elements that dynamically compose a vector are requested as inputs to the next operation exactly in the same order as they were generated. That is, for the purposes of bypassing, the N vector elements are treated as a single entity. Similar rules apply for the write-through path.

Selective bypassing of a multi-port register file

A configuration of vector units, digital circuitry and associated instructions is disclosed for the parallel processing of multiple Viterbi decoder butterflies on a programmable digital signal processor (DSP) that is based on single-instruction-multiple-data (SIMD) principles and provides indirect access to vector elements. The disclosed configuration uses a processor with two vector units and associated registers, where the vector units are connected back to back for processing Viterbi decoder state metrics. Viterbi add instructions increment vectors of state metrics from a first register, performing a desired permutation of state metrics while reading them indirectly through vector pointers, and writing intermediate result vectors to a second register. Viterbi select instructions perform element-wise maximum or minimum operations on vectors from the second register to determine survivor metrics, performing a desired inverse permutation of survivor metrics while writing them back to the first register and recording the corresponding decisions in a shift register for use in a subsequent traceback operation.

Viterbi decoding for SIMD vector processors with indirect vector element access

A method and apparatus for reducing logic activity in a microprocessor which examines every instruction before it is executed and determines in advance the minimum appropriate datapath width (in byte or half-word quantities) necessary to accurately execute the operation. Achieving this requires two major enhancements to a traditional microprocessor pipeline. First, extra logic (potentially an extra pipeline stage for determining an operation's effective bit width&#x2014;the WD width detection logic) is introduced between the Decode and Execution stages. Second, the traditional Execution stage architecture (including a register file RF and the arithmetic logical unit ALU), instead of being organized as one continuous 32-bit unit, is organized as a collection of multiple slices, where a slice can be of an 8-bit (a byte) or a 16-bit (double byte) granularity. Each slice in this case can operate independently of each other slice, and includes portion of the register file, functional unit and cache memory. Concatenating a multiple number of these slices together creates a required full width processor.

Method and apparatus for reducing logic activity in a microprocessor using reduced bit width slices that are enabled or disabled depending on operation width

A method and apparatus are provided for moving at least one of instructions and operand data throughout a plurality of caches included in a multiprocessor computer system, wherein each of the plurality of caches is included in one of a plurality of processing nodes of the system so as to provide history-based movement of shared-data in coherent cache memories. A plurality of entries are stored in a consume after produce (CAP) table attached to each of the plurality of caches. Each of the entries is associated with a plurality of storage elements in one of the plurality of caches and includes information of prior usage of the plurality of storage elements by each of the plurality of processing nodes. Upon a miss by a processing node to a cache included therein, any storage elements that caused the miss are transferred to the cache from one of main memory and another cache. An entry is created in the table that is associated with the storage elements that caused the miss. A push prefetching engine may be used to create the entry.

Method and apparatus for history-based movement of shared-data in coherent cache memories of a multiprocessor system using push prefetching

The present invention relates to a method for accessing elements from a shared resource to be used by consumers that perform actions according to corresponding operations. The method creates a packet of operations to be processed simultaneously, wherein the elements from the shared resource used by the operations are specified by source and destination identifier fields that are shared among the operations in such a way that the sum of all the elements from the shared resource used by the operations does not exceed a total number of identifiers available in the packet. The method also reads the elements from the shared resource according to the shared identifier fields specified in the packet. The method decodes a number of elements from the shared resource needed by each operation, by passing the operations to an operation decoder having a defined routing scheme based on the needs of the operations. The method also routes the elements to the consumers performing operations and resulting values to the shared resource, according to a routing signal of the operation decoder.

Growing community of inventors

Dobbs Ferry, NY, United States of America

Jaime Humberto Moreno