Hewlett-Packard Company

Trw Limited

Hewlett-Packard Development Company, L.p.

Bantwal R Rau

Ross A Towle

Philip J Kuekes

David W Yen

Christopher D Glaeser

Michael S Schlansker

Robert S Schreiber

Vinod Kumar Kathail

Santosh Abraham

Rajiv Gupta

Shail Aditya Gupta

William S Worley, Jr

Frederic C Amerson

Alain Darte

Scott A Mahlke

Wei-Chen Yen

A method of designing a pipeline comprises the steps of: accepting a task procedure expressed in a standard programming language, the task procedure including a sequence of computational steps; accepting a performance requirement of the pipeline; and automatically creating a hardware description of the pipeline, the pipeline comprising a plurality of interconnected processor stages, each of the processor stages for performing a respective one of the computational steps, the pipeline having characteristics consistent with the performance requirement of the pipeline.

Method and system for the design of pipelines of processors

A system is provided which simplifies and speeds up the process of designing a computer system by evaluating the components of the memory hierarchy for any member of a broad family of processors in an application-specific manner. The system uses traces produced by a reference processor in the design space for a particular cache design and characterizes the differences in behavior between the reference processor and an arbitrarily chosen processor. The differences are characterized as a series of dilation parameters which relate to how much the traces would expand because of the substitution of a target processor. In addition, the system characterizes the reference trace using a set of trace parameters that are part of a cache behavior model. The dilation and trace parameters are used to determine the factors for estimating the performance statistics of target processors with specific memory hierarchies.

Rapid design of memory systems using dilation modeling

A parallel compiler maps iterations of a nested loop to processor elements in a parallel array and schedules a start time for each iteration such that the processor elements are fully utilized without being overloaded. The compiler employs an efficient and direct method for generating a set of iteration schedules that satisfy the following constraints: no more than one iteration is in initiated per processor element in a specified initiation interval, and a new iteration begins on each processor element nearly every initiation interval. Since the iteration scheduling method efficiently generates a set of schedules, the compiler can select an iteration schedule that is optimized based on other criteria, such as memory bandwidth, local memory size of each processor element, estimated hardware cost of each processor element, etc. The iteration scheduling method is useful for compilers where the underlying architecture is fixed, as well as for an automated processor array synthesis system where the nested loop is converted into a set of parallel processes for synthesis into a parallel processor array.

Programmatic iteration scheduling for parallel processors

A method for supporting speculative execution includes designating operations as speculative or non-speculative, and then deferring exceptions generated by speculative operations while immediately reporting exceptions by non-speculative operations. If a speculative operation uses a result of a speculative operation that has generated an exception, the exception is propagated. Deferred exceptions are detected and reported using a check operation either incorporated into a non-speculative operation or inserted as a separate check operation. A system for supporting speculative execution includes a functional unit for recognizing a speculative operation and deferring any exceptions generated by such an operation. The functional unit may defer an exception by storing information indicating an error has occurred in the register file. To check for deferred exceptions, the functional unit then reads the register file.

Method and system for deferring exceptions generated during speculative

A computer system having a multi-module memory system. Accesses to the memory modules for reading or writing are undertaken in parallel. The memory system is addressed by input addresses. The memory system includes a map unit for transforming the input addresses to output addresses in a pseudo-random manner so as to tend to distribute memory accesses uniformly among the memory modules whereby contention resulting from multiple concurrent attempts to access the same memory module is reduced. The map unit performs addresses transforms that are repeatable so that the same input address maps to the same output address and that are one-to-one such that each input address maps to one and only one output address.

Apparatus for transforming addresses to provide pseudo-random access to

A parallel processor computer system. The computer includes parallel processor units, an instruction unit which provides instructions to the processors and generates input and output address offsets, an invariant address unit which combines a multiconnect pointer with the address offsets to generate input and output operand addresses, and a multiconnect storage unit. Storage elements in the multiconnect unit are arranged in a matrix such that an output operand from a processor is stored in all the elements of an associated row and an input operand for a processor is obtained from any element of an associated column.

Horizontal computer having register multiconnect for operand address

