Architecture for block processing computer system

• US 4,839,801 A
• Filed: 11/03/1986
• Issued: 06/13/1989
• Est. Priority Date: 11/03/1986
• Status: Expired due to Fees

• Current Assignee: Saxpy Computer Corporation
• Original Assignee: Saxpy Computer Corporation
• Inventors: Straub, Joseph E., Mannion, Joel, Schreiber, Rob, Leavitt, Ronald, Nicely, Mark C., Papenberg, Robert L., Lang, Gary R.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Nguyen, Viet Q.
• Application Number:
  US06/926,764
• Time in Patent Office: 953 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 710/35
• CPC Class Codes: G06F 15/8092 Array of vector units

Abstract

A block processing computing system includes a decomposition unit, a control circuit, a system memory, a data block path and a block processor. The decomposition unit receives externally-supplied primitive command packets and decomposes the primitive into machine language operations on computational blocks of data. The control circuitry generates control and address signals for performing the machine level operations. The data block path includes alignment circuitry for selecting data from burst-accessed blocks of data and a macropipeline for controllably storing and transferring blocks of data to and from the block processor. The block processor has interchangeable, double-buffered local zone memories and a parallel set of pipelined vector processors for performing block operations on computational blocks of data.

Claims

1. A computing system for performing externally-specified mathematical operations on externally-specified subarrays of an array of data words stored in a system memory (SMEM) having a memory I/O port, the system comprising:

(a) a system bus, said system bus being coupled to the memory I/O port for transmitting data words to and from the SMEM;

(b) alignment means, said alignment means being coupled to said system bus for controllably selecting data words from said system bus;

(c) block processing means for performing a block operation on at least one computational block of data words, said block processor means comprising a set of processors and block storage means for storing said at least one computational block of data words, said block processing means being coupled to said alignment means.

(d) decomposition and control means for receiving an externally-supplied command packet specifying the location of at least one subarray in said SMEM and specifying an operation to be performed on said at least one specified subarray, for defining computational blocks of data words from said at least one specififed subarray, for decomposing said operation into a series of block operations on said defined computational blocks, and for generating control and address signals to control and configure said SMEM to perform, at a burst transfer rate, at least one burst transfer of a plurality of data words onto said system bus, including the words contained in a first one of said defined computational blocks, and to control and configure said alignment means to select the words contained in said first defined computational block from said burst transferred plurality of data words on said system bus, and to control and configure said block processing means to transfer said selected words of said first defined computational block to selected storage locations of said block processing means, and to perform a first one of said series of block operations on said first defined computational block, said decomposition and control means being operatively coupled to said SMEM, said alignment means, and said block processing means.

2. The system of claim 1, wherein said decomposition and control means comprises:

block decomposition means for receiving said command packets, for defining said computational blocks, for decomposing said command packet into said series of block operations on said defined computational blocks, and for generating machine level operation signals (MLO fields), said MLO fields including data movement MLO fields for specifying the movement of data words between the SMEM and said block processing means and including block operation MLO fields for specifying the block operations to be performed on said defined computational blocks of data words; and

control and address signal generating means coupled to said block decomposition means and to said SMEM, said alignment means, and said block processing means, and responsive to said MLO fields for generating said control and address signals to control and configure said SMEM, said alignment means, and said block processor.

3. The system of claim 2, wherein said control and address signal generating means comprises:

data block movement control and address signal generating means responsive to said data movement MLO fields and coupled to said SMEM, said alignment means and said block processing means for generating control and address signals for transferring data between said SMEM and said block processing means;

processor control and address signal generating means responsive to said block operation MLO fields and coupled to said block processing means for controlling said block processing means to perform said first block operation on said first defined computational block of data; and

means responsive to subfields in said MLO fields for synchronizing said data block movement control and address signal generating means with said processor control and address signal generating means by ensuring that all necessary data block movement operations are completed prior to issuing processor control and address signals.

4. The system of claim 1 wherein said block processing means has a plurality of ports, and wherein said system further comprises:

