Single-chip multiprocessor with clock cycle-precise program scheduling of parallel execution

• US 7,895,587 B2
• Filed: 09/08/2006
• Issued: 02/22/2011
• Est. Priority Date: 02/17/2000
• Status: Expired due to Fees

• Current Assignee: Elbrus International Limited
• Original Assignee: Elbrus International Limited
• Inventors: Nazarov, Leonid N., Gruzdov, Feodor A., Rozhkov, Sergey A., Tikhorsky, Vladimir V., Chudakov, Mikhail L., Sakhin, Yuli Kh., Volkonskiy, Vladimir Yu., Babaian, Boris A.
• Primary Examiner(s): Dam; Tuan Q
• Assistant Examiner(s): TECKLU, ISAAC TUKU
• Application Number:
  US11/518,038
• Publication Number:
  US 20070006193A1
• Time in Patent Office: 1,628 Days
• Field of Search: None
• US Class Current: 717/161
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A single-chip multiprocessor system and operation method of this system based on a static macro-scheduling of parallel streams for multiprocessor parallel execution. The single-chip multiprocessor system has buses for direct exchange between the processor register files and access to their store addresses and data. Each explicit parallelism architecture processor of this system has an interprocessor interface providing the synchronization signals exchange, data exchange at the register file level and access to store addresses and data of other processors. The single-chip multiprocessor system uses ILP to increase the performance. Synchronization of the streams parallel execution is ensured using special operations setting a sequence of streams and stream fragments execution prescribed by the program algorithm.

Claims

1. A single-chip multiprocessor for executing programs compiled using a static clock-precise macro-scheduling program such that a compiled source program is a set of consecutive super-wide instructions, comprising:

K explicit parallelism architecture processors each of which may decode no more than N operations each clock cycle, wherein the K processors are configured to execute no more than K parallel streams, wherein the K parallel streams are created by partitioning each super-wide instruction into no more than K wide instructions, and wherein each wide instruction contains no more than N operations and belongs to only one parallel stream; and

a synchronization signal exchanger between the processors, wherein the synchronization signal exchanger transmits “

permit”

signals that control a sequence of execution of any two parallel streams, and wherein specified streams include synchronization points having synchronization operations that are included with wide instructions of specified streams, the synchronization operations including “

to permit execution of another parallel stream”

(“

permit”

) and “

to wait execution of another parallel stream”

(“

wait”

),

wherein “

permit” and

“

wait”

operations are defined from each processor to every other processor, wherein a first processor having a first “

permit”

operation at a first synchronization point is configured to send a first “

permit”

signal to a second processor, and wherein a second processor having a corresponding “

wait”

operation at a different synchronization point is configured to check a presence of the first “

permit”

signal from the first processor and stop execution while the first “

permit”

signal is absent,

wherein K and N are integers, and wherein K is greater than one.

2. The single-chip multiprocessor of claim 1, wherein the second processor is configured to send, after receiving the first “

permit”

signal, a second “

permit”

signal to the first processor to be checked by the first processor having a corresponding “

wait”

signal at a second synchronization point.

3. The single-chip multiprocessor of claim 1, wherein an execution of a “

permit”

operation by a processor executing one stream is locked by a lock signal received through the synchronization signal exchanger from another processor executing another stream when the another processor has not completed a “

wait”

operation corresponding to a “

permit”

operation previously received by the another processor.

4. The single-chip multiprocessor of claim 1, further comprising:

a first logic that produces a lock signal to stop execution of the second processor based on input signals from a second logic, wherein the second logic receives “

permit”

signals from the first processor and receives “

wait”

signals from the second processor.

5. The single-chip multiprocessor of claim 1, wherein the synchronization operations further include “

to wait execution of another parallel stream then to permit this another parallel stream”

(“

wait and permit”

) and “

to be indifferent to another parallel stream”

(“

indifferent”

), wherein;

the “

