Digital processing system

• US 6,760,744 B1
• Filed: 06/30/2000
• Issued: 07/06/2004
• Est. Priority Date: 10/09/1998
• Status: Expired due to Term

• Current Assignee: Fast Search & Transfer ASA (Microsoft Corporation)
• Original Assignee: Fast Search & Transfer ASA (Microsoft Corporation)
• Inventors: Leistad, Geirr I., Svingen, Børge, Halaas, Arne
• Primary Examiner(s): Chin, Stephen
• Assistant Examiner(s): Ha, Dac V.
• Application Number:
  US09/581,145
• Time in Patent Office: 1,467 Days
• Field of Search: 375/259, 375/286, 375/377, 709/200, 709/201, 709/249, 709/250, 709/252
• US Class Current: 709/201
• 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/8023 Two dimensional arrays, e.g. mesh, torus

Abstract

A digital processing system P, configured as a regular tree with n+1 levels S₀, S₁, S₂ . . . S_n and degree k, provided in the form of a circuit P_n on the level S_n and forms the root node of the tree, an underlying level S_n−q, q=1,2, . . . n−1, in the circuit P provided nested in the K^q−1 circuits P_n−q+1 on the overlying level S_n−q+1, each circuit P_n−q+1 on this level including k circuits P_n−q. A q=n defined zeroth level in the circuit P_n includes from Kⁿ⁻¹+1 to Kⁿ circuits P₀ which form kernel processors in the processing device P and on the level S₀ and constitute the leaf nodes of the tree, the kernel processor P₀ being provided nested in each of the circuits p₁ on the level S₁. Each of the circuits P₁, P₂, . . . P_n, includes a logic unit E which generally is connected with circuits P₀, P₁, . . . P_n−1. Each of the circuits P₀, P₁, . . . P_n has additionally identical interfaces I, such that I_P0−I_P1− . . . I_Pn.

Claims

1. A digital processing system P, for processing of digital data and signal structures, wherein the data and signal structures comprise repeated sequences and/or nested patterns, the digital processing system comprising:

a regular tree with n+1 levels S₀, S₁, . . . S_n and of degree k, where n and k are numbers;

a circuit P_n on the level S_n and that forms the root node of the tree, such that the nearest level S<sub>n−

1</sub> is provided nested in the circuit P_n;

k circuits P<sub>n−

1</sub> which form the child nodes of the root node, and an underlying level S<sub>n−

q</sub> in the circuit P_n, where q∈

{1,2 . . . n−

1};

including k^q circuits P<sub>n−

q</sub> provided nested in the k<sup>q−

1</sup> circuits P<sub>n−

q+1</sub> on the overlying level S<sub>n−

q+1</sub>, each circuit P<sub>n−

q+1</sub> on this level including k circuits P<sub>n−

q</sub>, such that a defined zeroth level S<sub>n−

q</sub>=S₀ in the circuit P_n for q=n includes from k<sup>n−

1</sup>+1 to kⁿ circuits P₀ which constitute kernel processors in the processing system P and on this level S₀ form leaf nodes in the tree, the kernel processor P₀ being provided nested in a number of 1 to k in each of the k<sup>n−

1</sup> circuits P₁ on the level S₁, such that each of the circuits P₁, P₂ . . . P_n on respective levels S₁, S₂ . . . S_n includes comprises a logic unit E which is connected with those circuits P₀, P₁ . . . P<sub>n−

1</sub> on the respective nearest underlying level S₀, S₁ . . . S<sub>n−

1</sub> provided nested in the respective circuits P₁, P₂, . . . P_n and configures a network of the former circuits in the respective circuits P₁, P₂ . . . P_n, wherein each of the circuits P₀, P₁ . . . P_n has identical interfaces I.

2. A digital processing device according to claim 1, wherein the zeroth level S₀ comprises kⁿ kernel processors P₀, such that a kernel processor P₀ recursively maps a circuit P₁ on the overlying level with a mapping factor r=k, such that the tree is an unreduced or complete tree, and that a circuit P_n−

q on the level S<sub>n−

q</sub> maps recursively a circuit P<sub>n−

q+1</sub> on the overlying level S<sub>n−

q+1</sub> with the factor r=k.

3. A digital processing system P according to claim 1, wherein the zeroth level S₀ comprises rkⁿ⁻

1 kernel processors P₀, 1<

r<

k, such that a kernel processor P₀ maps a circuit P₁ on the overlying level S₁ with the mapping factor r, 1<

r<

k such that the tree is a symmetrically reduced or balanced tree, and that generally a circuit P<sub>n−

q</sub> on all levels from the level S₁ maps a circuit P<sub>n−

q+1</sub> on the overlying level S<sub>n−

q+1</sub> recursively with the mapping factor r=k.

4. A digital processing system P according to claim 1, wherein respectively from 1 to k kernel processors are provided nested in each circuit P₁ on the level S₁, such that at least one of the circuits P₁ includes at least 2 and at most k−

1 kernel processors P₀, such that the total number of kernel processors P₀ on the level S₀ is at least k<sup>n−

1</sup>+1 and at the most kⁿ−

1 and the tree becomes an asymmetrically reduced or unbalanced tree, and that generally a circuit P<sub>n−

q</sub> on the level S<sub>n−

q</sub> is mapped by the circuits P<sub>n−

q−

1</sub> nested in the respective circuit P<sub>n−

q</sub>.

5. A digital processing system P according to claim 1, wherein the kernel processor P₀ at least comprises one combinatorial unit C and a memory unit M connected with at least one combinatorial unit C.

6. A digital processing system P according to claim 5, including at least a part of the memory unit M is configured as a register unit R.

7. A digital processing system P according to claim 6, wherein at least one combinatorial unit C and a register unit R are configured as an arithmetic logic unit ALU.

8. A digital processing system P according to claim 1, wherein the logic unit E comprises at least one combinatorial unit C and a register unit R connected with the at least one combinatorial unit C.

9. A digital processing system P according to claim 8, wherein at least one combinatorial unit C is a multiplexer.

10. A digital processing system P according to claim 9, wherein the logic unit E in a circuit P_n−

q is adapted to be connected with the logic unit E in a corresponding circuit P<sub>n−

q</sub> on the same level S<sub>n−

q</sub> in a neighbor tree.

11. A digital processing system P according to claim 9, wherein the logic unit E in a circuit P_n−

q, is adapted to be connected with the logic unit E in circuits P<sub>n−

q−

1</sub>, P<sub>n−

q−

2</sub>, . . . P₁ on respective underlying levels S<sub>n−

q−

1</sub>, S<sub>n−

q−

2</sub>, . . . S₁ in a neighbor tree.

12. A digital processing system P according to claim 11, wherein the logic unit E in a circuit P_n−

q is adapted to be connected with one or more kernel processors P₀ in a neighbor tree, either directly or via the logic unit E in the circuit P₁, where the kernel processor P₀ or the kernel processors P₀ in question are nested.