macropipeline means for controllably coupling said alignment means to said block processing means, said macropipeline means being coupled to said decomposition and control means and responsive to said generated control and address signals for coupling said alignment means to a selected one of said ports of said block processing means.

5. The system of claim 4 wherein said macropipeline means comprises:

a funnel buffer having first and second I/O ports, said first I/O port being coupled to said alignment means, for storing a computational block of data words; and

switching means coupled to the second buffer I/O port and to said block processing means for controllably transferring selected data words between selected storage locations of said funnel buffer and said selected one of said ports of said block processing means.

6. The system of claim 1, wherein said block storage means of saids block processing means comprises:

working side storage means coupled to said processors for storing a computational block and for reading data from and writing data to said processors during a block operation; and

I/O side storage means coupled to said alignment means for receiving and sending computational blocks of data;

said block processing means also having a global input port coupled between said alignment means and to each of said processors.

7. The system of claim 6, wherein said I/O side storage means has a plurality of ports, and wherein said system further comprises:

macropipeline means for controllably coupling said alignment means to said block processing means, said macropipeline means being coupled to said decomposition and control means, said alignment means, and said block processing means, and being responsive to said generated control and address signals for coupling said alignment means to said block processing means global input port or to a selected one of said ports of said I/O side storage means.

8. The system of claim 7 wherein said macropipeline means comprises:

a funnel buffer having first and second I/O ports, said first I/O port being coupled to said alignment means for receiving and storing a computational block of data words; and

switching means coupled to the second buffer I/O port and to said block processing means for controllably transferring selected data words between selected storage locations of said funnel buffer and said block processing means global input port or a selected one of said ports of said I/O side storage means.

9. The system of claim 8 wherein said funnel buffer comprises:

a pair of random access memories (RAMs); and

funnel buffer control unit means coupled to said RAMs and coupled to said decomposition and control means for translating and communicating address signals to said RAMs and for controllably switching the paths from said first and second buffer I/O ports to said RAMs so that one RAM is coupled to the first buffer I/O port when the other RAM is coupled to the second buffer I/O port.

10. The system of claim 8 wherein said decomposition and control means is operative to generate a buffer select signal and wherein said system comprises:

a plurality of funnel buffers, each having first and second I/O ports; and

SMEM interconnect means coupled to the first buffer I/O ports of said funnel buffers, to said alignment means, and to said decomposition and control means, for selectively coupling, in response to the buffer select signal, a selected funnel buffer to said alignment means, and for communicating address signals to said selected funnel buffer for addressing selected funnel buffer storage locations.

11. The system of claim 10, wherein said decomposition and control means is operative to generate a zone path select signal and a zone crossbar select signal, and wherein said switching means comprises:

zone path interconnect means having a plurality of zone path ports and coupled to the second I/O port of each funnel buffer and coupled to said decomposition and control means for receiving the zone path select signal and for controllably connecting, in response to said zone path select signal, a first funnel buffer either to a second funnel buffer or to one of said zone path ports, and for communicating address signals to said funnel buffers for addressing selected funnel buffer storage locations; and

a zone crossbar coupled to the zone path ports of said zone path interconnect means and to said I/O side storage means ports of said block processor, said zone crossbar being further coupled to said decomposition and control means for receiving the zone crossbar select signal, and for connecting, in response to said zone crossbar select signal, one of said I/O side storage means ports to one of said zone path ports.

12. The system of claim 11 wherein said decomposition and control means is operative to generate a direct path signal select and a direct crossbar select signal, and wherein said switching means further comprises:

direct path interconnect means having a plurality of direct path ports and coupled to the second I/O port of a third one of said funnel buffers and coupled to said decomposition and control means for receiving the direct path select signal, said third funnel buffer to said second one of said funnel buffers or to a direct path port, and for communicating address signals to said funnel buffers for addressing selected funnel buffer storage locations; and

a direct crossbar coupled to the direct path ports of said direct path interconnect means and to said processing means global input port and coupled to said decomposition and control means for receiving the direct crossbar select signal and for connecting, in response to said direct crossbar select signal, said processing means global input port to a selected direct path port.

