International Business Machines Corporation

Henry Stanley Warren, Jr

Peter H Hochschild

Monty Montague Denneau

Martin Edward Hopkins

Richard A Swetz

David Scott Ray

Larry Edward Thatcher

Peter W Markstein

Gregory J Chaitin

There is provided a method for routing packets on a linear of N processors connected in a nearest neighbor configuration. The method includes the step of, for each end processor of the array, connecting unused outputs to corresponding unused inputs. For each axis required to directly route a packet from a source to a destination processor, the following steps are performed. It is determined whether a result of directly sending a packet from an initial processor to a target processor is less than or greater than N/2 moves, respectively. The initial processor is the source processor in the first axis, and the target processor is the destination processor in the last axis. The packet is directly sent from the initial processor to the target processor, when the result is less than N/2 moves. The packet is indirectly sent so as to wrap around each end processor, when the result is greater than N/2 moves. The method may optionally include the step of randomly sending the packet using either of the sending steps, when the result is equal to N/2 moves and N is an even number.

Methods for routing packets on a linear array of processors

Caches are associated with processors, such multiple caches may be associated with multiple processors. This association may be different for different main memory address ranges. The techniques of the invention are flexible, as a system designer can choose how the caches are associated with processors and main memory banks, and the association between caches, processors, and main memory banks may be changed while the multiprocessor system is operating. Cache coherence may or may not be maintained. An effective address in an illustrative embodiment comprises an interest group and an associated address. The interest group is an index into a cache vector table and an entry into the cache vector table and the associated address is used to select one of the caches. This selection can be pseudo-random. Alternatively, in some applications, the cache vector table may be eliminated, with the interest group directly encoding the subset of caches to use.

Flexible techniques for associating cache memories with processors and main memory

There is provided a method for routing packets on a linear array of N processors connected in a nearest neighbor configuration. The method includes the step of, for each end processor of the array, connecting unused outputs to corresponding unused inputs. For each axis required to directly route a packet from a source to a destination processor, the following steps are performed. It is determined whether a result of directly sending a packet from an initial processor to a target processor is less than or greater than N/2 moves, respectively. The initial processor is the source processor in the first axis, and the target processor is the destination processor in the last axis. The packet is directly sent from the initial processor to the target processor, when the result is less than N/2 moves. The packet is indirectly sent so as to wrap around each end processor, when the result is greater than N/2 moves. The method may optionally include the step of randomly sending the packet using either of the sending steps, when the result is equal to N/2 moves and N is an even number.

The geometric processing of an ordered sequence of graphics commands is distributed over a set of processors by the following steps. The sequence of graphics commands is partitioned into an ordered set of N subsequences S . . . S , and an ordered set of N state vectors V . . . V is associated with said ordered set of subsequences S . . . S . A first phase of processing is performed on the set of processors whereby, for each given subsequence S in the set of subsequences S . . . S , state vector V is updated to represent state as if the graphics commands in subsequence S had been executed in sequential order. A second phase of the processing is performed whereby the components of each given state vector V in the set of state vectors V . . . V generated in the first phase is merged with corresponding components in the preceding state vectors V . . . V such that the state vector V represents state as if the graphics commands in subsequences S . . . S had been executed in sequential order. Finally, a third phase of processing is performed on the set of processors whereby, for each subsequence S in the set of subsequences S . . . S , geometry operations for subsequence S are performed using the state vector V generated in the second phase. In addition, in the third phase, geometry operations for subsequence S are performed using the state vector V . Advantageously, the present invention provides a mechanism that allows a large number of processors to work in parallel on the geometry operations of the three-dimensional rendering pipeline. Moreover, this high degree of parallelism is achieved with very little synchronization (one processor waiting from another) required, which results in increased performance over prior art graphics processing techniques.

Method and parallelizing geometric processing in a graphics rendering pipeline

A multiple execution unit processing system is provided wherein each execution unit has an associated instruction buffer and all instruction are executed in order. The first execution unit (unit 0) will always contain the oldest instruction and the second unit (unit 1) the newest. Processor instructions, such as load, store, add and the like are provided to each of the instruction buffers (0,1) from an instruction cache buffer. The first instruction (oldest) is placed in buffer 0 and the next (second) instruction is stored in buffer 1. It is determined during the decode stage whether the instructions are dependent on an immediately preceding instruction. If both instructions are independent of other instructions, then they can execute in parallel. However, if the second instruction is dependent on the first, then (subsequent to the first instruction being executed) it is laterally shifted to the first instruction buffer. Instructions are also defined as being dependent on an unavailable resource. In most cases these 'unavailable' instructions are allowed to executed in parallel on the execution units.

Multiple execution unit dispatch with instruction shifting between first

A compiler generates compiled object code from source code of a computer program in a manner that produces efficient object code for a computer with dissimilar register spaces. The technique comprising the steps of (1) generating code that references symbolic registers in which the register class is not distinguished, (2) making entries in a table denoting the context in which each symbolic register occurs and constructing an equivalence tree of symbolic registers for move instructions assigned to a same equivalence class, (3) for each equivalence class, forming the logical OR function of register usage information for all symbolic registers in the class, and for each symbolic register that appears in more than one register space context, generating new symbolic register numbers so that there is one number for each register space, and storing the numbers in said table, and (4) if a definition point of a symbolic register is encountered and that symbolic register is used in more than one register space context, inserting code in said program to either do the same operation as is done at the definition point in each register space or move a value in the symbolic register from one space to another. The improvement achieved is in object code space and time of execution.

Generating efficient code for a computer with dissimilar register spaces

A method for improving the quality of code generated by a compiler or assembler, for a target machine that has short and long forms of some of its instructions with the short forms executing faster or occupying less space. The method first determines which bits of the result of each computational instruction are significant, by a backwards pass over the program that is similar to liveness analysis. Then the significant bits thus computed are used to guide the code selection process to select the most efficient instruction that computes the correct result in all the significant bit positions.

Method for generating short form instructions in an optimizing compiler

A method for improving the quality of code generated by a compiler in terms of execution time, object code space, or both. The method is applicable to computers that have a redundancy of instructions, in that the same operation exists in forms that operate between registers, between main storage locations, and between registers and main storage. The method selects the best form of each such instruction to use, for the context in which the instruction lies.

Growing community of inventors

Ossining, NY, United States of America

Henry Stanley Warren, Jr