Hierarchical block-identified data communication for unified handling of structured data and data compression

• US 20090164754A1
• Filed: 12/19/2008
• Published: 06/25/2009
• Est. Priority Date: 12/21/2007
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Hicamp Systems Incorporated
• Inventors: Cheriton, David R.
• Granted Patent: US 8,370,458 B2
• Time in Patent Office: Days
• US Class Current: 712/29
• CPC Class Codes: G06F 15/16 Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs coordinating program control therefor G06F9/52; in regulating and control system G05B

Abstract

Data transmission efficiency for structured data can be improved by representing structured data using immutable blocks. The contents of the immutable blocks can include data and/or pointers to immutable blocks. An immutable data block cannot be altered after creation of the block. When data represented as immutable blocks is transmitted from one processor to another processor, the transmitter sends block contents for blocks that have not previously been defined at the receiver, and sends block IDs (as opposed to block contents) for blocks that have previously been defined at the receiver. The systematic use of block IDs instead of block contents in transmission where possible can significantly reduce transmission bandwidth requirements.

Claims

1. A method for transmitting data from a first processor to a second processor, the method comprising:

representing some or all data on said first and second processors with data structures consisting of immutable blocks, wherein contents of said immutable blocks can include data and/or pointers to said immutable blocks;

transmitting transfer data from said first processor to said second processor, wherein said transfer data is represented as one or more of said data structures consisting of immutable blocks, and wherein said immutable blocks of said one or more data structures are a set of transfer blocks;

determining a first set of said transfer blocks that have not been previously defined on said second processor;

determining a second set of said transfer blocks that have been previously defined on said second processor;

wherein said transmitting transfer data comprises transmitting contents of said first set of transfer blocks to said second processor;

wherein said transmitting transfer data comprises transmitting identification of said second set of transfer blocks to said second processor.

2. The method of claim 1, wherein said data structures consisting of immutable blocks are organized as directed acyclic graphs, linked by pointers included in contents of said immutable blocks.

3. The method of claim 1, further comprising deallocating one or more of said transfer blocks.

4. The method of claim 1, wherein each of said immutable blocks on said first processor has a physical block ID, and further comprising maintaining a first virtual block ID to physical block ID mapping for said immutable blocks on said first processor, wherein said mapping is mutable.

5. The method of claim 1, wherein each of said immutable blocks on said second processor has a physical block ID, and further comprising maintaining a second virtual block ID to physical block ID mapping for said immutable blocks on said second processor, wherein said mapping is mutable.

6. The method of claim 5, further comprising maintaining a virtual mapping of said virtual block IDs to local VIDs of said second processor.

7. The method of claim 1, further comprising maintaining a local physical mapping of said physical block IDs to local PIDs of said second processor.

8. The method of claim 1, further comprising maintaining a system-wide labeling of said immutable blocks in a system including at least said first and second processors.

9. The method of claim 8, wherein said maintaining a system-wide labeling comprises

assigning physical block IDs to said immutable blocks at a master processor;

providing a mapping of virtual block IDs to said physical block IDs at said master processor;

assigning temporary block IDs to said immutable blocks at slave processors;

automatically and equivalently replacing said temporary block IDs with said physical block IDs and said virtual block IDs as provided by said master processor.

10. The method of claim 9, wherein said immutable blocks are stored in a memory shared by at least said first and second processors.

11. The method of claim 9, wherein said immutable blocks are independently stored in separate memory units associated with at least said first and second processors.

12. The method of claim 1, wherein a reference count is maintained for each of said transfer blocks, and wherein each said transfer block is deallocated if and only if a corresponding one of said reference counts become zero.

13. The method of claim 1, further comprising:

providing a canonical representation of multi-block data to ensure unique representation of multi-block data;

enforcing non-duplication of immutable blocks having the same contents at said first and second processors, whereby said immutable blocks can be content-identified.

14. A set of computer instructions readable and executable from a computer readable medium for performing a method for transmitting data from a first processor to a second processor, the method comprising:

representing some or all data on said first and second processors with data structures consisting of immutable blocks, wherein contents of said immutable blocks can include data and/or pointers to said immutable blocks;

transmitting transfer data from said first processor to said second processor, wherein said transfer data is represented as one or more of said data structures consisting of immutable blocks, and wherein said immutable blocks of said one or more data structures are a set of transfer blocks;

determining a first set of said transfer blocks that have not been previously defined on said second processor;

determining a second set of said transfer blocks that have been previously defined on said second processor;

wherein said transmitting transfer data comprises transmitting contents of said first set of transfer blocks to said second processor;

wherein said transmitting transfer data comprises transmitting identification of said second set of transfer blocks to said second processor.

15. A computer system programmed to perform a method for transmitting data from a first processor to a second processor, the method comprising:

representing some or all data on said first and second processors with data structures consisting of immutable blocks, wherein contents of said immutable blocks can include data and/or pointers to said immutable blocks;

transmitting transfer data from said first processor to said second processor, wherein said transfer data is represented as one or more of said data structures consisting of immutable blocks, and wherein said immutable blocks of said one or more data structures are a set of transfer blocks;

determining a first set of said transfer blocks that have not been previously defined on said second processor;

determining a second set of said transfer blocks that have been previously defined on said second processor;

wherein said transmitting transfer data comprises transmitting contents of said first set of transfer blocks to said second processor;

wherein said transmitting transfer data comprises transmitting identification of said second set of transfer blocks to said second processor.