13. The system of claim 1 wherein said SMEM comprises a plurality of local memories, and wherein said system further comprises:

a plurality of local buses, each local bus being coupled to the I/O port of a corresponding one of said local memories; and

synchronous data buffer means coupled to said local buses for synchronously concatenating data words transmitted on said local buses to form a wide word for transmission on said system bus;

said alignment means being responsive to said generated control and address signals to select the words contained in said first defined computational block from the wide words on said system bus.

14. A computing system for performing externally-specified mathematic operations on externally-specified subarrays of an array of data words stored in a system memory (SMEM) having a memory I/O port, the system comprising:

(a) a system bus, said system bus being coupled to the memory I/O port for transmitting data words to and from the SMEM;

(b) a funnel buffer, said funnel buffer having first and second buffer I/O ports, for storing a computational block of data words of a specified subarray;

(c) alignment means, said alignment means being coupled to said system bus and to the first buffer I/O port of said funnel buffer, for controllably transferring selected data words between said system bus and selected storage locations of said funnel buffer;

(d) block processing means for performing a block operation on at least one computational block of data words, said block processing means including a plurality of processors and block storage means for storing said at least one computational block of data;

(e) switching means, said switching means being coupled to the second buffer I/O port of said funnel buffer and to the block processing means for controllably transferring selected data words between selected locations of said funnel buffer and said block processing means;

(f) block decomposition means for receiving an externally-supplied command packet specifying the locations of at least one subarray in the SMEM and specifying an operation to be performed on at least one specified subarray, for defining computational blocks of data words from said at least one specified subarray, for decomposing said operation into a series of block operations on said defined computational blocks, and for generating machine level operation signals (MLO fields) specifying machine-level operations to be performed on data words from said at least one specified subarray, said MLO fields including a data block definition set, a data block movement set and a data block computation set, said data block definition set for specifying said defined computational blocks of data words and for specifying the transfer of data words between the SMEM and said funnel buffer, said data block movement set for specifying the transfer of said defined computational blocks between said funnel buffer and said block processing means, and said data block computation set for specifying said series of block operations on said defined computational block of data words; and

(g) control and address signal generating means comprising;

SMEM control and address signal generating means, said SMEM control and address signal generating means being coupled to said block decomposition means for receiving said MLO field data block definition set and coupled to the SMEM, to said alignment means, and to said funnel buffer, for generating, in response to said MLO field data block definition set, SMEM control and address signals to control and configure the SMEM to perform, at a burst transfer rate, a burst transfer of a plurality of data words onto said system bus, including the words in a first one of said defined computational blocks, and to control and configure said alignment means to select the words contained in said first defined computational block from said burst transferred words on the system bus, and to transfer said first defined computational block of words between said system bus and selected storage locations of said funnel buffer;

pipeline control and address signal generating means, said pipeline control and address signal generating means being coupled to said block decomposition means for receiving said MLO field data block movement set and coupled to said funnel buffer, said switching means, and to said block processing means, for generating, in response to said MLO field data block movement set, block movement control and address signals to control and configure said switching means and said block processing means to transfer said first defined computational block of words between selected locations of said funnel buffer and selected storage locations of said block processing means; and

processor control and address signal generating means, said processor control and address signal generating means being coupled to said block decomposition means for receiving said MLO field data block computation set and coupled to said block processing means for generating, in response to said MLO field data block computation set, processor control and address signals to configure and control said block processing means to perform a first one of said series of block operations on said first defined computational block of words.

15. The system of claim 14 wherein said block storage means of said block processing means comprises:

working side storage means coupled to said processors for storing a computational block and for reading data from and writing data to said processors during a block operation; and

I/O side storage means coupled to said switching means for receiving and sending computational blocks of data;

said block processor means also having a global input port coupled between said switching means and each of said processors.

16. The system of claim 14 wherein said block processing means comprises a set of N vector processors, where N is an integer, a set of N working side buffers for writing data to and reading data from said vector processors during a block operation, a set of N I/O side buffers coupled to said switching means for receiving and sending a computational block of data, and a global input port coupled to each of said vector processors.