wait and permit”

operation consists of two operations “

wait” and

“

permit”

carried out consistently; and

the “

indifferent”

operation defines an indifferent relation of a processor to the state of another processor that executes another stream in a given synchronization point.

6. The single-chip multiprocessor of claim 1, further comprising a register exchanger for providing data exchange between the streams at a processor register file and control register level using special exchange processor operations added in wide instructions of specified streams.

7. The single-chip multiprocessor of claim 6, wherein the register exchanger transfers data between registers at a processor register file or control register level of any of two processors of the single-chip multiprocessor using an entrance FIFO buffer in each processor, wherein:

a “

transmit”

operation reads data from a register of a processor and then transmits this data from the register through the register exchanger to a FIFO buffer of another processor; and

a “

receive”

operation reads data received at an entrance FIFO buffer of a processor and then writes this data to a register of that processor.

8. The single-chip multiprocessor of claim 6, wherein:

a “

transmit”

operation execution on a processor is locked by a lock signal transmitted through the register exchanger from another processor if the entrance FIFO buffer of the another processor has a full state; and

a “

receive”

operation execution on a processor is locked if the entrance FIFO buffer of that processor has an empty state.

9. The single-chip multiprocessor of claim 1, further comprising:

a cache exchanger for providing for coherent state of internal processor caches of the single-chip multiprocessor, wherein the cache exchanger transmits address and data of all store operations from all processors to all other processors for a correction of the cache contents; and

multiple connection buses between the processors for transfer of store addresses and stored data.

10. The single-chip multiprocessor of claim 9, wherein the cache exchanger includes for each respective processor:

a first logic for sending addresses and stored data of store operations from a respective processor to all K-1 other processors;

a K−

1 input associative buffer for reception and temporary storing of store addresses and stored data from the K−

1 other processors, wherein received addresses and data are reviewed and used by memory access operations; and

a second logic for sending lock signals to the K−

1 other processors, wherein the lock signals prohibit completion of store operations of the K−

11 other processors if the associative buffer of the respective processor is full.

11. The single-chip multiprocessor of claim 1, wherein each respective processor contains K−

1 reverse counters for synchronizing events among the K processors, wherein each reverse counter of a respective processor corresponds to one of the K−

1 other processors, wherein each reverse counter calculates a difference between a number of received “

permit”

signals from the corresponding other processor and a number of “

wait”

signals from the respective processor, wherein the “

permit”

signals from the corresponding other processor increment the reverse counter if a counter value is less than a highest possible value, and wherein the “

wait”

signals decrement the reverse counter if a counter value is not zero.

12. The single-chip multiprocessor of claim 11, wherein:

a highest possible value of any reverse counter forms a first lock signal that is sent through the synchronization signal exchanger from a respective processor to the corresponding other processor, wherein the first lock signal prevents a “

permit”

signal from being sent to the respective processor from the corresponding other processor; and

a zero value of any reverse counter prevents receiving a “

wait”

signal from the respective processor.

13. The single-chip multiprocessor of claim 1, wherein the total number of processors in the single-chip multiprocessor is greater than K.

14. The single-chip multiprocessor of claim 1, further comprising a configuration unit that assigns virtual numbers to the explicit parallelism architecture processors for partitioning the processors into independently working subsystems.

15. A multi-chip multiprocessor system comprising:

a plurality of single-chip multiprocessors, wherein at least one of the single-chip multiprocessors executes programs compiled using a static clock-precise macro-scheduling program such that a compiled source program is a set of consecutive super-wide instructions, wherein the at least one single-chip multiprocessor includes;

K explicit parallelism architecture processors each of which may decode no more than N operations each clock cycle, wherein the K processors are configured to execute no more than K parallel streams, wherein the K parallel streams are created by partitioning each super-wide instruction into no more than K wide instructions, wherein each wide instruction contains no more than N operations and belongs to only one parallel stream; and

