Erasure coding and group computations using rooted binary and ternary trees

• US 7,716,250 B1
• Filed: 05/27/2005
• Issued: 05/11/2010
• Est. Priority Date: 05/27/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Thekkath, Chandramohan A, Silverberg, Alice, Manasse, Mark Steven
• Primary Examiner(s): Pham; Khanh B
• Application Number:
  US11/139,914
• Time in Patent Office: 1,810 Days
• Field of Search: None
• US Class Current: 707/797
• CPC Class Codes: G06F 16/9027 Trees

Abstract

High throughput in data computations and processing is maintained while minimizing latency. A binary tree architecture is provided in which two trees are used simultaneously, and initiation of the trees is staggered to allow for optimal use of bandwidth. These techniques are desirable for erasure codes and other computations where the addition operator is commutative. Additionally, a ternary tree architecture may be used, in which three trees co-exist on the same set of nodes to maintain high throughput while further improving latency.

Claims

1. A method of generating a tree structure comprising processing nodes for data processing, wherein each of the processing nodes of the tree structure represents a processor unit in a processor network, the method comprising:

providing a first pair of trees including an even tree A₀ employed to perform even-numbered computation steps in a sequence of steps and an odd tree A₁ employed to perform odd-numbered computation steps in the sequence of steps, each tree of the first pair having the same leaf node a and no parent node;

providing a second pair of trees wherein each of the trees in the second pair of trees is different than each of the trees in the first pair of trees, the second pair of trees including an even tree B₀ employed to perform even-numbered computation steps in the sequence of steps and an odd tree B₁ employed to perform odd-numbered computation steps in the sequence of steps, each tree of the second pair having the same leaf node b and no parent node; and

creating the tree structure comprising the processing nodes for improved concurrent processing of the sequence of steps by re-ordering the processing nodes in the first and second pairs of trees as follows;

generating a first node x for use as a parent node in the tree structure;

creating a first binary tree X₀ by combining the even tree A₀ of the first pair of trees and the odd tree B₁ of the second pair of trees and incorporating the first node x as a parent node of the first binary tree X₀; and

creating a second binary tree X₁ by combining the odd tree A₁ of the first pair of trees and the even tree B₀ of the second pair of trees and elevating the leaf node b of the second pair of trees to become a parent node of the second binary tree X₁.

2. The method of claim 1, wherein each of the first binary tree X₀ and the second binary tree X₁ has a common leaf node corresponding to the leaf node a of the first pair of trees.

3. The method of claim 1, wherein the first binary tree X₀ has a leaf node corresponding to the leaf node b of the second pair of trees, and the second binary tree X₀ has a leaf node corresponding to the parent node of the first binary tree X₀.

4. The method of claim 1, wherein the depth of each tree is log n/log k, where k is equal to 3.

5. A method of performing computations in a network computing environment comprising a plurality of processing nodes in a tree structure, wherein each processing node represents a processor unit in the network, the method comprising:

providing a first pair of processing nodes including an even processing node employed to perform even-numbered computation steps in a sequence of steps and an odd processing node employed to perform odd-numbered computation steps in the sequence of steps;

providing a second pair of processing nodes wherein each of the processing nodes in the second pair of processing nodes is different than the first pair of processing nodes and including an even processing node employed to perform even-numbered computation steps in the sequence of steps and an odd processing node employed to perform odd-numbered computation steps in the sequence of steps;

creating a tree structure for improved concurrent processing of the sequence of steps by re-ordering the processing nodes in the first and second pairs of processing nodes as follows;

combining the even one of the first pair of processing nodes and the odd one of the second pair of processing nodes into a first binary tree, and combining the odd one of the first pair of processing nodes and the even one of the second pair of processing nodes into a second binary tree, the first and second binary trees each having a parent node, wherein the first and second binary trees are linked together by at least one common processing node to improve concurrent processing of the sequence of steps by the first and second pairs of processing nodes;

generating a first computation result at the parent node of the first binary tree;

generating a second computation result at the parent node of the second binary tree; and

generating a third computation result by performing an operation on the first and second computation results.

6. The method of claim 5, wherein the operation comprises an addition operator that is commutative.

7. The method of claim 5, wherein the operation is an exclusive-or operation.

8. The method of claim 5, wherein each of the binary trees is used to perform one of an odd-numbered or an even numbered computation step.

9. The method of claim 5, wherein in the first pair of processing nodes, each processing node has the same first leaf node and no parent node, and wherein in the second pair of processing nodes, each processing node has the same second leaf node and no parent node.

10. The method of claim 9, wherein the two binary trees each have a common leaf node corresponding to the first leaf node, and further wherein the first binary tree has a leaf node corresponding to the second leaf node, and the second binary tree has a leaf node corresponding to the parent node of the first binary tree.

11. A method of generating a tree structure comprising processing nodes for data processing, wherein each of the processing nodes of the tree structure represents a processor unit in a processor network, the method comprising:

providing first, second, and third trios of trees, each trio including a first tree employed to perform first out of three computation steps in a sequence of steps, a second tree employed to perform second out of three computation steps in the sequence of steps, and a third tree employed to perform third out of three computation steps in the sequence of steps, each tree of the first trio having the same first leaf node and no parent node, each tree of the second trio having the same second leaf node and no parent node, and each tree of the third trio having the same third leaf node and no parent node; and

creating the tree structure comprising the processing nodes for improved concurrent processing of the sequence of steps by re-ordering the processing nodes in the first, second and third trios of trees as follows;

combining the first tree of the first trio of trees, the second tree of the second trio of trees, and the third tree of the third trio of trees into a first ternary tree X₀, combining the second tree of the first trio of trees, the third tree of the second trio of trees, and the first tree of the third trio of trees into a second ternary tree X₂, and combining the third tree of the first trio of trees, the first tree of the second trio of trees, and the second tree of the third trio of trees into a third ternary tree X₁;

elevating a leaf node to a parent node in one of the first or second ternary trees X₀ or X₂, and providing the generated parent node as a leaf node to the other of the first or second ternary trees; and

elevating a leaf node to a parent node in one of the second or third ternary trees X₂ or X₁, and providing the generated parent node as a leaf node to the other of the second or third ternary trees.