17. The system of claim 14 wherein said SMEM comprises a plurality of local memories, and wherein said system further comprises:

a plurality of local buses, each local bus being coupled to the I/O port of a corresponding one of said local memories; and

a synchronous data buffer means coupled to said local buses for synchronously concatenating data words transmitted on said local buses to form a wide word for transmission on said system bus; and

said alignment means being responsive to said block movement control and address signals to select the words contained in said first defined computational block from said wide words on said system bus.

18. The system of claim 14 wherein said funnel buffer comprises:

a pair of random access memories (RAMs); and

funnel buffer control unit means coupled to said RAMs and coupled to said SMEM control and address and address signal generating means for translating and communicating address signals to said RAMs and for controllably switching the paths from the first and second buffer I/O ports to said RAMs so that one RAM is coupled to the first buffer I/O port when the other RAM is coupled to the second buffer I/O port.

19. The system of claim 15, wherein said SMEM control and address signal generating means is operative to generate a buffer select signal, and wherein said system further comprises:

a plurality of funnel buffers, each having first and second I/O ports; and

SMEM interconnect means coupled to the first buffer I/O ports of said funnel buffers, to said alignment means, and to said SMEM control and address signal generating means, for selectively coupling, in response to the buffer select signal, a selected funnel buffer to said alignment means, and for communicating address signals to said selected funnel buffer for addressing selected funnel buffer storage locations.

20. The system of claim 19, wherein said I/O side storage means of said block processing means has a plurality of ports and said pipeline control and address signal generating means is operative to generate a zone path select signal and a zone crossbar select signal, and wherein said switching means comprises:

zone path interconnect means having a plurality of zone path ports and coupled to the second I/O port of each funnel buffer and coupled to said pipeline control and address signal generating means for receiving the zone path select signal and for controllably connecting, in response to said zone path select signal, a first funnel buffer either to a second funnel buffer or to one of said zone path ports, and for communicating address signals to said funnel buffers for addressing selected funnel buffer storage locations; and

a zone crossbar coupled to the zone path ports of said zone path interconnect means and to said I/O side storage means ports of said block processor, and coupled to said pipeline control signal generating means for receiving the zone crossbar select signal, and for connecting, in response to said zone crossbar select signal, one of said I/O side storage means ports to one of said zone path ports.

21. The system of claim 20, wherein the pipeline control and address signal generating means is operative to generate a direct path select signal and a direct crossbar select signal, and wherein said switching means further comprises:

direct path interconnect means having a plurality of direct path ports and coupled to the second I/O port of a third one of said funnel buffers and coupled to said pipeline control and address signal generating means for receiving the direct path select signal, and for connecting, in response to said direct path select signal, said third funnel buffer to said second one of said funnel buffers or to a selected direct path port, and for communicating address signals to said funnel buffers for addressing selected funnel buffer storage locations; and

a direct crossbar coupled to the direct path ports of said direct path interconnect means and to said processor global input port and coupled to said pipeline control signal generator means for receiving the direct crossbar select signal and for connecting, in response to said direct crossbar select signal, said processor global input port to a selected direct path port.

22. The system of claim 14, wherein said block decomposition means is operative to generate and transmit END-OF-SLICE signals for delimiting slices wherein said slices are groups of MLO fields that specify all the aspects of an identifiable block process within one section of the system,

and wherein said SMEM control and address signal generating means comprises:

SMEM control staging register means, coupled to said block decomposition means, for receiving and storing a data block definition MLO slice;

SMEM control working register means coupled to said SMEM control staging register means, for storing an SMEM control word;

SMEM control synchronizing means coupled to said SMEM control working register means, for loading the contents of said SMEM control staging register means into said SMEM control working register means to form said SMEM control word;

SMEM control word executing means coupled to said SMEM working register means, for executing said SMEM control word; and

wherein

said pipeline control and address signal generating means comprises;

pipeline control staging register means, coupled to said block decomposition means, for receiving and storing a data block movement MLO slice;

