International Business Machines Corporation

Altera Corporation

Lucent Technologies Inc.

Nokia Corporation

Other

Stamatis Vassiliadis

Gerald George Pechanek

Bartholomew Blaner

Jose Guadalupe Delgado-Frias

James Edward Phillips

Richard James Eickemeyer

Eric M Schwarz

Michael Putrino

Thomas L Jeremiah

Brice J Feal

Ann E Huffman

Walid M Kobrosly

Paul Gerard D'Arcy

Sanjay Jinturkar

Petri Liuha

C John Glossner

George Triantafyllos

David Allen Hrusecky

Phillip G Williams

Agnes Yee Ngai

Larry D Larsen

Jari Antero Nikara

Kent E Wires

Jesse Thilo

Dean Batten

Clair John Glossner

Josephine A Boston

Eric M Schwartz

Jarmo Takala

Jose G Delgado-Fnias

Dan Crisu

Sorin Cotofana

Baik M Sung

Techniques are described for decoupling fetching of an instruction stored in a main program memory from earliest execution of the instruction. An indirect execution method and program instructions to support such execution are addressed. In addition, an improved indirect deferred execution processor (DXP) VLIW architecture is described which supports a scalable array of memory centric processor elements that do not require local load and store units.

Methods and apparatus for storing expanded width instructions in a VLIW memory for deferred execution

Staging register file for use with multi-stage execution units

Methods and apparatus storing expanded width instructions in a VLIW memory deferred execution

The invention relates to a method, a device, a system and a software program product for determining for a pixel a coverage mask reflecting an orientation and possibly a distance from the pixel center of an original edge vector. The pixel is to be employed for displaying at least a part of a geometric primitive on a display, and the original edge vector represents an oriented edge of the geometric primitive. The method comprises as a first step determining one of four quadrants of a Cartesian coordinate system to which the original edge vector belongs due to its orientation. The original edge vector is then transposed into a predetermined one of the four quadrants. Next, a stored coverage mask is fetched, which is associated at least indirectly to the transposed edge vector. Finally, the fetched coverage mask is transformed to the quadrant to which the original edge vector belongs.

Determining a coverage mask for a pixel

A method and associated decoder, system, device and storage means for decoding codewords of variable length from a bit stream, in which minimum and maximum lengths are defined for the codewords, wherein the bit stream is processed in parts, each part being subjected to a search for codewords, and where found codewords are decoded. At least partly overlapping fields are extracted from the bit stream part in such a way that the starting point of at least two fields is a possible starting point of a codeword in that part. In at least one field, the end of the codeword is searched, and the data related to the codeword is determined on the basis of the end point of the codeword. Data relating to at least one codeword is used to determine the occurrence of the codeword intended to be decoded in a field, and the found codeword is decoded.

Method and a system for variable-length decoding, and a device for the localization of codewords

Image processing for multimedia workstations is a computationally intensive task requiring special purpose hardware to meet the high speed requirements associated with the task. One type of specialized hardware that meets the computation high speed requirements is the mesh connected computer. Such a computer becomes a massively parallel machine when an array of computers interconnected by a network are replicated in a machine. The nearest neighbor mesh computer consists of an N&times;N square array of Processor Elements(PEs) where each PE is connected to the North, South, East and West PEs only. The diagonal folded mesh array processor, which is called Oracle, allows the matrix transformation operation to be accomplished in one cycle by simple interchange of the data elements in the dual symmetric processor elements. The use of Oracle for a parallel 2-D convolution mechanish for image processing and multimedia applications and for a finite difference method of solving differential equations is presented, concentrating on the computational aspects of the algorithm.

Massively parallel array processor

The invention provides techniques for improving the performance of pipelined processors by eliminating unnecessary stalling of instructions. In an illustrative embodiment, a compiler is used to identify pipeline dependencies in a given set of instructions. The compiler then groups the set of instructions into a code block having a field which indicates the types of pipeline dependencies, if any, in the set of instructions. The field may indicate the types of pipeline dependencies by specifying which of a predetermined set of hazards arise in the plurality of instructions when executed on a given pipelined processor. For example, the field may indicate whether the code block includes any Read After Write (RAW) hazards, Write After Write (WAW) hazards or Write After Read (WAR) hazards. The code block may include one or more dynamic scheduling instructions, with each of the dynamic scheduling instructions including a set of instructions for execution in a multi-issue processor.

Compiler-controlled dynamic instruction dispatch in pipelined processors

A computer system supporting N different machine views, where N.gtoreq.2, includes a memory for storing instructions, a number of execution units for processing data based on execution controls, and N different decoders for generating the execution controls using instructions retrieved from the memory. Each of the N decoders is operative to decode retrieved instructions in accordance with one of the N machine views. A particular one of the N decoders to be used to decode a given retrieved instruction may be selected by a program running on the system. In one embodiment, the decoders for the N machine views are implemented as N separate decoders, and a multiplexer is used to select the output of one of the N decoders for connection to one or more of the execution units. In another embodiment, a set of reconfigurable hardware is dynamically reprogrammed to implement one or more of the N decoders as directed by the program running on the system.

Multiple machine view execution in a computer system

