Dynamic multi-mode parallel processing array

• US 5,475,856 A
• Filed: 10/17/1994
• Issued: 12/12/1995
• Est. Priority Date: 11/27/1991
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kogge, Peter M.
• Primary Examiner(s): Bowler, Alyssa H.
• Assistant Examiner(s): Nguyen, Dzung C.
• Application Number:
  US08/324,295
• Time in Patent Office: 421 Days
• Field of Search: 395/800, 395/250, 395/375, 364/DIG. 1, 364/228.3, 364/228.7, 364/228.9, 364/229.2, 364/231.9, 364/232.21, 364/232.9, 364/131, 364/132, 364/141
• US Class Current: 712/20
• CPC Class Codes: F02B 2075/027 four
• CPC Class Codes: G06F 15/17337 Direct connection machines, e.g. completely connected computers, point to point communication networks coupling between buses G06F13/4004
• CPC Class Codes: G06F 15/17343 wherein the interconnection is dynamically configurable, e.g. having loosely coupled nearest neighbor architecture reconfigurable processors arrays G06F15/7867
• CPC Class Codes: G06F 15/17368 non hierarchical topologies
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: G06F 15/8007 single instruction multiple data [SIMD] multiprocessors
• CPC Class Codes: G06F 15/8015 One dimensional arrays, e.g. rings, linear arrays, buses
• CPC Class Codes: G06F 15/803 Three-dimensional arrays or hypercubes
• CPC Class Codes: G06F 7/483 Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence
• CPC Class Codes: G06F 9/30 Arrangements for executing machine instructions, e.g. instruction decode for executing microinstructions G06F9/22
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/30145 Instruction analysis, e.g. decoding, instruction word fields
• CPC Class Codes: G06F 9/30167 of immediate specifier, e.g. constants
• CPC Class Codes: G06F 9/3017 Runtime instruction translation, e.g. macros
• CPC Class Codes: G06F 9/30189 according to execution mode, e.g. mode flag
• CPC Class Codes: G06F 9/38 Concurrent instruction execution, e.g. pipeline or look ahead
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3885 : using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/3887 : controlled by a single instruction for multiple data lanes [SIMD]
• CPC Class Codes: G06F 9/3888 : controlled by a single instruction for multiple threads [SIMT] in parallel
• CPC Class Codes: G06F 9/3889 : controlled by multiple instructions, e.g. MIMD, decoupled access or execute
• CPC Class Codes: G06F 9/3891 : organised in groups of units sharing resources, e.g. clusters

Abstract

A Parallel RISC computer system is provided by a multi-mode dynamic multi-mode parallel processor array with one embodiment illustrating a tightly coupled VLSI embodiment with an architecture which can be extended to more widely placed processing elements through the interconnection network which couples multiple processors capable of MIMD mode processing to one another with broadcast of instructions to selected groups of units controlled by a controlling processor. The coupling of the processing elements logic enables dynamic mode assignment and dynamic mode switching, allowing processors operating in a SIMD mode to make maximum memory and cycle time usage. On and instruction by instruction level basis, modes can be switched from SIMD to MIMD, and even into SISD mode on the controlling processor for inherently sequential computation allowing a programmer or complier to build a program for the computer system which uses the optimal kind of parallelism (SISD, SIMD, MIMD). Furthermore, this execution, particularly in the SIMD mode, can be set up for running applications at the limit of memory cycle time. With the ALLNODE switch and alternatives paths a system can be dynamically achieved in a few cycles for many many processors. Each processing element and memory and has MIMD capability the processor'"'"'s an instruction register, condition register and program counter provide common resources which are used in MIMD and SIMD. The program counter become a base register in SIMD mode.

Claims

1. A dynamic multi-mode parallel processing array, comprising:

a plurality of processors, each processor having a control unit for decoding and executing instructions of an instruction set, a data flow unit and a local memory, each of said control units having an instruction register, a program counter, a condition code register and a parallel mode bit (PMB), the PMB indicating whether the processor obtains instructions from a controlling processor or from said local memory;

an interconnection path between the instruction registers of the processors;

the instruction set having a plurality of instructions, each instruction having a parallel execution type bit (PET) that is used in conjunction with the PMB by the control unit to determine whether an instruction should be executed, the instruction set having a switch mode instruction for changing the PMB bit of a processor executing the instruction;

the processors organized into one or more groups, each group having a processor configured as the controlling processor, wherein any processor in the plurality of processors can be dynamically configured as the controlling processor, the controlling processor enabling the processors of a group to operate in a MIMD or SIMD mode, and to switch modes dynamically; and