pipeline control working register means coupled to said pipeline control staging register means, for storing a pipeline control word;

pipeline control synchronizing means coupled to said pipeline control working register means, for loading the contents of said pipeline control staging register means into said pipeline control working register means to form said pipeline control word; and

pipeline control word executing means coupled to said pipeline working register means, for executing said pipeline control word; and

wherein

said processor control signal generating means comprises;

processor control staging register means, coupled to said block decomposition means, for receiving and storing a data block computation MLO slice;

processor control working register means coupled to said processor control staging register means, for storing a processor control word;

processor control synchronizing means coupled to said processor control working register means, for loading the contents of said processor control staging register means into said processor control working register means to form said processor control word; and

processor control word executing means coupled to said processor working register means, for executing said processor control word;

whereby each of said control and address signal generating means can execute a control word while an MLO slice is being received to form the next control word.

23. The system of claim 22 wherein:

said SMEM control word executing means is coupled to said corresponding SMEM control synchronizing means and is operative to transmit a DONE signal to said corresponding SMEM control synchronizing means after said SMEM control word executing means has finished execution of an SMEM control word;

said pipeline control word executing means is coupled to said pipeline control synchronizing means and is operative to transmit a DONE signal to said corresponding pipeline control synchronizing means after said pipeline control word executing means has finished execution of a pipeline control word;

said processor control word executing means is coupled to said processor control synchronizing means and is operative to transmit a DONE signal to said corresponding processor control synchronizing means after said processor control word executing means has finished execution of a processor control word;

said SMEM control synchronizing means is operative, in response to both said DONE signal from said SMEM control word executing means and an END-OF-SLICE signal, to load the contents of said SMEM control staging register means into the corresponding SMEM control working register means;

said pipeline control synchronizing means is operative, in response to both said DONE signal from said pipeline control word executing means and an END-OF-SLICE signal, to load the contents of said pipeline control staging register means into the corresponding pipeline control working register means; and

said processor control synchronizing means is operative, in response to both said DONE signal from said processor control word executing means and an END-OF-SLICE signal, to load the contents of said processor control staging register means into the corresponding processor control working register means.

24. The system of claim 23 wherein:

each of said SMEM control staging register means, pipeline control staging register means, and processor control staging register means comprises a plurality of addressable staging registers;

said block decomposition means is operative to include a staging register address with each MLO field; and

said SMEM control and address signal generating means further comprises decoding means for loading each MLO field into the SMEM control staging register means addressed by said staging register address;

said pipeline control and address signal generating means further comprises decoding means for loading each MLO field into the pipeline control staging register means addressed by said staging register address;

said processor control and address signal generating means further comprises decoding means for loading each MLO field into the processor control staging register means addressed by said staging register address;

whereby an MLO slice may consist of selected MLO fields to be modified to form a control word comprising said selected MLO fields and the unmodified MLO fields from a previous control word.

25. The system of claim 23 wherein:

said SMEM control and address signal generator means is bi-directionally coupled to said pipeline control and address signal generator means for transmitting and receiving an intercontroller synchronization signal for synchronizing the execution of the SMEM control word and the pipeline control word;

said pipeline control and address signal generator means is bi-directionally coupled to said processor control signal generator means for transmitting and receiving an intercontroller synchronization signal for synchronizing the execution of the pipeline control word and the processor control word;

said block decomposition means is operative to generate and transmit an interlock signal associated with an MLO slice to interlock said MLO slice with a designated control and address signal generating means;

said SMEM control word executing means of said SMEM control and address signal generating means is operative, in response to an SMEM control word formed from an interlocked MLO slice, to transmit a DONE signal to the corresponding SMEM control word synchronizing means when said SMEM control word executing means has finished execution of said SMEM control word and said SMEM control word executing means has received an intercontroller synchronization signal from the designated control and address signal generating means;