A massively parallel diagonal-fold mesh array processor provides a triangular diagonally folded mesh computer with the same functionality as a square mesh computer but with half the number of connection wires. The diagonal-fold mesh array processor is modified in this invention to provide a more general purpose processor node and to enhance the connectivity between the processing nodes while still providing the image processing and finite difference capabilities of the original structure. By repeatedly folding the triangular diagonal-fold array structure, processing elements are placed together which, with additional connections, allows the improvement in connectivity. This enhancement would be difficult to achieve in a standard mesh organization. The resultant folded structure maintains the functionality of the original mesh while expanding its capabilities. A bitonic sort example is presented which demonstrates the utility of the enhanced connectivity. The multiple folded array concept is applied to a six neighborhood hexagonal array demonstrating the general nature of the concept.

Massively parallel multiple-folded clustered processor mesh array

A digital computer system capable of processing two or more computer instructions in parallel and having a cache storage unit for temporarily storing machine-level computer instructions in their journey from a higher-level storage unit of the computer system to the functional units which process the instructions. The computer system includes an instruction compounding unit located intermediate to the higher-level storage unit and the cache storage unit for analyzing the instructions and generating for to each instruction a compounding information which indicates whether or not that instruction may be processed in parallel with one or more neighboring instructions in the instruction stream. These tagged instructions are then stored in the cache unit with the compounding information. The computer system further includes a plurality of functional instruction processing units which operate in parallel with one another. The instructions supplied to these functional units are obtained from the cache storage unit. At instruction issue time, the compounding information for the instructions is examined and those instructions indicated for parallel processing are sent to different ones of the functional units in accordance with the codings of their operation code fields.

Method for processing instructions for parallel execution including

A massively parallel processor apparatus having an instruction set architecture for each of the N.sup.2 the PEs of the structure. The apparatus which we prefer will have a PE structure consisting of PEs that contain instruction and data storage units, receive instructions and data, and execute instructions. The N.sup.2 structure should contain 'N' communicating ALU trees, 'N' programmable root tree processor units, and an arrangement for communicating both instructions, data, and the root tree processor outputs back to the input processing elements by means of the communicating ALU trees. The apparatus can be structured as a bit-serial or word parallel system. The preferred structure contains N.sup.2 PEs, identified as PE.sub.column,row, in a N root tree processor system, placed in the form of a N by N processor array that has been folded along the diagonal and made up of diagonal cells and general cells. The Diagonal-Cells are comprised of a single processing element identified as PE.sub.i,i of the folded N by N processor array and the General-Cells are comprised of two PEs merged together, identified as PE.sub.i,j and PE.sub.j,i of the folded N by N processor array. Matrix processing algorithms are discussed followed by a presentation of the Diagonal-Fold Tree Array Processor architecture. The Massively Parallel Diagonal-Fold Tree Array Processor supports completely connected root tree processors through the use of the array of PEs that are interconnected by folded communication ALU trees.

Parallel diagonal-fold array processor

A system for processing a sequence of instructions has a set of compounding rules based on an analysis of existing instructions to separate them into different classes. The analysis determines which instructions qualify, either with instructions in their own class or with instructions in other classes, for parallel execution in a particular hardware configuration. Such compounding rules are used as a standard for pre-processing an instruction stream in order to look for groups of two or more adjacent scalar instructions that can be executed in parallel.

System for obtaining parallel execution of existing instructions in a

A massively parallel processor apparatus having an instruction set architecture for each of the N.sup.2 the PEs of the structure. The apparatus which we prefer will have a PE structure consisting of PEs that contain instruction and data storage units, receive instructions and data, and execute instructions. The N.sup.2 structure should contain 'N' communicating ALU trees, 'N' programmable root tree processor units, and an arrangement for communicating both instructions, data, and the root tree processor outputs back to the input processing elements by means of the communicating ALU trees. The apparatus can be structured as a bit-serial or word parallel system. The preferred structure contains N.sup.2 PEs, identified as PE.sub.column,row, in a N root tree processor system, placed in the form of a N by N processor array that has been folded along the diagonal and made up of diagonal cells and general cells. The Diagonal-Cells are comprised of a single processing element identified as PE.sub.i,j of the folded N by N processor array and the General-Cells are comprised of two PEs merged together, identified as PE.sub.i,j and PE.sub.j,i of the folded N by N processor array. Matrix processing algorithms are discussed followed by a presentation of the Diagonal-Fold Tree Array Processor architecture. The Massively Parallel Diagonal-Fold Tree Array Processor supports completely connected root tree processors through the use of the array of PEs that are interconnected by folded communication ALU trees.

Massively parallel diagonal-fold tree array processor

Apparatus for retaining the branch prediction bits of a line displaced from an integrated cache/branch history table and using the retained bits to initialize the prediction bits should that line be brought back into the cache, the operation of which may be overlapped with the activities normally associated with displacing a cache line with one fetched from memory, thus imposing no instruction processing penalty. The apparatus consists of an associative memory that provides storage for branch prediction bits associated with cache lines and comparison means for matching stored prediction bits with their corresponding cache lines.

Apparatus and method for storing and initializing branch prediction with

Growing community of inventors

Vestal, NY, United States of America

Stamatis Vassiliadis