Scalable deterministic interconnection network for efficient data movement

1 . A scalable distributed computing system with deterministic interconnection network and shared memory comprising:

wherein said scalable distributed computing system with deterministic interconnection network and shared memory further comprising an a×b processing elements arranged in a two dimensional grid with one side of said two dimensional grid having the size of a processing elements and the other side of said two dimensional grid having the size of b processing elements where a>2, b>2, and both a and b are non-negative numbers; and

Wherein said a×b processing elements are numbered with a representation in binary format having n bits, where 2 n−1 <a×b≤2 n and where n is a positive number; and

Wherein said a×b processing elements are arranged in said two dimensional grid so that a first processing element of said a×b processing elements is placed 2 k hops away either vertically or horizontally from a second processing element of said a×b processing elements when said all n bits of said representation in binary format of said first processing element and said representation in binary format of said second processing element are the same in each bit excepting in one of either (2×k+1)th least significant bit or (2×k+2)th least significant bit differ where k is a non-negative number; and

Wherein each processing element of said a×b processing elements arranged in said two dimensional grid comprising a router; and

Wherein said router comprising one or more local inlet buses and one or more local outlet buses; and

Wherein said router of a first processing element of said a×b processing elements is connected, by a 2 k hop length horizontal bus or a 2 k hop length vertical bus, to said router of a second processing element of said a×b processing elements when said all n bits of said representation in binary format of said first processing element and said representation in binary format of said second processing element are the same in each bit excepting in one of either (2×k+1)th least significant bit or (2×k+2)th least significant bit differ where k is a non-negative number and also said router of said first processing element of said a×b processing elements is connected, by a 2 k hop length horizontal bus or a 2 k hop length vertical bus, from said router of said second processing element of said a×b processing elements when said all n bits of said representation in binary format of said first processing element and said representation in binary format of said second processing element are the same in each bit excepting in one of either (2×k+1)th least significant bit or (2×k+2)th least significant bit differ where k is a non-negative number so that said router of each processing element of said a×b processing elements comprising one or more horizontal buses connecting to said router of one or more processing elements of said a×b processing elements and said router of each processing element of said a×b processing elements comprising one or more vertical buses connecting to said router of one or more processing elements of said a×b processing elements.

2 . The scalable distributed computing system with deterministic interconnection network and shared memory of claim 1 , wherein each processing element of said a×b processing elements further comprises a processor or local memory.

3 . The scalable distributed computing system with deterministic interconnection network and shared memory of claim 2 , wherein said processor of each processing element of said a×b processing elements is a Central Processing Unit (CPU) comprises functional units that perform such as additions, multiplications, or logical operations, for executing computer programs.

4 . The scalable distributed computing system with deterministic interconnection network and shared memory of claim 2 , wherein said processor of each processing element of said a×b processing elements comprises a domain specific architecture (DSA) based Deep Neural Network (DNN) processor comprising one or more multiply accumulate (MAC) units for performing matrix multiply operations.

5 . The scalable distributed computing system with deterministic interconnection network and shared memory of claim 2 , wherein said processor, said local memory and said router of each processing element of said a×b processing elements are directly connected to each other.

6 . The scalable distributed computing system with deterministic interconnection network and shared memory of claim 1 , wherein said two dimensional grid with one side of said two dimensional grid having said size of a processing elements and said other side of said two dimensional grid having said size of b processing elements is recursively scaled for larger sizes of said size of a processing elements or said other side of said two dimensional grid scaled for larger sizes of said size of b processing elements.

7 . The scalable distributed computing system with deterministic interconnection network and shared memory of claim 1 , wherein said a×b processing elements are implemented in said two dimensional grid 1) in a single die, or 2) in a plurality of dies on a semiconductor wafer, or 3) in a plurality of integrated circuit chips.

8 . A method for communication in a scalable distributed computing system with deterministic interconnection network and shared memory comprising:

wherein said scalable distributed computing system with deterministic interconnection network and shared memory further comprising an a×b processing elements arranged in a two dimensional grid with one side of said two dimensional grid having the size of a processing elements and the other side of said two dimensional grid having the size of b processing elements where a>1, b>1, and both a and b are non-negative numbers; and

Wherein said a×b processing elements are numbered with a representation in binary format having n bits, where 2 n−1 <a×b≤2 n and where n is a positive number; and

Wherein said a×b processing elements are arranged in said two dimensional grid so that a first processing element of said a×b processing elements is placed 2 k hops away either vertically or horizontally from a second processing element of said a×b processing elements when said all n bits of said representation in binary format of said first processing element and said representation in binary format of said second processing element are the same in each bit excepting in one of either (2×k+1)th least significant bit or (2×k+2)th least significant bit differ where k is a non-negative number; and

Wherein each processing element of said a×b processing elements arranged in said two dimensional grid comprising a router; and