A horizontal computer for execution of an instruction loop with a branch. The computer includes parallel processors, a multiconnect unit for storing operands for the processors, and instruction unit for specifying address offsets and operations to be performed by the processors, and an invariant address unit for combining the address offsets with a modifiable pointer to form source and destination addresses in the multiconnect unit. The instruction unit enables different ones of the processors both as a function of whether a branch instruction is to be executed and as a function of which iteration of the loop is being executed. The processors are enabled by processor control circuitry or by selectively providing instructions to the processors so that different operations are performed during different iterations.

Horizontal computer having register multiconnect for execution of a loop

A horizontal architecture computer in which a plurality of instructions are selectively communicated to a processing unit simultaneously or sequentially. The computer includes a processing unit with a plurality of processors, an instruction unit with a plurality of storage locations for storing instructions, and means for communicating the instructions to the processors. A first connection circuit provides a plurality of parallel communication channels between the storage locations and the processors and a second connection circuit provides a single serial communication channel between the storage locations and the processors. The first circuit is selected if a multioperation instruction is to be executed, otherwise the second circuit is selected instead.

System for selectively communicating instructions from memory locations

A horizontal computer for executing a loop with recurrence. The computer features a horizontal architecture in which parallel processors repeatedly iterate a loop of instructions with recurrence, that is, where a result operand from one iteration is used as a source operand in a later iteration. Some of the processors provide result operands and some perform operations on source operands. A multiconnect register stores the operands at addressable locations. An instruction unit counts iterations and gives source and result address offsets relative to a modifiable pointer. An invariant address unit assigns a value to the modifiable pointer according to which iteration is being performed and combines the pointer with the offsets to provide source and destination addresses. An epilog counter stores a count of ending iterations in which progressively fewer instructions are executed in each succeeding iteration.

Horizontal computer having register multiconnect for execution of an

A horizontal computer for execution of an instruction loop with overlapped code. The computer includes a plurality of processors, a multiconnect unit for storing operands for the processors, an instruction unit for specifying address offsets and operations to be performed by the processors, and an invariant address unit for combining the address offsets with a modifiable pointer to form source and destination addresses in the multiconnect unit. The instruction unit enables different ones of the processors as a function of which iteration of the loop is being executed, for example by means of processor control circuitry or by selectively providing instructions to the processors, so that different operations are performed during different iterations.

An interconnect circuit for use in a computer system employing horizontal architecture and having multiple resources of which the use must be scheduled in an optimum manner. The interconnect circuit reduces scheduling to a mechanical task by providing multi-word storage capability at each of a plurality of cross-points connected in data flow paths between the computer resources. At each cross-point of the interconnect circuit, data may be written into a selected location and retrieved from a selected location. Writing may be accomplished by an insertion operation in which already stored data is shifted to vacate the location selected for writing. Likewise, reading can be accompanied by a purge operation in which already stored data are shifted into the location from which a data word is purged. In this manner each cross-point can function as a time delay in a data path, to facilitate scheduling of resource usage.

Interconnect circuit

A computer system employing horizontal architecture and having multiple resources of which the use must be scheduled in an optimum manner. Scheduling is reduced to a mechanical task by the use of an interconnect circuit having multi-word storage capability at each of a plurality of cross-points providing data flow paths between the computer resources. At each cross-point of the interconnect circuit, data may be written into a selected location and retrieved from a selected location. Writing may be accomplished by an insertion operation in which already stored data is shifted to vacate the location selected for writing. Likewise, reading can be accompanied by a purge operation in which already stored data is shifted into the location from which data is purged. In this manner, each cross-point can function as a time delay in a data path, to facilitate scheduling of resource usage.

Easily schedulable horizontal computer

A memory circuit in which data words are held in a continuous sequence of locations, a new data word being insertable at a selected address, and a stored data word being readable from a selected address. On data word insertion, the selected location is first vacated by shifting data already stored above or below the selected address by one location. For example, all the data in locations having addresses equal to or greater than the selected address are shifted. Data read from the circuit may be optionally purged from the device and remaining data words are then shifted to fill the location vacated by the purged data. By appropriate selection of the various modes of operation, the memory circuit may be made to operate as a first-in-first-out memory, a last-in-first-out memory, or as a conventional random access memory. The circuit is well suited for use in a computer of the horizontal type, in which the use of computing resources has to be optimally scheduled, and data flowing between the resources has to be subjected to scheduled time delays.

Growing community of inventors

Los Gatos, CA, United States of America

Bantwal R Rau