when a group of processors are operating in SIMD mode the controlling processor provides instructions to the instruction registers of the other processors in the group, each instruction provided via the interconnection path when the controlling processor fetches the instruction;

wherein a controlling processor of a group of processors fetches instructions, and wherein other processors in the group latch into their instruction registers each instruction as the controlling processor fetches it, such that at the end of the instruction fetch all other processors have in their instruction register the fetched instruction; and

wherein the instruction set includes instructions which modify a processor'"'"'s program counter to function as a base register, including one or more of the following instructions;

a "Jump" instruction which when executed in a processor operating in SIMD mode sets the processor'"'"'s program counter to a value provide with the jump instruction; and

a "Load Immediate" instruction which when executed in a processor operating in SIMD mode loads a register with the contents of the processors'"'"' local memory, at the address specified by the processor'"'"'s program counter and then increments the program counter.

2. A dynamic multi-mode parallel processing array, comprising:

a plurality of processors, each processor having a control unit for decoding and executing instructions of an instruction set, a data flow unit and a local memory, each of said control units having an instruction register, a program counter, a condition code register and a parallel mode bit (PMB), the PMB indicating whether the processor obtains instructions from a controlling processor or from said local memory;

an interconnection path between the instruction registers of the processors;

the instruction set having a plurality of instructions, each instruction having a parallel execution type bit (PET) that is used in conjunction with the PMB by the control unit to determine whether an instruction should be executed, the instruction set having a switch mode instruction for changing the PMB bit of a processor executing the instruction;

the processors organized into one or more groups, each group having a processor configured as the controlling processor, wherein any processor in the plurality of processors can be dynamically configured as the controlling processor, the controlling processor enabling the processors of a group to operate in a MIMD or SIMD mode, and to switch modes dynamically; and

when a group of processors are operating in SIMD mode the controlling processor provides instructions to the instruction registers of the other processors in the group, each instruction provided via the interconnection path when the controlling processor fetches the instruction;

wherein a group of processors operating in SIMD mode switch to MIMD mode when the controlling processor provides each processor in the group with the switch mode instruction whereby each processor begins fetching instructions from its local memory; and

wherein the processors can communicate with each other using a load instruction to send and a store instruction to receive, said instructions containing an address which is used as a processor address on the interconnection path of the processor to communicate with, wherein the processor stalls until the communication takes place.

3. A dynamic multi-mode parallel processing array, comprising:

a plurality of processors, each processor having an control unit for decoding and executing instructions of an instruction set, a data flow unit and a local memory, each of said control units having an instruction register, a program counter, a condition code register and a parallel mode bit (PMB), the PMB indicating whether the processor obtains instructions from a controlling processor or from said local memory;

an interconnection path between the instruction registers of the processors;

the instruction set having a plurality of instructions, each instruction having a parallel execution type bit (PET) that is used in conjunction with the PMB by the control unit to determine whether an instruction should be executed, the instruction set having a switch mode instruction for changing the PMB bit of a processor executing the instruction;

the processors organized into one or more groups, each group having a processor configured as the controlling processor, wherein any processor in the plurality of processors can be dynamically configured as the controlling processor, the controlling processor enabling the processors of a group to operate in a MIMD or SIMD mode, and to switch modes dynamically; and

when a group of processors are operating in SIMD mode the controlling processor provides instructions to the instruction registers of the other processors in the group, each instruction provided via the interconnection path when the controlling processor fetches the instruction;

wherein a group of processors operating in SIMD mode switch to MIMD mode when the controlling processor provides each processor in the group with the switch mode instruction whereby each processor begins fetching instructions from its local memory; and

wherein a switch mode instruction executed by a first processor causes the first processor to stall and use an address provided by the switch mode instruction as a key back to the controlling processor, the controller processor can then execute a switch mode instruction with an "address" which matches the key, and causes the first processor to leave the stall and resume tracking the controlling processor'"'"'s instructions.

4. A dynamic multi-mode parallel processing array, comprising:

a plurality of processors, each processor having a control unit able to decode and execute instructions of an instruction set, a data flow unit and a local memory, each control unit having an instruction register, a program counter, a condition code register and a parallel mode bit (PMB), the PMB indicating whether the processor obtains instructions from a controlling processor or from local memory;

an interconnection path between the instruction registers of the processors;

the instruction set having a plurality of instructions, each instruction having a parallel execution type bit (PET) that is used in conjunction with the PMB by the control unit to determine whether an instruction should be executed, the instruction set having a switch mode instruction for changing the PMB bit of a processor executing the instruction;

the processors organized into one or more groups, each group having a processor configured as the controlling processor, wherein any processor in the plurality of processors can be dynamically configured as the controlling processor, the controlling processor enabling the processors of a group to operate in a MIMD or SIMD mode, and to switch modes dynamically; and