Wherein said router comprising one or more local inlet buses and one or more local outlet buses; and

Wherein each horizontal bus of said one or more 2 k hop length horizontal buses comprises one or more wires and each vertical bus of said one or more 2 k hop length vertical buses comprises one or more wires; and

Wherein said router of a first processing element of said a×b processing elements is connected, by a 2 k hop length horizontal bus of said one or more 2 k hop length horizontal buses or a 2 k hop length vertical bus of said one or more 2 k hop length vertical buses, to said router of a second processing element of said a×b processing elements when said all n bits of said representation in binary format of said first processing element and said representation in binary format of said second processing element are the same in each bit excepting in one of either (2×k+1)th least significant bit or (2×k+2)th least significant bit differ where k is a non-negative number and also said router of said first processing element of said a×b processing elements is connected, by a 2 k hop length horizontal bus of said one or more 2 k hop length horizontal buses or a 2 k hop length vertical bus of said one or more 2 k hop length vertical buses, from also said router of said second processing element of said a×b processing elements when if said all n bits of said representation in binary format of said first processing element and said representation in binary format of said second processing element are the same in each bit excepting in one of either (2×k+1)th least significant bit or (2×k+2)th least significant bit differ where k is a non-negative number so that said router of each processing element of said a×b processing elements comprising said one or more 2 k hop length horizontal buses connecting to said router of one or more processing elements of said a×b processing elements and said router of each processing element of said a×b processing elements comprising said one or more 2 k hop length vertical buses connecting to said router of one or more processing elements of said a×b processing elements; and

each processing element of said a×b processing elements further comprising one or more packets wherein each packet of said one or more packets comprises a data token and a length; and

said router of each processing element of said a×b processing elements is capable of concurrently transmitting, in a clock speed of operation, one or more packets of said one or more packets through one or more horizontal buses of said one or more 2 k hop length horizontal buses connected from said router of each processing element of said a×b processing elements (source processing element) to a processing element of said a×b processing elements (target processing element) and also through one or more vertical buses of said one or more 2 k hop length vertical buses connected from said router of each processing element of said a×b processing elements (source processing element) to a processing element of said a×b processing elements (target processing element); and

said method for communication further comprising:

performing concurrent broadcast of each packet of said one or more packets from each source processing element of said a×b processing elements to target processing elements of all the rest of said a×b processing elements in a plurality of deterministic number of time steps through said one or more 2 k hop length horizontal buses or said one or more 2 k hop length vertical buses; and

wherein said each packet of said one or more packets traverses through one or more processing element of said a×b processing elements (intermediate processing element) when said source processing element of said a×b processing elements and said target processing element of said a×b processing elements are not directly connected by one of either said one or more 2 k hop length horizontal buses or said one or more 2 k hop length vertical buses; and

wherein duration of each time step of said plurality of deterministic number of time steps is determined by the length of said one or more packets, the hop length of said one or more 2 k hop length horizontal buses, the hop length of said one or more 2 k hop length vertical buses, the number of wires in each bus of said one or more 2 k hop length horizontal buses, the number of wires in each bus of said one or more 2 k hop length vertical buses, an implemented non-transitory medium of said one or more 2 k hop length horizontal buses or said one or more 2 k hop length vertical buses, and said clock speed of operation; and

wherein said concurrent broadcast of each packet of said one or more packets of each processing element of said a×b processing elements is performed in a non-blocking, collision-free or without requiring queuing at the one or more intermediate processing elements of said a×b processing elements.

9 . The method for communication in a scalable distributed computing system with deterministic interconnection network and shared memory of claim 8 , wherein said each packet of said one or more packets of said each source processing element of said a×b processing elements broadcasts to said each target processing element of said a×b processing elements in a fixed path, by passing through said router of a predetermined number of intermediate processing elements of said a×b processing elements in said plurality of deterministic number of time steps or passing through said router of a predetermined order of intermediate processing elements of said a×b processing elements in said plurality of deterministic number of time steps.

10 . The method for communication in a scalable distributed computing system with deterministic interconnection network and shared memory of claim 9 , wherein a first said target processing element of said a×b processing elements receives said each packet of said one or more packets from said each source processing element of said a×b processing elements in a first predetermined order in said plurality of deterministic number of time steps.

11 . The method for communication in a scalable distributed computing system with deterministic interconnection network and shared memory of claim 10 , wherein a second said target processing element of said a×b processing elements receives said each packet of said one or more packets from said each source processing element of said a×b processing elements in a second predetermined order in said plurality of deterministic number of time steps and said second predetermined order is not the same as said first predetermined order.

12 . The method for communication in a scalable distributed computing system with deterministic interconnection network and shared memory of claim 8 , wherein said performing concurrent broadcast of each packet of said one or more packets at each processing element of said a×b processing elements in said plurality of deterministic number of time steps is repeated for every packet of said one or more packets of each processing element of said a×b processing elements in said deterministic number of time steps.