a synchronization signal exchanger between the processors, wherein the synchronization signal exchanger transmits “

permit”

signals that control a sequence of execution of any two parallel streams, and wherein specified streams include synchronization points having synchronization operations that are included with wide instructions of specified streams, the synchronization operations including “

to permit execution of another parallel stream”

(“

permit”

) and “

to wait execution of another parallel stream”

(“

wait”

),

wherein “

permit” and

“

wait”

operations are defined from each processor to every other processor, wherein a first processor having a first “

permit”

operation at a first synchronization point is configured to send a first “

permit”

signal to a second processor, and wherein a second processor having a corresponding “

wait”

operation is configured to check a presence of the first “

permit”

signal from the first processor and stop execution while the first “

permit”

signal is absent,

wherein K and N are integers, and wherein K is greater than one.

16. A single-chip multiprocessor for executing programs compiled using a static clock-precise macro-scheduling program such that a compiled source program is a set of consecutive super-wide instructions, comprising:

K explicit parallelism architecture processors each of which may decode no more than N operations each clock cycle, wherein the K processors are configured to execute no more than K parallel streams, wherein the K parallel streams are created by partitioning each super-wide instruction into no more than K wide instructions, wherein each wide instruction contains no more than N operations and belongs to only one parallel stream, wherein K and N are integers, and wherein K is greater than one;

a synchronization signal exchanger between the processors, wherein the synchronization signal exchanger transmits “

permit” and

lock signals that control a sequence of execution of any two parallel streams having synchronization points and synchronization operations included with wide instructions of specified streams, the synchronization operations including “

to permit execution of another parallel stream”

(“

permit”

) and “

to wait execution of another parallel stream”

(“

wait”

),

wherein “

permit” and

“

wait”

operations are defined from each processor to every other processor, wherein a first processor having a first “

permit”

operation at a first synchronization point is configured to send a first “

permit”

signal to a second processor, and wherein a second processor having a corresponding “

wait”

operation at a different synchronization point is configured to check a presence of the first “

permit”

signal from the first processor and stop execution while the first “

permit”

signal is absent, and

wherein an execution of a “

permit”

operation by a processor executing one stream is locked by a first lock signal received through the synchronization signal exchanger from another processor executing another stream when the another processor has not completed a “

wait”

operation corresponding to a “

permit”

operation previously received by the another processor;

a register exchanger for providing data exchange between the streams at a processor register file and control register level using special exchange processor operations “

transmit” and

“

receive”

added in wide instructions of specified streams, wherein the register exchanger transfers data between registers of two processors of the single-chip multiprocessor using an entrance FIFO buffer in each processor, wherein;

a “

transmit”

operation reads data from a register of a processor and then transmits this data from the register through the register exchanger to a FIFO buffer of another processor;

a “

receive”

operation reads data received at an entrance FIFO buffer of a processor and then writes this data to a register of that processor;

a “

transmit”

operation execution on a processor is locked by a second lock signal transmitted through the register exchanger from another processor if the entrance FIFO buffer of the another processor has a full state; and

a “

receive”

operation execution on a processor is locked if the entrance FIFO buffer of that processor has an empty state;

a cache exchanger for providing for coherent state of internal processor caches of the single-chip multiprocessor, wherein the cache exchanger transmits address and data of all store operations from all processors to all other processors for a correction of the cache contents; and

wherein the synchronization signal exchanger includes a multiple connection bus for transfer of synchronization signals, wherein the register exchanger includes a multiple connection bus for transfer of register files and control registers data, and wherein the cache exchanger includes a multiple connection bus for transfer of store addresses and stored data.

17. The single-chip multiprocessor of claim 16, wherein each processor sends “

permit”

signals simultaneously to any number of other processors and each processor waits for “

permit”

signals from any number of other processors, wherein each processor transmits register data simultaneously to any number of other processors, and wherein each processor receives register data from only one processor at a time.