when a group of processors are operating in SIMD mode the controlling processor provides instructions to the instruction registers of the other processors in the group, each instruction provided via the interconnection path when the controlling processor fetches the instruction;

wherein a group of processors operating in SIMD mode switch to MIMD mode when the controlling processor provides each processor in the group with the switch mode instruction whereby each processor begins fetching instructions from its local memory; and

wherein a variable subset of processors operating in MIMD mode execute switch mode instructions that cause the variable subset of processors to operate in SIMD mode while those processors that are not part of the variable subset continue operating in MIMD mode.

5. The array according to claim 4 wherein the variable subset of processors return to MIMD mode when the controlling processor provides each processor in the variable subset with the switch mode instruction.

6. A dynamic multi-mode parallel processing array, comprising:

a plurality of processors, each processor having a control unit for decoding and executing instructions of an instruction set, a data flow unit and a local memory, each of said control units having an instruction register, a program counter, a condition code register and a parallel mode bit (PMB), the PMB indicating whether the processor obtains instructions from a controlling processor or from said local memory;

an interconnection path between the instruction registers of the processors;

the instruction set having a plurality of instructions, each instruction having a parallel execution type bit (PET) that is used in conjunction with the PMB by the control unit to determine whether an instruction should be executed, the instruction set having a switch mode instruction for changing the PMB bit of a processor executing the instruction;

the processors organized into one or more groups, each group having a processor configured as the controlling processor, wherein any processor in the plurality of processors can be dynamically configured as the controlling processor, the controlling processor enabling the processors of a group to operate in a MIMD or SIMD mode, and to switch modes dynamically; and

when a group of processors are operating in SIMD mode the controlling processor provides instructions to the instruction registers of the other processors in the group, each instruction provided via the interconnection path when the controlling processor fetches the instruction; and

wherein the instruction set provides instructions where all memory references for data are performed via LOAD and STORE instructions, and where addressing for data accesses is a base plus displacement, and where addition and index register updates are applied after a memory operation has begun, as a post address update; and

wherein all instructions that perform computational operations are register to register, and said processors execute instructions in one or more execution cycles without need of memory references.

7. A dynamic multi-mode parallel processing array, comprising:

a plurality of processors, each processor having a control unit for decoding and executing instructions of an instruction set, a data flow unit and a local memory, each of said control units having an instruction register, a program counter, a condition code register and a parallel mode bit (PMB), the PMB indicating whether the processor obtains instructions from a controlling processor or from said local memory;

an interconnection path between the instruction registers of the processors;

the instruction set having a plurality of instructions, each instruction having a parallel execution type bit (PET) that is used in conjunction with the PMB by the control unit to determine whether an instruction should be executed, the instruction set having a switch mode instruction for changing the PMB bit of a processor executing the instruction;

the processors organized into one or more groups, each group having a processor configured as the controlling processor, wherein any processor in the plurality of processors can be dynamically configured as the controlling processor, the controlling processor enabling the processors of a group to operate in a MIMD or SIMD mode, and to switch modes dynamically; and

when a group of processors are operating in SIMD mode the controlling processor provides instructions to the instruction registers of the other processors in the group, each instruction provided via the interconnection path when the controlling processor fetches the instruction

wherein a controlling processor of a group of processors fetches instructions, and wherein other processors in the group latch into their instruction registers each instruction as the controlling processor fetches it, such that at the end of the instruction fetch all other processors have in their instruction register the fetched instruction; and

wherein after latching the fetched instruction each processor looks at its PMB and the PET obtained from the fetched instruction to determine whether to execute the fetched instruction, executing the fetched instruction accordingly.

8. The array according to claim 7 wherein while the processors are decoding and executing the fetched instruction the controlling processor begins fetching a next instruction.

9. The array according to claim 8 wherein the controlling processor of a group of processors fetches another instruction all processors in SIMD mode capture the memory reference in their instruction registers.

10. A dynamic multi-mode parallel processing array, comprising:

a plurality of processors, each processor having a control unit for decoding and executing instructions of an instruction set, a data flow unit and a local memory, each of said control units having an instruction register, a program counter, a condition code register and a parallel mode bit (PMB), the PMB indicating whether the processor obtains instructions from a controlling processor or from said local memory;

an interconnection path between the instruction registers of the processors;

the instruction set having a plurality of instructions, each instruction having a parallel execution type bit (PET) that is used in conjunction with the PMB by the control unit to determine whether an instruction should be executed, the instruction set having a switch mode instruction for changing the PMB bit of a processor executing the instruction;