13 . The method for communication in a scalable distributed computing system with deterministic interconnection network and shared memory of claim 12 , wherein a first said target processing element of said a×b processing elements receives said each packet of said one or more packets from said every each source processing element of said a×b processing elements in a predetermined order in said plurality of deterministic number of time steps and said first said target processing element of said a×b processing elements receives said one or more packets from said each source processing element of said a×b processing elements in a predetermined order in said plurality of deterministic number of time steps multiplied by number of said one or more packets where said first said target processing element of said a×b processing elements receives said one or more packets from said each source processing element of said a×b processing elements in the same order they were broadcasted by said first said target processing element of said a×b processing elements.

14 . The method for communication in a scalable distributed computing system with deterministic interconnection network and shared memory of claim 8 , when a=2; b=2, said performing concurrent broadcast of each packet of said one or more packets at each processing element of said a×b processing elements to all the rest of said a×b processing elements in a plurality of deterministic number of time steps is equal to 2.

15 . The method for communication in a scalable distributed computing system with deterministic interconnection network and shared memory of claim 8 , when a=4; b=2 or a=2; b=4, said performing concurrent broadcast of each packet of said one or more packets at each processing element of said a×b processing elements to all the rest of said a×b processing elements in a plurality of deterministic number of time steps is equal to 4.

16 . A scalable distributed computing system with deterministic interconnection network and shared memory comprising:

wherein said scalable distributed computing system with deterministic interconnection network and shared memory further comprising an a×b processing elements arranged in a two dimensional grid with one side of said two dimensional grid having the size of a processing elements and the other side of said two dimensional grid having the size of b processing elements where a>2, b>2, and both a and b are non-negative numbers; and

wherein each processing element of said a×b processing elements further comprises a processor or local memory; and

Wherein said a×b processing elements are numbered with a representation in binary format having n bits, where 2 n−1 <a×b≤2 n and where n is a positive number; and

Wherein said a×b processing elements are arranged in said two dimensional grid so that a first processing element of said a×b processing elements is placed 2 k hops away either vertically or horizontally from a second processing element of said a×b processing elements when said all n bits of said representation in binary format of said first processing element and said representation in binary format of said second processing element are the same in each bit excepting in one of either (2×k+1)th least significant bit or (2×k+2)th least significant bit differ where k is a non-negative number; and

Wherein each processing element of said a×b processing elements arranged in said two dimensional grid comprising a router; and

Wherein said router comprising one or more local inlet buses and one or more local outlet buses; and

Wherein said router of a first processing element of said a×b processing elements is connected, by a 2 k hop length horizontal bus or a 2 k hop length vertical bus, to said router of a second processing element of said a×b processing elements when said all n bits of said representation in binary format of said first processing element and said representation in binary format of said second processing element are the same in each bit excepting in one of either (2×k+1)th least significant bit or (2×k+2)th least significant bit differ where k is a non-negative number and also said router of said first processing element of said a×b processing elements is connected, by a 2 k hop length horizontal bus or a hop length vertical bus, from said router of said second processing element of said a×b processing elements when said all n bits of said representation in binary format of said first processing element and said representation in binary format of said second processing element are the same in each bit excepting in one of either (2×k+1)th least significant bit or (2×k+2)th least significant bit differ where k is a non-negative number so that said router of each processing element of said a×b processing elements comprising one or more horizontal buses connecting to said router of one or more processing elements of said a×b processing elements and said router of each processing element of said a×b processing elements comprising one or more vertical buses connecting to said router of one or more processing elements of said a×b processing elements.

17 . The scalable distributed computing system with deterministic interconnection network and shared memory of claim 16 , wherein said processor of each processing element of said a×b processing elements is a Central Processing Unit (CPU) comprises functional units that perform such as additions, multiplications, or logical operations, for executing computer programs.

18 . The scalable distributed computing system with deterministic interconnection network and shared memory of claim 16 , wherein said processor of each processing element of said a×b processing elements comprises a domain specific architecture (DSA) based Deep Neural Network (DNN) processor comprising one or more multiply accumulate (MAC) units for performing matrix multiply operations.

19 . The scalable distributed computing system with deterministic interconnection network and shared memory of claim 16 , wherein said processor, said local memory and said router of each processing element of said a×b processing elements are directly connected to each other.

20 . The scalable distributed computing system with deterministic interconnection network and shared memory of claim 16 , wherein said two dimensional grid with one side of said two dimensional grid having said size of a processing elements and said other side of said two dimensional grid having said size of b processing elements is recursively scaled for larger sizes of said size of a processing elements or said other side of said two dimensional grid scaled for larger sizes of said size of b processing elements; and

said a×b processing elements are implemented in said two dimensional grid 1) in a single die, or 2) in a plurality of dies on a semiconductor wafer, or 3) in a plurality of integrated circuit chips.