International Business Machines Corporation

Hungwen Li

Ming-Cheng Sheng

Mark Alan Lavin

Yarsun Hsu

Robert S Jaffe

Walter C Dietrich, Jr

Margaret M Kienzle

Ching-Chy Wang

In a multiprocessor system, memory accesses by the individual processing elements are checked by a common controller. The controller includes a table of values defining valid memory locations for a task. The controller verifies the address value used by each instruction to ensure that, it is within a valid memory area for the particular task. Additional circuitry for the controller and processing elements allows finer control, of memory accessibility. The multiprocessor system may be coupled to a host computer through a buffer. Data is serially written into the buffer by the host and is read out of the buffer in parallel by the multiprocessor system. The buffer used in this system includes apparatus which calculates an error correction code from a serial data stream and passes this code, along with the data, to the multiprocessor system. The multiprocessor system includes apparatus which processes the data in parallel to handle errors occurring during transfers as indicated by the code.

Method and apparatus for performing memory protection operations in a

A two-dimensional input/output system for a massively parallel SIMD computer system providing an interface for the two-way transfer of data between a host computer and the SIMD computer. A plurality of buffers equal in number, and distributed with the individual processing elements of the SIMD computer are used to provide a temporary storage area which allows data in different formats to be mapped in a format suitable for transfer to the host computer or for transfer to the SIMD processing elements. The temporary storage is controlled in such a way as to transfer entire blocks of data in a single SIMD system clock cycle thereby achieving an input/output data rate of N bits/cycle for a SIMD computer consisting of N processors. The system is capable of handling irregular as well as regular data structures. The system also emphasizes a distributed approach in having the input/output system divided into N pieces and distributed to each processor to reduce the wiring complexity while maintaining the I/O rate.

Input/output system for a massively parallel, single instruction,

A single instruction multiple datastream (SIMD) polymorphic mesh network array processing system is modified by the inclusion of a single instruction multiple address (SIMA) circuit including a content addressable packet buffer memory to enable processing of an algorithm representing an arbitrary graph. Packets of address information and related data information associated with each independently addressable processing element forming the polymorphic mesh network array are transferred between the processing elements in accordance with one of a first-available method, a force transfer method, or a buffer sensitive method.

Methods and circuit for implementing and arbitrary graph on a

Two-dimensional mesh architecture in an array processor of myriad processing elements allows relative ease in manufacturing, using planar integrated circuits and predominant X, Y connections. There is a need, in any array processor, to connect a selected processing element to another processing element. Rather than to supply the large number of connectors required for dedicated connection of processing element to processing element, implementation is by a very limited number of connecting conductors (NESW) in a two-dimensional mesh. The connecting conductors are coplanar, making construction compatible with present-day, essentially planar and predominantly XY, packaging of integrated circuits and printed circuit boards. Flexibility of interconnection by means of this limited and inflexible set of conductors is accomplished by equipping each processing element with a hopping circuit. This is an advantageous tradeoff of silicon area, since the few active elements of the hopping circuit consume much less silicon area than the large number of conductors otherwise required. The hopping circuits are programmable, by a shared routing controller, to send input to an internal register file within the processing element, or to respond to a HOP (direction)(step) command. The HOP command selects the direction parameter by selecting one of the limited external connections to an adjacent processing element. Connection to a remote processing element requires a number of HOP command steps, carried out in a series of cycles. Each hopping circuit includes multiplexer, sink register, demultiplexer and gates.

Two-dimensional array of processing elements for emulating a

Polymorphic mesh uses physical mesh connection to form twelve useful connection patterns for each of the processing elements making up an image procssor of cellular automata under software control. Each processing element includes a limited mesh of interconnections to related processing elements. This provides for programmable choice of network configuration. The limited mesh of network interconnection is controlled by information stored in a register within the affected processing element. The interconnection pattern controlled by this information is invoked by programming, or by the combination of programming and process data, so as to configure the network of processing elements dynamically in the desired mesh. Representative configurations are:

Polymorphic mesh network image processing system

Using a variable-duration clock circuit, together with programmable duration control to alter the clock waveform within strict rules, permits the programmer to arrange appropriately short durations for short data transfers, and to arrange appropriately longer durations for longer data transfers in an array processor of myriad processing elements. There is no need to allow sufficient time in every clock cycle for worst case data transfer between remote processing elements. The clock waveform has three recognizable edges (A,B,C) regardless of loss of sharpness during its travel to the various processing elements. The convention that three skew-sensitive activities, READ, WRITE and OPERAND SUPPLY conform to respectively assigned edges as follows:

Programmable variable-cycle clock circuit for skew-tolerant array

Table lookup for an N.times.N image on an M.times.M 2D array is speeded by enhancing an address word to access table entries greater in number than the address word bit structure normally permits. This is done by organizing a 2D array (M.times.M) as a 8-interconnected array, decomposing the N.times.N array into N/M.times.N/M subimages, and generating and enhancing dichotomy windows of size K.times.K at the subimage level as table lookup addresses. For arbitrary combinations of M, N and K, the address word is broken into two dichotomies, and each dichotomy is altered by incrementing and decrementing. This provides multi-bit addressing for sufficient table entries to carry out in a single cycle the complex table lookup required for processing a multi-bit (i.e., 3.times.3) window. The output of a programmable logic array accesses four quadrants of memory. The current pixel number CPN is made available from the computer control. This is divided into two halves, HCPN and LCPN, which are incremented or decremented to form signals IHCPN, ILCPN, DHCPN and DLCPN. Carry and borrow signals CIH and BDH, respectively, are concatenated with the other signals to provide the requisite number of table addresses. Address 00, for example, is HCPN when CIH=0. Addresses for the other memory banks are derived similarly.

Table lookup addressing by dichotomy window generation

Equipping individual processing elements with an instruction adapter provides an array processor with adaptive spatial-dependent and data-dependent processing capability. The instruction becomes variable, at the processing element level, in response to spatial and data parameters of the data stream. An array processor can be optimized, for example, to carry out very different instructions on spatial-dependent data such as blank margin surrounding the black lines of a sketch. Similarly, the array processor can be optimized for data-dependent values, for example to execute different instructions for positive data values than for negative data values. Providing each processing element with a processor identification register permits an easy setup by flowing the setup values to the individual processing elements, together with setup of condition control values. Each individual adaptive processing element responds to the composite values of original setup and of the data stream to derive the instruction for execution during the cycle. In the usual operation, each adaptive processing element is individually addressed to set up a base instruction; it also is conditionally set up to execute a derived instruction instead of the base instruction. An array processor made up of adaptive processing elements can adapt dynamically to changes in its input data stream, and thus can be dynamically optimized, resulting in greatly enhanced performance at very low incremental cost.

Growing community of inventors

Pleasantville, NY, United States of America

Hungwen Li