the processors organized into one or more groups, each group having a processor configured as the controlling processor, wherein any processor in the plurality of processors can be dynamically configured as the controlling processor, the controlling processor enabling the processors of a group to operate in a MIMD or SIMD mode, and to switch modes dynamically on an instruction-by, instruction basis; and

when a group of processors are operating in SIMD mode the controlling processor provides instructions to the instruction registers of the other processors in the group, each instruction provided via the interconnection path when the controlling processor fetches the instruction; and

wherein the PMB indicates SIMD and MIMD modes and the PET indicates local and array operations of the associated processor.

11. The array according to claim 10 wherein when a group of processors are operating in SIMD mode, the program counters provide a base register function in the processors receiving instructions from the controlling processor.

12. The array according to claim 10 wherein when a group of processors are operating in SIMD mode, the condition code register provide a local enable function in the processors receiving instructions from the controlling processor.

13. The array according to claim 10 wherein there is provided a plurality of groups, with each group dynamically switching between modes of operation.

14. The array according to claim 10 wherein the interconnection path is a dynamic switching connection network.

15. The array according to claim 10 wherein the interconnection path provides a broadcast path between the instructions registers of each processor in a group of processors executing in SIMD mode.

16. The array according to claim 10 wherein the interconnection path is a multi-stage interconnection network that provides a broadcast path to the instruction registers of a group of processors operating in a SIMD mode.

17. The array according to claim 10 wherein a switch mode instruction provides a value to load into the program counter when executed.

18. The array according to claim 10 wherein the switch mode instruction does not change the program counter when executed.

19. The array according to claim 10 wherein a group of processors operating in SIMD mode switch to MIMD mode when the controlling processor provides each processor in the group with the switch mode instruction whereby each processor begins fetching instructions from its local memory.

20. The array according to claim 10 wherein the interconnection path is utilized to pass broadcast messages and to interconnect a variety of subsets of processors within a group of processors, such that the processors may implement on a selective basis both SIMD and MIMD operations, some processors running SIMD and others running MIMD.

21. The array according to claim 10 wherein is included for processor interconnection a dynamic switching multi-stage network, wherein without blocking via alternative path selection processors can be set up as part of an interconnected system permitting selection of various groups of processors on the network which have desirable resources, and use them to run programs which can take advantage of the SIMD and MIMD needs of the application.

22. The array according to claim 10 wherein the controlling processor is dynamically rotated through a group of processors so that each processor is configured as the controlling processor for one or more instructions.

23. The array according to claim 10 wherein the instructions registers of processors are interconnected via an asynchronous network enabling a controlling processor to pass instructions through the interconnection network to other processor instruction registers coupled via said network.

24. The array according to claim 10 wherein each processor is provided with a port through which passes the switch mode instruction.

25. The array according to claim 10 wherein the controlling processor can switch to SISD mode permitting a programmer or compiler to build a program for the array which uses any one or all modes of parallelism.

26. The array according to claim 10 wherein the interconnection path is a dynamic multi-stage two sided switching network enabling point to point coupling of processors without blocking.

27. The array according to claim 26 wherein the multi-stage interconnection network provides broadcast paths to the instruction registers of a group of processors operating in SIMD mode.

28. The array according to claim 10 wherein a multi-stage interconnection network provides an alternative path between the instruction registers of a group of processors operating in SIMD mode.

29. The array according to claim 28 wherein the multi-stage interconnection network a dynamic multi-stage two sided switching network enabling point to point coupling of processors without blocking.

30. The may according to claim 10 wherein a controlling processor of a group of processors fetches instructions, and wherein other processors in the group latch into their instruction registers each instruction as the controlling processor fetches it, such that at the end of the instruction fetch all other processors have in their instruction register the fetched instruction.

31. The array according to claim 30 wherein execution of SIMD mode instructions proceeds with the program counter used as a base register.

32. The array according to claim 30 wherein the instruction set includes instructions which when executed in a processor operating in SIMD mode uses the program counter as a base register, the instruction including a Load immediate instruction and a store immediate instruction.

33. The array according to claim 10 wherein each processor is a reduced instruction set computer (RISC).

34. The array according to claim 33 wherein the interconnection path is provided by an ALLNODE interconnection network.

35. The array according to claim 10 including:

a first group of processors operating in SIMD mode having a first controlling processor providing instructions for said first group over the interconnection path; and

a second group operating in SIMD mode having a second controlling processor providing instructions for the second group over the interconnection path.

36. The array according to claim 35 wherein the first controlling processor provides the switch mode instruction to the first group of processors causing the first group of processors to enter MIMD mode.

37. The array according to claim 36 wherein the second controlling processor provides the switch mode instruction to the second group of processors causing the second group of processors to enter MIMD mode.