said pipeline control word executing means of said pipeline control and address signal generating means is operative, in response to a pipeline control word formed from an interlocked MLO slice, to transmit a DONE signal to the corresponding pipeline control word synchronizing means when said pipeline control word executing means has finished execution of said pipeline control word and said pipeline control word executing means has received an inter-controller synchronization signal from the designated control and address signal generating means; and

said processor control word executing means of said processor control and address signal generating means is operative, in response to a processor control word formed from an interlocked MLO slice, to transmit a DONE signal to the corresponding processor control word synchronizing means when said processor control word executing means has finished execution of said processor control word and said processor control word executing means has received an inter-controller synchronization signal from the designated control and address signal generating means.

26. The system of claim 16 wherein:

said data block computation set of MLO fields includes array-defining MLO fields for designating a starting address, a row stride, and a column stride;

and wherein said processor control and address signal generating means comprises;

processor control signal generating means for generating processor control signals for controlling said block processor, and for generating a column update signal and a next row signal; and

doubly-strided address generating means coupled to said processor control signal generating means for computing a series of linear addresses of storage locations in a block processor working side buffer, in response to said starting address, row stride, column stride, a plurality of column update signals, and a plurality of next row signals, thereby generating a series of linear addresses for designating the storage locations of the data words in the two-dimensional array defined by said array-defining MLO fields;

said processor control signal generating means being operative to generate a series of processor control signal words containing processor control signals, each of said processor control signal words being associated both with an operation to be performed on a data word and with one of the series of linear addresses computed by said doubly-strided address generated means, for controlling said block processing means to perform a set of operations on a data word stored at said linear address.

27. The system of claim 26 wherein said vector processors are pipelined processors having a plurality of processing stages, and wherein said processor control and address signal generating means further comprises delay means for timing the transmission of the processor control signals in the processor control signal word to each stage of a vector processor.

28. A method for performing externally-specified mathematical operations on externally specified subarrays of an array of data stored in a system memory (SMEM), said method comprising the steps of:

(a) receiving an externally-supplied command packet, said packet specifying the location of at least one subarray in the SMEM, specifying an operation to be performed on said at least one specified subarray, and specifying the desired location of a result subarray of data words;

(b) defining at least one computational block of data words from said at least one specified subarray;

(c) decomposing the specified operation into at least one block operation on said at least one defined computational block to produce at least one result block;

(d) designating the locations in said result subarray for storing the words in said at least one result block;

(e) generating control and address signals for moving data and performing said at least one block operation;

(f) in response to said control and address signals;

(i) performing a burst transfer of a plurality of data words from the SMEM onto a system bus (SBUS), said plurality of burst transferred data words including the words contained in a first one of said at least one defined computational blocks;

(ii) selecting the data words contained in said first defined computational block from the words on said SBUS;

(iii) transferring said selected words in said first defined computational block to selected storage locations in a block processor;

(iv) performing a first one of said series of block operations on said selected words in said first defined computational blocks to produce a first result block of data words; and

(v) transferring the data words in said first result block to the designated locations in said result subarray.

29. The method of claim 28 wherein said decomposing step produces at least two block operations on at least two computational blocks and wherein steps (f)(i) through (f)(v) are repeated for at least a second defined computational block and at least a second block operation until all of said block operations have been performed, thereby producing said result subarray.

30. The method of claim 28 further comprising, before said control and address signal generating step, the step of generating, in response to said command packet, machine level operation signals (MLO fields), specifying the movement of data words between the SMEM and the block processor and specifying the block operations to be performed on said defined computational blocks, said control and address generating step being performed in response to said MLO fields.

31. The method of claim 28 wherein said transferring step (f)(iii) comprises:

transferring said selected words in said first defined computational block to selected locations in a funnel buffer coupled to the SMEM and the block processor;

storing said selected words in said first defined computational block in said funnel buffer; and

transferring said stored words in said first defined computational block from said funnel buffer to selected storage locations in said block processor.

32. The method of claim 30 wherein said transferring step (f)(v) comprises:

transferring the data words in said first result block to selected locations in a funnel buffer;

storing said result block in said funnel buffer; and

transferring the data words in said result block from said funnel buffer to the designated locations in said result subarray.